Sturmian word

In mathematics, a Sturmian word (Sturmian sequence or billiard sequence), named after Jacques Charles François Sturm, is a certain kind of infinitely long sequence of characters. Such a sequence can be generated by considering a game of English billiards on a square table. The struck ball will successively hit the vertical and horizontal edges labelled 0 and 1 generating a sequence of letters. This sequence is a Sturmian word.

Sturmian sequences can be defined strictly in terms of their combinatoric properties or geometrically as cutting sequences for lines of irrational slope or codings for irrational rotations. They are traditionally taken to be infinite sequences on the alphabet of the two symbols 0 and 1.

For an infinite sequence of symbols w, let σ(n) be the complexity function of w; i.e., σ(n) = the number of distinct subwords in w of length n. w is Sturmian if σ(n)=n+1 for all n.

A set X of binary strings is called balanced if the Hamming weight of elements of X takes at most two distinct values. That is, for any ${\displaystyle s\in X}$ |s|₁=k or |s|₁=k' where |s|₁ is the number of 1s in s.

Let w be an infinite sequence of 0s and 1s and let ${\displaystyle {\mathcal {L}}_{n}(w)}$ denote the set of all length-n subwords of w. The sequence w is Sturmian if ${\displaystyle {\mathcal {L}}_{n}(w)}$ is balanced for all n and w is not eventually periodic.

...
Wikipedia