View source for 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 [[interval variety|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 {{abs|''w''}} and the number of occurrences of the letter '''i''' in ''w'' as {{abs|''w''}}<sub>'''i'''</sub>, as is standard notation in combinatorics on words. The notation ''w''(''u''<sub>0</sub>, ..., {{nowrap|''u''<sub>''r'' − 1</sub>}}) represents the word ''w'' in '''0''', '''1''', ..., {{nowrap|'''''r'' − 1'''}} but with '''i''' replaced by the word ''u''<sub>''i''</sub>.

=== Fraenkel words are balanced ===
{{theorem|contents=As circular words, Fraenkel words are [[balanced]].}}

The theorem will be a consequence of the following lemmas:

{{theorem|name=Lemma|contents=Let ''F''<sub>''n''</sub> denote the non-circular Fraenkel word on ''n'' letters. For {{nowrap|''n'' &ge; 1}} and {{nowrap|0 &le; ''i'' &le; ''n'' − 1}}, the letter '''i''' appears once every {{nowrap|2<sup>''i'' + 1</sup>}} letters in ''F''<sub>''n''</sub>; i.e. in every subword of the form '''i'''''w'''''i''', {{nowrap|{{abs|''w''}} {{=}} 2<sup>''i'' + 1</sup> − 1}}.}}

{{proof|contents=We prove this by induction on ''n''. The {{nowrap|''n'' {{=}} 1}} case being trivial, for {{nowrap|''n'' &gt; 1}} we start by observing that '''i''' always occurs as the greatest letter of a subword that is the Fraenkel word {{nowrap|''F''<sub>''i'' + 1</sub>}}, and {{nowrap|''F''<sub>''i'' + 1</sub>}} is always flanked (on at least one side) by letters that are greater. This subword '''i'''''F''<sub>''i''</sub> is not a suffix of ''F''<sub>''n''</sub>, and we thus have

'''i'''''F''<sub>''i''</sub>'''k'''...

where {{nowrap|''k'' &gt; ''i''}}, and ''F''<sub>0</sub> is the empty word. Since '''k''' occurs as the middle letter of {{nowrap|''F''<sub>''k'' + 1</sub>}}, there is a copy of ''F''<sub>''k''</sub> that follows '''k'''; ''F''<sub>''k''</sub> has ''F''<sub>i</sub> as a prefix. Thus ''F''<sub>''n''</sub> has a subword

'''i'''''F''<sub>''i''</sub>'''k'''''F''<sub>''i''</sub>'''i''',

as desired, since {{nowrap|{{abs|''F''<sub>i</sub>}} {{=}} 2<sup>''i''</sup> − 1}}.
}}

{{theorem|name=Lemma|contents=For all {{nowrap|''n'' &ge; 1|0 &le; ''i'' &le; ''n'' − 1}}, and {{nowrap|1 &le; {{abs|''w''}} &le; 2<sup>''n''/2</sup> − 2}}, the following holds for any subword ''w'' of ''F''<sub>''n''</sub>:
# If {{nowrap|{{abs|''w''}} ≡ 0 (mod 2<sup>''i'' + 1</sup>)}}, then {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> {{=}} {{abs|''w''}}/2<sup>''i'' + 1</sup>}}.
# If {{nowrap|{{abs|''w''}} ≢ 0 (mod 2<sup>''i'' + 1</sup>)}}, then {{abs|''w''}}<sub>'''i'''</sub> {{=}} either {{nowrap|{{floor|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}}}} or {{nowrap|{{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}}}}.
#* More precisely, if for a given ''i'' we have {{nowrap|''w'' {{=}} ''uv''}} or ''vu'' where ''u'' is a possibly empty word whose length is {{nowrap|0 (mod 2<sup>''i'' + 1</sup>)}}, and ''v'' is a nonempty word intersecting the middle of an {{nowrap|''F''<sub>''i'' + 1</sub>}}, then {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> {{=}} {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}}}}. Otherwise, {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> {{=}} {{floor|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}}}}.
}}

{{proof|contents=We use the previous lemma. In the first case, ''w'' is guaranteed to have exactly ''k''-many '''i'''s where {{abs|''w''}} = ''k''2<sup>''i'' + 1</sup>. In the second case, if ''k''2<sup>''i'' + 1</sup> < {{abs|''w''}} < (''k'' + 1)2<sup>''i'' + 1</sup> and ''w'' = ''uv'' or ''vu'' where {{abs|''u''}} ≡ 0 mod 2<sup>''i'' + 1</sup>,  then ''u'' satisfies {{abs|''u''}}<sub>'''i'''</sub> = ''k''2<sup>''i'' + 1</sup>/2<sup>''i'' + 1</sup> = ''k'' by the previous case. Thus {{abs|''w''}}<sub>'''i'''</sub>  is determined by {{abs|''v''}}<sub>'''i'''</sub>, which is 1 if ''v'' contains the '''i''' in the middle of ''F''<sub>''i''</sub>, implying {{abs|''w''}}<sub>'''i'''</sub> = {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}}, and 0 otherwise, implying {{abs|''w''}}<sub>'''i'''</sub> = floor({{abs|''w''}}/2<sup>''i'' + 1</sup>).}}

{{theorem|name=Lemma|contents=Let [''F''<sub>''n''</sub>] denote the circular Fraenkel word on ''n'' letters. Suppose ''w'' is a proper subword of [''F''<sub>''n''</sub>] such that {{nowrap|''w'' {{=}} ''uv''}} where ''u'' is a nonempty suffix of ''F''<sub>''n''</sub> and ''v'' is a nonempty prefix of ''F''<sub>''n''</sub>. For {{nowrap|1 &le; {{abs|''w''}} &le; 2<sup>''n''/2</sup> − 2}}, either {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> {{=}} {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}}}} or {{nowrap|{{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}} − 1}}.
}}

