|
|
| Line 13: |
Line 13: |
| Fraenkel words are named after mathematician Aviezri S. Fraenkel. | | Fraenkel words are named after mathematician Aviezri S. Fraenkel. |
| == Facts == | | == 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''{{!}}<sub>'''i'''</sub>, as is standard notation in combinatorics on words. The notation ''w''(''u''<sub>0</sub>, ..., ''u''<sub>''r''−1</sub>) represents the word ''w'' in '''0''', '''1''', ..., '''r−1''' but with '''i''' replaced by the word ''u''<sub>''i''</sub>.
| | {{theorem|contents=As circular words, Fraenkel words are [[balanced]].}} |
| === Fraenkel words are balanced ===
| |
| {{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''<sub>''n''</sub> denote the non-circular Fraenkel word on ''n'' letters. For all ''n'' ≥ 1, 0 ≤ ''i'' ≤ ''n'' − 1, and 1 ≤ {{!}}''w''{{!}} ≤ 2<sup>''n''/2</sup> − 2, the following holds for any subword ''w'' of ''G''<sub>''n''</sub>:
| | TODO: proof |
| # If {{!}}''w''{{!}} ≡ 0 mod 2<sup>''i''+1</sup>, then {{!}}''w''{{!}}<sub>'''i'''</sub> = {{!}}''w''{{!}}/2<sup>''i''+1</sup>.
| |
| # If {{!}}''w''{{!}} ≢ 0 mod 2<sup>''i''+1</sup>, then {{!}}''w''{{!}}<sub>'''i'''</sub> = either floor({{!}}''w''{{!}}/2<sup>''i''+1</sup>) or ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>).
| |
| }}
| |
| | |
| {{proof|contents=Assume first that ''w'' is a subword of ''G''<sub>''n''</sub>. 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''<sub>''n''− 1</sub> with 1 ≤ {{!}}''u''{{!}} ≤ 2<sup>''n''−1</sup> − 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''{{!}}<sub>'''0'''</sub> = {{!}}''w''{{!}}/2. Since {{!}}''u''{{!}} ≡ 0 mod 2<sup>''i''</sup>, by the inductive hypothesis applied to subwords of ''G''<sub>''n''−1</sub> we have {{!}}''w''{{!}}/2<sup>''i''+1</sup> = {{!}}''u''{{!}}/2<sup>''i''</sup> = {{!}}''u''{{!}}<sub>'''i−1'''</sub> = {{!}}''w''{{!}}<sub>'''i'''</sub> for 1 ≤ ''i'' ≤ ''n'' − 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''<sub>''n''−''r''</sub>. By the inductive hypothesis, ''v'' satisfies {{!}}''v''{{!}}<sub>'''j'''</sub> = floor({{!}}''v''{{!}}/2<sup>''j''+1</sup>) or ceil({{!}}''v''{{!}}/2<sup>''j''+1</sup>) for all ''j'', 0 ≤ j ≤ n − r − 1. This implies that {{!}}''u''{{!}}<sub>'''j+r'''</sub> = floor({{!}}''u''{{!}}/2<sup>''j''+''r''+1</sup>) or ceil({{!}}''u''{{!}}/2<sup>''j''+''r''+1</sup>). For 1 ≤ ''s'' < ''r'', we can apply the first case of the inductive hypothesis to the subword ''v''<sub>''s''</sub> corresponding to ''u'' in ''G''<sub>''n''−''s''</sub>, obtaining {{!}}''v''<sub>''s''</sub>{{!}}<sub>'''0'''</sub> = {{!}}''v''<sub>''s''</sub>{{!}}/2 and hence after substituting back, {{!}}''w''{{!}}<sub>'''s'''</sub> = {{!}}''w''{{!}}/2<sup>''s''+1</sup>.}}
| |
| | |
| TODO: Handle the case where the subword ''w'' of ''F''<sub>''n''</sub> is a concatenation of a suffix of ''G''<sub>''n''</sub> and a prefix of ''G''<sub>''n''</sub>.
| |
| -->
| |
|
| |
|
| == Open problems == | | == Open problems == |
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_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]
Fraenkel words are named after mathematician Aviezri S. Fraenkel.
Facts
Theorem — As circular words, Fraenkel words are balanced.
TODO: proof
Open problems
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][1] The conjecture is known to be true for 3 ≤ n ≤ 7.
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.