Math. Ann. (2010) 346:107–116
DOI 10.1007/s00208-009-0391-z

Mathematische Annalen

On the expansion of some exponential periods
in an integer base
Boris Adamczewski

Received: 25 September 2008 / Revised: 22 January 2009 / Published online: 25 July 2009
© Springer-Verlag 2009

Abstract We derive a lower bound for the subword complexity of the base-b expansion (b ≥ 2) of all real numbers whose irrationality exponent is equal to 2. This provides a generalization of a theorem due to Ferenczi and Mauduit. As a consequence,
we obtain the first lower bound for the subword complexity of the number e and ofsome other transcendental exponential periods.
1 Introduction√
The decimal expansion of real numbers like 2, π or e appears to be quite mysterious
and, for a long time, has baffled mathematicians. While numerical observations seemto speak in favour of a complex structure, most questions one may imagine to ask about
the decimal expansion of classical irrational constants turn out to be out of reach.
Kontsevitch and Zagier [17] offered a promising framework to try to distinguishusual constants from other real numbers by introducing the notions of period andof exponential period. Algebraic numbers, π , log 2 and ζ (3) are periods, while e isconjecturally not a period. However, e is a typical example of an exponential period.
Exponential periods form a countable set that contains the set of periods. We refer
the reader to [17] for exact definitions and more results about both notions, but toparaphrase these authors, all classical contants are periods in an appropriate sense.
Folklore suggests that all irrational periods are normal numbers. Recall that a real
number is a normal number if for every integer b ≥ 2 and every positive integer n,each one of the bn blocks of length n over the alphabet {0, 1, . . . , b − 1} occurs in its
B. Adamczewski (B)
CNRS, Université de Lyon, Université Lyon 1, Institut Camille Jordan,
43 boulevard du 11 novembre 1918, 69622 Villeurbanne cedex, France
e-mail: Boris.Adamczewski@math.univ-lyon1.fr
URL: http://math.univ-lyon1.fr/~adamczew/

123

108

B. Adamczewski

base b expansion with frequency 1/bn . This notion was introduced in 1909 by Borel[10] who proved that almost all numbers, with respect to the Lebesgue measure, arenormal despite the uncomfortable fact that not a single natural example of a normal
number is known.
An interesting (and perhaps more reasonable) way to tackle problems concernedwith the expansions of classical constants in integer bases is to consider the subword
complexity of real numbers. Let ξ be a real number and b ≥ 2 be a positive integer.
Then ξ has a unique expansion in the base b, that is, there exists a unique sequencea = (an )n≥−k with values in {0, 1, . . . , b − 1} such that
ξ =

! an

n≥−k

bn

:= a−k a−k+1 · · · a−1 a0 •a1 a2 · · ·The complexity function of ξ with respect to the base b is the function that associateswith each positive integer n the positive integerp(ξ, b, n) := Card{(a j , a j+1 , . . . , a j+n−1 ), j ≥ 1}.
A normal number thus has the maximum possible complexity in every integer base,that is, p(ξ, b, n) = bn for every positive integer n and every integer b ≥ 2.√Asmentioned before, one usually expects such a high complexity for numbers like 2,
π and e. This problem was first addressed in 1938 by Hedlund and Morse [18].
In their paper, Hedlund and Morse obtained a fundamental result that can be restatedas follows.
Theorem HM Let b ≥ 2 be an integer and ξ be a real number. Then ξ is rational if
and only if it has a bounded complexity function. Furthermore, if ξ is irrational, its
complexity function is increasing and thusp(ξ, b, n) − n ≥ 1, ∀n ≥ 1.
To find lower bounds for the complexity function of algebraic irrational numbers isa challenging problem. In 1997, Ferenczi and Mauduit [13] proved the theorem below.
Actually, their result is slightly weaker and the present statement is given according
to a clever remark of Allouche outlined in [6].
Theorem FM Let b ≥ 2 be an integer and ξ be an algebraic irrational number. Then,lim p(ξ, b, n) − n = +∞.

n→∞

(1)

The proof of Theorem FM mixes techniques from combinatorics on words andDiophantine approximation. The main ingredient is a p-adic version of Roth’s theorem due to Ridout [19]. Recently, Bugeaud and the author [1] (see also [4]) improved123On the expansion of some exponential periods in an integer base

109

Theorem FM by means of the Schmidt Subspace Theorem. Under the same assumption, these authors proved that (1) can be replaced byp(ξ, b, n)
= +∞.
n→∞
n
lim

