Proposition 7 ([Separation in the finite tree]). For every node v of height h , every x∈A , and every integer t with Q_v t , r_Lv (G_v(x),G_v(x+t w_v))≥4^-h L_v.

At a leaf, the two residue symbols differ. Suppose the proposition holds at the children of an internal node v , and write B=L_v/(mT) for their common word length. Compare any source row a in G_v(x) and any target row a' in G_v(x+t w_v) . In child vi , the relative input shift is (a'-a+tR_v)w_ vi . At least m/2 children have Q_ vi a'-a+tR_v . If a'=a , the assertion holds for every child: Q_v t and (Q_v,R_v)=1 imply Q_v tR_v . If a'≠a , divisibility by Q_ vi would require p_ j,i a'-a , since p_ j,i R_v . But 0<|a'-a|<T=k^ 20k (k^4)^ m/2 =k^ 40k >T. Thus m/2 distinct primes of the required sizes cannot all divide a'-a . By induction, the sum of the deficits over the child blocks in every pair of rows is at least d_h= m2\,4^ -(h-1) B. The child blocks have equal length, fixed order and disjoint alphabets. Also d_h≤(m-1)B . Lemma 1 ([Rows with ordered tags]) therefore gives r_ L_v (G_v(x),G_v(x+t w_v)) ≥(Td_h)/(2) =4^ -h mTB=4^ -h L_v. The lemma applies to arbitrary matchings, so this proves the induction for every state x .