OAI.TreeEdit.binary_lower_bound

The theorem states that there exist a real constant c>0 and a natural number d₀ such that for every natural number d≥d₀ there is a length n with 1≤n≤d and a finite set W of binary words (lists over Bool) of exactly length n with at least two elements such that growth(c,d)≤binarySetDistortion(W). Here ed is the edit distance on lists, the least number of unit-cost steps (insertion, deletion, or substitution of one symbol at any position) in an edit script, with no restriction on intermediate word lengths. The distortion of a map f from a metric-like space (X,ρ) into the real sequence space ℓ₁ is the product of the supremum of ‖f(x)−f(y)‖/ρ(x,y) and the supremum of ρ(x,y)/‖f(x)−f(y)‖ over pairs x≠y. The quantity c₁(X,ρ) is the infimum of this distortion over all injective maps into ℓ₁, and binarySetDistortion(W) is c₁ of W under edit distance. The growth function is growth(c,d)=exp(c·√(log d · log log d)). So for all large length caps, there are equal-length binary word sets whose optimal ℓ₁ embedding distortion under edit distance is at least this growth. The theorem is stated with its proof admitted.