The situation regarding transcendental constants is even worse: apparently, there is
not a single trancendental exponential period for which one knows an improvement of
the lower bound given by Theorem HM. Of course, one could choose an exponential
period ξ and compute the first digits of its base-b expansion. If one is lucky enough,one will find occurrences of many different blocks of digits of a given length. But, thiswould only lead, for some integer k, to a lower bound of the typep(ξ, b, n) − n ≥ k,for all sufficiently large positive integers n.
Recall that the irrationality exponent of an irrational number ξ , denoted by µ(ξ ),is defined as the supremum of the real numbers ρ for which the inequality"""""ξ − p " < 1"q " qρ

has infinitely many different rational solutions p/q. It always satifies
2 ≤ µ(ξ ) ≤ +∞.
The set of real numbers whose irrationality exponent is equal to 2 has full Lebesgue
measure. By Roth’s theorem [20], algebraic irrational numbers all have an irrationality
exponent equal to 2. The aim of this note is to generalize Theorem FM as follows.
Theorem 1 Let b ≥ 2 be an integer and ξ be an irrational real number such thatµ(ξ ) = 2. Then,lim p(ξ, b, n) − n = +∞.

n→∞

(2)

Our proof of Theorem 1 is essentially a combination of known results that rely onfine combinatorial properties of infinite words with a very low complexity. In particular, we use, in an essential way, a result due to Berthé et al. [9] concerning initialrepetitions occurring in Sturmian words.
We derive the following consequences of Theorem 1.
Corollary 2 For every integer b ≥ 2, the number e satisfies (2).
To our knowledge, this is the first example of a transcendental exponential period
for which we can improve the bound of Theorem HM.
The only property of the number e used in the proof of Corollary 2 is that µ(e) = 2,
which follows from Euler’s formula for the continued fraction expansion of e (see the

123

110

B. Adamczewski

proof of Corollary 2 in Sect. 3). Actually, many other examples of numbers involving
the exponential function, trigonometric functions, or the modified Bessel function atrational arguments also have an irrationality exponent equal to 2. In particular, the sameconclusion holds in Corollary 2, if we replace the number e by any of the following
numbers (see [11,22]):ea , a ∈ Q, a )= 0;
$
$
#
# $
#
1
1
1 √
1
, √ tan √, a ∈ N, a )= 0;, a tan √
tan
a
a
a
a
# $
2
tanh
, a ∈ N, a )= 0;
a
%
$
#
1
v
, u, v ∈ N, uv )= 0.
tanh √uuv
Other interesting values covered by our approach are the numbersJ( p/q)+1 (2/q)
J p/q (2/q)

andI( p/q)+1 (2/q), p/q ∈ Q,
I p/q (2/q)& 'λ (+∞ (i z/2)2nwhere Jλ (z) = 2zn=0 n! &(λ+n+1) denotes the Bessel function of the first kind(+∞ (z/2)λ+2n
and Iλ (z) = n=0 n! &(λ+n+1) denotes the modified (or hyperbolic) Bessel functionof the first kind (see for instance [16]).
Furthermore, multiplying any of these numbers by a nonzero rational and then adding a rational leads to a new example for which our result can be applied. We can also
take the natural action of GL2 (Z) on any of these numbers. That is, starting from oneof the above number ξ , the number (aξ + b)/(cξ + d), where |ad − bc| = 1, alsosatisfies the bound (2) of Theorem 1.
Another consequence of our Theorem 1 is that a real number with a boundedsequence of partial quotients in its continued fraction expansion cannot have base-b
expansions that are too simple.
Corollary 3 Let b ≥ 2 be an integer and ξ be an irrational real number whose continued fraction expansion is [a0 , a1 , a2 , . . .]. If the sequence of integers (an )n≥0 isbounded, then ξ satisfies (2).
2 Repetitions in infinite words with a low complexity
We first introduce some notation from combinatorics on words.
Let A be a finite set. The length of a word W on the alphabet A, that is, the numberof letters composing W , is denoted by |W |. If a is a letter and W a finite word, then
|W |a denotes the number of occurrences of the letter a in W . For any positive integerk, we write W k for the word
· · W,)W ·*+
ktimes123

On the expansion of some exponential periods in an integer base111

(the concatenation of the word W repeated k times). More generally, for any positive
real number x, W x denotes the word W *x+ W , , where W , is the prefix of W of length-(x −*x+)|W |.. Here, *x+ and -x. denote the floor and ceiling functions, respectively.
We now consider two exponents that measure repetitions occurring in infinite words.
They were introduced in [2,9] (see also [5]), respectively. The first exponent, the initial critical exponent of an infinite word a, is defined as the supremum of all positive
real numbers ρ for which there exist arbitrarily long prefixes V such that V ρ is also a
prefix of a. The second exponent, the Diophantine exponent of an infinite word a, isdefined as the supremum of the real numbers ρ for which there exist arbitrarily long
prefixes of a that can be factorized as U V w , where U and V are two finite words(U possibly empty) and w is a real number such that|U V w |≥ ρ.
|U V |The initial critical exponent and the Diophantine exponent of a are respectively
denoted by ice(a) and dio(a). Both exponents are clearly related by the following
relation
1 ≤ ice(a) ≤ dio(a) ≤ +∞.

(3)

Recall that the subword complexity function of an infinite word a = a1 a2 · · · is thefunction that associates with each positive integer n the positive integerp(a, n) := Card{(a j , a j+1 , . . . , a j+n−1 ), j ≥ 1}.
We now prove the following result.
Proposition 4 Let a be an infinite word such that the difference p(a, n)−n is bounded.
Thendio(a) > 2.
Proof Our first step is a reduction argument that was previously outlined by Allouche
in a similar context [6]. More precisely, we are going to prove that it is sufficient forour purpose to focus on the Diophantine exponent of Sturmian words. Sturmian words
are defined as the binary words s for which p(s, n) = n +1 for every positive integer n.
Recall that the set of Sturmian words is uncountable.
From now on, we fix an infinite word a = a1 a2 . . . defined over a finite alphabet A
and such that the difference p(a, n) − n is bounded. If a is eventually periodic, it iseasily checked that dio(a) is infinite. We can thus assume that a is aperiodic. Theorem
HM thus implies that the subword complexity function of a is increasing. Consequently, the difference p(a, n) − n is a nondecreasing sequence of bounded integers.
Such sequence is eventually constant and there thus exists two positive integers k andn 0 such thatp(a, n) = n + k, ∀n ≥ n 0 .

(4)

123

112

B. Adamczewski

By a result of Cassaigne [12], an infinite word a satisfies Equality (4) if and only
if there exist a finite word W , a Sturmian infinite word s defined over {0, 1}∗ and anonerasing morphism ϕ from the free monoid {0, 1}∗ into A∗ such thata = W ϕ(s).

(5)

Our infinite word a thus has such a decomposition and we claim thatdio(a) ≥ dio(s).

(6)

Set s = s1 s2 . . .. To prove that (6) holds, we only need a classical property of Sturmian words: each of the two letters occurring in a Sturmian word has a frequency. Thismeans that there exists a real number α in (0, 1) such that
lim

n→∞

|s1 s2 . . . sn |1= α,nand consequently,
lim

n→∞

|s1 s2 . . . sn |0= 1 − α.
n

The number α is always irrational and is termed the slope of s. It follows that|ϕ(s1 s2 . . . sn )| = δn + o(n),(7)

where δ := (α|ϕ(a)| + (1 − α)|ϕ(b)|). Here and in the sequel, o stands for the usual
Landau notation.
Now, let us assume that dio(s) = ρ for some positive real number ρ, and let ε be apositive real number. By definition of the Diophantine exponent, there exists an infinite
sequence of prefixes of s that can be factorized as Un Vnwn , with |Un Vnwn |/|Un Vn | >ρ − ε and such that the sequence (|Un Vn |)n≥1 increases. We then infer from (5) thata begins with the word
W ϕ(Un Vnwn ).
Set An = W ϕ(Un ) and Bn = ϕ(Vn ). There thus exists a positive real number rn suchthat
W ϕ(Un Vnwn ) = An Bnrn .
Since |Un Vn | can be chosen arbitrarily large, we infer from Equality (7) that
|W ϕ(Un Vnwn )| = δ|Un Vnwn | + o(|Un Vnwn |)and|ϕ(Un Vn )| = δ|Un Vn | + o(|Un Vn |).

123

On the expansion of some exponential periods in an integer base

113

Consequently,|An Bnrn |/|An Bn | ≥ ρ − 2ε,for every n large enough. This shows thatdio(a) ≥ ρ = dio(s)(8)

as desired.
We have now to distinguish two cases depending on the Diophantine properties ofthe slope α of the Sturmian words s. Let us denote by [0, m 1 , m 2 , . . .] the continued
fraction expansion of α.
First, let us assume that α has a bounded sequence of partial quotients, say bounded
by a positive integer M. Then there are only a finite number of distinct pairs (a j , a j+1 )and a fortiori of distinct triples (a j , a j+1 , a j+2 ). By the pigeonhole principle, there
exist either a pair of integers (s, t), 2 ≤ s ≤ M, 1 ≤ t ≤ M, such that (a j , a j+1 ) =(s, t) for infinitely many indices j, or there exist infinitely many indices j such that(a j , a j+1 , a j+2 ) = (1, 1, 1). In all cases, mixing Propositions 5.1 and 5.2 of [9] we
get thatice(s) ≥ 2 +1> 2.
2(M + 1)2 + 1

We thus infer from Inequality (3) thatdio(s) > 2.

(9)

On the other hand, if α has an unbounded sequence of partial quotients, it is shownin Proposition 11.1 of [3] thatdio(s) = +∞.

(10)

To sum up, (8)–(10) givedio(a) > 2,
1
0

concluding the proof.
3 Diophantine exponent and rational approximations

We now briefly recall some interplay between the Diophantine exponent and the irrationality exponent that can be found in [3]. Let ξ be a real number whose base-b
expansion is 0•a1 a2 . . . Set a = a1 a2 . . . Then the Diophantine exponent of a and theirrationality exponent of ξ are linked by the following inequality:
dio(a) ≤ µ(ξ ).

(11)

123

114

B. Adamczewski

Indeed, let us assume that the word a begins with a prefix of the form U V w . Set
q = b|U | (b|V | − 1). A simple computation shows that there exists an integer p suchthat
p/q = 0•U V V V · · ·Since ξ and p/q have the same first |U V w | digits, we obtain thatand thus""""1"ξ − p " <
w
"
"
|U
q
b V |
"
"
"
"
"ξ − p " < 1 ,"q " qρ

