Acta Math., 195 (2005), 1–20
c 2005 by Institut Mittag-Leﬄer. All rights reservedOn the complexity of algebraic numbers, II.
Continued fractions
by
BORIS ADAMCZEWSKI

and            

YANN BUGEAUD         

1. Introduction
Let b2 be an integer. Émile Borel [9] conjectured that every real irrational algebraic
number α should satisfy some of the laws shared by almost all real numbers with respect
to their b-adic expansions. Despite some recent progress [1], [3], [7], we are still very
far away from establishing such a strong result. In the present work, we are concernedwith a similar question, where the b-adic expansion of α is replaced by its sequence ofpartial quotients. Recall that the continued fraction expansion of an irrational number
α is eventually periodic if and only if α is a quadratic irrationality. However, very little
is known regarding the size of the partial quotients of algebraic real numbers of degree
at least three. Because of some numerical evidence and a belief that these numbers
behave like most of the numbers in this respect, it is often conjectured that their partial
quotients form an unbounded sequence, but we seem to be very far away from a proof(or a disproof). Apparently, Khinchin [16] was the ﬁrst to consider such a question (see[4], [27] and [29] for surveys including a discussion on this problem). Although almost
nothing has been proved yet in this direction, some more general speculations are dueto Lang [17], including the fact that algebraic numbers of degree at least three should
behave like most of the numbers with respect to the Gauss–Khinchin–Kuzmin–Lévy laws.
More modestly, we may expect that if the sequence of partial quotients of an irrational number α is, in some sense, ‘simple’, then α is either quadratic or transcendental.
The term ‘simple’ can of course lead to many interpretations. It may denote real numbers
whose continued fraction expansion has some regularity, or can be produced by a simple
algorithm (by a simple Turing machine, for example), or arises from a simple dynamicalsystem ... . The main results of the present work are two new combinatorial transcenThe second author was supported by the Austrian Science Fund (FWF), Grant M822-N12.

2

B. ADAMCZEWSKI AND Y. BUGEAUD

dence criteria, which considerably improve upon those from [5], [13] and [8]. It is of aparticular interest that such criteria naturally yield, in a uniﬁed way, several new resultson the diﬀerent approaches of the above-mentioned notion of simplicity/complexity forthe continued fraction expansions of algebraic real numbers of degree at least three.
This article is organized as follows. §2 is devoted to the statements of our two
transcendence criteria. Several applications of them are then brieﬂy discussed in §3. All
the proofs are postponed to §§ 4 and 5.

2. Transcendence criteria for stammering continued fractions
Before stating our theorems, we need to introduce some notation. Let A be a given set,
not necessarily ﬁnite. The length of a word W on the alphabet A, that is, the number ofletters composing W, is denoted by |W |. For positive integers l, we write W l for the word
W ... W (l times repeated concatenation of the word W ). More generally, for positive
rational numbers x, we denote by W x the word W [x] W , where W  is the 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 the real number y. Let a={al }l1 be asequence of elements from A, that we identify with the inﬁnite word a1 a2 ... al ... . Let
w be a rational number with w>1. We say that a satisﬁes Condition (∗)w if a is not
eventually periodic and if there exists a sequence of ﬁnite words {Vn }n1 such that(i) for n1, the word Vnw is a preﬁx of the word a;(ii) the sequence {|Vn |}n1 is increasing.
Roughly speaking, a satisﬁes Condition (∗)w if a is not eventually periodic and if
there exist inﬁnitely many ‘non-trivial’ repetitions (the size of which is measured by w)
at the beginning of the inﬁnite word a1 a2 ... al ... .
Our transcendence criterion for ‘purely’ stammering continued fractions can bestated as follows:
Theorem 1. Let a={al }l1 be a sequence of positive integers. Let {pl /ql }l1 denote the sequence of convergents to the real number
α := [0; a1 , a2 , ..., al , ...].
If there exists a rational number w2 such that a satisﬁes Condition (∗)w , then α
is transcendental. If there exists a rational number w>1 such that a satisﬁes Condi 1/l tion (∗)w , and if the sequence ql l1 is bounded (which is, in particular, the casewhen the sequence a is bounded ), then α is transcendental.
The main interest of the ﬁrst statement of Theorem 1 is that there is no conditionon the growth of the sequence {ql }l1 . Apparently, this fact has not been observed

ON THE COMPLEXITY OF ALGEBRAIC NUMBERS, II. CONTINUED FRACTIONS

3

previously. The second statement of Theorem 1 improves upon Theorem 4 from [5],which requires, together with some extra rather constraining hypotheses, the stronger 1/l assumption w> 32 . The condition that the sequence ql l1 has to be bounded is in
general very easy to check, and is not very restrictive, since it is satisﬁed by almost
all real numbers (in the sense of the Lebesgue measure). Apart from this assumption,
Theorem 1 does not depend on the size of the partial quotients of α. This is in a striking
contrast to all previous results [5], [13], [8], in which, roughly speaking, the size w of therepetition is required to be larger if the partial quotients are larger. Unlike these results,
our Theorem 1 can be easily applied even if α has unbounded partial quotients.
Unfortunately, in the statement of Theorem 1, the repetitions must appear at thevery beginning of a. Results from [13] allow a shift, whose length, however, must be
controlled in terms of the size of the repetitions. Similar results cannot be deduced
from our Theorem 1. However, many ideas from the proof of Theorem 1 can be used todeal also with this situation, under some extra assumptions, and to improve upon thetranscendence criterion from [13].
Keep the notation introduced at the beginning of this section. Let w and w be
non-negative rational numbers with w>1. We say that a satisﬁes Condition (∗∗)w,w if
a is not eventually periodic and if there exist two sequences of ﬁnite words {Un }n1 and{Vn }n1 such that(i) for n1, the word Un Vnw is a preﬁx of the word a;(ii) the sequence {|Un |/|Vn |}n1 is bounded from above by w ;(iii) the sequence {|Vn |}n1 is increasing.
We are now ready to state our transcendence criterion for (general) stammeringcontinued fractions.
Theorem 2. Let a={al }l1 be a sequence of positive integers. Let {pl /ql }l1 denote the sequence of convergents to the real number
α := [0; a1 , a2 , ..., al , ...].
Assume that the sequence 1/l 1/l
ql l1 is bounded and set M =lim supl→+∞ ql and m=

