Proposition 9 ([Finite obstruction]). For all sufficiently large k , the word image G(x):x∈A , with ordinary edit distance, has distortion at least C₁^-1 (k/4)^k , for an absolute constant C₁ .

Take an embedding of the word image with distortion D and rescale it so that its induced distance ρ on parameter states satisfies 1D(G(x),G(y))≤ρ(x,y)≤(G(x),G(y)). The map x↦G(x) need not be injective; composing it with the embedding still gives a map to which Lemma 8 ([Finite-group displacement]) applies. Write V(z)=_xρ(x,x+z) =∑_χ|1-χ(z)|^2H(χ), H(χ)≥0. First average over the entire cyclic coordinate of one leaf u . The average of |1-χ(t e_u)|^2 is two if χ is nontrivial on that coordinate and zero otherwise. Sum the leaf-cost bound in Lemma 6 ([Inexpensive finite translations]) over all m^k leaves. It follows that 2∑_χ(χ)H(χ)≤M. Now suppose an internal node v at depth j is active for χ but has fewer than k active children. Since χ(w_v)=χ(u_v)^ R_v ≠1 , the value χ(u_v) is a nontrivial root of unity. The inactive children contribute one to χ(u_v)=∏_iχ(w_ vi ) , so at least one child is active. Let q=(χ(u_v)) . This order divides the least common multiple of the active child periods, and q≤Q_v∏_ i:\,vi active p_ j,i ≤2k^ 5j+5(k-1) ≤2k^ 10k . Put J=4k^ 10k . For large k , J≤T and q≤J/2 . The integers 1,…,J contain J/q complete periods of this root of unity, with total length at least J/2 . On a complete nontrivial period the mean of |1-χ(su_v)|^2 is two. Consequently 1J∑_ s=1 ^J |1-χ(su_v)|^2≥1. This uses complete periods inside the averaging interval and does not require q to divide J . Because all Fourier weights are nonnegative, the total weight of characters with this property at the fixed node v is at most J^ -1 ∑_ s=1 ^J V(su_v) . Lemma 6 ([Inexpensive finite translations]) bounds that average by (2J/T)M/m^j . There are m^j nodes at depth j . Summing over nodes and all k internal depths bounds the weight of characters having any active internal node with fewer than k active children by 2k(J/T)M. The sets of characters for different nodes may overlap; nonnegativity makes their sum an upper bound for the union. Every other character active at the root has at least k active children at each active internal node. Iterating down the tree gives (χ)≥k^k . By, these characters have total weight at most M/(2k^k) . Root-inactive characters contribute zero to V(w_o) , and any root multiplier is at most four. Hence V(w_o)≤4M((2kJ)/(T)+1 2k^k ) ≤C_1Mk^ -k . Here J/T=4k^ -10k , so an absolute C_1 suffices for all large k . Finally Q_o=2 . Proposition 7 ([Separation in the finite tree]) with t=1 and imply ρ(x,x+w_o)≥4^ -k M/D at every state. Its average, compared with , gives D≥C_1^ -1 (k/4)^k .