Balanced word: Difference between revisions

Line 9:

* 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.

** 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''.

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

** A ''congruence substitution'' involves replacing the ''k''th occurrence of a fixed letter ''j'' in ''w'' with the ''k''th letter of ''u'', where ''u'' is a congruence word over a set of letters disjoint from that of ''w'', for all positive integers ''k''.

@@ Line 9: / Line 9: @@
 * 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'' &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''<sub>''m''</sub> and ''b''<sub>''m''</sub>.
+** A ''congruence word'' is a word ''u'' where the set of occurrences of each letter ''m'' in ''u'' is an arithmetic progression <math>\{a_m n + b_m : n \in \mathbb{N}\},</math> for integers ''a''<sub>''m''</sub> and ''b''<sub>''m''</sub>, ''a''<sub>''m''</sub> &ne; 0.
 ** A ''congruence substitution'' involves replacing the ''k''th occurrence of a fixed letter ''j'' in ''w'' with the ''k''th letter of ''u'', where ''u'' is a congruence word over a set of letters disjoint from that of ''w'', for all positive integers ''k''.