On the Stern–Brocot expansion of real numbers
Journal de Théorie des Nombres de Bordeaux, Tome 31 (2019) no. 3, pp. 697-722.

Le développement de Stern–Brocot d’un nombre réel est une suite finie ou infinie de symboles l,r, signifiant « gauche » et « droite », qui représente le chemin dans l’arbre de Stern–Brocot déterminé par ce nombre. On montre que ce développement est périodique si et seulement si le nombre est quadratique, positif, avec conjugué négatif ; dans ce cas la représentation de l’opposé du conjugué est obtenue par image miroir. Les pentes des suites sturmiennes morphiques sont exactement ces nombres. Deux nombres ont le même développement à partir d’un certain rang si et seulement s’ils sont équivalents sous l’action de SL 2 (). On obtient une relation d’adjacence pour les formes quadratiques binaires indéfinies, qui mène à un variante de la théorie des cycles de Gauss. Une bijection entre l’ensemble des mots de Lyndon sur deux lettres et les classes d’équivalence de ces formes est obtenue.

The Stern–Brocot expansion of a real number is a finite or infinite sequence of symbols r,l, 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 SL 2 ()-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 SL 2 ()-equivalence of these quadratic forms.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : https://doi.org/10.5802/jtnb.1104
Classification : 11E16,  11A55
Mots clés : Stern–Brocot tree, continued fractions, quadratic forms, quadratic numbers, Sturmian sequences
@article{JTNB_2019__31_3_697_0,
     author = {Reutenauer, Christophe},
     title = {On the {Stern{\textendash}Brocot} expansion of real numbers},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {697--722},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {31},
     number = {3},
     year = {2019},
     doi = {10.5802/jtnb.1104},
     language = {en},
     url = {http://archive.numdam.org/articles/10.5802/jtnb.1104/}
}
TY  - JOUR
AU  - Reutenauer, Christophe
TI  - On the Stern–Brocot expansion of real numbers
JO  - Journal de Théorie des Nombres de Bordeaux
PY  - 2019
DA  - 2019///
SP  - 697
EP  - 722
VL  - 31
IS  - 3
PB  - Société Arithmétique de Bordeaux
UR  - http://archive.numdam.org/articles/10.5802/jtnb.1104/
UR  - https://doi.org/10.5802/jtnb.1104
DO  - 10.5802/jtnb.1104
LA  - en
ID  - JTNB_2019__31_3_697_0
ER  - 
Reutenauer, Christophe. On the Stern–Brocot expansion of real numbers. Journal de Théorie des Nombres de Bordeaux, Tome 31 (2019) no. 3, pp. 697-722. doi : 10.5802/jtnb.1104. http://archive.numdam.org/articles/10.5802/jtnb.1104/

[1] Aigner, Martin Markov’s Theorem and 100 years of the Uniqueness Conjecture, a mathematical journey from irrational numbers to perfect matchings, Springer, 2013 | Zbl 1276.0006

[2] Allauzen, Cyril Une caractérisation simple des nombres de Sturm, J. Théor. Nombres Bordeaux, Volume 10 (1998) no. 2, pp. 237-241 | Article | Numdam | Zbl 0930.11051

[3] Allouche, Jean-Paul; Shallit, Jeffrey Automatic sequences. Theory, applications, generalizations, Cambridge University Press, 2003 | Zbl 1086.11015

[4] Berstel, Jean; Séébold, Patrice Morphismes de Sturm, Bull. Belg. Math. Soc. Simon Stevin, Volume 1 (1994) no. 2, pp. 175-189 | Article | MR 1318967 | Zbl 0803.68095

[5] Borel, Jean-Pierre Image par homographie de mots de Christoffel, Bull. Belg. Math. Soc. Simon Stevin, Volume 8 (2001) no. 2, pp. 241-255 | Article | MR 1838932 | Zbl 0994.68101

[6] Borel, Jean-Pierre; Laubie, François Quelques mots sur la droite projective réelle, J. Théor. Nombres Bordeaux, Volume 5 (1993) no. 1, pp. 23-51 | Article | Numdam | Zbl 0839.11008

[7] Brown, Thomas C A characterization of the quadratic irrationals, Can. Math. Bull., Volume 34 (1991) no. 1, pp. 36-41 | Article | MR 1108926 | Zbl 0688.10007

[8] Buell, Duncan A. Binary quadratic forms. Classical theory and modern computations, Springer, 1989 | Zbl 0698.10013

[9] Christoffel, Elwin B. Lehrsätze über arithmetische Eigenschaften der Irrationalzahlen, Annali di Mat., Volume XV (1887), pp. 253-276 | Article | Zbl 20.0068.01

[10] Crisp, David; Moran, William; Pollington, Andrew; Shiue, Peter Substitution invariant cutting sequences, J. Théor. Nombres Bordeaux, Volume 5 (1993) no. 1, pp. 123-137 | Article | Numdam | MR 1251232 | Zbl 0786.11041

[11] Dickson, Leonard E. Introduction to the theory of numbers, Dover Publications, 1957 | Zbl 0084.26901

[12] Droubay, Xavier; Justin, Jacques; Pirillo, Giuseppe Episturmian words and some contructions of de Luca and Rauzy, Theor. Comput. Sci., Volume 255 (2001) no. 1-2, pp. 539-553 | Article | Zbl 0981.68126

[13] Fatou, Pierre Sur l’approximation des incommensurables et les séries trigonométriques, C. R. Math. Acad. Sci. Paris, Volume 139 (1904), pp. 1019-1021 | Zbl 35.0275.02

[14] Substitutions in Dynamics, Arithmetics and Combinatorics (Fogg, N. Pytheas; Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A., eds.), Lecture Notes in Mathematics, 1794, Springer, 2002 | MR 1970385 | Zbl 1014.11015

[15] Grace, John H. The classification of rational approximations, Proc. Lond. Math. Soc., Volume 17 (1918), pp. 247-258 | Article | MR 1575573

[16] Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren Concrete mathematics, Addison-Wesley Publishing Group, 1994 | Zbl 0836.00001

[17] Hurwitz, Adolf Ueber die angenäherte Darstellung der Zahlen durch rationale Brüche, Math. Ann., Volume 44 (1894), pp. 417-436 | Article | Zbl 25.0322.04

[18] Hurwitz, Adolf Ueber die Reduction der binären quadratischen Formen, Math. Ann., Volume 45 (1894), pp. 85-117 | Article | Zbl 25.0313.01

[19] Ito, Shunji; Yasutomi, Shin-ichi On continued fractions, substitutions and characteristic sequences [nx+y]-[(n-1)x+y], Jap. J. Math., Volume 16 (1990), pp. 287-306 | MR 1091163 | Zbl 0721.11009

[20] Justin, Jacques; Pirillo, Giuseppe Episturmian words and episturmian morphisms, Theor. Comput. Sci., Volume 276 (2002) no. 1-2, pp. 281-313 | Article | MR 1896357 | Zbl 1002.68116

[21] Komatsu, Takao; van der Poorten, Alfred J. Substitution invariant Beatty sequences, Jap. J. Math., Volume 22 (1996) no. 2, pp. 349-354 | Article | MR 1432380 | Zbl 0868.11015

[22] Lothaire, M. Algebraic combinatorics on words, Encyclopedia of Mathematics and Its Applications, 90, Cambridge University Press, 2002 | MR 1905123 | Zbl 1001.68093

[23] Morse, Marston; Hedlund, Gustav A. Symbolic dynamics II: Sturmian Trajectories, Am. J. Math., Volume 62 (1940), pp. 1-42 | Article | MR 745 | Zbl 0022.34003

[24] Niqui, Milad Exact arithmetic on the Stern–Brocot tree, J. Discrete Algorithms, Volume 5 (2007) no. 2, pp. 356-379 | Article | MR 2317038 | Zbl 1127.68029

[25] Parvaix, Bruno Propriétés d’invariance des mots sturmiens, J. Théor. Nombres Bordeaux, Volume 9 (1997) no. 2, pp. 351-369 | Article | MR 1617403 | Zbl 0904.11008

[26] Raney, George N. On continued fractions and finite automata, Math. Ann., Volume 206 (1973), pp. 265-283 | Article | MR 340166 | Zbl 0251.10024

[27] Séébold, Patrice Sturmian images of non Sturmian words and standard morphisms, Theor. Comput. Sci., Volume 711 (2018), pp. 92-104 | Article | MR 3778827 | Zbl 1393.68145

[28] Serret, Joseph-Alfred Cours d’algèbre supérieure. I., éditions Jacques Gabay, 1992 | MR 1190472 | Zbl 17.0053.01

[29] Uludaǧ, A. Muhammed; Zeytin, Ayberk; Durmuş, Merve Binary quadratic forms as dessins, J. Théor. Nombres Bordeaux, Volume 29 (2017) no. 2, pp. 445-469 | Article | MR 3682475 | Zbl 1420.11096

[30] Zagier, Don B. Zetafunktionen und quadratische Körper, Eine Einführung in die Zahlentheorie, Springer, 1981 | Zbl 0459.10001

Cité par Sources :