2022/11/23 by Andrei Mandelshtam, Mandelshtam, Andrei
Computer Science · Mathematics · #Cellular Automata and Applications #Combinatorics (math.CO) #FOS: Mathematics #Mathematical Dynamics and Fractals #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2211.14229
openalex publication_date 2022/11/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Ulam words are binary words defined recursively as follows: the length-1 Ulam words are 0 and 1, and a binary word of length n is Ulam if and only if it is expressible uniquely as a concatenation of two shorter, distinct Ulam words. We discover, fully describe, and prove a surprisingly rich structure already in the set of Ulam words containing exactly two 1's. In particular, this leads to a complete description of such words and a logarithmic-time algorithm to determine whether a binary word with two 1's is Ulam. Along the way, we uncover delicate parity and biperiodicity properties, as well as sharp bounds on the number of 0's outside the two 1's. We also show that sets of Ulam words indexed by the number y of 0's between the two 1's have intricate tensor-based hierarchical structures determined by the arithmetic properties of y. This allows us to construct an infinite family of self-similar Ulam-word-based fractals indexed by the set of 2-adic integers, containing the outward Sierpinski gasket as a special case.