Annals of Mathematics, 165 (2007), 547–565

On the complexity of algebraic numbers I.
Expansions in integer bases
By Boris Adamczewski and Yann Bugeaud

Abstract
Let b ≥ 2 be an integer. We prove that the b-ary expansion of every
irrational algebraic number cannot have low complexity. Furthermore, we establish that irrational morphic numbers are transcendental, for a wide classof morphisms. In particular, irrational automatic numbers are transcendental.
Our main tool is a new, combinatorial transcendence criterion.
1. Introduction
Let b ≥ 2 be an integer. The b-ary expansion of every rational number
is eventually periodic, but what can be said about the b-ary expansion of an
irrational algebraic number? This question was addressed for the ﬁrst timeby Émile Borel [11], who made the conjecture that such an expansion should
satisfy some of the same laws as do almost all real numbers. In particular, it
is expected that every irrational algebraic number is normal in base b. Recall
that a real number θ is called normal in base b if, for any positive integer n,each one of the bn blocks of length n on the alphabet {0, 1, . . . , b − 1} occurs
in the b-ary expansion of θ with the same frequency 1/bn . This conjecture is
reputed to be out of reach: we even do not√know whether the digit 7 occurs
inﬁnitely often in the decimal expansion of 2. However, some (very) partial
results have been established.
As usual, we measure the complexity of an inﬁnite word u = u1 u2 . . .
deﬁned on a ﬁnite alphabet by counting the number p(n) of distinct blocks oflength n occurring in the word u. In particular, the b-ary expansion of every
real number normal in base b satisﬁes p(n) = bn for any positive integer n. Using a clever reformulation of a theorem of Ridout [33], Ferenczi and Mauduit[20] established the transcendence of the real numbers whose b-ary expansion
is a non eventually periodic sequence of minimal complexity, that is, which
satisﬁes p(n) = n + 1 for every n ≥ 1 (such a sequence is called a Sturmian
sequence, see the seminal papers by Morse and Hedlund [28], [29]). The combinatorial criterion given in [20] has been used subsequently to exhibit further

548

BORIS ADAMCZEWSKI AND YANN BUGEAUD

examples of transcendental numbers with low complexity [3], [6], [4], [34]. It
also implies that the complexity of the b-ary expansion of every irrational algebraic number satisﬁes lim inf n→∞ (p(n) − n) = +∞. Although this is very
far away from what is expected, no better result is known.
In 1965, Hartmanis and Stearns [21] proposed an alternative approachfor the notion of complexity of real numbers, by emphasizing the quantitative
aspect of the notion of calculability introduced by Turing [42]. According tothem, a real number is said to be computable in time T (n) if there exists
a multitape Turing machine which gives the ﬁrst n-th terms of its binary
expansion in (at most) T (n) operations. The ‘simpler’ real numbers in thatsense, that is, the numbers for which one can choose T (n) = O(n), are said tobe computable in real time. Rational numbers share clearly this property. The
problem of Hartmanis and Stearns, to which a negative answer is expected, isthe following: do there exist irrational algebraic numbers which are computablein real time? In 1968, Cobham [14] suggested to restrict this problem to aparticular class of Turing machines, namely to the case of ﬁnite automata (seeSection 3 for a deﬁnition). After several attempts by Cobham [14] in 1968 andby Loxton and van der Poorten [23] in 1982, Loxton and van der Poorten [24]ﬁnally claimed to have completely solved the restricted problem in 1988. Moreprecisely, they asserted that the b-ary expansion of every irrational algebraic
number cannot be generated by a ﬁnite automaton. The proof proposed in[24], which rests on a method introduced by Mahler [25], [26], [27], contains
unfortunately a rather serious gap, as explained by Becker [8] (see also [43]).
Furthermore, the combinatorial criterion established in [20] is too weak to
imply this statement, often referred to as the Cobham-Loxton-van der Poorten
conjecture.
In the present paper, we prove new results concerning both notions of complexity. Our Theorem 1 provides a sharper lower estimate for the complexityof the b-ary expansion of every irrational algebraic number. We are still far
away from proving that such an expansion is normal, but we considerably improve upon the earlier known results. We further establish (Theorem 2) the
Cobham-Loxton-van der Poorten conjecture, namely that irrational automatic
numbers are transcendental. Our proof yields more general statements andallows us to conﬁrm that irrational morphic numbers are transcendental, for awide class of morphisms (Theorems 3 and 4).
We derive Theorems 1 to 4 from a reﬁnement (Theorem 5) of the combinatorial criterion from [20], that we obtain as a consequence of the Schmidt
Subspace Theorem.
Throughout the present paper, we adopt the following convention. We
use small letters (a, u, etc.) to denote letters from some ﬁnite alphabet A. We
use capital letters (U , V , W , etc.) to denote ﬁnite words. We use bold small
letters (a, u, etc.) to denote inﬁnite sequences of letters. We often identify

ON THE COMPLEXITY OF ALGEBRAIC NUMBERS I

549

the sequence a = (ak )k≥1 with the inﬁnite word a1 a2 . . . , also called a. Thisshould not cause any confusion.
Our paper is organized as follows. The main results are stated in Section 2 and proved in Section 5. Some deﬁnitions from automata theory andcombinatorics on words are recalled in Section 3. Section 4 is devoted to the
new transcendence criterion and its proof. Finally, we show in Section 6 thatthe Hensel expansion of every irrational algebraic p-adic number cannot havea low complexity, and we conclude in Section 7 by miscellaneous remarks.
Some of the results of the present paper were announced in [2].
Acknowledgements. We would like to thank Guy Barat and Florian Lucafor their useful comments. The ﬁrst author is also most grateful to Jean-PaulAllouche and Valérie Berthé for their constant support.
2. Main results
As mentioned in the ﬁrst part of the Introduction, we measure the complexity of a real number written in some integral base b ≥ 2 by counting, forany positive integer n, the number p(n) of distinct blocks of n digits (on thealphabet {0, 1, . . . , b − 1}) occurring in its b-ary expansion. The function p is
commonly called the complexity function. It follows from results of Ferenczi
and Mauduit [20] (see also [4, Th. 3]) that the complexity function p of every
irrational algebraic number satisﬁes
lim inf (p(n) − n) = +∞.

