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

- A

## 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}+ 1.^{[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.