(12)

where ρ = |U V w |/|U V |. We do not claim here that p/q is written in lowest terms.
Actually, it may well happen that the gcd of p and q is quite large but (12) still holds inthat case. Inequality (11) then follows directly from the definition of both exponents.
We are now ready to conclude the proof of our main results.
Proof of Theorem 1 It is a straightforward consequence of Proposition 4 and Inequality (11).
10Proof of Corollary 2 It is known after Euler1 that the continued fraction expansion ofe has very special patterns; namelye = [2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, . . . , 1, 1, 2n, 1, 1 . . .].

(13)

From Euler’s formula, we can easily derive that the irrationality exponent of e satisfies µ(e) = 2, concluding the proof. Indeed, if qn and an respectively denote the nthconvergent and the nth partial quotient of a real number ξ , the theory of continued
fractions ensures that#$
log an+1.
µ(ξ ) = lim sup 2 +log qnn→∞10
Proof of Corollary 3 A basic result from the theory of continued fractions ensuresthat µ(ξ ) = 2 when ξ has a bounded sequence of partial quotients in its continued
fraction expansion (see for instance [15, Theorem 23, Page 36]).
1
0
1 Actually, this formula seems to have been discovered first by R. Cotes; Euler would be the first to give a

proof.

123

On the expansion of some exponential periods in an integer base