(1)

n→∞

As far as we are aware, no better result is known, although it has been proved[3], [6], [34] that some special real numbers with linear complexity are transcendental.
Our ﬁrst result is a considerable improvement of (1).
Theorem 1. Let b ≥ 2 be an integer. The complexity function of theb-ary expansion of every irrational algebraic number satisﬁes
lim inf
n→∞

p(n)
= +∞.
n

It immediately follows from Theorem 1 that every irrational real number
with sub-linear complexity (i.e., such that p(n) = O(n)) is transcendental.
However, Theorem 1 is slightly sharper, as is illustrated by an example due toFerenczi [19]: he established the existence of a sequence on a ﬁnite alphabet
whose complexity function p satisﬁes
lim inf
n→∞

p(n)
=2
n

and

lim supn→∞p(n)= +∞ for any t > 1.
nt

550

BORIS ADAMCZEWSKI AND YANN BUGEAUD

Most of the previous attempts towards a proof of the Cobham-Loxtonvan der Poorten conjecture have been made via the Mahler method [23],[24], [8], [31]. We stress that Becker [8] established that, for any given noneventually periodic automatic sequence u = u1 u2 . . . , the real number−k is transcendental, provided that the integer b is suﬃciently largek≥1 uk b(in terms of u). Since the complexity function p of any automatic sequencesatisﬁes p(n) = O(n) (see Cobham [15]), Theorem 1 conﬁrms straightforwardly
this conjecture.
Theorem 2. Let b ≥ 2 be an integer. The b-ary expansion of any irrational algebraic number cannot be generated by a ﬁnite automaton. In otherwords, irrational automatic numbers are transcendental.
Although Theorem 2 is a direct consequence of Theorem 1, we give in
Section 5 a short proof of it, that rests on another result of Cobham [15].
Theorem 2 establishes a particular case of the following widely believed
conjecture (see e.g. [5]). The deﬁnitions of morphism, recurrent morphism,and morphic number are recalled in Section 3.
Conjecture. Irrational morphic numbers are transcendental.
Our method allows us to conﬁrm this conjecture for a wide class of morphisms.
Theorem 3. Binary algebraic irrational numbers cannot be generated bya morphism.
As observed by Allouche and Zamboni [6], it follows from [20] combinedwith a result of Berstel and Séébold [9] that binary irrational numbers which
are ﬁxed point of a primitive morphism or of a morphism of constant length≥ 2 are transcendental. Our Theorem 3 is much more general.
Recently, by a totally diﬀerent method, Bailey, Borwein, Crandall, andPomerance [7] established new, interesting results on the density of the digits
in the binary expansion of algebraic numbers.
For b-ary expansions with b ≥ 3, we obtain a similar result as in Theorem 3, but an additional assumption is needed.
Theorem 4. Let b ≥ 3 be an integer. The b-ary expansion of an algebraic
irrational number cannot be generated by a recurrent morphism.
Unfortunately, we are unable to prove that ternary algebraic numbers
cannot be generated by a morphism. Consider for instance the ﬁxed point
u = 01212212221222212222212222221222 . . .
of the morphism deﬁned by 0 → 012, 1 → 12, 2 → 2, and set α =uk 3−k .

k≥1

Our method does not apply to show the transcendence of α. Let us mention

ON THE COMPLEXITY OF ALGEBRAIC NUMBERS I

551

that this α is known to be transcendental: this is a consequence of deep transcendence results proved in [10] and in [17], concerning the values of theta
series at algebraic points.
The proofs of Theorems 1 to 4 are given in Section 5. The key point
for them is a new transcendence criterion, derived from the Schmidt Subspace
Theorem, and stated in Section 4. Actually, we are able to deal also, undersome conditions, with non-integer bases (see Theorems 5 and 5A). Given a real
number β > 1, we can expand in base β every real number ξ in (0, 1) thanks to
the greedy algorithm: we then get the β-expansion of ξ, introduced by Rényi[32]. Using Theorem 5, we easily see that the conclusions of Theorems 1 to 4
remain true with the expansion in base b replaced by the β-expansion when β
is a Pisot or a Salem number. Recall that a Pisot (resp. Salem) number is areal algebraic integer > 1, whose complex conjugates lie inside the open unit
disc (resp. inside the closed unit disc, with at least one of them on the unit
circle). In particular, any integer b ≥ 2 is a Pisot number. For instance, we
get the following result.
Theorem 1A.Let β > 1 be a Pisot or a Salem number. The complexity
function of the β-expansion of every algebraic number in (0, 1) \ Q(β) satisﬁes
lim inf
n→∞

p(n)
= +∞.
n

Likewise, we can also state Theorems 2A, 3A, and 4A accordingly: Theorems 1 to 4 deal with algebraic irrational numbers, while Theorems 1A to
4A deal with algebraic numbers in (0, 1) which do not lie in the number ﬁeld
generated by β.
Moreover, our method also allows us to prove that p-adic irrational numbers whose Hensel expansions have low complexity are transcendental; see
Section 6.
3. Finite automata and morphic sequences
In this section, we gather classical deﬁnitions from automata theory andcombinatorics on words.
Finite automata and automatic sequences.
Let k be an integer withk ≥ 2. We denote by Σk the set {0, 1, . . . , k − 1}. A k-automaton is deﬁned
as a 6-tupleA = (Q, Σk , δ, q0 , ∆, τ ) ,where Q is a ﬁnite set of states, Σk is the input alphabet, δ : Q × Σk → Q
is the transition function, q0 is the initial state, ∆ is the output alphabet andτ : Q → ∆ is the output function.

