Fraenkel word: Difference between revisions
| Line 16: | Line 16: | ||
=== 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.}} | {{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'': | To prove this, we prove the following lemmas by induction on ''n'': | ||
| Line 33: | Line 33: | ||
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>. | 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 == | ||
Revision as of 02:26, 15 February 2024
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
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(u0, ..., ur−1) represents the word w in 0, 1, ..., r−1 but with i replaced by the word ui.
Fraenkel words are balanced
Theorem — For all n ≥ 1, the n-ary Fraenkel word is balanced as a circular word.
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.