lim inf l→+∞ ql . Let w and w be non-negative real numbers with
1/l

w > (2w +1)

log M
−w .
log m

If a satisﬁes Condition (∗∗)w,w , then α is transcendental.
We display an immediate consequence of Theorem 2.

(1)

4

B. ADAMCZEWSKI AND Y. BUGEAUD

Corollary 1. Let a={al }l1 be a sequence of positive integers. Let {pl /ql }l1denote the sequence of convergents to the real number
α := [0; a1 , a2 , ..., al , ...].
 1/l Assume that the sequence ql l1 converges. Let w and w be non-negative real numbers with w>w +1. If a satisﬁes Condition (∗∗)w,w , then α is transcendental.
Our Theorem 2 improves Theorem 6.3 of Davison [13]. Indeed, to apply his transcendence criterion, w and w must satisfy
3 log M,
w > 2w +2 log mwhich is a far stronger condition than (1).
Theorems 1 and 2 yield many new results that could not be obtained with the earliertranscendence criteria. Some of them are stated in §3, while many others will be given
in a subsequent work [2]. Theorems 1 and 2 are in the same spirit as the following result,established in [1] and [3], and which deals with the transcendence of b-adic expansions.
Theorem ABL. Let b2 be an integer. Let a={al }l1 be a sequence of integers
in {0, ..., b−1}. Let w and w be non-negative rational numbers with w>1. If a satisﬁeslCondition (∗∗)w,w , then the real numberl1 al /b is transcendental.
Theorem ABL is as strong for ‘purely’ stammering sequences as for general stammering sequences, provided that the repetitions do not occur too far away from the
beginning of the inﬁnite word. Unfortunately, in Theorem 2 we are unable to replace theassumption ‘w>w +1’ by the weaker one ‘w>1’, occurring in Theorem ABL.
The main tool for the proofs of Theorems 1 and 2, given in §4, is the Schmidt
subspace theorem [25], [26]. This (more precisely, a p-adic version of it) is also the key
auxiliary result for establishing Theorem ABL.

3. Applications to the complexity of algebraic continued fractions
Our transcendence criteria apply to establish that several well-known continued fractions
are transcendental, including the Thue–Morse continued fraction (whose transcendence
was ﬁrst proved by M. Queﬀélec [21]), the Rudin–Shapiro continued fraction, folded continued fractions, continued fractions arising from perturbed symmetries (these sequenceswere introduced by Mendès France [18]), continued fractions considered by Davison [13]and Baxa [8], etc. These applications are discussed in details in [2], where complete proofs
are given. We only focus here on applications related to our main problem, that is, tothe complexity of algebraic numbers with respect to their continued fraction expansions.

ON THE COMPLEXITY OF ALGEBRAIC NUMBERS, II. CONTINUED FRACTIONS

5

3.1. An algorithmic approach
We ﬁrst brieﬂy discuss how the complexity of the continued fraction of real numbers
can be interpreted in an algorithmic way. Following the pioneering work of Turing [28],a sequence is said to be computable if there exists a Turing machine capable to produce
its terms successively. Later, Hartmanis and Stearns [15] proposed to emphasize thequantitative aspect of this notion, and to take into account the number T (n) of operations
needed by a (multitape) Turing machine to produce the ﬁrst n terms of the sequence. In
this regard, a real number is considered to be simpler if its continued fraction expansion
can be produced faster by a Turing machine.
Finite automata are one of the most basic models of computation and take thus placeat the bottom of the hierarchy of Turing machines. In particular, such machines produce
sequences in real time, that is, with T (n)=O(n). An inﬁnite sequence a={an }n0 is
said to be generated by a k-automaton if an is a ﬁnite-state function of the base-k
representation of n. This means that there exists a ﬁnite automaton starting with the
k-ary expansion of n as input and producing the term an as output. A nice reference on
this topic is the book of Allouche and Shallit [6]. As a classical example of a sequence
generated by a 2-automaton, we mention the famous binary Thue–Morse sequence a={an }n0 = 0110100110010 ... . This sequence is deﬁned as follows: 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). In
view of the above discussion, we may expect that ﬁnite automata are ‘too simple’ Turingmachines to produce the continued fraction expansion of algebraic numbers that areneither rationals nor quadratics.
Problem 1. Do there exist algebraic numbers of degree at least three whose continued
fraction expansion can be produced by a ﬁnite automaton?
Thanks to Cobham [11], we know that sequences generated by ﬁnite automata can becharacterized in terms of iterations of morphisms of free monoids generated by ﬁnite sets.
We now recall this useful description. For a ﬁnite set A, let A∗ denote 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 a homomorphism
between the free monoids A∗ and B∗ . Such a homomorphism is called a morphism from
A to B. If there is a positive integer k such that each element of A is mapped to a wordof length k, then the morphism is called k-uniform or simply uniform. Similarly, anapplication from A to B can be uniquely extended to a homomorphism between the freemonoids A∗ and B∗ . Such an application is called a coding (the term ‘letter-to-letter’
morphism is also used in the literature).
A morphism σ from A into itself is said to be prolongable if there exists a letter a

6

B. ADAMCZEWSKI AND Y. BUGEAUD