552

BORIS ADAMCZEWSKI AND YANN BUGEAUD

For a state q in Q and for a ﬁnite word W = w1 w2 . . . wn on the alphabet
Σk , we deﬁne recursively δ(q, W ) by δ(q, W ) = δ(δ(q, w1 w2 . . . wn−1 ), wn ). Letn ≥ 0 be an integer and let wr wr−1 . . . w1 w0 in (Σk )r be the k-ary expansionr
of n; thus, n =wi k i . We denote by Wn the word w0 w1 . . . wr . Then, ai=0sequence a = (an )n≥0 is said to be k-automatic if there exists a k-automaton
A such that an = τ (δ(q0 , Wn )) for all n ≥ 0.
A classical example of a 2-automatic sequence is given by the binary ThueMorse sequence a = (an )n≥0 = 0110100110010 . . . This sequence is deﬁned asfollows: an is equal to 0 (resp. to 1) if the sum of the digits in the binary
expansion of n is even (resp. is odd). It is easy to check that this sequence canbe generated by the 2-automaton
A = {q0 , q1 }, {0, 1}, δ, q0 , {0, 1}, τ ,whereδ(q0 , 0) = δ(q1 , 1) = q0 ,δ(q0 , 1) = δ(q1 , 0) = q1 ,and τ (q0 ) = 0, τ (q1 ) = 1.
Morphisms. For a ﬁnite set A, we denote by A∗ the free monoid generated
by A. The empty word ε is the neutral element of A∗ . Let A and B be two
ﬁnite sets. An application from A to B ∗ can be uniquely extended to anhomomorphism between the free monoids A∗ and B ∗ . We call morphism from
A to B such an homomorphism.
Sequences generated by a morphism. A morphism φ from A into itself issaid to be prolongable if there exists a letter a such that φ(a) = aW , where
W is a non-empty word such that φk (W ) = ε for every k ≥ 0. In that case,the sequence of ﬁnite words (φk (a))k≥1 converges in AN (endowed with the
product topology of the discrete topology on each copy of A) to an inﬁnite
word a. This inﬁnite word is clearly a ﬁxed point for φ and we say that a isgenerated by the morphism φ. If, moreover, every letter occurring in a occurs
at least twice, then we say that a is generated by a recurrent morphism. If
the alphabet A has two letters, then we say that a is generated by a binary
morphism. More generally, an inﬁnite sequence a in AN is said to be morphic
if there exist a sequence u generated by a morphism deﬁned over an alphabet
B and a morphism from B to A such that a = φ(u).
For instance, the Fibonacci morphism σ deﬁned from the alphabet {0, 1}
into itself by σ(0) = 01 and σ(1) = 0 is a binary, recurrent morphism which
generates the Fibonacci inﬁnite worda = lim σ n (0) = 010010100100101001 . . .
n→∞

ON THE COMPLEXITY OF ALGEBRAIC NUMBERS I

553This inﬁnite word is an example of a Sturmian sequence and its complexity
function satisﬁes thus p(n) = n + 1 for every positive integer n.
Automatic and morphic real numbers.
Following the previous deﬁnitions, we say that a real number α is automatic (respectively, generated by amorphism, generated by a recurrent morphism, or morphic) if there exists an
integer b ≥ 2 such that the b-ary expansion of α is automatic (respectively,
generated by a morphism, generated by a recurrent morphism, or morphic).
A classical example of binary automatic number is given by
 1
n≥1

22 n

which is transcendental, as proved by Kempner [22].
4. A transcendence criterion for stammering sequences
First, we need to introduce some notation. Let A be a ﬁnite set. The
length of a word W on the alphabet A, that is, the number of letters composing
W , is denoted by |W |. For any positive integer , we write W  for the word
W . . . W ( times repeated concatenation of the word W ). More generally, forany positive real number x, we denote by W x the word W x W  , where W  isthe preﬁx of W of length (x − x)|W | . Here, and in all what follows, yand y denote, respectively, the integer part and the upper integer part of thereal number y. Let a = (ak )k≥1 be a sequence of elements from A, that we
identify with the inﬁnite word a1 a2 . . . Let w > 1 be a real number. We saythat a satisﬁes Condition (∗)w if a is not eventually periodic and if there exist
two sequences of ﬁnite words (Un )n≥1 , (Vn )n≥1 such that:(i) For any n ≥ 1, the word Un Vnw is a preﬁx of the word a;(ii) The sequence (|Un |/|Vn |)n≥1 is bounded from above;(iii) The sequence (|Vn |)n≥1 is increasing.
As suggested to us by Guy Barat, a sequence satisfying Condition (∗)w
for some w > 1 may be called a stammering sequence.
Theorem 5. Let β > 1 be a Pisot or a Salem number. Let a = (ak )k≥1
be a bounded sequence of rational integers. If there exists a real number w > 1
such that a satisﬁes Condition (∗)w , then the real number
α :=

+∞

ak
k=1

βk

554

BORIS ADAMCZEWSKI AND YANN BUGEAUD

