Balanced word
- Not to be confused with perfect balance.
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 scales to scales with three or more step sizes.
Mathematical definition
Let a be a letter in a word or necklace s. Define
[math] \mathsf{block\_balance}(s, a) := \max \big\{ \big| |w|_{a} - |w'|_{a} \big| : |w| = |w'| \big\},[/math]
where |u|a is the number of occurrences of the letter a in the word u and |u| is the length of the word u.
Then s is balanced if its block balance [idiosyncratic term ] 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]
Properties
- A balanced word or necklace on N letters has a maximum variety bound of [math] N \choose {\lceil N/2 \rceil}[/math].[1] 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. [2]
- 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, ..., 2N-1) arising from the Fraenkel word FN, 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 am and bm, am ≠ 0.
- A congruence substitution involves replacing the kth occurrence of a fixed letter j in w with the kth letter of u, where u is a congruence word over a set of letters disjoint from that of w, for all positive integers k.
Generalizations
- If [math] \mathsf{block\_balance}(s) \leq m,[/math] then we say that s is m-block-balanced [idiosyncratic term ].
- 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 term ] 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.[3] (Compare 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.
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.
- ↑ Brauner, N., Crama, Y., Delaporte, E., Jost, V., & Libralesso, L. (2019). Do balanced words have a short period?. Theoretical Computer Science, 793, 169-180.
- ↑ Sano, S., Miyoshi, N., & Kataoka, R. (2004). m-Balanced words: A generalization of balanced words. Theoretical computer science, 314(1-2), 97-120.