Fraenkel word: Difference between revisions
Jump to navigation
Jump to search
| Line 11: | Line 11: | ||
</math> | </math> | ||
== Open problems == | == Open problems == | ||
'''Fraenkel's conjecture''' asserts that the only balanced | '''Fraenkel's conjecture''' asserts that the only balanced circular words over ''n'' ≥ 3 letters with letter occurrences pairwise distinct are (letter reassignments of) infinite repetitions 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> In particular, it implies that the only balanced primitive circular words over at least 3 letters that have "step count vectors" with pairwise distinct components are Fraenkel words. The conjecture is known to be true for [[arity]] 3 to 7. | ||
== References == | == References == | ||
Revision as of 21:56, 9 February 2024
A Fraenkel word over n letters 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]
Open problems
Fraenkel's conjecture asserts that the only balanced circular words over n ≥ 3 letters with letter occurrences pairwise distinct are (letter reassignments of) infinite repetitions of [math]\displaystyle{ F_n. }[/math][1] In particular, it implies that the only balanced primitive circular words over at least 3 letters that have "step count vectors" with pairwise distinct components are Fraenkel words. The conjecture is known to be true for arity 3 to 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.