Fraenkel word: Difference between revisions

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

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

{{theorem|contents=For all ''n'' ≥ 1, the ''n''-ary Fraenkel word is [[balanced]] as a circular word.}}

To prove this, we prove the following lemmas by induction on ''n'':

{{theorem|name=Lemma|contents=Let ''G''_''n'' denote the non-circular Fraenkel word on ''n'' letters. For all ''n'' ≥ 1, 0 ≤ ''i'' ≤ ''n'' − 1, and 1 ≤ {{!}}''w''{{!}} ≤ 2^''n''/2 − 2, the following holds for any length-{{!}}''w''{{!}} subword ''w'' of ''G''_''n'':

# If {{!}}''w''{{!}} ≡ 0 mod 2^''i''+1, then {{!}}''w''{{!}}_'''i''' = {{!}}''w''{{!}}/2^''i''+1, unless ''w'' is a concatenation of an odd-length suffix of ''G''_''n'' and an odd-length prefix of ''G''_''n'', in which case {{!}}''w''{{!}}_'''i''' = {{!}}''w''{{!}}/2^''i''+1 + 1.

# If {{!}}''w''{{!}} ≢ 0 mod 2^''i''+1, then {{!}}''w''{{!}}_'''i''' = either floor({{!}}''w''{{!}}/2^''i''+1) or ceil({{!}}''w''{{!}}/2^''i''+1).

{{proof|contents=Assume first that ''w'' is a subword of ''G''_''n''. In the first case, it has the form

<math> w = u(\mathbf{1}^\prime, \mathbf{2}^\prime, ..., \mathbf{(n-1)}^\prime),</math>

where ''u'' is a subword of ''G''_{''n''&minus; 1} with 1 &le; {{!}}''u''{{!}} &le; 2^{''n''&minus;1} &minus; 2 and <math>\mathbf{j}^\prime</math> denotes either '''0j''' (for all ''j'', 0 < ''j'' < n) or '''j0''' (for all ''j'', 0 < ''j'' < ''n''). In particular, {{!}}''w''{{!}}_'''0''' = {{!}}''w''{{!}}/2. Since {{!}}''u''{{!}} ≡ 0 mod 2^''i'', by the inductive hypothesis applied to subwords of ''G''_{''n''&minus;1} we have {{!}}''w''{{!}}/2^''i''+1 = {{!}}''u''{{!}}/2^''i'' = {{!}}''u''{{!}}_{'''i&minus;1'''} = {{!}}''w''{{!}}_'''i''' for 1 &le; ''i'' &le; ''n'' &minus; 1, as desired.

In the second case, if {{!}}''w''{{!}} is odd, If {{!}}''w''{{!}} is even, we treat ''w'' as a word formed with consecutive length-2 subwords for letters, working in the next lower non-circular Fraenkel word, recursively until we reach a word ''v'' of odd length, say in ''G''_{''n''&minus;''r''}. By the inductive hypothesis, ''v'' satisfies {{!}}''v''{{!}}_'''j''' = floor({{!}}''v''{{!}}/2^''j''+1) or ceil({{!}}''v''{{!}}/2^''j''+1) for all ''j'', 0 &le; j &le; n &minus; r &minus; 1. This implies that {{!}}''u''{{!}}_'''j+r''' =  floor({{!}}''u''{{!}}/2^{''j''+''r''+1}) or ceil({{!}}''u''{{!}}/2^{''j''+''r''+1}). For 1 &le; ''s'' < ''r'', we can apply the first case of the inductive hypothesis to the subword ''v''_''s'' corresponding to ''u'' in ''G''_{''n''&minus;''s''}, obtaining {{!}}''v''_''s''{{!}}_'''0''' = {{!}}''v''_''s''{{!}}/2 and hence after substituting back, {{!}}''w''{{!}}_'''s''' = {{!}}''w''{{!}}/2^''s''+1.}}

For [[circular word]]s (equivalently, infinite periodic words), '''Fraenkel's conjecture''' asserts that the only [[balanced]] circular words over ''n'' &ge; 3 letters with letter occurrences pairwise distinct are (letter reassignments of) <math>F_n.</math><ref>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.</ref> The conjecture is known to be true for 3 &le; ''n'' &le; 7.