Transcendence of numbers with a low complexity expansion. (English) Zbl 0895.11029

The (block-) complexity of a sequence on a finite alphabet is the function \(n\to p(n)\), where \(p(n)\) counts the number of (different) blocks of length \(n\) occurring in the sequence. A small step towards the conjecture that any algebraic irrational number is normal in base \(k\) (hence contains all possible blocks in its base \(k\) expansion) would be to prove that, if too many blocks are missing (i.e., \(p(n)\) is small), then the number is either rational or transcendental. Let us call \(C\) the set of sequences on a given alphabet \(\{0,1,\dots, k-1\}\) having low complexity, and such that the corresponding real numbers in base \(k\) are either rational or transcendental. For automatic sequences, we have \(p(n)= O(n)\) and results of Loxton and van der Poorten seem to indicate that these sequences are in \(C\).
In the paper under review the authors translate in combinatorial terms Ridout’s theorem; they obtain a combinatorial criterion of transcendence that implies: Sturmian sequences (i.e., sequences of complexity \(n+k-1\) on the alphabet \(\{0,1,\dots, k-1\}\)) are in \(C\) (this was known only for subclasses); Arnoux-Rauzy sequences are in \(C\) (these sequences have complexity \(2n+1)\); fixed points with overlaps of primitive morphisms are in \(C\). This last result has been extended in the binary case by Luca Q. Zamboni (misspelled in the paper under review) and the reviewer to any fixed point of a binary morphism primitive or of constant length and non-trivial [J.-P. Allouche and L. Q. Zamboni, J. Number Theory 69, No. 1, 119–124 (1998; Zbl 0918.11016)].


11J81 Transcendence (general theory)
11B85 Automata sequences


Zbl 0918.11016
Full Text: DOI


[1] Adams, W. W.; Davison, J. L., A remarkable class of continued fractions, Proc. Amer. Math. Soc., 65, 194-198 (1977) · Zbl 0366.10027
[5] Arnoux, P.; Rauzy, G., Représentation géométrique de suites de complexité \(2n\), Bull. Soc. Math. France, 119, 199-215 (1991) · Zbl 0789.28011
[6] Berstel, J.; Séébold, P., A characterization of overlap-free morphisms, Disc. Appl. Math., 46, 275-281 (1993) · Zbl 0824.68093
[7] Bullett, S.; Sentenac, P., Ordered orbits of the shift, square roots, and the devil’s staircase, Math. Proc. Camb. Phil. Soc., 115, 451-481 (1994) · Zbl 0823.58012
[8] Cobham, A., Uniform tag sequences, Math. Systems Theory, 6, 164-192 (1972) · Zbl 0253.02029
[9] Davison, J. L., A series and its associated continued fraction, Proc. Amer. Math. Soc., 63, 29-32 (1977) · Zbl 0326.10030
[10] Dekking, M., Transcendance du nombre de Thue-Morse, C. R. Acad. Sci. Paris Sér. A-B, 285, A157-A160 (1977)
[11] Ehrenfeucht, A.; Lee, K. P.; Rozenberg, G., Subword complexities of various classes of deterministic developmental languages without interactions, Theoret. Comput. Sci., 1, 59-75 (1975) · Zbl 0316.68043
[12] Ferenczi, S., Les transformations de Chacon: combinatoire, structure géométrique, liens avec les systèmes de complexité \(2n\), Bull. Soc. Math. France, 123, 271-292 (1995) · Zbl 0855.28008
[13] Hedlund, G. A.; Morse, M., Symbolic dynamics II: Sturmian trajectories, Amer. J. Math., 62, 1-42 (1940) · JFM 66.0188.03
[14] Komatsu, T., A certain power series and the inhomogeneous continued fraction expansions, J. Number Theory, 59, 291-312 (1996) · Zbl 0872.11033
[15] Loxton, J. H.; van der Poorten, A. J., Arithmetic properties of automata: regular sequences, J. Reine Angew. Math., 392, 57-69 (1988) · Zbl 0656.10033
[17] Nishioka, K.; Tamura, J.-i.; Shiokawa, I., Arithmetical properties of a certain power series, J. Number Theory, 42, 61-87 (1992) · Zbl 0770.11039
[18] Ostrowski, A., Bemerkungen zur Theorie der Diophantischen Approximationen I, II, Abh. Math. Sem. Hamburg, 1 (1922) · JFM 48.0185.01
[19] Pansiot, J.-J., Complexité des facteurs des mots infinis enegendrés par morphismes itérés, ICALP ’84. ICALP ’84, Lecture Notes in Computer Science, 172 (1984), Springer-Verlag: Springer-Verlag New York/Berlin, p. 380-389 · Zbl 0554.68053
[20] Queffélec, M., Substitution Dynamical Systems-Spectral Analysis. Substitution Dynamical Systems-Spectral Analysis, Lecture Notes in Math., 1294 (1987), Springer-Verlag: Springer-Verlag New York/Berlin · Zbl 0642.28013
[21] Tamura, J.-i., A class of transcendental numbers having explicit \(g\), Acta. Arith., 71, 301-329 (1995) · Zbl 0828.11036
[22] Thue, A., Über die gegenseite Lage gleiche Teile gewisser Zeichenreihen, Norske vi. Selsk. Skr. Mat. Nat. Kl., 1, 1-67 (1912)
[23] Zhu, Y., The algebraic independence of certain transcendental continued fractions, Acta. Math. Sin., 2, 127-134 (1991) · Zbl 0736.11035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.