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_0 &= \epsilon, \\ 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]

Here ε is the empty word.

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 — As circular words, Fraenkel words are balanced.

The theorem will be a consequence of the following lemmas:

Lemma — Let F_n denote the non-circular Fraenkel word on n letters. For n ≥ 1 and 0 ≤ i ≤ n − 1, the letter i appears once every 2ⁱ⁺¹ letters in F_n; i.e. in every subword of the form iwi, |w| = 2ⁱ⁺¹ − 1.

Proof

We prove this by induction on n. The n = 1 case being trivial, for n > 1 we start by observing that i always occurs as the greatest letter of a subword that is the Fraenkel word F_i+1, and F_i+1 is always flanked by letters that are greater. This subword iF_i is not a suffix of F_n, and we thus have

iF_ik...

where k > i, and F₀ is the empty word. Since k occurs as the middle letter of F_k+1, there is a copy of F_k that follows k; F_k has F_i as a prefix. Thus F_n has a subword

iF_ikF_ii,

as desired, since |F_i| = 2ⁱ − 1. [math]\displaystyle{ \square }[/math]

Lemma — For all n ≥ 1, 0 ≤ i ≤ n − 1, and 1 ≤ |w| ≤ 2^n/2 − 2, the following holds for any subword w of F_n:

1. If |w| ≡ 0 mod 2ⁱ⁺¹, then |w|_i = |w|/2ⁱ⁺¹.
2. If |w| ≢ 0 mod 2ⁱ⁺¹, then |w|_i = either floor(|w|/2ⁱ⁺¹) or ceil(|w|/2ⁱ⁺¹).
   • More precisely, if for a given i we have w = uv or vu where u is a possibly empty word whose length is 0 mod 2ⁱ⁺¹, and v is a nonempty word intersecting the middle of an F_i+1, then |w|_i = ceil(|w|/2ⁱ⁺¹). Otherwise, |w|_i = floor(|w|/2ⁱ⁺¹).

Proof

We use the previous lemma. In the first case, w is guaranteed to have exactly k-many is where |w| = k2ⁱ⁺¹. In the second case, if k2ⁱ⁺¹ < |w| < (k + 1)2ⁱ⁺¹ and w = uv or vu where |u| ≡ 0 mod 2ⁱ⁺¹, then u satisfies |u|_i = k2ⁱ⁺¹/2ⁱ⁺¹ = k by the previous case. Thus |w|_i is determined by |v|_i, which is 1 if v contains the i in the middle of F_i, implying |w|_i = ceil(|w|/2ⁱ⁺¹), and 0 otherwise, implying |w|_i = floor(|w|/2ⁱ⁺¹). [math]\displaystyle{ \square }[/math]

Lemma — Let G_n denote the circular Fraenkel word on n letters. Suppose w is a proper subword of G_n such that w = uv where u is a nonempty suffix of F_n and v is a nonempty prefix of F_n. For 1 ≤ |w| ≤ 2^n/2 − 2, either |w|_i = ceil(|w|/2ⁱ⁺¹) or ceil(|w|/2ⁱ⁺¹) − 1.

Proof

There are 2 cases:

1. Both |u| and |v| are 0 mod 2ⁱ⁺¹.
2. At least one of |u| and |v| is not 0 mod 2ⁱ⁺¹.

In case 1, by the preceding lemma |u|_i = |u|/2ⁱ⁺¹ and |v|_i = |v|/2ⁱ⁺¹, and hence |w|_i = |w|/2ⁱ⁺¹ = ceil(|w|/2ⁱ⁺¹).

In case 2, suppose w = ustv where st is as in case 1 and |u| and |v| are less than 2ⁱ⁺¹. Neither u nor v can contain an i, as they are subwords of F_i. Since

|st| < |w| = |st| + |u| + |v| ≤ |st| + 2ⁱ⁺¹ − 2,

we have

|w|_i ≥ |st|_i = |st|/2ⁱ⁺¹ = ceil(|w|/2ⁱ⁺¹) − 1.

On the other hand, |w|_i < ceil(|w|/2ⁱ⁺¹), lest u or v have an i. Therefore |w|_i = ceil(|w|/2ⁱ⁺¹) − 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.