either belongs to Q(β), or is transcendental.
The proof of Theorem 5 rests on the Schmidt Subspace Theorem [39] (seealso [40]), and more precisely on a p-adic generalization due to Schlickewei [36],[37] and Evertse [18]. The particular case when β is an integer ≥ 2 was provedin [2]. Note that Adamczewski [1] and Corvaja and Zannier [16] proved that,
under a stronger assumption on the sequence (ak )k≥1 , the number α deﬁned
in the statement of Theorem 5 is transcendental. Note also that Troi andZannier [41] applied the Subspace Theorem on the same way as we do to prove
the transcendence of a particular real number.
Remarks.
• Theorem 5 is considerably stronger than the criterion ofFerenczi and Mauduit [20]: our assumption w > 1 replaces their assumption
w > 2. This type of condition is rather ﬂexible, compared with the Mahler
method, for which a functional equation is needed. For instance, the conclusionof Theorem 5 also holds if the sequence a is an unbounded sequence of integers
that does not increase too rapidly. Nevertheless, one should acknowledge that,when it can be applied, the Mahler method gives the transcendence of the−k for every algebraic number β such that this series
inﬁnite series +∞k=1 ak β
converges.
• We emphasize that if a sequence u satisﬁes Condition (∗)w and if φ isa non-erasing morphism (that is, if the image by φ of any letter has length atleast 1), then φ(u) satisﬁes Condition (∗)w , as well. This observation is usedin the proof of Theorem 2.
• If β is an algebraic number which is neither a Pisot, nor a Salem number, it is still possible to get a transcendence criterion using the approach
followed for proving Theorem 5. However, the assumption w > 1 should
then be replaced by a weaker one, involving the Mahler measure of β andlim supn→∞ |Un |/|Vn |. Furthermore, the same approach shows that the fullstrength of Theorem 5 holds when β is a Gaussian integer. More details will
be given in a subsequent work.
Before beginning the proof of Theorem 5, we quote a version of theSchmidt Subspace Theorem, as formulated by Evertse [18].
We normalize absolute values and heights as follows. Let K be an algebraic
number ﬁeld of degree d. Let M (K) denote the set of places on K. For x in
K and a place v in M (K), deﬁne the absolute value |x|v by(i) |x|v = |σ(x)|1/d

if v corresponds to the embedding σ : K → R;(ii) |x|v = |σ(x)|2/d = |σ(x)|2/d if v corresponds to the pair of conjugate
complex embeddings σ, σ : K → C;(iii) |x|v = (N p)−ordp (x)/dif v corresponds to the prime ideal p of OK .

ON THE COMPLEXITY OF ALGEBRAIC NUMBERS I

555

These absolute values satisfy the product formula|x|v = 1
for x in K∗ .
v∈M (K)Let x = (x1 , . . . , xn ) be in Kn with x = 0. For a place v in M (K), put1/(2d)n2d|xi |v
if v is real inﬁnite;|x|v =|x|v =

i=1

n

1/d
|xi |dv

if v is complex inﬁnite;

i=1|x|v = max{|x1 |v , . . . , |xn |v }Now deﬁne the height of x by
H(x) = H(x1 , . . . , xn ) =if v is ﬁnite.
|x|v .

v∈M (K)

We stress that H(x) depends only on x and not on the choice of the number
ﬁeld K containing the coordinates of x; see e.g. [18].
We use the following formulation of the Subspace Theorem over number
ﬁelds. In the sequel, we assume that the algebraic closure of K is Q. We
choose for every place v in M (K) a continuation of | · |v to Q, that we denotealso by | · |v .
Theorem E. Let K be an algebraic number ﬁeld. Let m ≥ 2 be an integer.
Let S be a ﬁnite set of places on K containing all inﬁnite places. For each v
in S, let L1,v , . . . , Lm,v be linear forms with algebraic coeﬃcients and withrank {L1,v , . . . , Lm,v } = m.
Let ε be real with 0 < ε < 1. Then, the set of solutions x in Km to theinequalitym |Li,v (x)|v≤ H(x)−m−ε|x|vv∈S i=1

lies in ﬁnitely many proper subspaces of Km .
For a proof of Theorem E, the reader is directed to [18], where a quantitative version is established (in the sense that one bounds explicitly the numberof exceptional subspaces).
We now turn to the proof of Theorem 5. Keep the notation and theassumptions of this theorem. Assume that the parameter w > 1 is ﬁxed,
as well as the sequences (Un )n≥1 and (Vn )n≥1 occurring in the deﬁnition ofCondition (∗)w . Set also rn = |Un | and sn = |Vn | for any n ≥ 1. We aim toprove that the real number
+∞

ak
α :=
βk
k=1

556

BORIS ADAMCZEWSKI AND YANN BUGEAUD

either lies in Q(β) or is transcendental. The key fact is the observation that α
admits inﬁnitely many good approximants in the number ﬁeld Q(β) obtainedby truncating its expansion and completing it by periodicity. Precisely, for any(n)positive integer n, we deﬁne the sequence (bk )k≥1 by(n)

bh = ah for 1 ≤ h ≤ rn + sn ,(n)
brn +h+jsn = arn +h for 1 ≤ h ≤ sn and j ≥ 0.
(n)

The sequence (bk )k≥1 is eventually periodic, with preperiod Un and withperiod Vn . Set+∞ (n)

bk
αn =
,
βk
k=1

and observe that+∞α − αn =(2)(n)

k=rn + wsn +1

ak − bk·βk

Lemma 1. For any integer n, there exists an integer polynomial Pn (X)of degree at most rn + sn − 1 such thatαn =Pn (β)·rn
β (β sn − 1)

Further, the coeﬃcients of Pn (X) are bounded in absolute value by 2 maxk≥1 |ak |.
Proof. By deﬁnition of αn , we getrn+∞ (n)(n)bkak
1  brn +k
=
+
β rn
β
βk
βk
βk
k=1
k=rn +1
k=1
k=1
 +∞

rn
sn

ak
arn +k  1
1 
=
+ rn
β
β jsn
βk
βk

αn =

rn

ak

+
k

k=1

=

rn

ak
k=1

βk

+

+∞


sn

k=1

k=1

j=0

arn +kPn (β)= r n sn
,
k+r
−s
s
n
n
n
β (β − 1)β(β − 1)

where we have set
Pn (X) =rn


ak X rn −k (X sn − 1) +

k=1

