Morse-Hedlund Theorem

The Morse-Hedlund theorem states that a right-infinite word is ultimately periodic if and only if its factor complexity satisfies

for some positive integer . A bi-infinite word is periodic if and only if the same inequality holds for some .

Equivalently, every aperiodic right-infinite or bi-infinite word satisfies for every positive integer . This lower bound is sharp: the aperiodic binary words satisfying for all are precisely the Sturmian sequences.