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,
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,
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),
½ ½ ½ ½
a-
p
q
½ ½ ½ ½
>
C
q
k
, C>0,
(1)
is satisfied for all integers p, q 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,
h:=
¥
å
n=0
1
10n!
,
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
x:=
¥
å
n=0
1
10
ë 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:
|Vn|®¥;
liminf
n®¥
|V'n|
|Vn|
>0;
limsup
n®¥
|Un|
|Vn|
<¥.
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:
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;
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
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.
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.
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.
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.