115

4 Comments
We end this note with few comments.
Remark 5 As already mentioned, the main ingredient in the proof of Theorem FM is ap-adic version of Roth’s theorem due to Ridout. Incidentally, our proof of Theorem 1
provides a new proof of Theorem FM. In particular, this shows that it can be obtainedwith the use of Roth’s theorem only. That is, p-adic considerations are unnecessary
to prove Theorem FM.
However, the use of some p-adic information by Ferenczi and Mauduit [13] turned
out to be of great importance since it led to the main lower bound for the complexityof algebraic irrational numbers obtained in [1].
Remark 6 It is likely that Proposition 4 could be improved to√3+ 5.
dio(a) ≥2(14)

This result would be optimal since the bound is reached for the Fibonacci word, whichis the most famous example among Sturmian words. We note that, as a consequenceof irrationality measures obtained by Baker [8], Inequality (14) would permit us toshow that the conclusion of Corollary 2 still holds if we replace the number e bylog(1 + 1/n), for every integer n ≥ 68. However, our approach would not permit
us to deduce a new lower bound for the complexity of expansions in integer basesof periods like π , log 2 or ζ (3) from (14) since the best known upper bounds for the√irrationality exponent of these numbers are all larger than (3 + 5)/2.
Remark 7 As a limitation of our approach, we quote that there are real numbers witha low complexity in some integer base but with an irrationality exponent equal to 2.
For instance, it was proved in [21] that the binary number
ξ :=

! 1
n≥0

22

n

