Conceptual
Browse Instruct Curate

Edit-Distance Diameter of Words in Substitution Systems

A quantitative bound on how dissimilar the length-n admissible words of a primitive substitution can be, measured by edit distance. Building on the fact that minimal substitution dynamical systems are loosely Kronecker (giving a diameter of o(n)), the result sharpens the upper bound to O(n/sqrt(log n)), treats the harder non-uniform case, and establishes a matching square-root lower bound for the Thue-Morse substitution.