Fraenkel word: Difference between revisions
Jump to navigation
Jump to search
| Line 20: | Line 20: | ||
https://doi.org/10.1016/S0012-365X(99)00411-2. | https://doi.org/10.1016/S0012-365X(99)00411-2. | ||
(https://www.sciencedirect.com/science/article/pii/S0012365X99004112)</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. | (https://www.sciencedirect.com/science/article/pii/S0012365X99004112)</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 == | |||
[[Category:Terms]] | [[Category:Terms]] | ||
[[Category:Combinatorics on words]] | [[Category:Combinatorics on words]] | ||
[[Category:Math]] | [[Category:Math]] | ||
[[Category:Articles with open problems]] | [[Category:Articles with open problems]] | ||
Revision as of 21:50, 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 infinite words (periodic or not) over n letters with letter densities pairwise distinct are eventually (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
- ↑ R. Tijdeman, Fraenkel's conjecture for six sequences, Discrete Mathematics, Volume 222, Issues 1–3, 2000, Pages 223-234, ISSN 0012-365X, https://doi.org/10.1016/S0012-365X(99)00411-2. (https://www.sciencedirect.com/science/article/pii/S0012365X99004112)