such that σ(a)=aW, where the word W is such that σ n (W ) is a non-empty word for everyn0. In that case, the sequence of ﬁnite words {σ n (a)}n1 converges in AZ0 (endowedwith 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 σ. We say that a sequence b isgenerated by the morphism σ if there exists a coding ϕ such that b=ϕ(a) . If, moreover,every letter appearing in a occurs at least twice, then we say that b is generated bya recurrent morphism. If the alphabet A has only two letters, then we say that b isgenerated by a binary morphism. Furthermore, if σ is uniform, then we say that b isgenerated by a uniform morphism.
For instance, the Fibonacci morphism σ deﬁned on the alphabet {0, 1} by σ(0)= 01
and σ(1)=0 is a binary, recurrent and non-uniform morphism which generates the celebrated Fibonacci inﬁnite worda = lim σ n (0) = 010010100100101001 ... .
n→+∞

Uniform morphisms and automatic sequences are strongly connected, as shown by
the following result of Cobham [11]:Theorem (Cobham). A sequence can be generated by a ﬁnite automaton if and only
if it is generated by a uniform morphism.
This useful description gives rise to the following challenging question:
Problem 2. Do there exist algebraic numbers of degree at least three whose continued
fraction expansion is generated by a morphism?
Our main contribution towards both problems is the following result:
Theorem 3. The continued fraction expansion of an algebraic number of degree atleast three cannot be generated by a recurrent morphism.
The class of primitive morphisms has been extensively studied. In particular, Theorem 3 fully solved a question studied by M. Queﬀélec [22]. We display the following
direct consequence of Theorem 3:
Corollary 2. The continued fraction expansion of an algebraic number of degree
at least three cannot be generated by a binary morphism.
Indeed, it is easy to see that binary morphisms are either recurrent or they generate
only eventually periodic sequences.

ON THE COMPLEXITY OF ALGEBRAIC NUMBERS, II. CONTINUED FRACTIONS

7

3.2. A dynamical approach
In this section, we discuss the notion of complexity of the continued fraction expansionof a real number from a dynamical point of view.
Let A be a given set, ﬁnite or not. A subshift on A is a symbolic dynamical system(X, S), where S is the classical shift transformation deﬁned from AZ1 into itself by
S({an }n1 )={an }n2 and X is a subset of AZ1 such that S(X)⊂X. With an inﬁnite
sequence a in AZ1, we associate the subshift Xa =(X, S), where X:= O(a) denotes theclosure of the orbit of the sequence a under the action of S. The complexity function paof a sequence a associates with a positive integer n the number pa (n) of distinct blocksof n consecutive letters occurring in it. More generally, the complexity function pX of
a subshift X =(X, S) associates with a positive integer n the number pX (n) of distinct
blocks of n consecutive letters occurring in at least one element of X.
With a subshift X =(X, S) on Z1 one can associate the set CX deﬁned by
CX = {α = [0; a1 , a2 ...] ∈ (0, 1) : {an }n1 ∈ X }.
In particular, if a real number α lies in CX , then this is also the case for every β in Cα :={T n (α)}n0 , where T denotes the Gauss map, deﬁned from (0, 1) into itself by T (x)={1/x}. Indeed, we clearly have T ([0; a1 , a2 , ...])=[0; a2 , a3 , ...]. A way to investigate thequestion of the complexity of the continued fraction expansion of α is to determine thebehaviour of the sequence {T n (α)}n0 or, equivalently, to determine the structure of theunderlying dynamical system (Cα , T ). Roughly speaking, we can consider that the larger
Cα is, the more complex is the continued fraction expansion of α.
Thus, if the symbolic dynamical system X has a too simple structure, for instanceif it has low complexity, then we can expect that no algebraic number of degree at least
three lies in the set CX .
Problem 3. Let X be a subshift on Z1 with sublinear complexity, that is, whose
complexity function satisﬁes pX (n)M n for some absolute constant M and every positive
integer n. Does the set CX only contain quadratic or transcendental numbers?
Only very partial results are known in the direction of Problem 3. A famous resultof Morse and Hedlund [19] states that a subshift X whose complexity function satisﬁes
pX (n)n for some positive integer n must be periodic. In that case, it follows that CX
is a ﬁnite set composed only of quadratic numbers. Further, it is shown in [5] that fora Sturmian subshift X , that is, a subshift with complexity pχ (n)=n+1 for every n1,
the set CX is an uncountable set composed only of transcendental numbers. Theorem 4slightly improves this result.

8

B. ADAMCZEWSKI AND Y. BUGEAUDTheorem 4. Let X be a subshift on Z1 . If the set CX contains a real algebraic
number of degree at least three, then the complexity function of X satisﬁes
lim pX (n)−n = +∞.

n→+∞Linearly recurrent subshifts form a class of particular interest of subshifts of low
complexity. Let X =(X, S) be a subshift and W be a ﬁnite word. The cylinder associatedwith W is, by deﬁnition, the subset W  of X formed by the sequences that begin in
the word W. A minimal subshift (X, S) is linearly recurrent if there exists a positive
constant c such that for each cylinder W  the return time to W  under S is boundedby c|W |. Such dynamical systems, studied, e.g., in [14], are uniquely ergodic and have
low complexity (in particular, they have zero entropy), but without being necessarily
trivial. Another contribution to Problem 3 is given by Theorem 5.
Theorem 5. Let X be a linearly recurrent subshift on Z1 . Then the set CX is
composed only by quadratic or transcendental numbers.
The proofs of Theorems 3–5 are postponed to §5.

4. Proofs of Theorems 1 and 2
The proofs of Theorems 1 and 2 rest on the following deep result, commonly known as
the Schmidt subspace theorem.
Theorem A (W. M. Schmidt). Let m2 be an integer. Let L1 , ..., Lm be linearly
independent linear forms in x=(x1 , ..., xm ) with algebraic coeﬃcients. Let ε be a positive
real number. Then the set of solutions x=(x1 , ..., xm ) in Zm to the inequality|L1 (x) ... Lm (x)|  (max{|x1 |, ..., |xm |})−ε
lies in ﬁnitely many proper subspaces of Qm.
Proof. See, e.g., [25] or [26]. The case m=3 has been established earlier in [24]. Compared with the pioneering work [12] and the recent papers [21], [5], [13] and [8],the novelty in the present paper is that we are able to use Theorem A with m=4 andnot only with m=3, as in all of these works.
We further need an easy auxiliary result.

ON THE COMPLEXITY OF ALGEBRAIC NUMBERS, II. CONTINUED FRACTIONS

9

Lemma 1. Let α=[a0 ; a1 , a2 , ...] and β =[b0 ; b1 , b2 , ...] be real numbers. Assume that,for some positive integer m, we have aj =bj for j =0, ..., m. Then we have−2|α−β| < qm,

where qm is the denominator of the convergent [a0 ; a1 , ..., am ].
Proof. Since [a0 ; a1 , ..., am ] =: pm /qm is a convergent to α and to β, the real numbers−2α−pm /qm and β −pm /qm have the same sign and are both in absolute value less than qm,
and hence the lemma follows.
Now, we have all the tools to establish Theorems 1 and 2.
Proof of Theorem 1. Keep the notation and the hypothesis of this theorem. Assume
that the parameter w>1 is ﬁxed, as well as the sequence {Vn }n1 occurring in thedeﬁnition of Condition (∗)w . Set also sn =|Vn | for n1. We want to prove that the real
numberα := [0; a1 , a2 , ...]
is transcendental. We assume that α is algebraic of degree at least three, and we aim atderiving a contradiction. Throughout this section, the constants implied bydependonly on α.
Let {pl /ql }l1 denote the sequence of convergents to α. Observe ﬁrst that we have
ql+1

ql1.1

for l  1,

(2)

by Roth’s theorem [23].
The key fact for the proof of Theorem 1 is the observation that α admits inﬁnitely
many good quadratic approximants obtained by truncating its continued fraction expansion and completing by periodicity. Precisely, for positive integers n, we deﬁne the (n) sequence bk k1 by(n)bh+jsn = ahfor 1  h  sn and j  0.

 (n) The sequence bk k1 is purely periodic with period Vn . Set
(n)

(n)

αn = [0; b1 , b2 , ...]and observe that αn is a root of the quadratic polynomial
Pn (X) := qsn −1 X 2 +(qsn −psn −1 )X−psn .

10

B. ADAMCZEWSKI AND Y. BUGEAUD

By Rolle’s theorem and Lemma 1, for positive integers n, we have|Pn (α)| = |Pn (α)−Pn (αn )|−2
qsn q[ws,n]qsn |α−αn |(3)since the ﬁrst [wsn ] partial quotients of α and αn are the same. Furthermore, we clearlyhave|qsn α−psn |  qs−1,
(4)n
and we infer from (2) that|qsn −1 α−psn −1 |  qs−1
n −1

qs−0.9.
n(5)Consider now the four linearly independent linear forms
L1 (X1 , X2 , X3 , X4 ) = α2X2 +α(X1 −X4 )−X3 ,
L2 (X1 , X2 , X3 , X4 ) = αX1 −X3 ,
L3 (X1 , X2 , X3 , X4 ) = X1 ,
L4 (X1 , X2 , X3 , X4 ) = X2 .
Evaluating them on the quadruple (qsn , qsn −1 , psn , psn −1 ), it follows from (3) and (4) that


|Lj (qsn , qsn −1 , psn , psn −1 )|−2
qs2n q[ws
.
n]

(6)

1j4

By assumption, there exists a real number M such that log ql  l log M for positive integers l. Furthermore, an immediate induction shows that ql+2 2ql holds for positive
integers l. Consequently, for integers n3, we get√q[wsn ] √ [(w−1)sn ]−12 )/log Mn )(log 2
 qs(w−1−2/s,nqsn

and we infer from (6) and w>1 that


|Lj (qsn , qsn −1 , psn , psn −1 )|

qs−ε
n

1j4

holds for some positive real number ε, when n is large enough.
It then follows from Theorem A that the points (qsn , qsn −1 , psn , psn −1 ) lie in a ﬁnite number of proper subspaces of Q4 . Thus, there exist a non-zero integer quadruple(x1 , x2 , x3 , x4 ) and an inﬁnite set of distinct positive integers N1 such thatx1 qsn +x2 qsn −1 +x3 psn +x4 psn −1 = 0(7)

ON THE COMPLEXITY OF ALGEBRAIC NUMBERS, II. CONTINUED FRACTIONS

11

for n in N1 . Observe that (x2 , x4 ) =(0, 0), since, otherwise, by letting n tend to inﬁnity
along N1 in (7), we would get that the real number α is rational. Dividing (7) by qsn ,we obtainqs −1
psps −1 qsn −1= 0.
(8)x1 +x2 n +x3 n +x4 n
qsn
qsn
qsn −1 qsn
By letting n tend to inﬁnity along N1 in (8), we get that
β :=

lim

N1n→+∞

qsn −1x1 +x3 α=−.
qsn
x2 +x4 αFurthermore, observe that, for n in N1 , we have
 


 


β − qsn −1  =  x1 +x3 α − x1 +x3 psn /qsn 



qsn
x2 +x4 α x2 +x4 psn −1 /qsn −1 11

qs2n −1

qs1.8
n

,

(9)

by (4) and (5). Since qsn −1 and qsn are coprime and sn tends to inﬁnity when n tends
to inﬁnity along N1 , this implies that β is irrational.
Consider now the three linearly independent linear formsL1 (Y1 , Y2 , Y3 ) = βY1 −Y2 ,

L2 (Y1 , Y2 , Y3 ) = αY1 −Y3 ,

L3 (Y1 , Y2 , Y3 ) = Y1 .

Evaluating them on the triple (qsn , qsn −1 , psn ) with n∈N1 , we infer from (4) and (9) that|Lj (qsn , qsn −1 , psn )| qs−0.8
.
n
1j3

It then follows from Theorem A that the points (qsn , qsn −1 , psn ) with n∈N1 lie in a ﬁnite
number of proper subspaces of Q3 . Thus, there exist a non-zero integer triple (y1 , y2 , y3 )and an inﬁnite set of distinct positive integers N2 such thaty1 qsn +y2 qsn −1 +y3 psn = 0(10)

for n in N2 . Dividing (10) by qsn and letting n tend to inﬁnity along N2 , we get
y1 +y2 β +y3 α = 0.

(11)

To obtain another equation linking α and β, we consider the three linearly independent linear formsL1 (Z1 , Z2 , Z3 ) = βZ1 −Z2 ,L2 (Z1 , Z2 , Z3 ) = αZ2 −Z3 ,L3 (Z1 , Z2 , Z3 ) = Z1 .

Evaluating them on the triple (qsn , qsn −1 , psn −1 ) with n∈N1 , we infer from (5) and (9)that|Lj (qsn , qsn −1 , psn −1 )| qs−0.7
.
n
1j3

12

B. ADAMCZEWSKI AND Y. BUGEAUD

It then follows from Theorem A that the points (qsn , qsn −1 , psn −1 ) with n∈N1 lie in aﬁnite number of proper subspaces of Q3 . Thus, there exist a non-zero integer triple(z1 , z2 , z3 ) and an inﬁnite set of distinct positive integers N3 such thatz1 qsn +z2 qsn −1 +z3 psn −1 = 0(12)

for n in N3 . Dividing (12) by qsn −1 and letting n tend to inﬁnity along N3 , we get
z1+z2 +z3 α = 0.
β(13)Observe that y2 =0 since α is irrational. We infer from (11) and (13) that(z3 α+z2 )(y3 α+y1 ) = y2 z1 .
If y3 z3 =0, then (11) and (13) yield that β is rational, which is a contradiction. Consequently, y3 z3 =0 and α is a quadratic real number, which is again a contradiction. This
completes the proof of the second assertion of the theorem.
It then remains for us to explain why we can drop the assumption on the sequence 1/l ql l1 when w is suﬃciently large. We return to the beginning of the proof, and weassume that w2. Using well-known facts from the theory of continuants (see, e.g., [20]),
inequality (3) becomes|Pn (α)|−2
qsn q2sn

qsn qs−4nqs−3n

H(Pn )−3 ,where H(Pn ) denotes the height of the polynomial Pn , that is, the maximum of theabsolute values of its coeﬃcients. By the main result from [24] (or by using Theorem A
with m=3 and the linear forms α2X2 +αX1 +X0 , X2 and X1 ), this immediately implies
that α is transcendental.

Proof of Theorem 2. Assume that the parameters w and w are ﬁxed, as well as thesequences {Un }n1 and {Vn }n1 occurring in the deﬁnition of Condition (∗∗)w,w . Without any loss of generality, we add in the statement of Condition (∗∗)w,w the following
two assumptions:(iv) The sequence {|Un |}n1 is unbounded;(v) For n1, the last letter of the word Un diﬀers from the last letter of the word Vn .
We point out that the conditions (iv) and (v) do not at all restrict the generality.
Indeed, if (iv) is not fulﬁlled by a sequence a satisfying (i)–(iii) of Condition (∗∗)w,w ,then the desired result follows from Theorem 1. To see that (v) does not cause any
trouble, we make the following observation. Let a be a letter, and U and V be two words

13

ON THE COMPLEXITY OF ALGEBRAIC NUMBERS, II. CONTINUED FRACTIONS

such that a begins with Ua(Va)w . Then a also begins with U (aV )w, and we have trivially|U |/|aV ||Ua|/|Va|.
Set rn =|Un | and sn =|Vn | for n1. We want to prove that the real number
α := [0; a1 , a2 , ...]
is transcendental. We assume that α is algebraic of degree at least three, and we aim atderiving a contradiction. Let {pl /ql }l1 denote the sequence of convergents to α.
Let n be a positive integer. Since w>1 and rn wsn , we get
2rn +sn
2wsn +sn
2w +1 log m
<
,
 
= 
rn +wsn w sn +wsn
w +w
log M
by (1). Consequently, there exist positive real numbers η and η  with η<1 such that(1+η)(1+η  )(2rn +sn ) log M < (1−η  )(rn +wsn ) log m(14)

for n1. Notice that we have
ql+1

ql1+η

for l  1,

(15)

by Roth’s theorem [23].
As for the proof of Theorem 1, we observe that α admits inﬁnitely many goodquadratic approximants obtained by truncating its continued fraction expansion andcompleting by periodicity. Precisely, for positive integers n, we deﬁne the sequence (n) bk k1 by(n)b h = ah(n)
brn +h+jsn = arn +hfor 1  h  rn +sn ,for 1  h  sn and j  0.

 (n) The sequence bk k1 is eventually periodic, with preperiod Un and with period Vn .
Set
(n)

(n)

αn = [0; b1 , b2 , ...]and observe that αn is a root of the quadratic polynomial
Pn (X) := (qrn −1 qrn +sn −qrn qrn +sn −1 )X 2−(qrn −1 prn +sn −qrn prn +sn −1 +prn −1 qrn +sn −prn qrn +sn −1 )X+(prn −1 prn +sn −prn prn +sn −1 ).

14

B. ADAMCZEWSKI AND Y. BUGEAUD

For positive integers n, we infer from Rolle’s theorem and Lemma 1 that
|Pn (α)| = |Pn (α)−Pn (αn )|qrn qrn +sn |α−αn |qrn qrn +sn qr−2,
n +[wsn ](16)

since the ﬁrst rn +[wsn ] partial quotients of α and αn are the same. Furthermore, by (15),
we have|(qrn −1 qrn +sn −qrn qrn +sn −1 )α−(qrn −1 prn +sn −qrn prn +sn −1 )|qrn qr−1+η
n +sn

(17)

qr−1+η
qrn +sn .
n

(18)

and
|(qrn −1 qrn +sn −qrn qrn +sn −1 )α−(prn −1 qrn +sn −prn qrn +sn −1 )|We have as well the obvious upper bound|qrn −1 qrn +sn −qrn qrn +sn −1 |  qrn qrn +sn .

(19)Consider now the four linearly independent linear forms
L1 (X1 , X2 , X3 , X4 ) = α2X1 −α(X2 +X3 )+X4 ,
L2 (X1 , X2 , X3 , X4 ) = αX1 −X2 ,
L3 (X1 , X2 , X3 , X4 ) = αX1 −X3 ,
L4 (X1 , X2 , X3 , X4 ) = X1 .
Evaluating them on the quadruple
z n := (qrn −1 qrn +sn −qrn qrn +sn −1 , qrn −1 prn +sn −qrn prn +sn −1 ,prn −1 qrn +sn −prn qrn +sn −1 , prn −1 prn +sn −prn prn +sn −1 ),it follows from (16), (17), (18) and (19) that


|Lj (z n )|

qr2+η
qr2+η
q −2
n
n +sn rn +[wsn ](qrn qrn +sn )−η (qr1+η
qr1+η
q −1
)2 .
n
n +sn rn +[wsn ]1j4

Assuming n suﬃciently large, we have

qrn  M (1+η )rn,

qrn +sn  M (1+η )(rn +sn )and

qrn +[wsn ]  m(1−η )(rn +wsn ),with η  as in (14). Consequently, we get(qr1+η
qr1+η
q −1)  M (1+η)(1+η )(2rn +sn ) m−(1−η )(rn +wsn )  1,nn +sn rn +[wsn ]15

ON THE COMPLEXITY OF ALGEBRAIC NUMBERS, II. CONTINUED FRACTIONS

by (14). Thus, we get the upper bound(qrn qrn +sn )−η

|Lj (z n )|1j4

for positive integers n.
It then follows from Theorem A that the points z n lie in a ﬁnite number of proper
subspaces of Q4 . Thus, there exist a non-zero integer quadruple (x1 , x2 , x3 , x4 ) and an
inﬁnite set of distinct positive integers N1 such thatx1 (qrn −1 qrn +sn −qrn qrn +sn −1 )+x2 (qrn −1 prn +sn −qrn prn +sn −1 )+x3 (prn −1 qrn +sn −prn qrn +sn −1 )+x4 (prn −1 prn +sn −prn prn +sn −1 ) = 0(20)

for n in N1 .
Divide (20) by qrn qrn +sn −1 and observe that prn /qrn and prn +sn /qrn +sn tend to α
as n tends to inﬁnity along N1 . Taking the limit, we get that either
x1 +(x2 +x3 )α+x4 α2 = 0
or

qrn −1 qrn +sn→ 1,
qrn qrn +sn −1(21)

as n → ∞ along N1 ,(22)

must hold. In the former case, since α is irrational and not quadratic, we get thatx1 =x4 =0 and x2 =−x3 . Then x2 is non-zero and, for n in N1 , we haveqrn −1 prn +sn −qrn prn +sn −1 = prn −1 qrn +sn −prn qrn +sn −1 .
Thus, the polynomial Pn (X) can simply be expressed as
Pn (X) := (qrn −1 qrn +sn −qrn qrn +sn −1 )X 2
−2(qrn −1 prn +sn −qrn prn +sn −1 )X +(prn −1 prn +sn −prn prn +sn −1 ).
Consider now the three linearly independent linear formsL1 (Y1 , Y2 , Y3 ) = α2X1 −2αX2 +X3 ,
L2 (Y1 , Y2 , Y3 ) = αX1 −X2 ,
L3 (Y1 , Y2 , Y3 ) = X1 .
Evaluating them on the triplez n := (qrn −1 qrn +sn −qrn qrn +sn −1 , qrn −1 prn +sn −qrn prn +sn −1 ,prn −1 prn +sn −prn prn +sn −1 ),16

B. ADAMCZEWSKI AND Y. BUGEAUD

it follows from (16), (17) and (19) that|Lj (z n )| qr3n qr1+η
q −2
n +sn rn +[wsn ]qr2n qr2+η
q −2
n +sn rn +[wsn ](qrn qrn +sn )−η,1j3

by the above computation.
It then follows from Theorem A that the points z n lie in a ﬁnite number of proper
subspaces of Q3 . Thus, there exist a non-zero integer triple (x1 , x2 , x3 ) and an inﬁnite
set of distinct positive integers N2 included in N1 such thatx1 (qrn −1 qrn +sn −qrn qrn +sn −1 )+x2 (qrn −1 prn +sn −qrn prn +sn −1 )+x3 (prn −1 prn +sn −prn prn +sn −1 ) = 0(23)

for n in N2 .
Divide (23) by qrn qrn +sn −1 and observe that prn /qrn and prn +sn /qrn +sn tend to α
as n tends to inﬁnity along N2 . Taking the limit, we get that eitherx1 +x2 α+x3 α2 = 0
or

qrn −1 qrn +sn→ 1,
qrn qrn +sn −1

as n → ∞ along N2 ,

(24)

(25)

must hold. In the former case, we have a contradiction since α is irrational and notquadratic.
Consequently, to conclude the proof of our theorem, it is enough to derive a contradiction from (22) (resp. from (25)), assuming that (21) (resp. (24)) does not hold. To
this end, we observe that (20) (resp. (23)) allows us to control the speed of convergenceof Qn :=(qrn −1 qrn +sn )/(qrn qrn +sn −1 ) to 1 along N1 (resp. along N2 ).
Thus, we assume that the quadruple (x1 , x2 , x3 , x4 ) obtained after the ﬁrst application of Theorem A satisﬁes x1 +(x2 +x3 )α+x4 α2 =0. Dividing (20) by qrn qrn +sn −1 , we
get




prn +sn prn +sn −1
prn −1 prn−−+x3 Qnx1 (Qn −1)+x2 Qn
qrn +sn qrn +sn −1
qrn −1 qrn(26)
prn −1 prn +sn prn prn +sn −1+x4 Qn−=0
qrn −1 qrn +sn qrn qrn +sn −1
for n in N1 . To shorten the notation, for l1, we put Rl :=α−pl /ql . We rewrite (26) as
x1 (Qn −1)+x2 (Qn (α−Rrn +sn )−(α−Rrn +sn −1 ))+x3 (Qn (α−Rrn −1 )−(α−Rrn ))+x4 (Qn (α−Rrn −1 )(α−Rrn +sn )−(α−Rrn )(α−Rrn +sn −1 )) = 0.

ON THE COMPLEXITY OF ALGEBRAIC NUMBERS, II. CONTINUED FRACTIONS

17This yields(Qn −1)(x1 +(x2 +x3 )α+x4 α2 )= x2 Qn Rrn +sn −x2 Rrn +sn −1 +x3 Qn Rrn −1 −x3 Rrn(27)−x4 Qn Rrn −1 Rrn +sn +x4 Rrn Rrn +sn −1+α(x4 Qn Rrn −1 +x4 Qn Rrn +sn −x4 Rrn −x4 Rrn +sn −1 ).

Observe that |Rl |1/ql2 for l1. Furthermore, for n large enough, we have 12 Qn 2,
by our assumption (22). Consequently, we derive from (27) that|(Qn −1)(x1 +(x2 +x3 )α+x4 α2 )||Rrn −1 |

qr−2
.
n −1

Since we have assumed that (21) does not hold, we get|Qn −1|

qr−2
.
n −1

(28)

On the other hand, observe that the rational number Qn is the quotient of thetwo continued fractions [arn +sn ; arn +sn −1 , ..., a1 ] and [arn ; arn −1 , ..., a1 ]. By assumption (v) from Condition (∗∗)w,w , we have arn +sn =arn , and thus either arn +sn −arn 1or arn −arn +sn 1 holds. A simple calculation then shows that|Qn −1|

−1
−1
−1
−1
a−1
rn min{arn +sn −1 +arn −2 , arn +sn −2 +arn −1 }−1
a−1
rn qrn −1 ,since qrn −1 max{arn −1 , arn −2 }. Combined with (28), this gives arn
qrn  arn qrn −1

qrn −1 andqr2n −1 .

(29)

Since η<1 and (29) holds for inﬁnitely many n, we get a contradiction with (15).
We derive a contradiction from (25) in an entirely similar way. This completes theproof of our theorem.


5. Proofs of Theorems 3–5
Before establishing Theorems 3–5, we state an easy, but useful, auxiliary result.
Lemma 2. Let σ be a prolongable morphism deﬁned on a ﬁnite alphabet A. Let abe the associated ﬁxed point and a be the ﬁrst letter of a. Then there exists a positive
constant c such that, for every positive integer n and every letter b occurring in a, wehave |σ n (a)|c|σ n (b)|.
Proof. Without loss of generality, we may assume that A is exactly the set of lettersoccurring in a. Let b be in A. Since a is obtained as the limit limn→+∞ σ n (a), there
exists an integer nb such that the word σ nb (a) contains the letter b. Set
s = max{|σ(b)|}
b∈A

and

n0 = max{nb }.
b∈A

18

B. ADAMCZEWSKI AND Y. BUGEAUD

Let n be a positive integer. If nn0 , then we have|σ n (a)|  1 

1|σ n (b)|.
sn0

If n>n0 , then we get|σ n (a)| = |σ n−n0 (σ n0 (a))|  |σ n−n0 (b)| and the lemma follows by taking c=s−n0 .

1|σ n (b)|,sn0Proof of Theorem 3. Let us assume that b is a sequence generated by a recurrent
morphism σ and that b is not eventually periodic. There exists a ﬁxed point a of σ anda coding ϕ such that b=ϕ(a). By assumption, the ﬁrst letter a which occurs in a should
appear at least twice. Thus, there exists a ﬁnite (possibly empty) word W such that aWa
is a preﬁx of the word a. We check that the assumptions of Theorem 1 are satisﬁed byb with the sequence {Vn }n1 deﬁned by Vn =ϕ(σ n (aW )) for n1. Indeed, by Lemma 2,
there exists a positive rational number c, depending only on σ and W, such that
|σ n (a)|  c |σ n (aW )|.
This implies that ϕ(σ n (aWa)) begins in (ϕ(σ n (aW )))1+c. Since ϕ(σ n (aWa)) is a preﬁxof a, we get that the sequence b satisﬁes Condition (∗)1+c . We conclude by applying
Theorem 1.
Proof of Theorem 4. Let X =(X, S) be a subshift such that pX (n)−n is bounded
and let α be an element of CX . By deﬁnition of the set CX , there exists a sequencea={al }l1 in X such that α=[0; a1 , a2 , ...].
First, assume that the complexity function of the sequence a satisﬁes pa (n)n forsome n. It follows from a theorem of Morse and Hedlund [19] that a is eventually periodic,
and thus α is a quadratic number.
Now, assume that pX (n)>n for every integer n. Since pX (n)−n is bounded, there
exist two positive integers n0 and a such that pX (n)=n+a for all nn0 (see, e.g., [4]).
This implies (see, e.g., [10]) that there exist a ﬁnite word W, a non-erasing morphism φand a Sturmian sequence u such that a=Wφ(u). Since u begins with arbitrarily longsquares (this is proved in [5]) and since φ is a non-erasing morphism, it follows thatφ(u) also begins with arbitrarily long squares, and hence it satisﬁes Condition (∗)2 .
We then infer from Theorem 1 that the real number α =[0; a|W |+1 , a|W |+2 , a|W |+3 , ...] istranscendental. It immediately follows that α is a transcendental number, concluding
the proof of the theorem.
ON THE COMPLEXITY OF ALGEBRAIC NUMBERS, II. CONTINUED FRACTIONS

19

Proof of Theorem 5. Let X =(X, S) be a linearly recurrent subshift and let α bean element of CX . By the deﬁnition of the set CX , there exists a sequence a={al }l1
in X such that α=[0; a1 , a2 , ...]. By assumption, there exists a positive integer k suchthat the gap between two consecutive occurrences in a of every factor W of length n
is at most kn. For every positive integer n, let Un denote the preﬁx of length n of a,and let Wn be the word of length kn deﬁned by U(k+1)n = Un Wn . Since, by assumption,
Un has at least one occurrence in the word Wn , there exist two (possibly empty) ﬁnite
words An and Bn such that Wn =An Un Bn . It follows that Un An Un is a preﬁx of aand, moreover, Un An Un =(Un An )w for some rational number w with w1+1/k. Theneither a is eventually periodic (in which case, α is a quadratic number) or a satisﬁes
Condition (∗)1+1/k , and the transcendence of α follows from Theorem 1, concluding theproof.
Acknowledgement. We would like to warmly thank Jean-Paul Allouche for many
useful remarks. The ﬁrst author is also most grateful to Valérie Berthé for her constanthelp and support.

References[1] Adamczewski, B. & Bugeaud, Y., On the complexity of algebraic numbers I. Expansions
in integer bases. To appear in Ann. of Math.
[2] Adamczewski, B., Bugeaud, Y. & Davison, J. L., Continued fractions and transcendental numbers. Preprint, 2005.
[3] Adamczewski, B., Bugeaud, Y. & Luca, F., Sur la complexité des nombres algébriques.
C. R. Acad. Sci. Paris, 339 (2004), 11–14.
[4] Allouche, J.-P., Nouveaux résultats de transcendance de réels à développement nonaléatoire. Gaz. Math., 84 (2000), 19–34.
[5] Allouche, J.-P., Davison, J. L., Queffélec, M. & Zamboni, L. Q., Transcendence ofSturmian or morphic continued fractions. J. Number Theory, 91 (2001), 39–66.
[6] Allouche, J.-P. & Shallit, J., Automatic Sequences: Theory, Applications, Generalizations. Cambridge Univ. Press, Cambridge, 2003.
[7] Bailey, D. H., Borwein, J. M., Crandall, R. E. & Pomerance, C., On the binary
expansions of algebraic numbers. J. Théor. Nombres Bordeaux, 16 (2004), 487–518.
[8] Baxa, C., Extremal values of continuants and transcendence of certain continued fractions.
Adv. in Appl. Math., 32 (2004), 754–790.
√[9] Borel, É., Sur les chiﬀres décimaux de 2 et divers problèmes de probabilités en chaı̂ne.
C. R. Acad. Sci. Paris, 230 (1950), 591–593.
[10] Cassaigne, J., Sequences with grouped factors, in Developments in Language Theory, III(Thessaloniki, 1997), pp. 211–222. World Sci. Publishing, River Edge, NJ, 1998.
[11] Cobham, A., Uniform tag sequences. Math. Systems Theory, 6 (1972), 164–192.
[12] Davison, J. L., A class of transcendental numbers with bounded partial quotients, in
Number Theory and Applications (Banﬀ, AB, 1988), pp. 365–371. NATO Adv. Sci.
Inst. Ser. C Math. Phys. Sci., 265. Kluwer, Dordrecht, 1989.

20

B. ADAMCZEWSKI AND Y. BUGEAUD[13] — Continued fractions with bounded partial quotients. Proc. Edinburgh Math. Soc., 45(2002), 653–671.
[14] Durand, F., Linearly recurrent subshifts have a ﬁnite number of non-periodic subshift
factors. Ergodic Theory Dynam. Systems, 20 (2000), 1061–1078; Corrigendum and addendum. Ibid., 23 (2003), 663–669.
[15] Hartmanis, J. & Stearns, R. E., On the computational complexity of algorithms. Trans.
Amer. Math. Soc., 117 (1965), 285–306.
[16] Khinchin, A. Ya., Continued Fractions, 2nd edition. Gosudarstv. Izdat. Techn.-Teor. Lit.,
Moscow–Leningrad, 1949 (Russian); English translation: The University of Chicago
Press, Chicago–London, 1964.
[17] Lang, S., Introduction to Diophantine Approximations, 2nd edition. Springer, New York,
1995.
[18] Mendès France, M., Principe de la symétrie perturbée, in Séminaire de Théorie desNombres (Paris, 1979–80), pp. 77–98. Progr. Math., 12. Birkhäuser, Boston, MA, 1981.
[19] Morse, M. & Hedlund, G. A., Symbolic dynamics. Amer. J. Math., 60 (1938), 815–866.
[20] Perron, O., Die Lehre von den Kettenbrüchen. Teubner, Leipzig, 1929.
[21] Queffélec, M., Transcendance des fractions continues de Thue–Morse. J. Number Theory,73 (1998), 201–211.
[22] — Irrational numbers with automaton-generated continued fraction expansion, in Dynamical Systems (Luminy–Marseille, 1998), pp. 190–198. World Sci. Publishing, River
Edge, NJ, 2000.
[23] Roth, K. F., Rational approximations to algebraic numbers. Mathematika, 2 (1955), 1–20;
Corrigendum. Ibid., 2 (1955), 168.
[24] Schmidt, W. M., On simultaneous approximations of two algebraic numbers by rationals.
Acta Math., 119 (1967), 27–50.
[25] — Norm form equations. Ann. of Math., 96 (1972), 526–551.
[26] — Diophantine Approximation. Lecture Notes in Math., 785. Springer, Berlin, 1980.
[27] Shallit, J., Real numbers with bounded partial quotients: a survey. Enseign. Math., 38(1992), 151–187.
[28] Turing, A. M., On computable numbers, with an application to the Entscheidungsproblem.
Proc. London Math. Soc., 42 (1937), 230–265.
[29] Waldschmidt, M., Un demi-siècle de transcendance, in Development of Mathematics
1950–2000, pp. 1121–1186. Birkhäuser, Basel, 2000.
Boris Adamczewski
CNRS, Institut Camille Jordan
Université Claude Bernard Lyon I
Bât. Braconnier
21, avenue Claude Bernard
FR-69622 Villeurbanne Cedex
Franceboris.adamczewski@math.univ-lyon1.fr
Received May 16, 2005

Yann Bugeaud
Université Louis Pasteur
U.F.R. de mathématiques
7, rue René Descartes
FR-67084 Strasbourg Cedex
Francebugeaud@math.u-strasbg.fr