# Fraenkel word

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

[math]\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*_{0}, ..., *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 **i***w***i**, |*w*| = 2^{i+1} − 1.

**Proof**

*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

**i**

*F*

_{i}is not a suffix of

*F*

_{n}, and we thus have

**i***F*_{i}**k**...

where *k* > *i*, and *F*_{0} 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

**i***F*_{i}**k***F*_{i}**i**,

*F*

_{i}| = 2

^{i}− 1. [math]\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}:

- If |
*w*| ≡ 0 mod 2^{i+1}, then |*w*|_{i}= |*w*|/2^{i+1}. - If |
*w*| ≢ 0 mod 2^{i+1}, then |*w*|_{i}= either floor(|*w*|/2^{i+1}) or ceil(|*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}= ceil(|*w*|/2^{i+1}). Otherwise, |*w*|_{i}= floor(|*w*|/2^{i+1}).

- More precisely, if for a given

**Proof**

*w*is guaranteed to have exactly

*k*-many

**i**s where |

*w*| =

*k*2

^{i+1}. In the second case, if

*k*2

^{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}=

*k*2

^{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}= ceil(|

*w*|/2

^{i+1}), and 0 otherwise, implying |

*w*|

_{i}= floor(|

*w*|/2

^{i+1}). [math]\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} = ceil(|*w*|/2^{i+1}) or ceil(|*w*|/2^{i+1}) − 1.

**Proof**

- Both |
*u*| and |*v*| are 0 mod 2^{i+1}. - 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} = ceil(|*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*|_{i}2^{i+1}, we have

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

thus

|*w*|_{i} ≥ |*st*|_{i} = |*st*|/2^{i+1} = ceil(|*w*|/2^{i+1}) − 1.

*w*|

_{i}< ceil(|

*w*|/2

^{i+1}), lest

*u*or

*v*have an

**i**. Therefore |

*w*|

_{i}= ceil(|

*w*|/2

^{i+1}) − 1. [math]\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]F_n.[/math]^{[1]} 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 2*k*-th Fibonacci number: 1, 3, 8, 21, ...) for every *k* ≥ 1.

**Conjecture:** For all *k* > 0, MV(*F _{k}n*) =

*f*

_{k+1}.

Let G_{k} be a modified Fraenkel word, defined by

[math]\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 _{k}n*) = 2

^{k}.

## See also

## References

- ↑ Bulgakova, D. V., Buzhinsky, N., & Goncharov, Y. O. (2023). On balanced and abelian properties of circular words over a ternary alphabet. Theoretical Computer Science, 939, 227-236.