Transcendence of Numbers whose Expansion in Base b or into Continued Fractions is ``Too Regular''

J.-P. Allouche

LRI, Université Paris-Sud

Algorithms Seminar

February 7, 2000

[summary by Philippe Flajolet]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

1   Normality and Transcendence

Émile Borel introduced the concept of normal numbers: a real is normal in base b if its expansion in this base contains each k-block a ``normal'' number of times, that is, with a frequency asymptotic to 1/bk. This concept of normality is closely related to the famous Borel--Cantelli lemma, a consequence of which is that almost all numbers (in a measure-theoretic sense) are normal [3]. Borel himself returned to the subject towards the end of his life and conducted detailed statistical studies [4] on the first two thousand digits of (2)1/2 as well as on other numbers like e or p. For instance the frequencies of appearance of 0--9 amongst the first 50 digits of the decimal representation of p,
p=3.14159 26535 89793 23846 26433 83279 50288 41971 69399 3751...
are respectively 1, 5, 5, 9, 4, 5, 4, 4, 5, 8, and irregularities tend to be much smoothed out when more digits are considered. Every mathematician believes that numbers like (2)1/2 or p are normal in any base. However, such conjectures, tested nowadays to billions of digits, seem well beyond the reach of current mathematical knowledge.

A similar notion of normality can be defined for continued fraction expansions. Every number has a continued fraction expansion, for instance,
(Hn-log n)=
  = / 1, 1, 2, 1, 2, 1, 4, 3, 13, 5, 1, 1, 8, 1, 2, 4, 1, 1, 40, 1, 11, 3, 7, 1, 7, 1, 1, 5, 1, 49, 4, 1, 65, .../.
