Balanced word: Difference between revisions

(7 intermediate revisions by 2 users not shown)

Line 1:

{{distinguish|perfect balance}}{{Todo|rework|inline=1|text=this can probably be explained without invoking "words"}}

An abstract scale pattern is '''balanced''' if it satisfies a certain (quite strong) restriction on how much the intervals in within any of the scale's interval classes can differ; by one characterization of the ~~balancedness~~, for any step size, ~~the property stipulates that~~ no two ''k''-steps can differ too much in how many times the step size occurs in them. ~~Balanced~~ words are one of many possible generalizations of [[MOS scale]]s to scales with three or more step sizes.

An abstract scale pattern is '''balanced''' if it satisfies a certain (quite strong) restriction on how much the intervals within any of the scale's interval classes can differ; by one characterization of the property, it stipulates that for any step size, no two ''k''-steps can differ too much in how many times the step size occurs in them. The simplest non-trivial examples of balanced scales are [[MOS scales]], and balanced words are one of many possible generalizations of [[MOS scale]]s to scales with three or more step sizes.

== Mathematical definition ==

Let ''a'' be a letter in a [[word]] or [[necklace]] ''s''. Define

Line 10:

Line 11:

Then ''s'' is '''balanced''' if its '''block balance'''{{idiosyncratic}} satisfies the following:

<math> \mathsf{block\_balance}(s) := \max \big\{ \mathsf{block\_balance}(s, a) : a \text{ is a letter of }s \big\} \leq 1,</math>

<math> \mathsf{block\_balance}(s) := \max \big\{ \mathsf{block\_balance}(s, a) : a \text{ is a letter of }s \big\} \leq 1.</math>

== Properties ==

* A balanced word or necklace on ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</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, binary balanced periodic words are MOS words.

* A balanced word or necklace on ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</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, binary balanced periodic words are MOS words, and ternary balanced periodic words have maximum variety 3.

* 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 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 21:

Line 22:

== Generalizations ==

# If <math> \mathsf{block\_balance}(s) \leq m,</math> then we say that ''s'' is ''m''-'''block-balanced'''{{idiosyncratic}}.

# The following stronger property implies ''m''-block-balancedness for ''m'' ≥ 1 but is not equivalent to it unless ''m'' = 1: ''s'' is ''m''-'''chain-balanced'''{{idiosyncratic}} if for every letter ''a'' in ''s'' and every factor of ''s'' of the form ''awa'', any factor ''w' '' in ''s'' such that len(w') = len(''w'') + ''m'' + 1 satisfies |w'|''a'' ~~≥~~ |''w''|''a'' ~~+ 1~~.<ref>Sano, S., Miyoshi, N., & Kataoka, R. (2004). m-Balanced words: A generalization of balanced words. Theoretical computer science, 314(1-2), 97-120.</ref> (Compare [[recursive structure of MOS scales|MOS chunks]]; proving that the chunk sizes in a MOS themselves form a MOS word proves that for binary scales, balanced implies 1-chain-balanced.)

# The following stronger property implies ''m''-block-balancedness for ''m'' ≥ 1 but is not equivalent to it unless ''m'' = 1: ''s'' is ''m''-'''chain-balanced'''{{idiosyncratic}} if for every letter ''a'' in ''s'' and every factor of ''s'' of the form ''awa'', any factor ''w' '' in ''s'' such that len(w') = len(''w'') + ''m'' + 1 satisfies |w'|''a'' > |''w''|''a''.<ref>Sano, S., Miyoshi, N., & Kataoka, R. (2004). m-Balanced words: A generalization of balanced words. Theoretical computer science, 314(1-2), 97-120.</ref> (Compare [[recursive structure of MOS scales|MOS chunks]]; proving that the chunk sizes in a MOS themselves form a MOS word proves that for binary scales, balanced implies 1-chain-balanced.)

Block and chain balancedness are equivalent for balanced scales (which are 1-balanced in both senses) and ternary billiard ones, but ''m''-chain-balancedness is stronger than ''m''-block-balancedness in the general case.