{{proof|contents=
There are 2 cases:
# Both {{abs|''u''}} and {{abs|''v''}} are {{nowrap|0 (mod 2<sup>''i'' + 1</sup>)}}.
# At least one of {{abs|''u''}} and {{abs|''v''}} is not {{nowrap|0 (mod 2<sup>''i'' + 1</sup>)}}.
In case 1, by the preceding lemma {{nowrap|{{abs|''u''}}<sub>'''i'''</sub> {{=}} {{abs|''u''}}/2<sup>''i'' + 1</sup>}} and {{nowrap|{{abs|''v''}}<sub>'''i'''</sub> {{=}} {{abs|''v''}}/2<sup>''i'' + 1</sup>}}, and hence {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> {{=}} {{abs|''w''}}/2<sup>''i'' + 1</sup>}} {{nowrap|{{=}} {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}}}}.

In case 2, suppose {{nowrap|''w'' {{=}} ''ustv''}} where ''st'' is as in case 1 and {{abs|''u''}} and {{abs|''v''}} are less than {{nowrap|2<sup>''i'' + 1</sup>}}. Neither ''u'' nor ''v'' can contain an '''i''', as they are subwords of ''F''<sub>''i''</sub>. Using {{nowrap|{{abs|''st''}} {{=}} {{abs|''st''}}<sub>'''i'''</sub>2<sup>''i'' + 1</sup>}}, we have

{{nowrap|{{abs|''st''}}<sub>'''i'''</sub>2<sup>''i'' + 1</sup> &lt; {{abs|''w''}}}} {{nowrap|{{=}} {{abs|''st''}}<sub>'''i'''</sub>2<sup>''i'' + 1</sup> + {{abs|''u''}} + {{abs|''v''}}}} {{nowrap|&le; {{abs|''st''}}<sub>'''i'''</sub>2<sup>''i'' + 1</sup> + 2<sup>''i'' + 1</sup> − 2}}, 

thus

{{nowrap|{{abs|''w''}}<sub>'''i'''</sub> &ge; {{abs|''st''}}<sub>'''i'''</sub>}} {{nowrap|{{=}} {{abs|''st''}}/2<sup>''i'' + 1</sup>}} {{nowrap|{{=}} {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}} − 1}}. 

On the other hand, {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> &lt; {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}}}}, lest ''u'' or ''v'' have an '''i'''. Therefore {{nowrap|{{abs|''w''}}<sub>'''i'''</sub> {{=}} {{ceil|{{abs|''w''}}/2<sup>''i'' + 1</sup>|1.75}} − 1}}.
}}

== Open problems ==
=== Fraenkel's conjecture ===
For [[circular word]]s (equivalently, infinite periodic words), '''Fraenkel's conjecture''' asserts that the only [[balanced]] circular words over {{nowrap|''n'' &ge; 3}} letters with letter occurrences pairwise distinct are (letter reassignments of) <math>F_n.</math><ref>Bulgakova, D. V., Buzhinsky, N., &amp; Goncharov, Y. O. (2023). On balanced and abelian properties of circular words over a ternary alphabet. Theoretical Computer Science, 939, 227-236.</ref> The conjecture is known to be true for {{nowrap|3 &le; ''n'' &le; 7}}.

=== Other conjectures ===
'''Conjecture:''' Let MV(''s'') denote the [[maximum variety]] of the circular word ''s''. Then <nowiki>{</nowiki>{{nowrap|MV(''F''<sub>2''k'' − 1</sub>)}}, MV(''F''<sub>2''k''</sub>), {{nowrap|MV(''F''<sub>2''k'' + 1</sub>)}}<nowiki>}</nowiki> is an arithmetic progression with common difference ''f''<sub>2''k''</sub> (the 2''k''-th Fibonacci number: 1, 3, 8, 21, ...) for every {{nowrap|''k'' &ge; 1}}.

'''Conjecture:''' For all {{nowrap|''k'' &gt; 0|MV(''F<sub>k</sub>'''n''''') {{=}} ''f''<sub>''k'' + 1</sub>}}.

Let G<sub>k</sub> 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 {{nowrap|''k'' > 1}}, {{nowrap|MV(''G<sub>k</sub>'') {{=}} 3{{dot}}2<sup>''k'' − 1</sup> − 1}}.

'''Conjecture:''' For all {{nowrap|''k'' > 1}}, {{nowrap|MV(''G<sub>k</sub>'''n''''') {{=}} 2<sup>''k''</sup>}}.

== See also ==
* [[ABACABA JI scales]]
* [[ABACABADABACABA JI scales]]

== References ==
<references />

[[Category:Terms]]
[[Category:Combinatorics on words]]
[[Category:Math]]
[[Category:Pages with open problems]]