The ``law of Gauss'' predicts the asymptotic frequency of digit k to be log2((k+1)2/(k(k+2)) for a random real number, say, uniform over (0,1); see [8, Sec. 4.5.3] for an agreeable introduction. Though it is observed numerically on extensive data that many classical constants like ([)1/23]2, p, or g obey the law of Gauss, proofs are currently not in sight. (E.g., it is not even known whether the continued fraction expansion of Euler's constant g terminates, i.e., whether the constant g is irrational).

Very roughly, two conjectures are believed by most to be true:
Conjecture 1   The base b expansion of any irrational algebraic number is normal.
Conjecture 2   The continued fraction expansion of any algebraic irrational number that is not a quadratic number is normal. In particular the continued fraction digits of any such number should be unbounded.
Given these conjectures, one may then expect the following: base expansions or continued fraction expansions that are in a sense ``too regular'' (hence fail to satisfy the strong normality condition) should determine transcendental numbers. The research described in this talk proceeds along these lines; see [1] to which we refer for an extensive bibliography.

Since transcendence of numbers is at stake it may be appropriate to start with a few basic facts; see Gel'fond's book [7] for a pleasant introduction. Liouville was the first in 1844 to observe that algebraic numbers are not well approximated by rationals: if a is algebraic of degree n, then the inequality (a one-liner),
,     C>0,     (1)
is satisfied for all integers pq with k=n. By the converse implication, a transcendence criterion results and, in particular, Liouville deduced that numbers with ``very sparse'' non-zero digits in some base representation, for instance,
must be transcendental. Thue, Siegel, and Roth in the twentieth century refined Liouville's estimate (1) by showing successively that one could take k>1/2n+1, k>2(n)1/2, and finally any k>2 (Roth, 1955); see the insightful description of the story in [2, Ch. 7]. Such improvements considerably enlarge the class of numbers recognized to be transcendental. For instance, the ``sparse'' number
ë bnû
,     b>1,
is now known to be transcendental (its nonzero digits are denser than those of h). These classical examples thus provide a first class of numbers with explicit base representations (but very sparse non-zero digits, though!) that are provably transcendental. They also entail that continued fraction whose digits grow ``too fast'' lead to transcendental numbers.

For base representations and for continued fraction expansions, transcendence thus becomes accessible to proof whenever one can derive rational approximations that are ``too good''. This will be the case, in connection with the results mentioned above, as soon as enough combinatorial regularities of sorts happen to be present in number representations.

2   Base Representations and Transcendence

In 1997, Ferenczi and Mauduit [5] proved the following:
Theorem 1   Assume that the base b representation of a is for each n of the form 0.UnVnVnV'n..., where V'n is a prefix of Vn, and the following length conditions are satisfied:
Then, the number a is transcendental.
This theorem states that a number is transcendental if its base representation contains ``near-cubes'' (VnVnV'n) that are ``not too far'' from the beginning and long enough (the length conditions). Roughly, such numbers turn out to be too well approximated by numbers that are ``close'' to b-adic rationals (i.e., rationals whose denominator is a power of b). They are proved to be transcendental by virtue of a theorem established by Ridout in 1957 (see [2, p. 68]) that constitutes a generalization of the Liouville and Roth theorems to the p-adic domain.1 Allouche [1] noticed that the methods of [5] give a bit more. First define the complexity of a sequence {un} of digits as the function k|® p(k) that counts the number of distinct blocks of length k appearing in the sequence. A normal number (in base b) certainly has p(k)=bk. Thus, we might expect in view of Conjecture 1 that any number with p(k)<bk is transcendental. A step in this direction is provided by the following theorem:
Theorem 2   Assume that p(k) is for k large enough dominated by a function of the form k+a. Then x is either rational or transcendental.
The proof relies on combinatorial properties of sequences of low complexity. The case is reduced by a suitable morphism2) to that of Sturmian sequences, that is, binary sequences such that p(k)=k+1. For these a suitable version of Theorem 1 can be applied.

Extending Theorem 2 to sequences of complexity p(k)=O(k) seems to be hard. Cases of special interest amongst sequences of complexity O(k) are those that are determined by iteration of morphisms3 that are ``simple enough''. For example:
  1. the Fibonacci sequence, i.e., the fixed point of the morphism 0|®01, 1|®0 that starts as
    0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1;
  2. the Thue--Morse sequence defined by the morphism 0|®01, 1|®10, that starts as
    0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1.
(Note: there seems to be gaps in technical results of Loxton and van der Poorten concerning the transcendence of automatic sequences.) Zamboni and Allouche proved recently:

Theorem 3   If the binary expansion of a real number is the fixed point of a morphism that is either ``primitive'' (e.g., the Fibonacci sequence) or of fixed length (e.g., the Thue--Morse sequence), then this number is either rational or transcendental.
There, the notion of primitivity is the one familiar from the theory of positive matrices and Markov chains [6].

3   Continued Fraction Expansions and Transcendence

Somewhat similar results have been established for continued fractions (abbreviated as CF) whose digits---one also says quotients---are too regular. Results here are due to Davison, Queffélec, Zamboni and Allouche. A special rôle is played in this context by quadratic irrationals whose CF expansion is eventually periodic. A theorem of Schmidt relates approximability by quadratic irrationals to transcendence. (It is in a sense the analogue of the refinements of Liouville's criterion.) Roughly, like what happens with base representations, too much combinatorial regularity is shown to imply transcendence.

We shall only quote here two typical results surveyed in [1] that are relative to CF digit sequences of complexities (k+1) and O(k).

Theorem 4  
  1. If the sequence of CF digits of a number a is a Sturmian sequence (i.e., a binary sequence of complexity k+1), then the number a is transcendental.
  2. Let q be irrational and let the sequence of CF digits of a number a be defined as
    an=1+ ( ë nqûmod 2 ) ,
    Then, the number a is transcendental.

Thus CF representations corresponding to digit sequences of low complexity produce transcendental numbers. This is supplemented by other results (see [1, 9]) implying for instance that the numbers (in CF representation) defined by any nontrivial rewriting of the Thue--Morse sequence is transcendental.


Allouche (Jean-Paul). -- Nouveaux résultats de transcendance de réels à développement non aléatoire. Gazette des Mathématiciens, n°84, 2000, pp. 19--34.

Baker (Alan). -- Transcendental number theory. -- Cambridge University Press, Cambridge, 1990, second edition, x+165p.

Billingsley (Patrick). -- Probability and measure. -- John Wiley & Sons Inc., New York, 1986, second edition, xiv+622p.

Borel (Émile). -- Sur les chiffres décimaux de (2)1/2 et divers problèmes de probabilités en chaîne. Comptes rendus de l'Académie des Sciences de Paris, vol. 230, 1950, pp. 591--593.

Ferenczi (Sébastien) and Mauduit (Christian). -- Transcendence of numbers with a low complexity expansion. Journal of Number Theory, vol. 67, n°2, 1997, pp. 146--161.

Gantmacher (F. R.). -- Matrizentheorie. -- VEB Deutscher Verlag der Wissenschaften, Berlin, 1986, 654p. Translated from the Russian original (1966) by Helmut Boseck, Dietmar Soyka and Klaus Stengert.

Gel'fond (A. O.). -- Transcendental and algebraic numbers. -- Dover Publications Inc., New York, 1960, vii+190p. Translated from the first Russian edition (1952) by Leo F. Boron.

Knuth (Donald E.). -- The art of computer programming. -- Addison-Wesley Publishing Co., Reading, Mass., 1997, third edition, xiv+762p. Volume 2: Seminumerical algorithms.

Queffélec (M.). -- Transcendance des fractions continues de Thue--Morse. Journal of Number Theory, vol. 73, n°2, 1998, pp. 201--211.

Ridout's theorem is: If a is an algebraic number and e>0 is arbitrary, then there exist only finitely many integers p, q comprised solely of a fixed set of primes such that |a-p/q|<q-e.
A morphism here is a substitution of letters by words.
Note that a general sequence defined by iteration of a morphism may have complexity of the order of k2.

This document was translated from LATEX by HEVEA.