On the Stern–Brocot expansion of real numbers
Christophe Reutenauer
Abstract
The Stern–Brocot expansion of a real number is a finite or infinite sequence of symbols <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo>,</mml:mo> <mml:mi>l</mml:mi> </mml:mrow> </mml:math> , meaning “right” and “left”, which represents the path in the Stern–Brocot tree determined by this number. It is shown that the expansion is periodic if and only if the number is positive quadratic with a negative conjugate; in this case the conjugate opposite’s expansion is obtained by reversal. The slopes of morphic Sturmian sequences are these quadratic numbers. Two numbers have ultimately the same exapansion if and only they are <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi mathvariant="normal">SL</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>ℤ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> -equivalent. A related neighbouring relation for indefinite binary quadratic forms leads to a variant of the Gauss theory of cycles. A bijection is obtained between the set of binary Lyndon words and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi mathvariant="normal">SL</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>ℤ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> -equivalence of these quadratic forms.