has bounded partial quotients in its continued fraction expansion, while a classicaltheorem of Cobham implies that p(ξ, 2, n) = O(n) (see for instance Corollary 10.3.2
of [7, Page 304]). Actually, one can deduce from the proof of Lemma 2.4 in [14] themore precise upper bound p(ξ, 2, n) ≤ (2 + ln 3)n + 4, for every positive integer n.
Remark 8 It would also be very interesting to investigate the complexity of expansions of e and other contants from a computational point of view. In this direction,
we pose the following open question. Note that similar open questions were posed byAllouche and Shallit [7, Page 402, Problems 3 and 4].
Problem Prove that the decimal expansion of e cannot be produced by a finite automaton.

123

116

B. Adamczewski

Acknowledgments The author thanks the ANR for its support through the project “DyCoNum”–JCJC06
134288. He is grateful to Yann Bugeaud and Michel Waldschmidt for their comments on an earlier draftof this note. The author is also indebted to Tanguy Rivoal for suggesting relevant references and to theanonymous referee for his very careful reading that helped him to improve the presentation of the present
work.

References
1. Adamczewski, B., Bugeaud, Y.: On the complexity of algebraic numbers I. Expansions in integer
bases. Ann. Math. 165, 547–565 (2007)
2. Adamczewski, B., Bugeaud, Y.: Dynamics for β-shifts and Diophantine approximation. Ergod. Th.
Dyn. Sys. 27, 1695–1710 (2007)
3. Adamczewski, B., Bugeaud, Y.: Nombres réels de complexité sous-linéaire : mesures d’irrationalité etde transcendance, Preprint available at http://math.univ-lyon1.fr/~adamczew/ClasseCL.pdf
4. Adamczewski, B., Bugeaud, Y., Luca, F.: Sur la complexité des nombres algébriques. C. R. Acad. Sci.
Paris 339, 11–14 (2004)
5. Adamczewski, B., Cassaigne, J.: Diophantine properties of real numbers generated by finite automata. Compos. Math. 142, 1351–1372 (2006)
6. Allouche, J.-P.: Nouveaux résultats de transcendance de réels à développements non aléatoire. Gaz.
Math. 84, 19–34 (2000)
7. Allouche, J.-P., Shallit, J.O.: Automatic Sequences: Theory, Applications, Generalizations. Cambridge
University Press, London (2003)
8. Baker, A.: Approximations to the logarithms of certain rational numbers. Acta Arith. 10, 315–323(1964)
9. Berthé, V., Holton, C., Zamboni, L.Q.: Initial powers of Sturmian words. Acta Arith. 122, 315–347(2006)
10. Borel, É.: Les probabilités dénombrables et leurs applications arithmétiques. Rend. Circ. Mat.
Palermo 27, 247–271 (1909)
11. Bundschuh, P.: Irrationalitätsmaße für ea , a ) = 0 rational oder Liouville-Zahl. Math. Ann. 129,
229–242 (1971)
12. Cassaigne, J.: Sequences with grouped factors. In: DLT’97, Developments in Language Theory III,
Thessaloniki, Aristotle University of Thessaloniki, pp. 211–222 (1998)
13. Ferenczi, S., Mauduit, Ch.: Transcendence of numbers with a low complexity expansion. J. Number
Theory 67, 146–161 (1997)
14. Gheorghiciuc, I.: The subword complexity of a class of infinite binary words. Adv. Appl. Math. 39,
237–259 (2007)
15. Khintchine, A.Ya.: Continued Fractions. University of Chicago Press, Chicago (1964)
16. Komatsu, T.: Hurwitz continued fractions with confluent hypergeometric functions. Czechoslovak
Math. J. 57, 919–932 (2007)
17. Kontsevich, M., Zagier, D.: Periods. In: Mathematics unlimited—2001 and beyond, pp. 771–808.
Springer, Heidelberg (2001)
18. Morse, M., Hedlund, G.A.: Symbolic dynamics. Am. J. Math. 60, 815–866 (1938)
19. Ridout, D.: Rational approximations to algebraic numbers. Mathematika 4, 125–131 (1957)
20. Roth, K.F.: Rational approximations to algebraic numbers. Mathematika 2, 1–20 (1955) [corrigendum,
169]
21. Shallit, J.: Simple continued fractions for some irrational numbers. J. Number Theory 11, 209–217(1979)
22. Tasoev, B.G.: Rational approximations to certain numbers. Mat. Zametki 67 931–937 (2000) [translation in Math. Notes 67, 786–791 (2000)]123