Balanced word: Difference between revisions

Line 8:

* A balanced word or necklace on ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</math>.

* If ''w'' is an aperiodic infinite balanced word, then ''w'' is constructed via a finite sequence of "congruence substitutions" beginning with a Sturmian word. Over 3 or more letters, all such words have a density vector (vector of relative letter frequencies) '''a''' = (a_i) which has a pair of components that are equal. <ref>Brauner, N., Crama, Y., Delaporte, E., Jost, V., & Libralesso, L. (2019). Do balanced words have a short period?. Theoretical Computer Science, 793, 169-180.</ref>

* Some periodic balanced words are not obtainable via congruence substitutions. For alphabets of size ''N'' = 3, ..., 7, the only examples of density vectors with all components distinct are permutations of (1, 2, 4, ..., 2''N''-1) arising from the Fraenkel word ''F''''N'', defined via <math>F_1 = \mathbf{0}, F_n = F_{n-1} \mathbf{(n-1)} F_{n-1}.</math> The assertion that this is true for all ''N'' > 3 is Fraenkel's conjecture.

* Some periodic balanced words are not obtainable via congruence substitutions. For alphabets of size ''N'' = 3, ..., 7, the only examples of density vectors with all components distinct are permutations of (1, 2, 4, ..., 2''N''-1) arising from the Fraenkel word ''F''''N'', defined via <math>F_1 = \mathbf{0}, F_n = F_{n-1} \mathbf{(n-1)} F_{n-1}.</math> The assertion that this is true for all ''N'' ≥ 3 is Fraenkel's conjecture.

<!--

** A ''congruence word'' is a word u where the set of occurrences of each letter m in u is of the form <math>\{a_m n + b_m : n \in \mathbb{N}\},</math> for integers a_m and b_m.

@@ Line 8: / Line 8: @@
 * A balanced word or necklace on ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</math>.
 * If ''w'' is an aperiodic infinite balanced word, then ''w'' is constructed via a finite sequence of "congruence substitutions" beginning with a Sturmian word. Over 3 or more letters, all such words have a density vector (vector of relative letter frequencies) '''a''' = (a_i) which has a pair of components that are equal. <ref>Brauner, N., Crama, Y., Delaporte, E., Jost, V., & Libralesso, L. (2019). Do balanced words have a short period?. Theoretical Computer Science, 793, 169-180.</ref>
-* Some periodic balanced words are not obtainable via congruence substitutions. For alphabets of size ''N'' = 3, ..., 7, the only examples of density vectors with all components distinct are permutations of (1, 2, 4, ..., 2<sup>''N''-1</sup>) arising from the Fraenkel word ''F''<sub>''N''</sub>, defined via <math>F_1 = \mathbf{0}, F_n = F_{n-1} \mathbf{(n-1)} F_{n-1}.</math> The assertion that this is true for all ''N'' > 3 is Fraenkel's conjecture.
+* Some periodic balanced words are not obtainable via congruence substitutions. For alphabets of size ''N'' = 3, ..., 7, the only examples of density vectors with all components distinct are permutations of (1, 2, 4, ..., 2<sup>''N''-1</sup>) arising from the Fraenkel word ''F''<sub>''N''</sub>, defined via <math>F_1 = \mathbf{0}, F_n = F_{n-1} \mathbf{(n-1)} F_{n-1}.</math> The assertion that this is true for all ''N'' &ge; 3 is Fraenkel's conjecture.
 <!--
 ** A ''congruence word'' is a word u where the set of occurrences of each letter m in u is of the form <math>\{a_m n + b_m : n \in \mathbb{N}\},</math> for integers a_m and b_m.