Fraenkel word: Difference between revisions

F_{n} &= F_{n-1}(\mathbf{n-1})F_{n-1},

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.

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''}}_'''i''', as is standard notation in combinatorics on words. The notation ''w''(''u''₀, ..., {{nowrap|''u''_{''r'' − 1}}}) represents the word ''w'' in '''0''', '''1''', ..., {{nowrap|'''''r'' − 1'''}} but with '''i''' replaced by the word ''u''_''i''.

 

{{theorem|name=Lemma|contents=Let ''F''_''n'' denote the non-circular Fraenkel word on ''n'' letters. For {{nowrap|''n'' ≥ 1}} and {{nowrap|0 ≤ ''i'' ≤ ''n'' − 1}}, the letter '''i''' appears once every {{nowrap|2^{''i'' + 1}}} letters in ''F''_''n''; i.e. in every subword of the form '''i'''''w'''''i''', {{nowrap|{{abs|''w''}} {{=}} 2^{''i'' + 1} − 1}}.}}

{{proof|contents=We prove this by induction on ''n''. The {{nowrap|''n'' {{=}} 1}} case being trivial, for {{nowrap|''n'' > 1}} we start by observing that '''i''' always occurs as the greatest letter of a subword that is the Fraenkel word {{nowrap|''F''_{''i'' + 1}}}, and {{nowrap|''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

where {{nowrap|''k'' > ''i''}}, and ''F''₀ is the empty word. Since '''k''' occurs as the middle letter of {{nowrap|''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''',

as desired, since {{nowrap|{{abs|''F''_i}} {{=}} 2^''i'' − 1}}.

{{theorem|name=Lemma|contents=For all {{nowrap|''n'' ≥ 1|0 ≤ ''i'' ≤ ''n'' − 1}}, and {{nowrap|1 ≤ {{abs|''w''}} ≤ 2^''n''/2 − 2}}, the following holds for any subword ''w'' of ''F''_''n'':

# If {{nowrap|{{abs|''w''}} ≡ 0 (mod 2^{''i'' + 1})}}, then {{nowrap|{{abs|''w''}}_'''i''' {{=}} {{abs|''w''}}/2^{''i'' + 1}}}.

# If {{nowrap|{{abs|''w''}} ≢ 0 (mod 2^{''i'' + 1})}}, then {{abs|''w''}}_'''i''' {{=}} either {{nowrap|{{floor|{{abs|''w''}}/2^{''i'' + 1}|1.75}}}} or {{nowrap|{{ceil|{{abs|''w''}}/2^{''i'' + 1}|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^{''i'' + 1})}}, and ''v'' is a nonempty word intersecting the middle of an {{nowrap|''F''_{''i'' + 1}}}, then {{nowrap|{{abs|''w''}}_'''i''' {{=}} {{ceil|{{abs|''w''}}/2^{''i'' + 1}|1.75}}}}. Otherwise, {{nowrap|{{abs|''w''}}_'''i''' {{=}} {{floor|{{abs|''w''}}/2^{''i'' + 1}|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^{''i'' + 1}. In the second case, if ''k''2^{''i'' + 1} < {{abs|''w''}} < (''k'' + 1)2^{''i'' + 1} and ''w'' = ''uv'' or ''vu'' where {{abs|''u''}} ≡ 0 mod 2^{''i'' + 1},  then ''u'' satisfies {{abs|''u''}}_'''i''' = ''k''2^{''i'' + 1}/2^{''i'' + 1} = ''k'' by the previous case. Thus {{abs|''w''}}_'''i'''  is determined by {{abs|''v''}}_'''i''', which is 1 if ''v'' contains the '''i''' in the middle of ''F''_''i'', implying {{abs|''w''}}_'''i''' = {{ceil|{{abs|''w''}}/2^{''i'' + 1}|1.75}}, and 0 otherwise, implying {{abs|''w''}}_'''i''' = floor({{abs|''w''}}/2^{''i'' + 1}).}}

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

# Both {{abs|''u''}} and {{abs|''v''}} are {{nowrap|0 (mod 2^{''i'' + 1})}}.

# At least one of {{abs|''u''}} and {{abs|''v''}} is not {{nowrap|0 (mod 2^{''i'' + 1})}}.

In case 1, by the preceding lemma {{nowrap|{{abs|''u''}}_'''i''' {{=}} {{abs|''u''}}/2^{''i'' + 1}}} and {{nowrap|{{abs|''v''}}_'''i''' {{=}} {{abs|''v''}}/2^{''i'' + 1}}}, and hence {{nowrap|{{abs|''w''}}_'''i''' {{=}} {{abs|''w''}}/2^{''i'' + 1}}} {{nowrap|{{=}} {{ceil|{{abs|''w''}}/2^{''i'' + 1}|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^{''i'' + 1}}}. Neither ''u'' nor ''v'' can contain an '''i''', as they are subwords of ''F''_''i''. Using {{nowrap|{{abs|''st''}} {{=}} {{abs|''st''}}_'''i'''2^{''i'' + 1}}}, we have

{{nowrap|{{abs|''st''}}_'''i'''2^{''i'' + 1} &lt; {{abs|''w''}}}} {{nowrap|{{=}} {{abs|''st''}}_'''i'''2^{''i'' + 1} + {{abs|''u''}} + {{abs|''v''}}}} {{nowrap|&le; {{abs|''st''}}_'''i'''2^{''i'' + 1} + 2^{''i'' + 1} − 2}},  

{{nowrap|{{abs|''w''}}_'''i''' &ge; {{abs|''st''}}_'''i'''}} {{nowrap|{{=}} {{abs|''st''}}/2^{''i'' + 1}}} {{nowrap|{{=}} {{ceil|{{abs|''w''}}/2^{''i'' + 1}|1.75}} − 1}}.  

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

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}}.

 

 

 

 

G_{n} &= G_{n-1}(\mathbf{n-1})G_{n-1}(\mathbf{n-1})G_{n-1}.