sn


arn +k X sn −k .

k=1

The last assertion of the lemma is clear.
Set K = Q(β) and denote by d the degree of K. We assume that α isalgebraic, and we consider the following linear forms, in three variables andwith algebraic coeﬃcients. For the place v corresponding to the embedding of

ON THE COMPLEXITY OF ALGEBRAIC NUMBERS I

557

K deﬁned by β → β, set L1,v (x, y, z) = x, L2,v (x, y, z) = y, and L3,v (x, y, z) =αx + αy + z. It follows from (2) and Lemma 1 that(3)
1,
|L3,v (β rn +sn , −β rn , −Pn (β))|v = |α(β rn (β sn − 1)) − Pn (β)|1/d(w−1)sn /dβwhere we have chosen the continuation of | · |v to Q deﬁned by |x|v = |x|1/d .
Here and throughout this Section, the constants implied by the Vinogradovsymboldepend (at most) on α, β, and maxk≥1 |ak |, but are independentof n.
 the set of all other inﬁnite places on K and by S the
Denote by S∞
0
set of all ﬁnite places on K dividing β. Observe that S0 is empty if β is an , set L (x, y, z) = x, L (x, y, z) = y, andalgebraic unit. For any v in S0 ∪S∞
1,v
2,v
L3,v (x, y, z) = z. Denote by S the union of S0 and the inﬁnite places on K.
Clearly, for any v in S, the forms L1,v , L2,v and L3,v are linearly independent.
To simplify the exposition, set
xn = (β rn +sn , −β rn , −Pn (β)).
We wish to estimate the product
Π :=

3
 
|Li,v (xn )|vv∈S i=1|xn |v=|β rn +sn |v |β rn |v

v∈S|L3,v (xn )|v|xn |3v

from above. By the product formula and the deﬁnition of S, we immediately
get that |L3,v (xn )|v(4)Π=.
|xn |3v
v∈S

Since the polynomial Pn (X) has integer coeﬃcients and since β is an algebraic
integer, we have |L3,v (xn )|v = |Pn (β)|v ≤ 1 for any place v in S0 . Furthermore,as the conjugates of β have moduli at most 1, we have for any inﬁnite place v
in S∞|L3,v (xn )|v(rn + sn )dv /d ,where dv = 1 or 2 according as v is real inﬁnite or complex inﬁnite, respectively.
Together with (3) and (4), this givesΠ (rn + sn )(d−1)/d β −(w−1)sn /d|xn |−3v(d−1)/d(rn + sn )β−(w−1)sn /dv∈SH(xn )−3 ,since |xn |v = 1 if v does not belong to S.
Furthermore, it follows from Lemma 1 and from the fact that the moduli
of the complex conjugates of β are at most 1 thatH(xn )(rn + sn )d β (rn +sn )/d .

558

BORIS ADAMCZEWSKI AND YANN BUGEAUD

Consequently, we infer from Condition (∗)w that3 |Li,v (xn )|vv∈S i=1|xn |v(rn + sn )dw H(xn )−(w−1)sn /(rn +sn ) H(xn )−3H(xn )−3−ε ,for some positive real number ε.
It then follows from Theorem E that the points (β rn +sn , −β rn , −Pn (β))
lie in a ﬁnite number of proper subspaces of K3 . Thus, there exist a non-zero
triple (x0 , y0 , z0 ) in K3 and inﬁnitely many integers n such thatx0 − y0

β rn
β rn +sn− z0

Pn (β)= 0.
β rn +sn

Taking the limit along this subsequence of integers and noting that (sn )n≥1
tends to inﬁnity, we get that x0 = z0 α. Thus, α belongs to K = Q(β), as
asserted.
Let us restrict our attention to the case when β is a Pisot number. Dealing
with the β-expansions of real numbers (instead of arbitrary power series in β)
allows us to improve the conclusion of Theorem 5.
Theorem 5A. Let β > 1 be a Pisot number. Let α be in (0, 1), andconsider its β-expansion
+∞

ak
.
α :=
βk
k=1

If (ak )k≥1 satisﬁes Condition (∗)w for some real number w > 1, then α istranscendental.
Proof. By a result of K. Schmidt [38], we know that the β-expansion of
every element of Q(β) ∩ (0, 1) is eventually periodic. Thus, it does not satisfy
Condition (∗)w . We conclude by applying Theorem 5.
Note that for a Salem number β, it is an important open problem to decide
whether every element of Q(β) ∩ (0, 1) has an eventually periodic β-expansion.
5. Proofs of Theorems 1 to 4
We begin by a short proof of Theorem 2.
Proof of Theorem 2.
Let a = (ak )k≥1 be a non-eventually periodic
automatic sequence deﬁned on a ﬁnite alphabet A. Recall that a morphism
is called uniform if the images of each letter have the same length. Following
Cobham [15], there exist a morphism φ from an alphabet B = {1, 2, . . . , r}to the alphabet A and an uniform morphism σ from B into itself such that

559

ON THE COMPLEXITY OF ALGEBRAIC NUMBERS I

