Fraenkel word

In combinatorics on words, the Fraenkel word over n letters [math]\displaystyle{ \mathbf{0}, \mathbf{1}, ..., (\mathbf{n-1}) }[/math] is defined recursively by

[math]\displaystyle{ \displaystyle{ \begin{align*} F_1 &= \mathbf{0}, \\ F_2 &= \mathbf{010}, \\ F_3 &= \mathbf{0102010}, \\ &\ \ \vdots \\ F_{n} &= F_{n-1}(\mathbf{n-1})F_{n-1}. \end{align*}} }[/math]

Fraenkel words are named after mathematician Aviezri S. Fraenkel.

Facts

Below we denote the length of a word w by |w| and the number of occurrences of the letter i in w as |w|_i, as is standard notation in combinatorics on words. The notation w(u₀, ..., u_r−1) represents the word w in 0, 1, ..., r−1 but with i replaced by the word u_i.

Fraenkel words are balanced

Theorem — For all n ≥ 1, the n-ary Fraenkel word is balanced as a circular word.

To prove this, we prove the following lemmas by induction on n:

Lemma — Let G_n denote the non-circular Fraenkel word on n letters. For all n ≥ 1, 0 ≤ i ≤ n − 1, and 1 ≤ |w| ≤ 2^n/2 − 2, the following holds for any length-|w| subword w of G_n:

1. If |w| ≡ 0 mod 2ⁱ⁺¹, then |w|_i = |w|/2ⁱ⁺¹, unless w is a concatenation of an odd-length suffix of G_n and an odd-length prefix of G_n, in which case |w|_i = |w|/2ⁱ⁺¹ + 1.
2. If |w| ≢ 0 mod 2ⁱ⁺¹, then |w|_i = either floor(|w|/2ⁱ⁺¹) or ceil(|w|/2ⁱ⁺¹).

Proof

Assume first that w is a subword of G_n. In the first case, it has the form

[math]\displaystyle{ w = u(\mathbf{1}^\prime, \mathbf{2}^\prime, ..., \mathbf{(n-1)}^\prime), }[/math]

where u is a subword of G_{n− 1} with 1 ≤ |u| ≤ 2ⁿ⁻¹ − 2 and [math]\displaystyle{ \mathbf{j}^\prime }[/math] denotes either 0j (for all j, 0 < j < n) or j0 (for all j, 0 < j < n). In particular, |w|₀ = |w|/2. Since |u| ≡ 0 mod 2ⁱ, by the inductive hypothesis applied to subwords of G_n−1 we have |w|/2ⁱ⁺¹ = |u|/2ⁱ = |u|_i−1 = |w|_i for 1 ≤ i ≤ n − 1, as desired.

In the second case, if |w| is odd, If |w| is even, we treat w as a word formed with consecutive length-2 subwords for letters, working in the next lower non-circular Fraenkel word, recursively until we reach a word v of odd length, say in G_n−r. By the inductive hypothesis, v satisfies |v|_j = floor(|v|/2^j+1) or ceil(|v|/2^j+1) for all j, 0 ≤ j ≤ n − r − 1. This implies that |u|_j+r = floor(|u|/2^j+r+1) or ceil(|u|/2^j+r+1). For 1 ≤ s < r, we can apply the first case of the inductive hypothesis to the subword v_s corresponding to u in G_n−s, obtaining |v_s|₀ = |v_s|/2 and hence after substituting back, |w|_s = |w|/2^s+1. [math]\displaystyle{ \square }[/math]

Open problems

For circular words (equivalently, infinite periodic words), Fraenkel's conjecture asserts that the only balanced circular words over n ≥ 3 letters with letter occurrences pairwise distinct are (letter reassignments of) [math]\displaystyle{ F_n. }[/math] The conjecture is known to be true for 3 ≤ n ≤ 7.