@@ Line 1: / Line 1: @@
-{{distinguish|perfect balance}}
+{{distinguish|perfect balance}}{{Todo|rework|inline=1|text=this can probably be explained without invoking "words"}}
-An abstract scale pattern is '''balanced''' if it satisfies a certain (quite strong) restriction on how much the intervals in within any of the scale's interval classes can differ; by one characterization of the balancedness, for any step size, the property stipulates that no two ''k''-steps can differ too much in how many times the step size occurs in them. Balanced words are one of many possible generalizations of [[MOS scale]]s to scales with three or more step sizes.
+An abstract scale pattern is '''balanced''' if it satisfies a certain (quite strong) restriction on how much the intervals within any of the scale's interval classes can differ; by one characterization of the property, it stipulates that for any step size, no two ''k''-steps can differ too much in how many times the step size occurs in them. The simplest non-trivial examples of balanced scales are [[MOS scales]], and balanced words are one of many possible generalizations of [[MOS scale]]s to scales with three or more step sizes.
 == Mathematical definition ==
 Let ''a'' be a letter in a [[word]] or [[necklace]] ''s''. Define
@@ Line 10: / Line 11: @@
 Then ''s'' is '''balanced''' if its '''block balance'''{{idiosyncratic}} satisfies the following:
-<math> \mathsf{block\_balance}(s) := \max \big\{ \mathsf{block\_balance}(s, a) : a \text{ is a letter of }s \big\} \leq 1,</math>
+<math> \mathsf{block\_balance}(s) := \max \big\{ \mathsf{block\_balance}(s, a) : a \text{ is a letter of }s \big\} \leq 1.</math>
 == Properties ==
-* A balanced word or necklace on ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</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, binary balanced periodic words are MOS words.
+* A balanced word or necklace on ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</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, binary balanced periodic words are MOS words, and ternary balanced periodic words have maximum variety 3.
 * 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.
+* 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 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''.
@@ Line 21: / Line 22: @@
 == Generalizations ==
 # If <math> \mathsf{block\_balance}(s) \leq m,</math> then we say that ''s'' is ''m''-'''block-balanced'''{{idiosyncratic}}.
-# The following stronger property implies ''m''-block-balancedness for ''m'' &ge; 1 but is not equivalent to it unless ''m'' = 1: ''s'' is ''m''-'''chain-balanced'''{{idiosyncratic}} if for every letter ''a'' in ''s'' and every factor of ''s'' of the form ''awa'', any factor ''w' '' in ''s'' such that len(<i>w'</i>) = len(''w'') + ''m'' + 1 satisfies |<i>w'</i>|<sub>''a''</sub> &ge; |''w''|<sub>''a''</sub> + 1.<ref>Sano, S., Miyoshi, N., & Kataoka, R. (2004). m-Balanced words: A generalization of balanced words. Theoretical computer science, 314(1-2), 97-120.</ref> (Compare [[recursive structure of MOS scales|MOS chunks]]; proving that the chunk sizes in a MOS themselves form a MOS word proves that for binary scales, balanced implies 1-chain-balanced.)
+# The following stronger property implies ''m''-block-balancedness for ''m'' &ge; 1 but is not equivalent to it unless ''m'' = 1: ''s'' is ''m''-'''chain-balanced'''{{idiosyncratic}} if for every letter ''a'' in ''s'' and every factor of ''s'' of the form ''awa'', any factor ''w' '' in ''s'' such that len(<i>w'</i>) = len(''w'') + ''m'' + 1 satisfies |<i>w'</i>|<sub>''a''</sub> > |''w''|<sub>''a''</sub>.<ref>Sano, S., Miyoshi, N., & Kataoka, R. (2004). m-Balanced words: A generalization of balanced words. Theoretical computer science, 314(1-2), 97-120.</ref> (Compare [[recursive structure of MOS scales|MOS chunks]]; proving that the chunk sizes in a MOS themselves form a MOS word proves that for binary scales, balanced implies 1-chain-balanced.)
 Block and chain balancedness are equivalent for balanced scales (which are 1-balanced in both senses) and ternary billiard ones, but ''m''-chain-balancedness is stronger than ''m''-block-balancedness in the general case.