Balanced word

A word or necklace s is balanced if its block balance^{[idiosyncratic term]} satisfies the following:

[math]\displaystyle{ \mathsf{block\_balance}(s) := \max \big\{ \big| |w|_{a} - |w'|_{a} \big| : a \text{ is a letter of }s\text{ and }k = \operatorname{len}(w) = \operatorname{len}(w') \big\} \leq 1, }[/math]

where |u|_a is the number of occurrences of the letter a in the word u.

Properties

• A balanced word or necklace on N letters has a maximum variety bound of [math]\displaystyle{ N \choose {\lceil N/2 \rceil} }[/math].
• 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.
• 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]\displaystyle{ 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.

Generalizations

1. If [math]\displaystyle{ \mathsf{block\_balance}(s) \leq m, }[/math] then we say that s is m-block-balanced^{[idiosyncratic term]}.
2. The following stronger property implies but is not equivalent to m-block-balancedness: 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.