a = φ(u), where u is a ﬁxed point for σ. Observe ﬁrst that the sequencea satisﬁes Condition (∗)w if this is the case for u. Further, by the Dirichlet
Schubfachprinzip, the preﬁx of length r + 1 of u can be written under the form
W1 uW2 uW3 , where u is a letter and W1 , W2 , W3 are (possibly empty) ﬁnite
words. We check that the assumptions of Theorem 1 are satisﬁed by u withthe sequences (Un )n≥1 and (Vn )n≥1 deﬁned for any n ≥ 1 by Un = σ n (W1 ) and
Vn = σ n (uW2 ). Indeed, since σ is a morphism of constant length, we get, on
the one hand, that
|Un |
|W1 |
≤
≤r−1
|Vn |
1 + |W2 |and, on the other hand, that σ n (u) is a preﬁx of Vn of length at least 1/r
times the length of Vn . It follows that Condition (∗)1+1/r is satisﬁed by thesequence u, and thus by our sequence a (here, we use the observation we madein Section 4). Let b ≥ 2 be an integer. By applying Theorem 5 with β = b, we−k is transcendental.
conclude that the automatic number +∞k=1 ak b
Proof of Theorem 1. Let α be an irrational number. Without any loss ofgenerality, we assume that α is in (0, 1) and we denote by 0.u1 u2 . . . uk . . . its
b-ary expansion. The sequence (uk )k≥1 takes its values in {0, 1, . . . , b − 1} andis not eventually periodic. We assume that there exists an integer κ ≥ 2 suchthat the complexity function p of (uk )k≥1 satisﬁesp(n) ≤ κn

for inﬁnitely many integers n ≥ 1,

and we shall derive that Condition (∗)w is then fulﬁlled by the sequence (uk )k≥1
for a suitable w > 1. By Theorem 5, this will imply that α is transcendental.
Let nk be an integer with p(nk ) ≤ κnk . Denote by U ( ) the preﬁx of
u := u1 u2 . . . of length . By the Dirichlet Schubfachprinzip, there exists(at least) one word Mk of length nk which has (at least) two occurrences inU ((κ + 1)nk ). Thus, there are (possibly empty) words Ak , Bk , Ck and Dk ,such that
U ((κ + 1)nk ) = Ak Mk Ck Dk = Ak Bk Mk Dk

and|Bk | ≥ 1.

We observe that |Ak | ≤ κnk . We have to distinguish three cases:(i) |Bk | > |Mk |;(ii) |Mk |/3 ≤ |Bk | ≤ |Mk |;(iii) 1 ≤ |Bk | < |Mk |/3 .
(i). Under this assumption, there exists a word Ek such that
U ((κ + 1)nk ) = Ak Mk Ek Mk Dk .

560

BORIS ADAMCZEWSKI AND YANN BUGEAUD

Since |Ek | ≤ (κ − 1)|Mk |, the word Ak (Mk Ek )s with s = 1 + 1/κ is a preﬁxof u. Furthermore, we observe that
|Ak |
.
κ
(ii). Under this assumption, there exist two words Ek and Fk such that|Mk Ek | ≥ |Mk | ≥

1/3

1/3

U ((κ + 1)nk ) = Ak Mk Ek Mk Ek Fk .
1/3

Thus, the word Ak (Mk Ek )2 is a preﬁx of u. Furthermore, we observe that
|Mk |
|Ak |
≥
.
3
3κ
(iii). In the present case, Bk is clearly a preﬁx of Mk , and we infer from
Bk Mk = Mk Ck that Bkt is a preﬁx of Mk , where t is the integer part of|Mk |/|Bk |. Observe that t ≥ 3. Setting s = t/2, we see that Ak (Bks )2 is a
preﬁx of u and
|Mk |
|Ak |
≥
.
|Bks | ≥4
4κ
1/3|Mk Ek | ≥In each of the three cases above, we have proved that there are ﬁnite words
1+1/κ
is a preﬁx of u and:Uk , Vk such that Uk Vk• |Uk | ≤ κnk ;• |Vk | ≥ nk /4;• w ≥ 1 + 1/κ > 1.
Consequently, the sequence (|Uk |/|Vk |)k≥1 is bounded from above by 4κ. Furthermore, it follows from the lower bound |Vk | ≥ nk /4 that we may assume thatthe sequence (|Vk |)k≥1 is strictly increasing. This implies that the sequence u
satisﬁes Condition (∗)1+1/κ . By applying Theorem 5 with β = b, we conclude
that α is transcendental.
Proof of Theorem 3. Let a be a sequence generated by a morphism φdeﬁned on a ﬁnite alphabet A. For any positive integer n, there exists a letteran satisfying|φn (an )| = max{|φn (j)| : j ∈ A}.
This implies the existence of a letter a in A and of a strictly increasing sequenceof positive integers (nk )k≥1 such that for every k ≥ 1 we have|φnk (a)| = max{|φnk (j)| : j ∈ A}.
Assume from now on that A has two elements. Since the sequence a is not
eventually periodic there exist at least two occurrences in a of the two elements

ON THE COMPLEXITY OF ALGEBRAIC NUMBERS I

561

of A. In particular, there exist at least two occurrences of the letter a inthe sequence a. We can thus ﬁnd two (possibly empty) ﬁnite words W1 andW2 such that W1 aW2 a is a preﬁx of a. We check that the assumptions ofTheorem 5 are satisﬁed by a with the sequences (Uk )k≥1 and (Vk )k≥1 deﬁned
by Uk = φnk (W1 ) and Vk = φnk (aW2 ) for any k ≥ 1. Indeed, by deﬁnition ofa, we have|Uk |≤ |W1 |
|Vk |and φnk (a) is a preﬁx of Vk of length at least 1/(|W2 | + 1) times the lengthof Vk . It follows that Condition (∗)w is satisﬁed by the sequence a with w =1 + 1/(|W2 | + 1). We conclude by applying Theorem 5.
Proof of Theorem 4. Let a be a sequence generated by a recurrent morphism φ deﬁned on an alphabet A. As we have already noticed in the beginningof the proof of Theorem 3, there exist a letter a and a strictly increasing sequence of positive integers (nk )k≥1 such that for every k ≥ 1 we have|φnk (a)| = max{|φnk (j)| : j ∈ A}.
Since by assumption the sequence a is recurrent there exist at least two occurrences of the letter a. We then apply the same trick as in the proof of
Theorem 3, and we again conclude by applying Theorem 5.
6. Transcendence of p-adic numbers
Let p be a prime number. As usual, we denote by Qp the ﬁeld of p-adic
numbers. We call algebraic (resp. transcendental) any element of Qp whichis algebraic (resp. transcendental) over Q. A suitable version of the Schmidt
Subspace Theorem, due to Schlickewei [35], can be applied to derive a lower
bound for the complexity of the Hensel expansion of every irrational algebraic
number in Qp .
Theorem 1B. Let α be an irrational algebraic number in Qp and denote
by
α=

