Journal of Integer Sequences, Vol. 16 (2013), Article 13.9.7

On a Class of Lyndon Words Extending Christoffel Words and Related to a Multidimensional Continued Fraction Algorithm

Guy Melançon
Université de Bordeaux
351, cours de la Libération
33405 Talence

Christophe Reutenauer
Département de Mathématiques
Case Postale 8888, Succ. Centre-ville
Montréal, Québec H3C 3P8


We define a class of Lyndon words, called Christoffel-Lyndon words. We show that they are in bijection with n-tuples of relatively prime natural numbers. We give a geometrical interpretation of these words. They are linked to an algorithm of Euclidean type. It admits an extension to n-tuples of real numbers; we show that if the algorithm is periodic, then these real numbers are algebraic of degree at most n and that the associated multidimensional continued fraction converges to these numbers.

Full version:  pdf,    dvi,    ps,    latex    

Received March 26 2013; revised version received November 15 2013. Published in Journal of Integer Sequences, November 17 2013.

Return to Journal of Integer Sequences home page