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]

where ε is the empty word. Fraenkel words may be encountered as exceptional examples of scale properties alongside larger families, e.g. for the maximum/strict variety 3 and balance properties.

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^{i + 1} letters in F_n; i.e. in every subword of the form iwi, |w| = 2^{i + 1} − 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 (on at least one side) 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^{i + 1}), then |w|_i = |w|/2^{i + 1}.
2. If |w| ≢ 0 (mod 2^{i + 1}), then |w|_i = either ⌊|w|/2^{i + 1}⌋ or ⌈|w|/2^{i + 1}⌉.
   • 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^{i + 1}), and v is a nonempty word intersecting the middle of an F_{i + 1}, then |w|_i = ⌈|w|/2^{i + 1}⌉. Otherwise, |w|_i = ⌊|w|/2^{i + 1}⌋.

Proof

We use the previous lemma. In the first case, w is guaranteed to have exactly k-many is where |w| = k2^{i + 1}. In the second case, if k2^{i + 1} < |w| < (k + 1)2^{i + 1} and w = uv or vu where |u| ≡ 0 mod 2^{i + 1}, then u satisfies |u|_i = k2^{i + 1}/2^{i + 1} = 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 = ⌈|w|/2^{i + 1}⌉, and 0 otherwise, implying |w|_i = floor(|w|/2^{i + 1}). [math]\displaystyle{ \square }[/math]

Lemma — Let [F_n] denote the circular Fraenkel word on n letters. Suppose w is a proper subword of [F_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 = ⌈|w|/2^{i + 1}⌉ or ⌈|w|/2^{i + 1}⌉ − 1.

Proof

There are 2 cases:

1. Both |u| and |v| are 0 (mod 2^{i + 1}).
2. At least one of |u| and |v| is not 0 (mod 2^{i + 1}).

In case 1, by the preceding lemma |u|_i = |u|/2^{i + 1} and |v|_i = |v|/2^{i + 1}, and hence |w|_i = |w|/2^{i + 1} = ⌈|w|/2^{i + 1}⌉.

In case 2, suppose w = ustv where st is as in case 1 and |u| and |v| are less than 2^{i + 1}. Neither u nor v can contain an i, as they are subwords of F_i. Using |st| = |st|_i2^{i + 1}, we have

|st|_i2^{i + 1} < |w| = |st|_i2^{i + 1} + |u| + |v| ≤ |st|_i2^{i + 1} + 2^{i + 1} − 2,

thus

|w|_i ≥ |st|_i = |st|/2^{i + 1} = ⌈|w|/2^{i + 1}⌉ − 1.

On the other hand, |w|_i < ⌈|w|/2^{i + 1}⌉, lest u or v have an i. Therefore |w|_i = ⌈|w|/2^{i + 1}⌉ − 1. [math]\displaystyle{ \square }[/math]

Open problems

Fraenkel's conjecture

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.

Other conjectures

Conjecture: Let MV(s) denote the maximum variety of the circular word s. Then {MV(F_{2k − 1}), MV(F_2k), MV(F_{2k + 1})} is an arithmetic progression with common difference f_2k (the 2k-th Fibonacci number: 1, 3, 8, 21, ...) for every k ≥ 1.

Conjecture: For all k > 0, MV(F_kn) = f_{k + 1}.

Let G_k be a modified Fraenkel word, defined by

[math]\displaystyle{ \displaystyle{ \begin{align*} G_0 &= \epsilon, \\ G_1 &= \mathbf{0}, \\ G_2 &= \mathbf{01010}, \\ G_3 &= \mathbf{01010201010201010}, \\ &\ \ \vdots \\ G_{n} &= G_{n-1}(\mathbf{n-1})G_{n-1}(\mathbf{n-1})G_{n-1}. \end{align*}} }[/math]

Conjecture: For all k > 1, MV(G_k) = 3 ⋅ 2^{k − 1} − 1.

Conjecture: For all k > 1, MV(G_kn) = 2^k.

See also

• ABACABA JI scales
• ABACABADABACABA JI scales