+∞


ak pk

k=−m

its Hensel expansion. Then, the complexity function p of the sequence (ak )k≥−m
satisﬁesp(n)lim inf= +∞.
n→∞n
Likewise (see Section 2), we can also state Theorems 2B, 3B and 4B.
Theorem 1B follows from Theorem 6 below, along with the arguments used in
the proof of Theorem 1.

562

BORIS ADAMCZEWSKI AND YANN BUGEAUD

The method of proof of Theorem 5 applies to provide us with a newtranscendence criterion for p-adic numbers.
Theorem 6. Let p be a prime number and let (ak )k≥−m be a sequence
taking its values in {0, 1, . . . , p − 1}. Let w > 1 be a real number. If thesequence (ak )k≥1 satisﬁes Condition (∗)w , then the p-adic number
+∞


α :=

ak pk

k=−m

is transcendental.
We brieﬂy outline the proof of Theorem 6. Let p and (ak )k≥−m be as
in the statement of this theorem. There exist a parameter w > 1 and two
sequences (Un )n≥1 and (Vn )n≥1 of ﬁnite words as in the deﬁnition of Condition(∗)w . For any n ≥ 1, set rn = |Un | and sn = |Vn |. To establish Theorem 6, it
is enough to prove that the p-adic number
α :=

+∞


ak pk

k=1

is transcendental. As in the proof of Theorem 5, the key fact is the observation that α admits inﬁnitely many good rational approximants obtained bytruncating its Hensel expansion and completing by periodicity. Precisely, for(n)any positive integer n, we deﬁne the sequence (bk )k≥1 exactly as in Section 4,
and we set
+∞

(n)
αn =
b k pk .
k=1

An easy calculation shows that we have|α − αn |p ≤ p−rn −wsn ,
where
pn =


rn
k=1

αn =


ak p

k

(p

sn

− 1) −snpn,
ps n − 1arn +k prn +k .

k=1

Assuming that α is an algebraic number in Qp , we apply Theorem 4.1
of Schlickewei [35] with the linear forms L1,p (x, y, z) = x, L2,p (x, y, z) =y, L3,p (x, y, z) = α x + α y + z, L1,∞ (x, y, z) = x, L2,∞ (x, y, z) = y, andL3,∞ (x, y, z) = z. Setting xn := (psn , −1, −pn ), we get |L1,p (xn )|p = p−sn and|L3,p (xn )|p ≤ p−rn −wsn . We then follow the same lines as in the proof of Theorem 5, and we end up in a contradiction. This proves that α is transcendental.

563

ON THE COMPLEXITY OF ALGEBRAIC NUMBERS I

7. Concluding remarks
It is of interest to compare our results with a celebrated theorem of Christol, Kamae, Mendès France, and Rauzy [13] (see also [12]) concerning algebraic
elements of the ﬁeld Fp ((X)). Their result asserts that, for any given prime
number p, the sequence
of integers u = (uk )k≥1 is p-automatic if and only if the
uk X k is algebraic over the ﬁeld of rational functions
formal power seriesk≥1

Fp (X). Thanks to Theorem 2, we thus easily derive the following statement.
Theorem 7. Let
number. The
a uprimeb ≥ 2 be an integer and p bekk
uk X and the real number
are both algebraic
formal power series
bk
k≥1

k≥1

(over Fp (X) and over Q, respectively) if and only if they are rational.
Note that Theorem 2B (see Section 6) naturally gives rise to asimilaruk
is replaced by the q-adic number
uk q k ,result where the real number
bk
k≥1

k≥1

for an arbitrary prime number q. In particular, this holds true for q = p.
In 1991, Morton and Mourant [30] proved the following result: If k ≥ 2
is an integer, P is a non-zero pattern of digits in base k, and if ek,P,b (n) ∈{0, 1, . . . , b − 1} counts the number of occurrences modulo b of P in the k-ary+∞
ek,P,b (n)expansion of n, then the real number α(k, P, b) =is transcendenbn
n=0
tal except when k = 3, P = 1 and b = 2. Moreover, we have α(3, 1, 2) = 2/3
in this particular case.
The proof given by Morton and Mourant is based on Theorem 2 and theirpaper refers to the work of Loxton and van der Poorten [24]. The present work
validates their result.
It is interesting to remark that the simplest case k = 2, P = 1 and b = 2
corresponds to the well-known Thue-Morse number, whose transcendence has
been proved by Mahler [25]. The theorem of Morton and Mourant can thus beseen as a full generalisation of the Mahler result.
CNRS, Université Claude Bernard Lyon 1, Villeurbanne, France
E-mail address: Boris.Adamczewski@math.univ-lyon1.fr
Université Louis Pasteur, Strasbourg, France
E-mail address: bugeaud@math.u-strasbg.fr

References[1]

B. Adamczewski, Transcendance à la Liouville de certain nombres réels, C. R. Acad.
Sci. Paris 338 (2004), 511–514.

564

BORIS ADAMCZEWSKI AND YANN BUGEAUD[2]

B. Adamczewski, Y. Bugeaud, and F. Luca, Sur la complexité des nombres algébriques,
C. R. Acad. Sci. Paris 339 (2004), 11–14.

[3]

B. Adamczewski and J. Cassaigne, On the transcendence of real numbers with a regularexpansion, J. Number Theory 103 (2003), 27–37.

[4]

J.-P. Allouche, Nouveaux résultats de transcendance de réels à développements nonaléatoire, Gaz. Math. 84 (2000), 19–34.

