# 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

$\mathsf{block\_balance}(s, a) := \max \big\{ \big| |w|_{a} - |w'|_{a} \big| : |w| = |w'| \big\},$

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:

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

## Properties

• A balanced word or necklace on N letters has a maximum variety bound of $N \choose {\lceil N/2 \rceil}$.[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 $F_1 = \mathbf{0}, F_n = F_{n-1} \mathbf{(n-1)} F_{n-1}.$ 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 $\{a_m n + b_m : n \in \mathbb{N}\},$ 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

1. If $\mathsf{block\_balance}(s) \leq m,$ then we say that s is m-block-balanced[idiosyncratic term].
2. 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

1. 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.
2. Brauner, N., Crama, Y., Delaporte, E., Jost, V., & Libralesso, L. (2019). Do balanced words have a short period?. Theoretical Computer Science, 793, 169-180.
3. Sano, S., Miyoshi, N., & Kataoka, R. (2004). m-Balanced words: A generalization of balanced words. Theoretical computer science, 314(1-2), 97-120.