[5]

J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, General-

izations, Cambridge University Press, Cambridge, 2003.
[6]

J.-P. Allouche and L. Q. Zamboni, Algebraic irrational binary numbers cannot be ﬁxed
points of non-trivial constant length or primitive morphisms, J. Number Theory 69(1998), 119–124.

[7]

D. H. Bailey, J. M. Borwein, R. E. Crandall, and C. Pomerance, On the binary expansions of algebraic numbers, J. Théor. Nombres Bordeaux 16 (2004), 487–518.

[8]

P. G. Becker, k-regular power series and Mahler-type functional equations, J. Number
Theory 49 (1994), 269–286.

[9]

J. Berstel and P. Séébold, A characterization of overlap-free morphisms, Disc. Appl.
Math. 46 (1993), 275–281.

[10] D. Bertrand, Theta functions and transcendence, Ramanujan J. 1 (1997), 339–350.
√´ Borel, Sur les chiﬀres décimaux de 2 et divers problèmes de probabilités en chaı̂ne,[11] E.
C. R. Acad. Sci. Paris 230 (1950), 591–593.
[12] G. Christol, Ensembles presque périodiques k-reconnaissables, Theor. Comput. Sci. 9(1979), 141–145.
[13] G. Christol, T. Kamae, M. Mendès France, and G. Rauzy, Suites algébriques, automates
et substitutions, Bull. Soc. Math. France 108 (1980), 401–419.
[14] A. Cobham, On the Hartmanis-Stearns problem for a class of tag machines, Conference
Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, Schenectady, New York (1968), 51–60.
[15] ——— , Uniform tag sequences, Math. Systems Theory 6 (1972), 164–192.
[16] P. Corvaja and U. Zannier, Some new applications of the subspace theorem, Compositio
Math. 131 (2002), 319–340.
[17] D. Duverney, Ke. Nishioka, Ku. Nishioka, and I. Shiokawa, Transcendence of Jacobi’s
theta series, Proc. Japan Acad. 72 (1996), 202–203.
[18] J.-H. Evertse, An improvement of the quantitative Subspace theorem, Compositio Math.
101 (1996), 225–311.
[19] S. Ferenczi, Rank and symbolic complexity, Ergodic Theory Dynam. Systems 16 (1996),
663–682.
[20] S. Ferenczi and C. Mauduit, Transcendence of numbers with a low complexity expansion, J. Number Theory 67 (1997), 146–161.
[21] J. Hartmanis and R. E. Stearns, On the computational complexity of algorithms, Trans.
Amer. Math. Soc. 117 (1965), 285–306.
[22] A. J. Kempner, On Transcendental Numbers, Trans. Amer. Math. Soc. 17 (1916), 476–
482.
[23] J. H. Loxton and A. J. van der Poorten, Arithmetic properties of the solutions of aclass of functional equations, J. Reine Angew. Math. 330 (1982), 159–172.
[24] ——— , Arithmetic properties of automata: regular sequences, J. Reine Angew. Math.
392 (1988), 57–69.

ON THE COMPLEXITY OF ALGEBRAIC NUMBERS I

565[25] K. Mahler, Arithmetische Eigenschaften der Lösungen einer Klasse von Funktionalgleichungen, Math. Ann. 101 (1929), 342–366; Corrigendum, 103 (1930), 532.
[26] ——— , Arithmetische Eigenschaften einer Klasse transzendental-transzendenter Funktionen, Math. Z . 32 (1930), 545–585.
[27] ——— , Über das Verschwinden von Potenzreihen mehrerer Veränderlichen in speziellen
Punktfolgen, Math. Ann. 103 (1930), 573–587.
[28] M. Morse and G. A. Hedlund, Symbolic dynamics, Amer. J. Math. 60 (1938), 815–866.
[29] ——— , Symbolic dynamics II, Amer. J. Math. 62 (1940), 1–42.
[30] P. Morton and W. J. Mourant, Digit patterns and transcendental numbers, J. Australian Math. Soc. 51 (1991), 216–236.
[31] Ku. Nishioka, Mahler Functions and Transcendence, Lecture Notes in Math. 1631,
Springer-Verlag, New York, 1996.
[32] A. Rényi, Representations for real numbers and their ergodic properties, Acta Math.
Sci. Hungar . 8 (1957), 477–493.
[33] D. Ridout, Rational approximations to algebraic numbers, Mathematika 4 (1957), 125–131.
[34] R. N. Risley and L. Q. Zamboni, A generalization of Sturmian sequences: combinatorial
structure and transcendence, Acta Arith. 95 (2000), 167–184.
[35] H. P. Schlickewei, On products of special linear forms with algebraic coeﬃcients, Acta
Arith. 31 (1976), 389–398.
[36] ——— , The p-adic Thue-Siegel-Roth-Schmidt theorem, Arch. Math. 29 (1977), 267–
270.
[37] ——— , The quantitative subspace theorem for number ﬁelds, Compositio Math. 82(1992), 245–273.
[38] K. Schmidt, On periodic expansions of Pisot numbers and Salem numbers, Bull. London
Math. Soc. 12 (1980), 269–278.
[39] W. M. Schmidt, Norm form equations, Ann. of Math. 96 (1972), 526–551.
[40] ——— , Diophantine Approximation, Lecture Notes in Math. 785 (1980), SpringerVerlag, New York.
[41] G. Troi and U. Zannier, Note on the density constant in the distribution of self-numbers.
II, Boll. Unione Mat. Ital. (8) 2-B (1999), 397–399.
[42] A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc. 42 (1937), 230–265.
[43] M. Waldschmidt, Un demi-siècle de transcendance, in Development of Mathematics
1950–2000, 1121–1186, Birkhäuser, Basel, 2000.

(Received May 30, 2004)