The Mathematical Intelligencer
ISSN 0343-6993
Volume 35
Number 1
Math Intelligencer (2013) 35:42-60
DOI 10.1007/s00283-012-9340-x
Walking on Real Numbers
Francisco J. Aragón Artacho, David
H. Bailey, Jonathan M. Borwein & Peter
B. Borwein
1 23
Your article is protected by copyright and all
rights are held exclusively by Springer Science
+Business Media New York. This e-offprint is
for personal use only and shall not be self-
archived in electronic repositories. If you
wish to self-archive your work, please use the
accepted author’s version for posting to your
own website or your institution’s repository.
You may further deposit the accepted author’s
version on a funder’s repository at a funder’s
request, provided it is not made publicly
available until 12 months after publication.
Walking on Real
Numbers
F
RANCISCO
J. A
RAGO
´
N
A
RTACHO
,D
AVID
H. B
AILEY
,J
ONATHAN
M. B
ORWEIN
,
AND
P
ETER
B. B
ORWEIN
T
T
he digit expansions of
p
;
e
;
ffiffiffi
2
p
, and other mathemat-
ical constants have fascinated mathematicians from
the dawn of history. Indeed, one prime motivation
for computing and analyzing digits of
p
is to explore the
age-old question of whether and why these digits appear
‘‘random.’’ The first computation on ENIAC in 1949 of
p
to
2037 decimal places was proposed by John von Neumann
so as to shed some light on the distribution of
p
(and of
e
)
[
15
, pg. 277–281].
One key question of some significance is whether (and
why) numbers such as
p
and
e
are ‘‘normal.’’ A real constant
a
is
b
-normal if, given the positive integer
b
C
2, every
m
-long
string of base-
b
digits appears in the base-
b
expansion of
a
with precisely the expected limiting frequency 1/
b
m
.Itisa
well-established, albeit counterintuitive, fact that given an
integer
b
C
2, almost all real numbers, in the measure theory
sense, are
b
-normal. What’s more, almost all real numbers are
b
-normal simultaneously for all positive integer bases (a
property known as ‘‘absolutely normal’’).
Nonetheless, it has been surprisingly difficult to prove
normality for well-known mathematical constants for any
given base
b
, much less all bases simultaneously. The first
constant to be proven 10-normal is the Champernowne
number, namely the constant 0
:
12345678910111213141516
…
,
produced by concatenating the decimal representation of all
positive integers in order. Some additional results of this sort
were established in the 1940s by Copeland and Erd
}
os [
26
].
At present, normality proofs are not available for any well-
known constant such as
p
;
e
;
log 2
;
ffiffiffi
2
p
. We do not even know,
say, that a 1 appears one-half of the time, in the limit, in the
binary expansion of
ffiffiffi
2
p
(although it certainly appears to), nor
do we know for certain that a 1 appears infinitely often in the
decimal expansion of
ffiffiffi
2
p
. For that matter, it is widely believed
that
every
irrational algebraic number (i.e., every irrational root
of an algebraic polynomial with integer coefficients) is
b
-normal to all positive integer bases
b
, but there is no proof,
not for any specific algebraic number to any specific base.
In 2002, one of the present authors (Bailey) and Richard
Crandall showed that given a real number
r
in [0,1), with
r
k
denoting the
k
-th binary digit of
r
, the real number
a
2
;
3
ð
r
Þ
:
¼
X
1
k
¼
1
1
3
k
2
3
k
þ
r
k
ð
1
Þ
is 2-normal. It can be seen that if
r
=
s
, then
a
2,3
(
r
)
=
a
2,3
(
s
),
so that these constants are all distinct. Since
r
can range over
the unit interval, this class of constants is uncountable. So, for
example, the constant
a
2
;
3
¼
a
2
;
3
ð
0
Þ¼
P
k
1
1
=
ð
3
k
2
3
k
Þ¼
0
:
0418836808315030
...
is provably 2-normal (this special
case was proven by Stoneham in 1973 [
43
]). A similar result
applies if 2 and 3 in formula (
1
) are replaced by any pair of
coprime integers (
b
,
c
) with
b
C
2 and
c
C
2[
10
]. More
recently, Bailey and Michal Misiurewicz were able to
establish 2-normality of
a
2,3
by a simpler argument, by uti-
lizing a ‘‘hot spot’’ lemma proven using ergodic theory
methods [
11
].
In 2004, two of the present authors (Bailey and Jonathan
Borwein), together with Richard Crandall and Carl Pomer-
ance, proved the following: If a positive real
y
has algebraic
degree
D
[
1, then the number #(
y
,
N
) of 1-bits in the binary
expansion of
y
through bit position
N
satisfies #(
y
,
N
)
[
CN
1/
D
,
for a positive number
C
(depending on
y
) and all sufficiently
large
N
[
5
]. A related result has been obtained by Hajime
Kaneko of Kyoto University in Japan [
37
]. However, these
results fall far short of establishing
b
-normality for any irra-
tional algebraic in any base
b
, even in the single-digit sense.
Supported in part by the Director, Office of Computational and Technology Research, Division of Mathematical, Information, and Computational Scien
ces of the U.S.
Department of Energy, under contract number DE-AC02-05CH11231.
42
THE MATHEMATICAL INTELLIGENCER
2012 Springer Science+Business Media New York
DOI 10.1007/s00283-012-9340-x
Author’s
personal
copy
1 Twenty-First Century Approaches
to the Normality Problem
In spite of such developments, there is a sense in the field that
more powerful techniques must be brought to bear on this
problem before additional substantial progress can be
achieved. One idea along this line is to study directly the
decimal expansions (or expansions in other number bases) of
various mathematical constants by applying some techniques
of scientific visualization and large-scale data analysis.
In a recent paper [
4
], by accessing the results of several
extremely large recent computations [
46
,
47
], the authors tes-
ted the first roughly four trillion hexadecimal digits of
p
by
means of a Poisson process model: in this model, it is
extraordinarily unlikely that
p
is not normal base 16, given its
initial segment. During that work, the authors of [
4
], like many
others, investigated visual methods of representing their large
mathematical data sets. Their chosen tool was to represent
these data as walks in the plane.
In this work, based in part on sources such as [
22
,
23
,
21
,
19
,
14
], we make a more rigorous and quantitative study of these
walks on numbers. We pay particular attention to
p
, for which
we have copious data and which—despite the fact that its
digits can be generated by simple algorithms—behaves
remarkably ‘‘randomly.’’
The organization of the article is as follows. In Section
2
we
describe and exhibit uniform walks on various numbers, both
rational and irrational, artificial and natural. In the next two
sections, we look at quantifying two of the best-known fea-
tures of random walks: the expected distance traveled after
N
steps (Section
3
) and the number of sites visited (Section
4
)
In Section
5
we describe two classes for which normality and
nonnormality results are known, and one for which we have
only surmise. In Section
6
we show various examples and
leave some open questions. Finally, in Appendix
7
we collect
the numbers we have examined, with concise definitions and
a few digits in various bases.
2 Walking on Numbers
2.1 Random and Deterministic Walks
One of our tasks is to compare deterministic walks (such as
those generated by the digit expansion of a constant) with
pseudorandom walks of the same length. For example, in
Figure
1
we draw a uniform pseudorandom walk with one
million base-4 steps, where at each step the path moves one
unit east, north, west, or south, depending on the whether the
pseudorandom iterate at that position is 0, 1, 2, or 3. The color
indicates the path followed by the walk—it is shifted up the
spectrum (red-orange-yellow-green-cyan-blue-purple-red)
following an HSV scheme with
S
and
V
equal to one. The HSV
(hue, saturation, and value) model is a cylindrical-coordinate
representation that yields a rainbow-like range of colors.
Figure 1.
A uniform pseudorandom walk.
……………………………………………………………………………………………………………….
……………………..
AUTHORS
FRANCISCO J. ARAGO
´
N ARTACHO
earned his Ph.D. in optimization in 2007 at
the University of Murcia, Spain. After work-
ing for a business in Madrid for a year, he
took a postdoctoral position at the Univer-
sity of Alicante, supported by the program
‘‘Juan de la Cierva.’’ In 2011, he became a
Research Associate at the Priority Research
Centre for Computer-Assisted Research
Mathematics and its Applications (CARMA),
University of Newcastle, Australia, under the
direction of Jonathan Borwein, with whom
he’s currently collaborating on several
projects.
Centre for Computer Assisted Research
Mathematics and its Applications
(CARMA)
Volume 35
Number 1
Math Intelligencer (2013) 35:42-60
DOI 10.1007/s00283-012-9340-x
Walking on Real Numbers
Francisco J. Aragón Artacho, David
H. Bailey, Jonathan M. Borwein & Peter
B. Borwein
1 23
Your article is protected by copyright and all
rights are held exclusively by Springer Science
+Business Media New York. This e-offprint is
for personal use only and shall not be self-
archived in electronic repositories. If you
wish to self-archive your work, please use the
accepted author’s version for posting to your
own website or your institution’s repository.
You may further deposit the accepted author’s
version on a funder’s repository at a funder’s
request, provided it is not made publicly
available until 12 months after publication.
Walking on Real
Numbers
F
RANCISCO
J. A
RAGO
´
N
A
RTACHO
,D
AVID
H. B
AILEY
,J
ONATHAN
M. B
ORWEIN
,
AND
P
ETER
B. B
ORWEIN
T
T
he digit expansions of
p
;
e
;
ffiffiffi
2
p
, and other mathemat-
ical constants have fascinated mathematicians from
the dawn of history. Indeed, one prime motivation
for computing and analyzing digits of
p
is to explore the
age-old question of whether and why these digits appear
‘‘random.’’ The first computation on ENIAC in 1949 of
p
to
2037 decimal places was proposed by John von Neumann
so as to shed some light on the distribution of
p
(and of
e
)
[
15
, pg. 277–281].
One key question of some significance is whether (and
why) numbers such as
p
and
e
are ‘‘normal.’’ A real constant
a
is
b
-normal if, given the positive integer
b
C
2, every
m
-long
string of base-
b
digits appears in the base-
b
expansion of
a
with precisely the expected limiting frequency 1/
b
m
.Itisa
well-established, albeit counterintuitive, fact that given an
integer
b
C
2, almost all real numbers, in the measure theory
sense, are
b
-normal. What’s more, almost all real numbers are
b
-normal simultaneously for all positive integer bases (a
property known as ‘‘absolutely normal’’).
Nonetheless, it has been surprisingly difficult to prove
normality for well-known mathematical constants for any
given base
b
, much less all bases simultaneously. The first
constant to be proven 10-normal is the Champernowne
number, namely the constant 0
:
12345678910111213141516
…
,
produced by concatenating the decimal representation of all
positive integers in order. Some additional results of this sort
were established in the 1940s by Copeland and Erd
}
os [
26
].
At present, normality proofs are not available for any well-
known constant such as
p
;
e
;
log 2
;
ffiffiffi
2
p
. We do not even know,
say, that a 1 appears one-half of the time, in the limit, in the
binary expansion of
ffiffiffi
2
p
(although it certainly appears to), nor
do we know for certain that a 1 appears infinitely often in the
decimal expansion of
ffiffiffi
2
p
. For that matter, it is widely believed
that
every
irrational algebraic number (i.e., every irrational root
of an algebraic polynomial with integer coefficients) is
b
-normal to all positive integer bases
b
, but there is no proof,
not for any specific algebraic number to any specific base.
In 2002, one of the present authors (Bailey) and Richard
Crandall showed that given a real number
r
in [0,1), with
r
k
denoting the
k
-th binary digit of
r
, the real number
a
2
;
3
ð
r
Þ
:
¼
X
1
k
¼
1
1
3
k
2
3
k
þ
r
k
ð
1
Þ
is 2-normal. It can be seen that if
r
=
s
, then
a
2,3
(
r
)
=
a
2,3
(
s
),
so that these constants are all distinct. Since
r
can range over
the unit interval, this class of constants is uncountable. So, for
example, the constant
a
2
;
3
¼
a
2
;
3
ð
0
Þ¼
P
k
1
1
=
ð
3
k
2
3
k
Þ¼
0
:
0418836808315030
...
is provably 2-normal (this special
case was proven by Stoneham in 1973 [
43
]). A similar result
applies if 2 and 3 in formula (
1
) are replaced by any pair of
coprime integers (
b
,
c
) with
b
C
2 and
c
C
2[
10
]. More
recently, Bailey and Michal Misiurewicz were able to
establish 2-normality of
a
2,3
by a simpler argument, by uti-
lizing a ‘‘hot spot’’ lemma proven using ergodic theory
methods [
11
].
In 2004, two of the present authors (Bailey and Jonathan
Borwein), together with Richard Crandall and Carl Pomer-
ance, proved the following: If a positive real
y
has algebraic
degree
D
[
1, then the number #(
y
,
N
) of 1-bits in the binary
expansion of
y
through bit position
N
satisfies #(
y
,
N
)
[
CN
1/
D
,
for a positive number
C
(depending on
y
) and all sufficiently
large
N
[
5
]. A related result has been obtained by Hajime
Kaneko of Kyoto University in Japan [
37
]. However, these
results fall far short of establishing
b
-normality for any irra-
tional algebraic in any base
b
, even in the single-digit sense.
Supported in part by the Director, Office of Computational and Technology Research, Division of Mathematical, Information, and Computational Scien
ces of the U.S.
Department of Energy, under contract number DE-AC02-05CH11231.
42
THE MATHEMATICAL INTELLIGENCER
2012 Springer Science+Business Media New York
DOI 10.1007/s00283-012-9340-x
Author’s
personal
copy
1 Twenty-First Century Approaches
to the Normality Problem
In spite of such developments, there is a sense in the field that
more powerful techniques must be brought to bear on this
problem before additional substantial progress can be
achieved. One idea along this line is to study directly the
decimal expansions (or expansions in other number bases) of
various mathematical constants by applying some techniques
of scientific visualization and large-scale data analysis.
In a recent paper [
4
], by accessing the results of several
extremely large recent computations [
46
,
47
], the authors tes-
ted the first roughly four trillion hexadecimal digits of
p
by
means of a Poisson process model: in this model, it is
extraordinarily unlikely that
p
is not normal base 16, given its
initial segment. During that work, the authors of [
4
], like many
others, investigated visual methods of representing their large
mathematical data sets. Their chosen tool was to represent
these data as walks in the plane.
In this work, based in part on sources such as [
22
,
23
,
21
,
19
,
14
], we make a more rigorous and quantitative study of these
walks on numbers. We pay particular attention to
p
, for which
we have copious data and which—despite the fact that its
digits can be generated by simple algorithms—behaves
remarkably ‘‘randomly.’’
The organization of the article is as follows. In Section
2
we
describe and exhibit uniform walks on various numbers, both
rational and irrational, artificial and natural. In the next two
sections, we look at quantifying two of the best-known fea-
tures of random walks: the expected distance traveled after
N
steps (Section
3
) and the number of sites visited (Section
4
)
In Section
5
we describe two classes for which normality and
nonnormality results are known, and one for which we have
only surmise. In Section
6
we show various examples and
leave some open questions. Finally, in Appendix
7
we collect
the numbers we have examined, with concise definitions and
a few digits in various bases.
2 Walking on Numbers
2.1 Random and Deterministic Walks
One of our tasks is to compare deterministic walks (such as
those generated by the digit expansion of a constant) with
pseudorandom walks of the same length. For example, in
Figure
1
we draw a uniform pseudorandom walk with one
million base-4 steps, where at each step the path moves one
unit east, north, west, or south, depending on the whether the
pseudorandom iterate at that position is 0, 1, 2, or 3. The color
indicates the path followed by the walk—it is shifted up the
spectrum (red-orange-yellow-green-cyan-blue-purple-red)
following an HSV scheme with
S
and
V
equal to one. The HSV
(hue, saturation, and value) model is a cylindrical-coordinate
representation that yields a rainbow-like range of colors.
Figure 1.
A uniform pseudorandom walk.
……………………………………………………………………………………………………………….
……………………..
AUTHORS
FRANCISCO J. ARAGO
´
N ARTACHO
earned his Ph.D. in optimization in 2007 at
the University of Murcia, Spain. After work-
ing for a business in Madrid for a year, he
took a postdoctoral position at the Univer-
sity of Alicante, supported by the program
‘‘Juan de la Cierva.’’ In 2011, he became a
Research Associate at the Priority Research
Centre for Computer-Assisted Research
Mathematics and its Applications (CARMA),
University of Newcastle, Australia, under the
direction of Jonathan Borwein, with whom
he’s currently collaborating on several
projects.
Centre for Computer Assisted Research
Mathematics and its Applications
(CARMA)
DAVID H. BAILEY
is a Senior Scientist at
Lawrence Berkeley National Laboratory.
Before coming to the Berkeley Lab in 1998,
he was at NASA’s Ames Research Center for
14 years. Bailey has received the Chauvenet
Prize from the Mathematical Association of
America, the Sidney Fernbach Award from
the IEEE Computer Society, and the Gordon
Bell Prize from the Association for Computing
Machinery. He is the author of five books,
including
Mathematics by Experiment: Plausi-
ble Reasoning in the 21st Century
, coau-
thored with Jonathan Borwein.
Lawrence Berkeley National Laboratory
Berkeley, CA 94720
USA
2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013
43
Author’s
personal
copy
The rational numbers
Q
1and
Q
2 represent the two possi-
bilities when one computes a walk on a rational number:
either the walk is bounded as in Figure
2
(a) (for any walk with
more than 440 steps one obtains the same plot), or it is
unbounded but repeating some pattern after a finite number
of digits as in Figure
2
(b).
Of course, not all rational numbers are that easily identified
by plotting their walks. It is possible to create a rational
number whose period is of any desired length. For example,
the following rational numbers from [
39
],
Q
3
¼
3624360069
7000000001
and
Q
4
¼
123456789012
1000000000061
;
have base-10 periodic parts with length 1,750,000,000 and
1,000,000,000,060, respectively. A walk on the first million
digits of both numbers is plotted in Figure
3
. These huge
periods derive from the fact that the numerators and
denominators of
Q
3 and
Q
4 are relatively prime, and the
denominators are not congruent to 2 or 5. In such cases, the
period
P
is simply the discrete logarithm of the denomi-
nator
D
modulo 10; or, in other words,
P
is the smallest
n
such that 10
n
mod
D
¼
1.
Graphical walks can be generated in a similar way for other
constants in various bases—see Figures
2
through
7
.Where
the base
b
C
3, the base-
b
digits can be used to a select, as a
direction, the corresponding base-
b
complex root of unity—a
multiple of 120
for base three, a multiple of 90
for base four, a
multiple of 72
for base 5, etc. We generally treat the case
b
=
2 as a base-4 walk, by grouping together pairs of base-2
digits (we could render a base-2 walk on a line, but the
resulting images would be much less interesting). In Figure
4
the origin has been marked, but since this information is not
that important for our purposes, and can be approximately
deduced by the color in most cases, it is not indicated in the
others. The color scheme for Figures
2
through
7
is the same as
the above, except that Figure
6
is colored to indicate the
number of returns to each point.
2.2 Normal Numbers as Walks
As noted previously, proving normality for specific constants
of interest in mathematics has proven remarkably difficult.
The tenor of current knowledge in this arena is illustrated by
[
45
,
14
,
34
,
38
,
40
,
39
,
44
]. It is useful to know that, while small
in measure, the ‘‘absolutely abnormal’’ or ‘‘absolutely non-
normal’’ real numbers (namely those that are not
b
-normal for
any integer
b
) are residual in the sense of topological category
[
1
]. Moreover, the Hausdorff–Besicovitch dimension of the set
of real numbers having no asymptotic frequencies is equal to
1. Likewise the set of Liouville numbers has measure zero but
is of the second category [
18
,p.352].
(a)
(b)
Figure 2.
Walks on the rational numbers
Q
1 and
Q
2.
Figure 4.
A million-step base-4 walk on
e
.
(a)(b)
Figure 3.
Walks on the first million base-10 digits of the rationals
Q
3 and
Q
4 from [
39
].
2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013
45
Author’s
personal
copy
One question that has possessed mathematicians for cen-
turies is whether
p
is normal. Indeed, part of the original
motivation of the present study was to develop new tools for
investigating this age-old problem.
In Figure
5
we show a walk on the first 100 billion base-4
digits of
p
. This may be viewed dynamically in more detail
online at
is a Senior Scientist at
Lawrence Berkeley National Laboratory.
Before coming to the Berkeley Lab in 1998,
he was at NASA’s Ames Research Center for
14 years. Bailey has received the Chauvenet
Prize from the Mathematical Association of
America, the Sidney Fernbach Award from
the IEEE Computer Society, and the Gordon
Bell Prize from the Association for Computing
Machinery. He is the author of five books,
including
Mathematics by Experiment: Plausi-
ble Reasoning in the 21st Century
, coau-
thored with Jonathan Borwein.
Lawrence Berkeley National Laboratory
Berkeley, CA 94720
USA
2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013
43
Author’s
personal
copy
The rational numbers
Q
1and
Q
2 represent the two possi-
bilities when one computes a walk on a rational number:
either the walk is bounded as in Figure
2
(a) (for any walk with
more than 440 steps one obtains the same plot), or it is
unbounded but repeating some pattern after a finite number
of digits as in Figure
2
(b).
Of course, not all rational numbers are that easily identified
by plotting their walks. It is possible to create a rational
number whose period is of any desired length. For example,
the following rational numbers from [
39
],
Q
3
¼
3624360069
7000000001
and
Q
4
¼
123456789012
1000000000061
;
have base-10 periodic parts with length 1,750,000,000 and
1,000,000,000,060, respectively. A walk on the first million
digits of both numbers is plotted in Figure
3
. These huge
periods derive from the fact that the numerators and
denominators of
Q
3 and
Q
4 are relatively prime, and the
denominators are not congruent to 2 or 5. In such cases, the
period
P
is simply the discrete logarithm of the denomi-
nator
D
modulo 10; or, in other words,
P
is the smallest
n
such that 10
n
mod
D
¼
1.
Graphical walks can be generated in a similar way for other
constants in various bases—see Figures
2
through
7
.Where
the base
b
C
3, the base-
b
digits can be used to a select, as a
direction, the corresponding base-
b
complex root of unity—a
multiple of 120
for base three, a multiple of 90
for base four, a
multiple of 72
for base 5, etc. We generally treat the case
b
=
2 as a base-4 walk, by grouping together pairs of base-2
digits (we could render a base-2 walk on a line, but the
resulting images would be much less interesting). In Figure
4
the origin has been marked, but since this information is not
that important for our purposes, and can be approximately
deduced by the color in most cases, it is not indicated in the
others. The color scheme for Figures
2
through
7
is the same as
the above, except that Figure
6
is colored to indicate the
number of returns to each point.
2.2 Normal Numbers as Walks
As noted previously, proving normality for specific constants
of interest in mathematics has proven remarkably difficult.
The tenor of current knowledge in this arena is illustrated by
[
45
,
14
,
34
,
38
,
40
,
39
,
44
]. It is useful to know that, while small
in measure, the ‘‘absolutely abnormal’’ or ‘‘absolutely non-
normal’’ real numbers (namely those that are not
b
-normal for
any integer
b
) are residual in the sense of topological category
[
1
]. Moreover, the Hausdorff–Besicovitch dimension of the set
of real numbers having no asymptotic frequencies is equal to
1. Likewise the set of Liouville numbers has measure zero but
is of the second category [
18
,p.352].
(a)
(b)
Figure 2.
Walks on the rational numbers
Q
1 and
Q
2.
Figure 4.
A million-step base-4 walk on
e
.
(a)(b)
Figure 3.
Walks on the first million base-10 digits of the rationals
Q
3 and
Q
4 from [
39
].
2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013
45
Author’s
personal
copy
One question that has possessed mathematicians for cen-
turies is whether
p
is normal. Indeed, part of the original
motivation of the present study was to develop new tools for
investigating this age-old problem.
In Figure
5
we show a walk on the first 100 billion base-4
digits of
p
. This may be viewed dynamically in more detail
online at
http://gigapan.org/gigapans/106803
, where the full-
sized image has a resolution of 372,224
9
290,218 pixels
(108.03 gigapixels in total). This must be one of the largest
mathematical images ever produced. The computations for
creating this image took roughly a month, where several parts
of the algorithm were run in parallel with 20 threads on
CARMA’s MacPro cluster.
By contrast, Figure
6
exhibits a 100 million base-4 walk on
p
, where the color is coded by the number of returns to the
point. In [
4
], the authors empirically tested the normality of its
first roughly four trillion hexadecimal (base-16) digits using a
Poisson process model, and they concluded that, according to
this test, it is ‘‘extraordinarily unlikely’’ that
p
is not 16-normal
(of course, this result does not pretend to be a proof).
In what follows, we propose various methods of analyzing
real numbers and visualizing them as walks. Other methods
widely used to visualize numbers include the matrix repre-
sentations shown in Figure
8
, where each pixel is colored
depending on the value of the digit to the right of the decimal
point, following a left-to-right up-to-down direction (in base 4
the colors used for 0, 1, 2, and 3 are red, green, cyan, and
purple, respectively). This method has been mainly used to
visually test ‘‘randomness.’’ In some cases, it clearly shows the
features of some numbers; as for small periodic rationals, see
Figure
8
(c). This scheme also shows the nonnormality of the
number
a
2,3
—see Figure
8
(d) (where the horizontal red bands
correspond to the strings of zeroes)—and it captures some of
the special peculiarities of the Champernowne’s number
C
4
(normal) in Figure
8
(e). Nevertheless, it does not reveal
the apparently nonrandom behavior of numbers such
as the Erd
}
os–Borwein constant; compare Figure
8
(f) with
Figure
7
(e). See also Figure
21
.
As we will see in what follows, the study of normal numbers
and suspected normal numbers as walks will permit us to
compare them with true random (or pseudorandom) walks,
obtaining in this manner a new way to empirically test ‘‘ran-
domness’’ in their digits.
3 Expected Distance to the Origin
Let
b
2f
3
;
4
;
…
g
be a fixed base, and let
X
1
;
X
2
;
X
3
;
…
be a
sequence of independent bivariate discrete random variables
whose common probability distribution is given by
PX
¼
cos
2
p
b
k
sin
2
p
b
k
¼
1
b
for
k
¼
1
;
…
;
b
:
ð
2
Þ
Then the random variable
S
N
:
=
P
m
=1
N
X
m
represents a
base-
b
random walk in the plane of
N
steps.
The following result on the asymptotic expectation of the
distance to the origin of a base-
b
random walk is probably
known, but being unable to find any reference in the litera-
ture, we provide a proof.
T
HEOREM
3.1
The expected distance to the origin of a
base-b random walk of N steps is asymptotically equal
to
ffiffiffiffiffiffiffi
p
N
p
=
2.
P
ROOF
.
By the multivariate central limit theorem, the ran-
dom variable 1
=
ffiffiffiffi
N
p
P
N
m
¼
1
ð
X
m
l
Þ
is asymptotically
bivariate normal with mean
0
0
and covariance matrix
M
,
where
l
is the two-dimensional mean vector of
X
and
M
is its
2
9
2 covariance matrix. By applying Lagrange’s trigono-
metric identities, one obtains
l
¼
1
b
P
b
k
¼
1
cos
2
p
b
k
1
b
P
b
k
¼
1
sin
2
p
b
k
!
¼
1
b
1
2
þ
sin
ð
b
þ
1
=
2
Þ
2
p
b
ðÞ
2 sin
ð
p
=
b
Þ
1
2
cot
ð
p
=
b
Þ
cos
ð
b
þ
1
=
2
Þ
2
p
b
ðÞ
2 sin
ð
p
=
b
Þ
0
B
@
1
C
A
¼
0
0
:
ð
3
Þ
Thus,
M
¼
1
b
P
b
k
¼
1
cos
2
2
p
b
k
P
b
k
¼
1
cos
2
p
b
k
sin
2
p
b
k
P
b
k
¼
1
cos
2
p
b
k
sin
2
p
b
k
P
b
k
¼
1
sin
2
2
p
b
k
“#
:
ð
4
Þ
Figure 5.
A walk on the first 100 billion base-4 digits of
p
(normal?).
Figure 6.
A walk on the first 100 million base-4 digits of
p
, col-
ored by number of returns (normal?). Color follows an HSV model
(green-cyan-blue-purple-red) depending on the number of returns
to each point (where the maxima show a tinge of pink/red).
46
THE MATHEMATICAL INTELLIGENCER
Author’s
personal
copy
Since
X
b
k
¼
1
cos
2
2
p
b
k
¼
X
b
k
¼
1
1
þ
cos
4
p
b
k
2
¼
b
2
;
X
b
k
¼
1
sin
2
2
p
b
k
¼
X
b
k
¼
1
1
cos
4
p
b
k
2
¼
b
2
;
X
b
k
¼
1
cos
2
p
b
k
sin
2
p
b
k
¼
X
b
k
¼
1
sin
4
p
b
k
2
¼
0
;
ð
5
Þ
formula (
4
) reduces to
M
¼
1
2
0
0
1
2
:
ð
6
Þ
Hence,
S
N
=
ffiffiffiffi
N
p
is asymptotically bivariate normal with mean
0
0
and covariance matrix
M
. Because its components
ð
S
N
1
=
ffiffiffiffi
N
p
;
S
N
2
=
ffiffiffiffi
N
p
Þ
T
are uncorrelated, then they are inde-
pendent random variables, whose distribution is (univariate)
(a)(b)
(c)(d)
(e)(f)
Figure 7.
Walks on various numbers in different bases.
2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013
47
Author’s
personal
copy
normal with mean 0 and variance 1/2. Therefore, the random
variable
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
ffiffiffi
2
p
ffiffiffiffi
N
p
S
N
1
2
þ
ffiffiffi
2
p
ffiffiffiffi
N
p
S
N
2
2
s
ð
7
Þ
converges in distribution to a
v
random variable with two
degrees of freedom. Then, for
N
sufficiently large,
E
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
ð
S
N
1
Þ
2
þð
S
N
2
Þ
2
q
¼
ffiffiffiffi
N
p
ffiffiffi
2
p
E
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
ffiffiffi
2
p
ffiffiffiffi
N
p
S
N
1
2
þ
ffiffiffi
2
p
ffiffiffiffi
N
p
S
N
2
2
s
0
@
1
A
ffiffiffiffi
N
p
ffiffiffi
2
p
C
ð
3
=
2
Þ
C
ð
1
Þ
¼
ffiffiffiffiffiffiffi
p
N
p
2
;
ð
8
Þ
where
E
ð Þ
stands for the expectation of a random
variable. Therefore, the expected distance to the
(a)(b)
(c)(d)
(e)(f)
Figure 8.
Horizontal color representation of a million digits of various numbers.
48
THE MATHEMATICAL INTELLIGENCER
Author’s
personal
copy
origin of the random walk is asymptotically equal to
ffiffiffiffiffiffiffi
p
N
p
=
2.
As a consequence of this result, for any random walk of
N
steps in any given base, the expectation of the distance to the
origin multiplied by 2
=
ffiffiffiffiffiffiffi
p
N
p
(which we will call
normalized
distance
to the origin) must approach 1 as
N
goes to infinity.
Therefore, for a ‘‘sufficiently’’ big random walk, one would
expect that the arithmetic mean of the normalized distances
(which will be called
average normalized distance
to the
origin) should be close to 1.
We have created a sample of 10,000 (pseudo)random
walks base-4 of one million points each in Python
1
,andwe
have computed their average normalized distance to the ori-
gin. The arithmetic mean of these numbers for the mentioned
sample of pseudorandom walks is 1.0031, whereas its stan-
dard deviation is 0.3676, so the asymptotic result fits quite well.
We have also computed the normalized distance to the origin
of 10,000 walks of one million steps each generated by the first
ten billion digits of
p
. The resulting arithmetic mean is 1.0008,
whereas the standard deviation is 0.3682. In Table
1
we show
the average normalized distance to the origin of various
numbers. There are several surprises in there data, such as the
Table 1. Average of the normalized distance to the origin of the walk of
various constants in different bases
Number Base Steps Average normalized
distance to the origin
Normal
Mean of 10,000
random walks
4 1,000,000 1.00315 Yes
Mean of 10,000 walks
on the digits of
p
4 1,000,000 1.00083 ?
a
2,3
3 1,000,000 0.89275 ?
a
2,3
4 1,000,000 0.25901 Yes
a
2,3
5 1,000,000 0.88104 ?
a
2,3
6 1,000,000 108.02218 No
a
4,3
3 1,000,000 1.07223 ?
a
4,3
4 1,000,000 0.24268 Yes
a
4,3
6 1,000,000 94.54563 No
a
4,3
12 1,000,000 371.24694 No
a
3,5
3 1,000,000 0.32511 Yes
a
3,5
5 1,000,000 0.85258 ?
a
3,5
15 1,000,000 370.93128 No
p
4 1,000,000 0.84366 ?
p
6 1,000,000 0.96458 ?
p
10 1,000,000 0.82167 ?
p
10 10,000,000 0.56856 ?
p
10 100,000,000 0.94725 ?
p
10 1,000,000,000 0.59824 ?
e
4 1,000,000 0.59583 ?
ffiffiffi
2
p
4 1,000,000 0.72260 ?
log 2 4 1,000,000 1.21113 ?
Champernowne
C
10
10 1,000,000 59.91143 Yes
EB
(2) 4 1,000,000 6.95831 ?
CE
(10) 4 1,000,000 0.94964 ?
Rational number
Q
1
4 1,000,000 0.04105 No
Rational number
Q
2
4 1,000,000 58.40222 No
Euler constant
c
10 1,000,000 1.17216 ?
Fibonacci
F
10 1,000,000 1.24820 ?
f
ð
2
Þ¼
p
2
6
4 1,000,000 1.57571 ?
f
ð
3
Þ
4 1,000,000 1.04085 ?
Catalan’s constant
G
4 1,000,000 0.53489 ?
Thue–Morse
TM
2
4 1,000,000 531.92344 No
Paper-folding
P
4 1,000,000 0.01336 No
Table 2. Number of points visited in various
N
-step base-4 walks. The
values of the two last columns are upper and lower bounds on the
expectation of the number of distinct sites visited during an
N
-step
random walk; see [31, Theorem 2] and [
32
]
Number Steps Sites visited Bounds on the expectation
of sites visited by a random
walk
Lower
bound
Upper
bound
Mean of 10,000
random walks
1,000,000 202,684 199,256 203,060
Mean of 10,000
walks on the
digits of
p
1,000,000 202,385 199,256 203,060
a
2,3
1,000,000 95,817 199,256 203,060
a
4,3
1,000,000 68,613 199,256 203,060
a
3,2
1,000,000 195,585 199,256 203,060
p
1,000,000 204,148 199,256 203,060
p
10,000,000 1,933,903 1,738,645 1,767,533
p
100,000,000 16,109,429 15,421,296 15,648,132
p
1,000,000,000 138,107,050 138,552,612 140,380,926
e
1,000,000 176,350 199,256 203,060
ffiffiffi
2
p
1,000,000 200,733 199,256 203,060
log 2 1,000,000 214,508 199,256 203,060
Champernowne
C
4
1,000,000 548,746 199,256 203,060
EB
(2) 1,000,000 279,585 199,256 203,060
CE(10) 1,000,000 190,239 199,256 203,060
Rational number
Q
1
1,000,000 378 199,256 203,060
Rational number
Q
2
1,000,000 939,322 199,256 203,060
Euler constant
c
1,000,000 208,957 199,256 203,060
f
ð
2
Þ
1,000,000 188,808 199,256 203,060
f
ð
3
Þ
1,000,000 221,598 199,256 203,060
Catalan’s
constant
G
1,000,000 195,853 199,256 203,060
TM
2
1,000,000 1,000,000 199,256 203,060
Paper-folding
P
1,000,000 21 199,256 203,060
1
Python uses the Mersenne Twister as the core generator and produces 53-bit precision floats, with a period of 2
19937
-
1
&
10
6002
. Compare the length of this period to the
comoving distance from Earth to the edge of the observable universe in any direction, which is approximately
4
:
6
10
37
nanometers, or to the number of protons in the universe,
which is approximately 10
80
.
2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013
49
Author’s
personal
copy
fact that by this measure, Champernowne’s number
C
10
is far
from what is expected of a truly ‘‘random’’ number.
4 Number of Points Visited during an
N
-Step
base-4 Walk
The number of distinct points visited during a walk of a given
constant (on a lattice) can be also used as an indicator of how
‘‘random’’ the digits of that constant are. It is well known that
the expectation of the number of distinct points visited by an
N
-step random walk on a two-dimensional lattice is asymp-
totically equal to
p
N
/log(
N
); see, for example, [
36
,pg.338]or
[
13
, pg. 27]. This result was first proven by Dvoretzky and
Erd
}
os [
33
, Thm. 1]. The main practical problem with this
asymptotic result is that its convergence is rather slow; spe-
cifically, it has order of
ON
log log
N
=
ð
log
N
Þ
2
.In[
31
,
32
],
Downham and Fotopoulos show the following bounds on the
expectation of the number of distinct points,
p
ð
N
þ
0
:
84
Þ
1
:
16
p
1
log 2
þ
log
ð
N
þ
2
Þ
;
p
ð
N
þ
1
Þ
1
:
066
p
1
log 2
þ
log
ð
N
þ
1
Þ
!
;
ð
9
Þ
which provide a tighter estimate on the expectation than the
asymptotic limit
p
N
/log(
N
). For example, for
N
=
10
6
, these
bounds are (199256.1, 203059.5), whereas
p
N
/log(
N
)
=
227396, which overestimates the expectation.
In Table
2
we have calculated the number of distinct points
visited by the base-4 walks on several constants. One can see
that the values for different step walks on
p
fit quite well the
expectation. On the other hand, numbers that are known to be
normal such as
a
2,3
or the base-4 Champernowne number
substantially differ from the expectation of a random walk.
These constants, despite being normal, do not have a ‘‘ran-
dom’’ appearance when one draws the associated walk, see
Figure
7
(d).
At first look, the walk on
a
2,3
might seem random, see
Figure
7
(c). A closer look, shown in Figure
12
, shows a more
complex structure: the walk appears to be somehow self-
repeating. This helps explain why the number of sites visited
by the base-4 walk on
a
2,3
or
a
4,3
is smaller than the
expectation for a random walk. A detailed discussion of the
Stoneham constants and their walks is provided in Section
5.2
,
where the precise structure of Figure
12
is conjectured.
5 Copeland–Erd
}
os, Stoneham, and Erd
}
os–
Borwein Constants
As well as the classical numbers—such as
e
,
p
,
c
—listed in the
Appendix, we also considered various other constructions,
which we describe in the next three subsections.
5.1 Champernowne Number and Its Concatenated
Relatives
The first mathematical constant proven to be 10-normal is
the
Champernowne number
, which is defined as the concat-
enation of the decimal values of the positive integers, that
is,
C
10
¼
0
:
12345678910111213141516
…
Champernowne
proved that
C
10
is 10-normal in 1933 [
24
]. This was later
extended to base-
b
normality (for base-
b
versions of the
Champernowne constant) as in Theorem 5.1. In 1946,
Copeland and Erd
}
os established that the corresponding
concatenation of primes 0
:
23571113171923
…
and the con-
catenation of composites 0
:
46891012141516
…
,among
others, are also 10-normal [
26
]. In general they proved that
concatenation leads to normality if the sequence grows slowly
enough. We call such numbers
concatenation numbers
:
T
HEOREM
5.1
([
26
]). If
a
1
;
a
2
;
…
is an increasing sequence
of integers such that for every
h
\
1
the number of a
i
’s up
to N exceeds N
h
provided N is sufficiently large, then the
infinite decimal
0
:
a
1
a
2
a
3
is normal with respect to the base b in which these integers
are expressed
.
This result clearly applies to the Champernowne numbers
(Fig.
7
(d)), to the primes of the form
ak
+
c
with
a
and
c
rel-
atively prime, in any given base, and to the integers that are the
sum of two squares (since every prime of the form 4
k
+
1is
(a)
(b)
Figure 9.
Number of points visited by 10
4
base-4 million-step walks.
50
THE MATHEMATICAL INTELLIGENCER
Author’s
personal
copy
show no skewing. Indeed, for
CE
(2) we have checked that
2
m
1
(
n
)
[
n
for all
n
B
10
9
, see also Figure
11
(a). Thus
motivated, we are currently developing tests for strong nor-
mality of numbers such as
CE
(2) and
a
2,3
below in binary.
For
a
2,3
, the corresponding computation of the first 10
9
values of
m
1
ð
n
Þ
n
=
2
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
2
n
log log
n
p
leads to the plot in Figure
11
(b) and leads
us to conjecture that it is 2-strongly normal.
5.2 Stoneham Numbers: A Class Containing Provably
Normal and Nonnormal Constants
Giving further motivation for these studies is the recent pro-
vision of rigorous proofs of normality for the
Stoneham
numbers
, which are defined by
a
b
;
c
:
¼
X
m
1
1
c
m
b
c
m
;
ð
11
Þ
for relatively prime integers
b
,
c
[
10
].
T
HEOREM
5.4
(Normality of Stoneham constants [
3
]).
For
every coprime pair of integers
(
b
,
c
)
with b
C
2
and c
C
2
,
the constant
a
b
,
c
=
P
m
C
1
1/(
c
m
b
c
m
)
is b-normal
.
So, for example, the constant
a
2
;
3
¼
P
k
1
1
=
ð
3
k
2
3
k
Þ¼
0
:
0418836808315030
…
is provably 2-normal. This special
case was proven by Stoneham in 1973 [
43
]. More recently,
Bailey and Misiurewicz were able to establish this normality
result by a much simpler argument, based on techniques of
ergodic theory [
11
][
16
, pg. 141–173].
Equally interesting is the following result:
T
HEOREM
5.5
(Nonnormality of Stoneham constants [
3
]).
Given coprime integers b
C
2
and c
C
2
, and integers p
,
q
,
r
C
1
, with neither b nor c dividing r , let B
=
b
p
c
q
r.
Assume that the condition D
=
c
q
/
p
r
1/
p
/
b
c
-1
\
1
is satisfied.
Then the constant
a
b
;
c
¼
P
k
0
1
=
ð
c
k
b
c
k
Þ
is B-nonnormal
.
In various of the Figures and Tables, we explore the striking
differences of behavior—proven and unproven—for
a
b
,
c
as
we vary the base. For instance, the nonnormality of
a
2,3
in
base-6 digits was proved just before we started to draw walks.
Contrast Figure
7
(b) to Figure
7
(c) and Figure
7
(a). Now
compare the values presented in Table
1
and Table
2
. Clearly,
from this sort of visual and numeric data, the discovery of other
cases of Theorem 5.5 is very easy.
As illustrated also in the ‘‘zoom’’ of Figure
12
, we can use
these images to discover more subtle structure. We conjecture
the following relations on the digits of
a
2,3
in base 4 (which
explain the values in Tables
1
and
2
):
C
ONJECTURE
5.6
(Base-4 structure of
a
2,3
).
Denote
by a
k
the k
th
digit of
a
2,3
in its base-
4
expansion; that
is
,
a
2
;
3
¼
P
1
k
¼
1
a
k
=
4
k
,with a
k
2f
0
;
1
;
2
;
3
g
for all k. Then,
for all n
¼
0
;
1
;
2
;
…
one has:
(i)
P
3
2
ð
3
n
þ
1
Þþ
3
n
k
¼
3
2
ð
3
n
þ
1
Þ
e
a
k
p
i
=
2
¼
ð
1
Þ
n
þ
1
1
2
þ
ð
1
Þ
n
1
2
i
¼
i
;
nodd
1
;
n even
;
(ii)
a
k
¼
a
k
þ
3
n
¼
a
k
þ
2
3
n
for all k
¼
3
2
ð
3
n
þ
1
Þ
;
3
2
ð
3
n
þ
1
Þþ
1
;
…
;
3
2
ð
3
n
þ
1
Þþ
3
n
1.
In Figure
13
, we show the position of the walk after
3
2
ð
3
n
þ
1
Þ
;
3
2
ð
3
n
þ
1
Þþ
3
n
and
3
2
ð
3
n
þ
1
Þþ
2
3
n
steps for
(a)(b)
Figure 11.
Plot of the first 10
9
values of
m
1
ð
n
Þ
n
=
2
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
2
n
log log
n
p
.
Figure 12.
Zooming in on the base-4 walk on
a
2,3
of
Figure
7
(c) and Conjecture 5.6.
52
THE MATHEMATICAL INTELLIGENCER
Author’s
personal
copy
n
¼
0
;
1
;
…
;
11, which, together with Figures
7
(c) and
12
,
graphically explain Conjecture 5.6. Similar results seem to
hold for other Stoneham constants in other bases. For
instance, for
a
3,5
base 3 we conjecture the following.
C
ONJECTURE
5.7
(Base-3 structure of
a
3,5
).
Denote by
a
k
the k
th
digit of
a
3,5
in its base-
3
expansion; that is
,
a
3
;
5
¼
P
1
k
¼
1
a
k
=
3
k
,witha
k
2f
0
;
1
;
2
g
for all k
.
Then, for
all n
¼
0
;
1
;
2
;
…
one has:
(i)
P
2
þ
5
n
þ
1
þ
4
5
n
k
¼
2
þ
5
n
þ
1
e
a
k
p
i
=
2
¼ð
1
Þ
n
1
þ
ffiffi
3
p
i
2
¼
e
ð
3
n
þ
2
Þ
p
i
=
3
;
(ii)
a
k
¼
a
k
þ
4
5
n
¼
a
k
þ
8
5
n
¼
a
k
þ
12
5
n
¼
a
k
þ
16
5
n
for k
¼
5
n
þ
1
þ
j
;
j
¼
2
;
…
;
2
þ
4
5
n
.
Along this line, Bailey and Crandall showed that, given a
real number
r
in [0,1), and
r
k
denoting the
k
-th binary digit of
r
,
the real number
a
2
;
3
ð
r
Þ
:
¼
X
1
k
¼
0
1
3
k
2
3
k
þ
r
k
ð
12
Þ
is 2-normal. It can be seen that if
r
=
s
, then
a
2,3
(
r
)
=
a
2,3
(
s
), so that these constants are all distinct.
Thus, this generalized class of Stoneham constants is un-
countably infinite. A similar result applies if 2 and 3 in this
formula are replaced by any pair of co-prime integers
(
b
,
c
) greater than 1, [
10
][
16
, pg. 141–173]. We have not yet
studied this generalized class by graphical methods.
5.3 The Erd
}
os–Borwein Constants
The constructions of the previous two subsections exhaust
most of what is known for concrete irrational numbers. By
contrast, we finish this section with a truly tantalizing case:
In a base
b
C
2, we define the
Erd
}
os–(Peter) Borwein
constant EB
(
b
)bythe
Lambert series
[
18
]:
EB
ð
b
Þ
:
¼
X
n
1
1
b
n
1
¼
X
n
1
s
ð
n
Þ
b
n
;
ð
13
Þ
where
s
(
n
) is the number of divisors of
n
. It is known that
the numbers
P
n
C
1
1/(
b
n
-
r
) are irrational for
r
a nonzero
rational and
b
¼
2
;
3
;
…
such that
r
=
b
n
for all
n
[
20
].
Whence, as provably irrational numbers other than the
standard examples are few and far between, it is interesting
to consider their normality.
Crandall [
27
] has observed that the structure of (
13
)is
analogous to the ‘‘BBP’’ formula for
p
(see [
7
,
16
]) and used
this, as well as some nontrivial knowledge of the arithmetic
properties of
s
, to establish results such as that the googol-th
bit (namely, the bit in position 10
100
to the right of the ‘‘deci-
mal’’ point) of
EB
(2) is a 1.
In [
27
] Crandall also computed the first 2
43
bits (one Tbyte)
of
EB
(2), which required roughly 24 hours of computation,
and found that there are
435
9105565638 zeroes and
443
6987456570 ones. There is a corresponding variation in the
second and third place in the single-digit hex (base-16) dis-
tributions. This certainly leaves some doubt as to its normality.
Likewise, Crandall finds that in the first 1,000 decimal positions
after the quintillionth digit (10
18
), the respective digit counts for
digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 are 104, 82, 87, 100, 73, 126,
87, 123, 114, 104. Our own more modest computations of
EB
(10) base-10 again leave it far from clear that
EB
(10) is
10-normal. See also Figure
7
(e) but contrast it to Figure
8
(f).
We should note that for computational purposes, we
employed the identity
X
n
1
1
b
n
1
¼
X
n
1
b
n
þ
1
b
n
1
1
b
n
2
;
for |
b
|
[
1, due to Clausen, as did Crandall [
27
].
6 Other Avenues and Concluding Remarks
Let us recall two further examples used in [
14
], that of
X
ð
n
Þ
,the
Liouville function
, which counts the parity of the number of
prime factors of
n
(see Figure
14
), and the human genome
taken from the
UCSC Genome Browser
at
sized image has a resolution of 372,224
9
290,218 pixels
(108.03 gigapixels in total). This must be one of the largest
mathematical images ever produced. The computations for
creating this image took roughly a month, where several parts
of the algorithm were run in parallel with 20 threads on
CARMA’s MacPro cluster.
By contrast, Figure
6
exhibits a 100 million base-4 walk on
p
, where the color is coded by the number of returns to the
point. In [
4
], the authors empirically tested the normality of its
first roughly four trillion hexadecimal (base-16) digits using a
Poisson process model, and they concluded that, according to
this test, it is ‘‘extraordinarily unlikely’’ that
p
is not 16-normal
(of course, this result does not pretend to be a proof).
In what follows, we propose various methods of analyzing
real numbers and visualizing them as walks. Other methods
widely used to visualize numbers include the matrix repre-
sentations shown in Figure
8
, where each pixel is colored
depending on the value of the digit to the right of the decimal
point, following a left-to-right up-to-down direction (in base 4
the colors used for 0, 1, 2, and 3 are red, green, cyan, and
purple, respectively). This method has been mainly used to
visually test ‘‘randomness.’’ In some cases, it clearly shows the
features of some numbers; as for small periodic rationals, see
Figure
8
(c). This scheme also shows the nonnormality of the
number
a
2,3
—see Figure
8
(d) (where the horizontal red bands
correspond to the strings of zeroes)—and it captures some of
the special peculiarities of the Champernowne’s number
C
4
(normal) in Figure
8
(e). Nevertheless, it does not reveal
the apparently nonrandom behavior of numbers such
as the Erd
}
os–Borwein constant; compare Figure
8
(f) with
Figure
7
(e). See also Figure
21
.
As we will see in what follows, the study of normal numbers
and suspected normal numbers as walks will permit us to
compare them with true random (or pseudorandom) walks,
obtaining in this manner a new way to empirically test ‘‘ran-
domness’’ in their digits.
3 Expected Distance to the Origin
Let
b
2f
3
;
4
;
…
g
be a fixed base, and let
X
1
;
X
2
;
X
3
;
…
be a
sequence of independent bivariate discrete random variables
whose common probability distribution is given by
PX
¼
cos
2
p
b
k
sin
2
p
b
k
¼
1
b
for
k
¼
1
;
…
;
b
:
ð
2
Þ
Then the random variable
S
N
:
=
P
m
=1
N
X
m
represents a
base-
b
random walk in the plane of
N
steps.
The following result on the asymptotic expectation of the
distance to the origin of a base-
b
random walk is probably
known, but being unable to find any reference in the litera-
ture, we provide a proof.
T
HEOREM
3.1
The expected distance to the origin of a
base-b random walk of N steps is asymptotically equal
to
ffiffiffiffiffiffiffi
p
N
p
=
2.
P
ROOF
.
By the multivariate central limit theorem, the ran-
dom variable 1
=
ffiffiffiffi
N
p
P
N
m
¼
1
ð
X
m
l
Þ
is asymptotically
bivariate normal with mean
0
0
and covariance matrix
M
,
where
l
is the two-dimensional mean vector of
X
and
M
is its
2
9
2 covariance matrix. By applying Lagrange’s trigono-
metric identities, one obtains
l
¼
1
b
P
b
k
¼
1
cos
2
p
b
k
1
b
P
b
k
¼
1
sin
2
p
b
k
!
¼
1
b
1
2
þ
sin
ð
b
þ
1
=
2
Þ
2
p
b
ðÞ
2 sin
ð
p
=
b
Þ
1
2
cot
ð
p
=
b
Þ
cos
ð
b
þ
1
=
2
Þ
2
p
b
ðÞ
2 sin
ð
p
=
b
Þ
0
B
@
1
C
A
¼
0
0
:
ð
3
Þ
Thus,
M
¼
1
b
P
b
k
¼
1
cos
2
2
p
b
k
P
b
k
¼
1
cos
2
p
b
k
sin
2
p
b
k
P
b
k
¼
1
cos
2
p
b
k
sin
2
p
b
k
P
b
k
¼
1
sin
2
2
p
b
k
“#
:
ð
4
Þ
Figure 5.
A walk on the first 100 billion base-4 digits of
p
(normal?).
Figure 6.
A walk on the first 100 million base-4 digits of
p
, col-
ored by number of returns (normal?). Color follows an HSV model
(green-cyan-blue-purple-red) depending on the number of returns
to each point (where the maxima show a tinge of pink/red).
46
THE MATHEMATICAL INTELLIGENCER
Author’s
personal
copy
Since
X
b
k
¼
1
cos
2
2
p
b
k
¼
X
b
k
¼
1
1
þ
cos
4
p
b
k
2
¼
b
2
;
X
b
k
¼
1
sin
2
2
p
b
k
¼
X
b
k
¼
1
1
cos
4
p
b
k
2
¼
b
2
;
X
b
k
¼
1
cos
2
p
b
k
sin
2
p
b
k
¼
X
b
k
¼
1
sin
4
p
b
k
2
¼
0
;
ð
5
Þ
formula (
4
) reduces to
M
¼
1
2
0
0
1
2
:
ð
6
Þ
Hence,
S
N
=
ffiffiffiffi
N
p
is asymptotically bivariate normal with mean
0
0
and covariance matrix
M
. Because its components
ð
S
N
1
=
ffiffiffiffi
N
p
;
S
N
2
=
ffiffiffiffi
N
p
Þ
T
are uncorrelated, then they are inde-
pendent random variables, whose distribution is (univariate)
(a)(b)
(c)(d)
(e)(f)
Figure 7.
Walks on various numbers in different bases.
2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013
47
Author’s
personal
copy
normal with mean 0 and variance 1/2. Therefore, the random
variable
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
ffiffiffi
2
p
ffiffiffiffi
N
p
S
N
1
2
þ
ffiffiffi
2
p
ffiffiffiffi
N
p
S
N
2
2
s
ð
7
Þ
converges in distribution to a
v
random variable with two
degrees of freedom. Then, for
N
sufficiently large,
E
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
ð
S
N
1
Þ
2
þð
S
N
2
Þ
2
q
¼
ffiffiffiffi
N
p
ffiffiffi
2
p
E
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
ffiffiffi
2
p
ffiffiffiffi
N
p
S
N
1
2
þ
ffiffiffi
2
p
ffiffiffiffi
N
p
S
N
2
2
s
0
@
1
A
ffiffiffiffi
N
p
ffiffiffi
2
p
C
ð
3
=
2
Þ
C
ð
1
Þ
¼
ffiffiffiffiffiffiffi
p
N
p
2
;
ð
8
Þ
where
E
ð Þ
stands for the expectation of a random
variable. Therefore, the expected distance to the
(a)(b)
(c)(d)
(e)(f)
Figure 8.
Horizontal color representation of a million digits of various numbers.
48
THE MATHEMATICAL INTELLIGENCER
Author’s
personal
copy
origin of the random walk is asymptotically equal to
ffiffiffiffiffiffiffi
p
N
p
=
2.
As a consequence of this result, for any random walk of
N
steps in any given base, the expectation of the distance to the
origin multiplied by 2
=
ffiffiffiffiffiffiffi
p
N
p
(which we will call
normalized
distance
to the origin) must approach 1 as
N
goes to infinity.
Therefore, for a ‘‘sufficiently’’ big random walk, one would
expect that the arithmetic mean of the normalized distances
(which will be called
average normalized distance
to the
origin) should be close to 1.
We have created a sample of 10,000 (pseudo)random
walks base-4 of one million points each in Python
1
,andwe
have computed their average normalized distance to the ori-
gin. The arithmetic mean of these numbers for the mentioned
sample of pseudorandom walks is 1.0031, whereas its stan-
dard deviation is 0.3676, so the asymptotic result fits quite well.
We have also computed the normalized distance to the origin
of 10,000 walks of one million steps each generated by the first
ten billion digits of
p
. The resulting arithmetic mean is 1.0008,
whereas the standard deviation is 0.3682. In Table
1
we show
the average normalized distance to the origin of various
numbers. There are several surprises in there data, such as the
Table 1. Average of the normalized distance to the origin of the walk of
various constants in different bases
Number Base Steps Average normalized
distance to the origin
Normal
Mean of 10,000
random walks
4 1,000,000 1.00315 Yes
Mean of 10,000 walks
on the digits of
p
4 1,000,000 1.00083 ?
a
2,3
3 1,000,000 0.89275 ?
a
2,3
4 1,000,000 0.25901 Yes
a
2,3
5 1,000,000 0.88104 ?
a
2,3
6 1,000,000 108.02218 No
a
4,3
3 1,000,000 1.07223 ?
a
4,3
4 1,000,000 0.24268 Yes
a
4,3
6 1,000,000 94.54563 No
a
4,3
12 1,000,000 371.24694 No
a
3,5
3 1,000,000 0.32511 Yes
a
3,5
5 1,000,000 0.85258 ?
a
3,5
15 1,000,000 370.93128 No
p
4 1,000,000 0.84366 ?
p
6 1,000,000 0.96458 ?
p
10 1,000,000 0.82167 ?
p
10 10,000,000 0.56856 ?
p
10 100,000,000 0.94725 ?
p
10 1,000,000,000 0.59824 ?
e
4 1,000,000 0.59583 ?
ffiffiffi
2
p
4 1,000,000 0.72260 ?
log 2 4 1,000,000 1.21113 ?
Champernowne
C
10
10 1,000,000 59.91143 Yes
EB
(2) 4 1,000,000 6.95831 ?
CE
(10) 4 1,000,000 0.94964 ?
Rational number
Q
1
4 1,000,000 0.04105 No
Rational number
Q
2
4 1,000,000 58.40222 No
Euler constant
c
10 1,000,000 1.17216 ?
Fibonacci
F
10 1,000,000 1.24820 ?
f
ð
2
Þ¼
p
2
6
4 1,000,000 1.57571 ?
f
ð
3
Þ
4 1,000,000 1.04085 ?
Catalan’s constant
G
4 1,000,000 0.53489 ?
Thue–Morse
TM
2
4 1,000,000 531.92344 No
Paper-folding
P
4 1,000,000 0.01336 No
Table 2. Number of points visited in various
N
-step base-4 walks. The
values of the two last columns are upper and lower bounds on the
expectation of the number of distinct sites visited during an
N
-step
random walk; see [31, Theorem 2] and [
32
]
Number Steps Sites visited Bounds on the expectation
of sites visited by a random
walk
Lower
bound
Upper
bound
Mean of 10,000
random walks
1,000,000 202,684 199,256 203,060
Mean of 10,000
walks on the
digits of
p
1,000,000 202,385 199,256 203,060
a
2,3
1,000,000 95,817 199,256 203,060
a
4,3
1,000,000 68,613 199,256 203,060
a
3,2
1,000,000 195,585 199,256 203,060
p
1,000,000 204,148 199,256 203,060
p
10,000,000 1,933,903 1,738,645 1,767,533
p
100,000,000 16,109,429 15,421,296 15,648,132
p
1,000,000,000 138,107,050 138,552,612 140,380,926
e
1,000,000 176,350 199,256 203,060
ffiffiffi
2
p
1,000,000 200,733 199,256 203,060
log 2 1,000,000 214,508 199,256 203,060
Champernowne
C
4
1,000,000 548,746 199,256 203,060
EB
(2) 1,000,000 279,585 199,256 203,060
CE(10) 1,000,000 190,239 199,256 203,060
Rational number
Q
1
1,000,000 378 199,256 203,060
Rational number
Q
2
1,000,000 939,322 199,256 203,060
Euler constant
c
1,000,000 208,957 199,256 203,060
f
ð
2
Þ
1,000,000 188,808 199,256 203,060
f
ð
3
Þ
1,000,000 221,598 199,256 203,060
Catalan’s
constant
G
1,000,000 195,853 199,256 203,060
TM
2
1,000,000 1,000,000 199,256 203,060
Paper-folding
P
1,000,000 21 199,256 203,060
1
Python uses the Mersenne Twister as the core generator and produces 53-bit precision floats, with a period of 2
19937
-
1
&
10
6002
. Compare the length of this period to the
comoving distance from Earth to the edge of the observable universe in any direction, which is approximately
4
:
6
10
37
nanometers, or to the number of protons in the universe,
which is approximately 10
80
.
2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013
49
Author’s
personal
copy
fact that by this measure, Champernowne’s number
C
10
is far
from what is expected of a truly ‘‘random’’ number.
4 Number of Points Visited during an
N
-Step
base-4 Walk
The number of distinct points visited during a walk of a given
constant (on a lattice) can be also used as an indicator of how
‘‘random’’ the digits of that constant are. It is well known that
the expectation of the number of distinct points visited by an
N
-step random walk on a two-dimensional lattice is asymp-
totically equal to
p
N
/log(
N
); see, for example, [
36
,pg.338]or
[
13
, pg. 27]. This result was first proven by Dvoretzky and
Erd
}
os [
33
, Thm. 1]. The main practical problem with this
asymptotic result is that its convergence is rather slow; spe-
cifically, it has order of
ON
log log
N
=
ð
log
N
Þ
2
.In[
31
,
32
],
Downham and Fotopoulos show the following bounds on the
expectation of the number of distinct points,
p
ð
N
þ
0
:
84
Þ
1
:
16
p
1
log 2
þ
log
ð
N
þ
2
Þ
;
p
ð
N
þ
1
Þ
1
:
066
p
1
log 2
þ
log
ð
N
þ
1
Þ
!
;
ð
9
Þ
which provide a tighter estimate on the expectation than the
asymptotic limit
p
N
/log(
N
). For example, for
N
=
10
6
, these
bounds are (199256.1, 203059.5), whereas
p
N
/log(
N
)
=
227396, which overestimates the expectation.
In Table
2
we have calculated the number of distinct points
visited by the base-4 walks on several constants. One can see
that the values for different step walks on
p
fit quite well the
expectation. On the other hand, numbers that are known to be
normal such as
a
2,3
or the base-4 Champernowne number
substantially differ from the expectation of a random walk.
These constants, despite being normal, do not have a ‘‘ran-
dom’’ appearance when one draws the associated walk, see
Figure
7
(d).
At first look, the walk on
a
2,3
might seem random, see
Figure
7
(c). A closer look, shown in Figure
12
, shows a more
complex structure: the walk appears to be somehow self-
repeating. This helps explain why the number of sites visited
by the base-4 walk on
a
2,3
or
a
4,3
is smaller than the
expectation for a random walk. A detailed discussion of the
Stoneham constants and their walks is provided in Section
5.2
,
where the precise structure of Figure
12
is conjectured.
5 Copeland–Erd
}
os, Stoneham, and Erd
}
os–
Borwein Constants
As well as the classical numbers—such as
e
,
p
,
c
—listed in the
Appendix, we also considered various other constructions,
which we describe in the next three subsections.
5.1 Champernowne Number and Its Concatenated
Relatives
The first mathematical constant proven to be 10-normal is
the
Champernowne number
, which is defined as the concat-
enation of the decimal values of the positive integers, that
is,
C
10
¼
0
:
12345678910111213141516
…
Champernowne
proved that
C
10
is 10-normal in 1933 [
24
]. This was later
extended to base-
b
normality (for base-
b
versions of the
Champernowne constant) as in Theorem 5.1. In 1946,
Copeland and Erd
}
os established that the corresponding
concatenation of primes 0
:
23571113171923
…
and the con-
catenation of composites 0
:
46891012141516
…
,among
others, are also 10-normal [
26
]. In general they proved that
concatenation leads to normality if the sequence grows slowly
enough. We call such numbers
concatenation numbers
:
T
HEOREM
5.1
([
26
]). If
a
1
;
a
2
;
…
is an increasing sequence
of integers such that for every
h
\
1
the number of a
i
’s up
to N exceeds N
h
provided N is sufficiently large, then the
infinite decimal
0
:
a
1
a
2
a
3
is normal with respect to the base b in which these integers
are expressed
.
This result clearly applies to the Champernowne numbers
(Fig.
7
(d)), to the primes of the form
ak
+
c
with
a
and
c
rel-
atively prime, in any given base, and to the integers that are the
sum of two squares (since every prime of the form 4
k
+
1is
(a)
(b)
Figure 9.
Number of points visited by 10
4
base-4 million-step walks.
50
THE MATHEMATICAL INTELLIGENCER
Author’s
personal
copy
show no skewing. Indeed, for
CE
(2) we have checked that
2
m
1
(
n
)
[
n
for all
n
B
10
9
, see also Figure
11
(a). Thus
motivated, we are currently developing tests for strong nor-
mality of numbers such as
CE
(2) and
a
2,3
below in binary.
For
a
2,3
, the corresponding computation of the first 10
9
values of
m
1
ð
n
Þ
n
=
2
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
2
n
log log
n
p
leads to the plot in Figure
11
(b) and leads
us to conjecture that it is 2-strongly normal.
5.2 Stoneham Numbers: A Class Containing Provably
Normal and Nonnormal Constants
Giving further motivation for these studies is the recent pro-
vision of rigorous proofs of normality for the
Stoneham
numbers
, which are defined by
a
b
;
c
:
¼
X
m
1
1
c
m
b
c
m
;
ð
11
Þ
for relatively prime integers
b
,
c
[
10
].
T
HEOREM
5.4
(Normality of Stoneham constants [
3
]).
For
every coprime pair of integers
(
b
,
c
)
with b
C
2
and c
C
2
,
the constant
a
b
,
c
=
P
m
C
1
1/(
c
m
b
c
m
)
is b-normal
.
So, for example, the constant
a
2
;
3
¼
P
k
1
1
=
ð
3
k
2
3
k
Þ¼
0
:
0418836808315030
…
is provably 2-normal. This special
case was proven by Stoneham in 1973 [
43
]. More recently,
Bailey and Misiurewicz were able to establish this normality
result by a much simpler argument, based on techniques of
ergodic theory [
11
][
16
, pg. 141–173].
Equally interesting is the following result:
T
HEOREM
5.5
(Nonnormality of Stoneham constants [
3
]).
Given coprime integers b
C
2
and c
C
2
, and integers p
,
q
,
r
C
1
, with neither b nor c dividing r , let B
=
b
p
c
q
r.
Assume that the condition D
=
c
q
/
p
r
1/
p
/
b
c
-1
\
1
is satisfied.
Then the constant
a
b
;
c
¼
P
k
0
1
=
ð
c
k
b
c
k
Þ
is B-nonnormal
.
In various of the Figures and Tables, we explore the striking
differences of behavior—proven and unproven—for
a
b
,
c
as
we vary the base. For instance, the nonnormality of
a
2,3
in
base-6 digits was proved just before we started to draw walks.
Contrast Figure
7
(b) to Figure
7
(c) and Figure
7
(a). Now
compare the values presented in Table
1
and Table
2
. Clearly,
from this sort of visual and numeric data, the discovery of other
cases of Theorem 5.5 is very easy.
As illustrated also in the ‘‘zoom’’ of Figure
12
, we can use
these images to discover more subtle structure. We conjecture
the following relations on the digits of
a
2,3
in base 4 (which
explain the values in Tables
1
and
2
):
C
ONJECTURE
5.6
(Base-4 structure of
a
2,3
).
Denote
by a
k
the k
th
digit of
a
2,3
in its base-
4
expansion; that
is
,
a
2
;
3
¼
P
1
k
¼
1
a
k
=
4
k
,with a
k
2f
0
;
1
;
2
;
3
g
for all k. Then,
for all n
¼
0
;
1
;
2
;
…
one has:
(i)
P
3
2
ð
3
n
þ
1
Þþ
3
n
k
¼
3
2
ð
3
n
þ
1
Þ
e
a
k
p
i
=
2
¼
ð
1
Þ
n
þ
1
1
2
þ
ð
1
Þ
n
1
2
i
¼
i
;
nodd
1
;
n even
;
(ii)
a
k
¼
a
k
þ
3
n
¼
a
k
þ
2
3
n
for all k
¼
3
2
ð
3
n
þ
1
Þ
;
3
2
ð
3
n
þ
1
Þþ
1
;
…
;
3
2
ð
3
n
þ
1
Þþ
3
n
1.
In Figure
13
, we show the position of the walk after
3
2
ð
3
n
þ
1
Þ
;
3
2
ð
3
n
þ
1
Þþ
3
n
and
3
2
ð
3
n
þ
1
Þþ
2
3
n
steps for
(a)(b)
Figure 11.
Plot of the first 10
9
values of
m
1
ð
n
Þ
n
=
2
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
2
n
log log
n
p
.
Figure 12.
Zooming in on the base-4 walk on
a
2,3
of
Figure
7
(c) and Conjecture 5.6.
52
THE MATHEMATICAL INTELLIGENCER
Author’s
personal
copy
n
¼
0
;
1
;
…
;
11, which, together with Figures
7
(c) and
12
,
graphically explain Conjecture 5.6. Similar results seem to
hold for other Stoneham constants in other bases. For
instance, for
a
3,5
base 3 we conjecture the following.
C
ONJECTURE
5.7
(Base-3 structure of
a
3,5
).
Denote by
a
k
the k
th
digit of
a
3,5
in its base-
3
expansion; that is
,
a
3
;
5
¼
P
1
k
¼
1
a
k
=
3
k
,witha
k
2f
0
;
1
;
2
g
for all k
.
Then, for
all n
¼
0
;
1
;
2
;
…
one has:
(i)
P
2
þ
5
n
þ
1
þ
4
5
n
k
¼
2
þ
5
n
þ
1
e
a
k
p
i
=
2
¼ð
1
Þ
n
1
þ
ffiffi
3
p
i
2
¼
e
ð
3
n
þ
2
Þ
p
i
=
3
;
(ii)
a
k
¼
a
k
þ
4
5
n
¼
a
k
þ
8
5
n
¼
a
k
þ
12
5
n
¼
a
k
þ
16
5
n
for k
¼
5
n
þ
1
þ
j
;
j
¼
2
;
…
;
2
þ
4
5
n
.
Along this line, Bailey and Crandall showed that, given a
real number
r
in [0,1), and
r
k
denoting the
k
-th binary digit of
r
,
the real number
a
2
;
3
ð
r
Þ
:
¼
X
1
k
¼
0
1
3
k
2
3
k
þ
r
k
ð
12
Þ
is 2-normal. It can be seen that if
r
=
s
, then
a
2,3
(
r
)
=
a
2,3
(
s
), so that these constants are all distinct.
Thus, this generalized class of Stoneham constants is un-
countably infinite. A similar result applies if 2 and 3 in this
formula are replaced by any pair of co-prime integers
(
b
,
c
) greater than 1, [
10
][
16
, pg. 141–173]. We have not yet
studied this generalized class by graphical methods.
5.3 The Erd
}
os–Borwein Constants
The constructions of the previous two subsections exhaust
most of what is known for concrete irrational numbers. By
contrast, we finish this section with a truly tantalizing case:
In a base
b
C
2, we define the
Erd
}
os–(Peter) Borwein
constant EB
(
b
)bythe
Lambert series
[
18
]:
EB
ð
b
Þ
:
¼
X
n
1
1
b
n
1
¼
X
n
1
s
ð
n
Þ
b
n
;
ð
13
Þ
where
s
(
n
) is the number of divisors of
n
. It is known that
the numbers
P
n
C
1
1/(
b
n
-
r
) are irrational for
r
a nonzero
rational and
b
¼
2
;
3
;
…
such that
r
=
b
n
for all
n
[
20
].
Whence, as provably irrational numbers other than the
standard examples are few and far between, it is interesting
to consider their normality.
Crandall [
27
] has observed that the structure of (
13
)is
analogous to the ‘‘BBP’’ formula for
p
(see [
7
,
16
]) and used
this, as well as some nontrivial knowledge of the arithmetic
properties of
s
, to establish results such as that the googol-th
bit (namely, the bit in position 10
100
to the right of the ‘‘deci-
mal’’ point) of
EB
(2) is a 1.
In [
27
] Crandall also computed the first 2
43
bits (one Tbyte)
of
EB
(2), which required roughly 24 hours of computation,
and found that there are
435
9105565638 zeroes and
443
6987456570 ones. There is a corresponding variation in the
second and third place in the single-digit hex (base-16) dis-
tributions. This certainly leaves some doubt as to its normality.
Likewise, Crandall finds that in the first 1,000 decimal positions
after the quintillionth digit (10
18
), the respective digit counts for
digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 are 104, 82, 87, 100, 73, 126,
87, 123, 114, 104. Our own more modest computations of
EB
(10) base-10 again leave it far from clear that
EB
(10) is
10-normal. See also Figure
7
(e) but contrast it to Figure
8
(f).
We should note that for computational purposes, we
employed the identity
X
n
1
1
b
n
1
¼
X
n
1
b
n
þ
1
b
n
1
1
b
n
2
;
for |
b
|
[
1, due to Clausen, as did Crandall [
27
].
6 Other Avenues and Concluding Remarks
Let us recall two further examples used in [
14
], that of
X
ð
n
Þ
,the
Liouville function
, which counts the parity of the number of
prime factors of
n
(see Figure
14
), and the human genome
taken from the
UCSC Genome Browser
at
http://hgdownload.
cse.ucsc.edu/goldenPath/hg19/chromosomes/
(see Fig.
15
).
Note the similarity of the genome walk to the those of con-
catenation sequences. We have explored a wide variety of
walks on genomes, but we will reserve the results for a future
study.
We should emphasize that, to the best of our knowledge,
the normality and transcendence status of the numbers
explored is unresolved other than in the cases indicated in
sections
5.1
and
5.2
and indicated in Appendix 7. Although
one of the clearly nonrandom numbers (say Stoneham or
Copeland–Erd
}
os) may pass muster on one or other measure of
the walk, it is generally the case that it fails another. Thus, the
Liouville number
k
2
(see Fig.
14
) exhibits a much more
structured drift than
p
or
e
, but looks more like them than like
Figure
15
(a).
This situation provides hope for more precise future anal-
yses. We conclude by remarking on some unresolved issues
and plans for future research.
6.1 Fractal and Box-Dimension
Another approach is to estimate the fractal dimensions of
walks, which is an appropriate tool with which to measure the
geometrical complexity of a set, characterizing its space-filling
capacity (see, e.g., [
6
] for a nice introduction about fractals).
The
box-counting dimension
, also known as the
Minkowski–
Figure 13.
A pattern in the digits of
a
2,3
base 4. We show
only positions of the walk after
3
2
ð
3
n
þ
1
Þ
;
3
2
ð
3
n
þ
1
Þþ
3
n
and
3
2
ð
3
n
þ
1
Þþ
2
3
n
steps for
n
¼
0
;
1
;
…
;
11.
2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013
53
Author’s
personal
copy
Bouligand dimension
, permits us to estimate the fractal
dimension of a given set and often coincides with the fractal
dimension. The box-dimension of the walk of numbers such
as
p
turns out to be close to 2, whereas for nonrandom num-
bers as
a
2,3
in base 6 or Champernowne’s number, the box-
dimension is nearly 1.
6.2 Three Dimensions
We have also explored three-dimensional graphics—using
base-6 for directions—both in perspective and in a large
passive (glasses-free) three-dimensional viewer outside the
CARMA laboratory; but we have not yet quantified these
excursions.
6.3 Genome Comparison
Genomes are made up of so-called purine and pyrimidine
nucleotides. In DNA, purine nucleotide bases are adenine and
guanine (A and G), whereas the pyrimidine bases are thymine
and cytosine (T and C). Thymine is replaced by uracyl in RNA.
The haploid human genome (i.e., 23 chromosomes) is
estimated to hold about 3.2 billion base pairs and so to contain
20,000-25,000 distinct genes. Hence there are many ways of
representing a stretch of a chromosome as a walk, say as a
base-4 uniform walk on the symbols (A, G, T, C) illustrated in
Figure
15
(where A, G, T, and C draw the new point to the
south, north, west, and east, respectively, and we have not
plotted undecoded or unused portions), or as a three-
dimensional logarithmic walk inside a tetrahedron.
We have also compared random
chaos games
in a square
with genomes and numbers plotted by the same rules.
2
As an
illustration, we show twelve games in Figure
16
:fourona
triangle, four on a square, and four on a hexagon. At each step
we go from the current point halfway toward one of the ver-
tices, chosen depending on the value of the digit. The color
indicates the number of hits, in a similar manner as in Figure
6
.
The nonrandom behavior of the Champernowne numbers is
apparent in the coloring patterns, as are the special features of
the Stoneham numbers described in Section
5.2
(the non-
normality of
a
2,3
and
a
3,2
in base 6 yields a paler color, whereas
the repeating structure of
a
2,3
and
a
3,5
is the origin of the purple
tone, see Conjectures 5.6 and 5.7).
(a)(b)
Figure 14.
Two different rules for plotting a base-2 walk on the first two million values of
k
(
n
) (the Liouville number
k
2
).
(a)(b)
Figure 15.
Base-4 walks on 10
6
bases of the X-chromosome and 10
6
digits of log 2.
2
The idea of a chaos game was described by Barnsley in his 1988 book
Fractals Everywhere
[
6
]. Games on amino acids seem to originate with [
35
]. For a recent summary see
[
17
, pp. 194–205].
54
THE MATHEMATICAL INTELLIGENCER
Author’s
personal
copy
6.4 Automatic Numbers
We have also explored numbers originating with finite state
automata, such as those of the
paper-folding
and the
Thue–
Morse
sequences,
P
and
TM
2
, see [
2
] and Section
7
. Automatic
numbers are never normal and are typically transcendental; by
comparison, the Liouville number
k
2
is not
p
-automatic for any
prime
p
[
25
].
The walks on
P
and
TM
2
have a similar shape, see
Figure
17
, but while the Thue–Morse sequence generates very
large pictures, the paper-folding sequence generates very
small ones, because it is highly self-replicating; see also the
values in Tables
1
and
2
.
A
turtle plot
on these constants, where each binary digit
corresponds to either ‘‘forward motion’’ of length 1 or
‘‘rotate the Logo turtle’’ in a fixed angle, exhibits some of
their striking features (see Fig.
18
). For instance, drawn
with a rotating angle of
p
=
3
;
TM
2
converges to a Koch
snowflake [
41
]; see Figure
18
(c). We show a corresponding
turtle graphic of
p
in Figure
18
(d). Analogous features
occur for the paper-folding sequence as described in [
28
,
29
,
30
], and two variants are shown in Figures
18
(a) and
18(b).
6.5 Continued Fractions
Simple continued fractions often encode more information
than base expansions about a real number. Basic facts are that
a continued fraction terminates or repeats if and only if the
Figure 16.
Chaos games on various numbers, colored by frequency. Row 1:
C
3
,
a
3,5
, a (pseudo)random number, and
a
2,3
. Row 2:
C
4
,
p
, a (pseudo)random number, and
a
2,3
. Row 3:
C
6
,
a
3,2
, a (pseudo)random number, and
a
2,3
.
(a)(b)
Figure 17.
Walks on two automatic and nonnormal numbers.
2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013
55
Author’s
personal
copy
number is rational or a quadratic irrational, respectively; see
[
16
,
7
]. By contrast, the simple continued fractions for
p
and
e
start as follows in the standard compact form:
p
¼½
3
;
7
;
15
;
1
;
292
;
1
;
1
;
1
;
2
;
1
;
3
;
1
;
14
;
2
;
1
;
1
;
2
;
2
;
2
;
2
;
1
;
84
;
2
;
1
;
1
;
15
;
3
;
13
;
1
;
4
;
…
e
¼½
2
;
1
;
2
;
1
;
1
;
4
;
1
;
1
;
6
;
1
;
1
;
8
;
1
;
1
;
10
;
1
;
1
;
12
;
1
;
1
;
14
;
1
;
1
;
16
;
1
;
1
;
18
;
1
;
1
;
20
;
1
;
…
;
from which the surprising regularity of
e
and apparent
irregularity of
p
as continued fractions is apparent. The
counterpart to Borel’s theorem—that almost all numbers
are normal—is that almost all numbers have ‘‘normal’’
continued fractions
a
¼½
a
1
;
a
2
;
…
;
a
n
;
…
, for which the
Gauss–Kuzmin distribution
holds [
16
]: for each
k
¼
1
;
2
;
3
;
…
Prob
f
a
n
¼
k
g¼
log
2
1
1
ð
k
þ
1
Þ
2
!
;
ð
14
Þ
so that roughly 41.5% of the terms are 1, 16.99% are 2,
9.31% are 3, etc.
In Figure
19
, we show a histogram of the first 100 million
terms, computed by Neil Bickford and accessible at
http://
neilbickford.com/picf.htm
, of the continued fraction of
p
.
We have not yet found a satisfactory way to embed this in
a walk on a continued fraction, but in Figure
20
we show base-
4 walks on
p
and
e
where we use the remainder modulo 4 to
build the walk (with 0 being right, 1 being up, 2 being left, and
3 being down). We also show turtle plots on
p
,
e
.
Andrew Mattingly has observed that:
P
ROPOSITION
6.1
With probability
1,
amod-
4
random
walk (with
0
being right,
1
being up,
2
being left, and
3
being
down) on the simple continued fraction coefficients of a real
number is asymptotic to a line making a positive angle with
the x-axis of:
arctan
1
2
log
2
ð
p
=
2
Þ
1
log
2
ð
p
=
2
Þ
2 log
2
C
3
=
4
ðÞ
ðÞ
110
:
44
:
(a)
(b)
(d)
(c)
Figure 18.
Turtle plots on various constants with different rotating angles in base 2—where ‘‘0’’ gives forward motion and ‘‘1’’
rotation by a fixed angle.
56
THE MATHEMATICAL INTELLIGENCER
Author’s
personal
copy
P
ROOF
.
The result comes by summing the expected
Gauss–Kuzmin probabilities of each step being taken as
given by (
14
).
This is illustrated in Figure
20
(a) with a 90
anticlockwise
rotation; thus making the case that one must have some
apriori
knowledge before designing tools.
It is also instructive to compare digits and continued frac-
tions of numbers as horizontal matrix plots of the form already
used in Figure
8
. In Figure
21
, we show six pairs of million-
term digit-strings and the corresponding continued fraction.
In some cases both look random, in others one or the other
does.
In conclusion, we have only scratched the surface of what is
becoming possible in a period in which data—for example,
five-hundred million terms of the continued fraction or five-
trillion binary digits of
p
, full genomes, and much more—can
be downloaded from the Internet, then rendered and visually
mined, with fair rapidity.
(a)(b)
Figure 19.
Expected values of the Gauss–Kuzmin distribution of (14) and the values of 100 million terms of the continued fraction
of
p
.
(a)
(b)
(d)
(c)
Figure 20.
Uniform walks on
p
and
e
based on continued fractions.
2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013
57
Author’s
personal
copy
7 Appendix Selected Numerical Constants
In what follows,
x
:
¼
0
:
a
1
a
2
a
3
a
4
…
b
denotes the base-
b
expansion of the number
x
,sothat
x
¼
P
1
k
¼
1
a
k
b
k
.Base-
10 expansions are denoted without a subscript.
Catalan’s constant
(irrational?; normal?):
G
:
¼
X
1
k
¼
0
ð
1
Þ
k
ð
2
k
þ
1
Þ
2
¼
0
:
9159655941
…
ð
15
Þ
Champernowne numbers
(irrational; normal to correspond-
ing base):
C
b
:
¼
X
1
k
¼
1
P
b
k
1
m
¼
b
k
1
mb
km
ð
b
k
1
1
Þ
½
b
P
k
1
m
¼
0
m
ð
b
1
Þ
b
m
1
ð
16
Þ
C
10
¼
0
:
123456789101112
…
C
4
¼
0
:
1231011121320212223
…
4
Copeland–Erd
}
os constants
(irrational; normal to
corresponding base):
CE
ð
b
Þ
:
¼
X
1
k
¼
1
p
k
b
k
þ
P
k
m
¼
1
b
log
b
p
m
c
;
where
p
k
is the
k
th
prime number
ð
17
Þ
CE
ð
10
Þ¼
0
:
2357111317
…
CE
ð
2
Þ¼
0
:
1011101111
…
2
Exponential constant
(transcendental; normal?):
e
:
¼
X
1
k
¼
0
1
k
!
¼
2
:
7182818284
…
ð
18
Þ
Erd
}
os–Borwein constants
(irrational; normal?):
EB
ð
b
Þ
:
¼
X
1
k
¼
1
1
b
k
1
ð
19
Þ
EB
ð
2
Þ¼
1
:
6066951524
…
¼
1
:
212311001
…
4
Euler–Mascheroni constant
(irrational?; normal?):
c
:
¼
lim
m
!1
X
m
k
¼
1
1
k
log
m
!
¼
0
:
5772156649
…
ð
20
Þ
Fibonacci constant
(irrational [
12
, Theorem 2]; normal?):
F
:
¼
X
1
k
¼
1
F
k
10
1
þ
k
þ
P
k
m
¼
1
b
log
10
F
m
c
;
where
F
k
¼
1
þ
ffiffi
5
p
2
k
1
ffiffi
5
p
2
k
ffiffiffi
5
p
¼
0
:
011235813213455
…
Liouville number
(irrational; not
p
-automatic):
k
2
:
¼
X
1
k
¼
1
k
ð
k
Þþ
1
2
2
k
ð
22
Þ
Figure 21.
Million-step comparisons of base-4 digits and continued fractions. Row 1:
a
2,3
(
base
6) and
C
4
. Row 2:
e
and
p
. Row 3:
Q
1
and pseudorandom iterates; as listed from top left to bottom right.
58
THE MATHEMATICAL INTELLIGENCER
Author’s
personal
copy
(see Fig.
15
).
Note the similarity of the genome walk to the those of con-
catenation sequences. We have explored a wide variety of
walks on genomes, but we will reserve the results for a future
study.
We should emphasize that, to the best of our knowledge,
the normality and transcendence status of the numbers
explored is unresolved other than in the cases indicated in
sections
5.1
and
5.2
and indicated in Appendix 7. Although
one of the clearly nonrandom numbers (say Stoneham or
Copeland–Erd
}
os) may pass muster on one or other measure of
the walk, it is generally the case that it fails another. Thus, the
Liouville number
k
2
(see Fig.
14
) exhibits a much more
structured drift than
p
or
e
, but looks more like them than like
Figure
15
(a).
This situation provides hope for more precise future anal-
yses. We conclude by remarking on some unresolved issues
and plans for future research.
6.1 Fractal and Box-Dimension
Another approach is to estimate the fractal dimensions of
walks, which is an appropriate tool with which to measure the
geometrical complexity of a set, characterizing its space-filling
capacity (see, e.g., [
6
] for a nice introduction about fractals).
The
box-counting dimension
, also known as the
Minkowski–
Figure 13.
A pattern in the digits of
a
2,3
base 4. We show
only positions of the walk after
3
2
ð
3
n
þ
1
Þ
;
3
2
ð
3
n
þ
1
Þþ
3
n
and
3
2
ð
3
n
þ
1
Þþ
2
3
n
steps for
n
¼
0
;
1
;
…
;
11.
2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013
53
Author’s
personal
copy
Bouligand dimension
, permits us to estimate the fractal
dimension of a given set and often coincides with the fractal
dimension. The box-dimension of the walk of numbers such
as
p
turns out to be close to 2, whereas for nonrandom num-
bers as
a
2,3
in base 6 or Champernowne’s number, the box-
dimension is nearly 1.
6.2 Three Dimensions
We have also explored three-dimensional graphics—using
base-6 for directions—both in perspective and in a large
passive (glasses-free) three-dimensional viewer outside the
CARMA laboratory; but we have not yet quantified these
excursions.
6.3 Genome Comparison
Genomes are made up of so-called purine and pyrimidine
nucleotides. In DNA, purine nucleotide bases are adenine and
guanine (A and G), whereas the pyrimidine bases are thymine
and cytosine (T and C). Thymine is replaced by uracyl in RNA.
The haploid human genome (i.e., 23 chromosomes) is
estimated to hold about 3.2 billion base pairs and so to contain
20,000-25,000 distinct genes. Hence there are many ways of
representing a stretch of a chromosome as a walk, say as a
base-4 uniform walk on the symbols (A, G, T, C) illustrated in
Figure
15
(where A, G, T, and C draw the new point to the
south, north, west, and east, respectively, and we have not
plotted undecoded or unused portions), or as a three-
dimensional logarithmic walk inside a tetrahedron.
We have also compared random
chaos games
in a square
with genomes and numbers plotted by the same rules.
2
As an
illustration, we show twelve games in Figure
16
:fourona
triangle, four on a square, and four on a hexagon. At each step
we go from the current point halfway toward one of the ver-
tices, chosen depending on the value of the digit. The color
indicates the number of hits, in a similar manner as in Figure
6
.
The nonrandom behavior of the Champernowne numbers is
apparent in the coloring patterns, as are the special features of
the Stoneham numbers described in Section
5.2
(the non-
normality of
a
2,3
and
a
3,2
in base 6 yields a paler color, whereas
the repeating structure of
a
2,3
and
a
3,5
is the origin of the purple
tone, see Conjectures 5.6 and 5.7).
(a)(b)
Figure 14.
Two different rules for plotting a base-2 walk on the first two million values of
k
(
n
) (the Liouville number
k
2
).
(a)(b)
Figure 15.
Base-4 walks on 10
6
bases of the X-chromosome and 10
6
digits of log 2.
2
The idea of a chaos game was described by Barnsley in his 1988 book
Fractals Everywhere
[
6
]. Games on amino acids seem to originate with [
35
]. For a recent summary see
[
17
, pp. 194–205].
54
THE MATHEMATICAL INTELLIGENCER
Author’s
personal
copy
6.4 Automatic Numbers
We have also explored numbers originating with finite state
automata, such as those of the
paper-folding
and the
Thue–
Morse
sequences,
P
and
TM
2
, see [
2
] and Section
7
. Automatic
numbers are never normal and are typically transcendental; by
comparison, the Liouville number
k
2
is not
p
-automatic for any
prime
p
[
25
].
The walks on
P
and
TM
2
have a similar shape, see
Figure
17
, but while the Thue–Morse sequence generates very
large pictures, the paper-folding sequence generates very
small ones, because it is highly self-replicating; see also the
values in Tables
1
and
2
.
A
turtle plot
on these constants, where each binary digit
corresponds to either ‘‘forward motion’’ of length 1 or
‘‘rotate the Logo turtle’’ in a fixed angle, exhibits some of
their striking features (see Fig.
18
). For instance, drawn
with a rotating angle of
p
=
3
;
TM
2
converges to a Koch
snowflake [
41
]; see Figure
18
(c). We show a corresponding
turtle graphic of
p
in Figure
18
(d). Analogous features
occur for the paper-folding sequence as described in [
28
,
29
,
30
], and two variants are shown in Figures
18
(a) and
18(b).
6.5 Continued Fractions
Simple continued fractions often encode more information
than base expansions about a real number. Basic facts are that
a continued fraction terminates or repeats if and only if the
Figure 16.
Chaos games on various numbers, colored by frequency. Row 1:
C
3
,
a
3,5
, a (pseudo)random number, and
a
2,3
. Row 2:
C
4
,
p
, a (pseudo)random number, and
a
2,3
. Row 3:
C
6
,
a
3,2
, a (pseudo)random number, and
a
2,3
.
(a)(b)
Figure 17.
Walks on two automatic and nonnormal numbers.
2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013
55
Author’s
personal
copy
number is rational or a quadratic irrational, respectively; see
[
16
,
7
]. By contrast, the simple continued fractions for
p
and
e
start as follows in the standard compact form:
p
¼½
3
;
7
;
15
;
1
;
292
;
1
;
1
;
1
;
2
;
1
;
3
;
1
;
14
;
2
;
1
;
1
;
2
;
2
;
2
;
2
;
1
;
84
;
2
;
1
;
1
;
15
;
3
;
13
;
1
;
4
;
…
e
¼½
2
;
1
;
2
;
1
;
1
;
4
;
1
;
1
;
6
;
1
;
1
;
8
;
1
;
1
;
10
;
1
;
1
;
12
;
1
;
1
;
14
;
1
;
1
;
16
;
1
;
1
;
18
;
1
;
1
;
20
;
1
;
…
;
from which the surprising regularity of
e
and apparent
irregularity of
p
as continued fractions is apparent. The
counterpart to Borel’s theorem—that almost all numbers
are normal—is that almost all numbers have ‘‘normal’’
continued fractions
a
¼½
a
1
;
a
2
;
…
;
a
n
;
…
, for which the
Gauss–Kuzmin distribution
holds [
16
]: for each
k
¼
1
;
2
;
3
;
…
Prob
f
a
n
¼
k
g¼
log
2
1
1
ð
k
þ
1
Þ
2
!
;
ð
14
Þ
so that roughly 41.5% of the terms are 1, 16.99% are 2,
9.31% are 3, etc.
In Figure
19
, we show a histogram of the first 100 million
terms, computed by Neil Bickford and accessible at
http://
neilbickford.com/picf.htm
, of the continued fraction of
p
.
We have not yet found a satisfactory way to embed this in
a walk on a continued fraction, but in Figure
20
we show base-
4 walks on
p
and
e
where we use the remainder modulo 4 to
build the walk (with 0 being right, 1 being up, 2 being left, and
3 being down). We also show turtle plots on
p
,
e
.
Andrew Mattingly has observed that:
P
ROPOSITION
6.1
With probability
1,
amod-
4
random
walk (with
0
being right,
1
being up,
2
being left, and
3
being
down) on the simple continued fraction coefficients of a real
number is asymptotic to a line making a positive angle with
the x-axis of:
arctan
1
2
log
2
ð
p
=
2
Þ
1
log
2
ð
p
=
2
Þ
2 log
2
C
3
=
4
ðÞ
ðÞ
110
:
44
:
(a)
(b)
(d)
(c)
Figure 18.
Turtle plots on various constants with different rotating angles in base 2—where ‘‘0’’ gives forward motion and ‘‘1’’
rotation by a fixed angle.
56
THE MATHEMATICAL INTELLIGENCER
Author’s
personal
copy
P
ROOF
.
The result comes by summing the expected
Gauss–Kuzmin probabilities of each step being taken as
given by (
14
).
This is illustrated in Figure
20
(a) with a 90
anticlockwise
rotation; thus making the case that one must have some
apriori
knowledge before designing tools.
It is also instructive to compare digits and continued frac-
tions of numbers as horizontal matrix plots of the form already
used in Figure
8
. In Figure
21
, we show six pairs of million-
term digit-strings and the corresponding continued fraction.
In some cases both look random, in others one or the other
does.
In conclusion, we have only scratched the surface of what is
becoming possible in a period in which data—for example,
five-hundred million terms of the continued fraction or five-
trillion binary digits of
p
, full genomes, and much more—can
be downloaded from the Internet, then rendered and visually
mined, with fair rapidity.
(a)(b)
Figure 19.
Expected values of the Gauss–Kuzmin distribution of (14) and the values of 100 million terms of the continued fraction
of
p
.
(a)
(b)
(d)
(c)
Figure 20.
Uniform walks on
p
and
e
based on continued fractions.
2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013
57
Author’s
personal
copy
7 Appendix Selected Numerical Constants
In what follows,
x
:
¼
0
:
a
1
a
2
a
3
a
4
…
b
denotes the base-
b
expansion of the number
x
,sothat
x
¼
P
1
k
¼
1
a
k
b
k
.Base-
10 expansions are denoted without a subscript.
Catalan’s constant
(irrational?; normal?):
G
:
¼
X
1
k
¼
0
ð
1
Þ
k
ð
2
k
þ
1
Þ
2
¼
0
:
9159655941
…
ð
15
Þ
Champernowne numbers
(irrational; normal to correspond-
ing base):
C
b
:
¼
X
1
k
¼
1
P
b
k
1
m
¼
b
k
1
mb
km
ð
b
k
1
1
Þ
½
b
P
k
1
m
¼
0
m
ð
b
1
Þ
b
m
1
ð
16
Þ
C
10
¼
0
:
123456789101112
…
C
4
¼
0
:
1231011121320212223
…
4
Copeland–Erd
}
os constants
(irrational; normal to
corresponding base):
CE
ð
b
Þ
:
¼
X
1
k
¼
1
p
k
b
k
þ
P
k
m
¼
1
b
log
b
p
m
c
;
where
p
k
is the
k
th
prime number
ð
17
Þ
CE
ð
10
Þ¼
0
:
2357111317
…
CE
ð
2
Þ¼
0
:
1011101111
…
2
Exponential constant
(transcendental; normal?):
e
:
¼
X
1
k
¼
0
1
k
!
¼
2
:
7182818284
…
ð
18
Þ
Erd
}
os–Borwein constants
(irrational; normal?):
EB
ð
b
Þ
:
¼
X
1
k
¼
1
1
b
k
1
ð
19
Þ
EB
ð
2
Þ¼
1
:
6066951524
…
¼
1
:
212311001
…
4
Euler–Mascheroni constant
(irrational?; normal?):
c
:
¼
lim
m
!1
X
m
k
¼
1
1
k
log
m
!
¼
0
:
5772156649
…
ð
20
Þ
Fibonacci constant
(irrational [
12
, Theorem 2]; normal?):
F
:
¼
X
1
k
¼
1
F
k
10
1
þ
k
þ
P
k
m
¼
1
b
log
10
F
m
c
;
where
F
k
¼
1
þ
ffiffi
5
p
2
k
1
ffiffi
5
p
2
k
ffiffiffi
5
p
¼
0
:
011235813213455
…
Liouville number
(irrational; not
p
-automatic):
k
2
:
¼
X
1
k
¼
1
k
ð
k
Þþ
1
2
2
k
ð
22
Þ
Figure 21.
Million-step comparisons of base-4 digits and continued fractions. Row 1:
a
2,3
(
base
6) and
C
4
. Row 2:
e
and
p
. Row 3:
Q
1
and pseudorandom iterates; as listed from top left to bottom right.
58
THE MATHEMATICAL INTELLIGENCER
Author’s
personal
copy
Journal de Th ´eorie des Nombres
de Bordeaux
16
(2004), 487–518
On the binary expansions of algebraic numbers
par
David H. BAILEY, Jonathan M. BORWEIN,
Richard E. CRANDALL
et
Carl POMERANCE
R
´
esum
´
e.
En combinant des concepts de th ´eorie additive des nom-
bres avec des r ´esultats sur les d ´eveloppements binaires et les s ´eries
partielles, nous ´etablissons de nouvelles bornes pour la densit ´e de
1 dans les d ´eveloppements binaires de nombres alg ´ebriques r ´eels.
Un r ´esultat clef est que si un nombre r ´eel
y
est alg ´ebrique de degr ´e
D >
1, alors le nombre #(
|
y
|
,N
) de 1 dans le d ´eveloppement de
|
y
|
parmi les
N
premiers chiffres satisfait
#(
|
y
|
,N
)
> CN
1
/D
avec un nombre positif
C
(qui d ´epend de
y
), la minoration ´etant
vraie pour tout
N
suffisamment grand. On en d ´eduit la transcen-
dance d’une classe de nombres r ´eels
P
n
=
0
1
/
2
f
(
n
)
quand la fonc-
tion
f
, `a valeurs enti`eres, crot suffisamment vite, disons plus vite
que toute puissance de
n
. Grce `a ces m ´ethodes on red ´emontre la
transcendance du nombre de Kempner–Mahler
P
n
=
0
1
/
2
2
n
; nous
consid ´erons ´egalement des nombres ayant une densit ´e sensible-
ment plus grande de 1. Bien que le nombre
z
=
P
n
=
0
1
/
2
n
2
ait
une densit ´e de 1 trop grande pour que nous puissions lui appliquer
notre r ´esultat central, nous parvenons `a d ´evelopper une analyse
fine de th ´eorie des nombres avec des calculs ´etendus pour r ´ev ´eler
des propri ´et ´es de la structure binaire du nombre
z
2
.
Abstract.
Employing concepts from additive number theory, to-
gether with results on binary evaluations and partial series, we
establish bounds on the density of 1’s in the binary expansions
of real algebraic numbers. A central result is that if a real
y
has
algebraic degree
D >
1, then the number #(
|
y
|
,N
) of 1-bits in
the expansion of
|
y
|
through bit position
N
satisfies
#(
|
y
|
,N
)
> CN
1
/D
Manuscrit re ¸cu le 20 mars 2003.
Bailey’s work is supported by the Director, Office of Computational and Technology Research,
Division of Mathematical, Information, and Computational Sciences of the U.S. Department of
Energy, under contract number DE-AC03-76SF00098.
Borwein’s work is funded by NSERC and the Canada Research Chair Program.
488
D. H.
Bailey
, J. M.
Borwein
, R. E.
Crandall
, C.
Pomerance
for a positive number
C
(depending on
y
) and sufficiently large
N
. This in itself establishes the transcendency of a class of re-
als
P
n
=
0
1
/
2
f
(
n
)
where the integer-valued function
f
grows suffi-
ciently fast; say, faster than any fixed power of
n
. By these meth-
ods we re-establish the transcendency of the Kempner–Mahler
number
P
n
=
0
1
/
2
2
n
, yet we can also handle numbers with a sub-
stantially denser occurrence of 1’s. Though the number
z
=
P
n
=
0
1
/
2
n
2
has too high a 1’s density for application of our cen-
tral result, we are able to invoke some rather intricate number-
theoretical analysis and extended computations to reveal aspects
of the binary structure of
z
2
.
1. Introduction
Research into the statistical character of digit expansions is often focused
on the concept of normality. We call a real number
b
-normal if its base-
b
digits are random in a certain technical sense (see [31], [21], [3], and refer-
ences therein). Qualitatively speaking,
b
-normality requires every string of
k
consecutive base-
b
digits to occur, in the limit, 1
/b
k
of the time, as if the
digits are generated by tossing a “fair”
b
-sided die. In spite of the known
fact that almost all numbers are
b
-normal (in fact almost all are absolutely
normal, meaning
b
-normal for
every
base
b
= 2
,
3
,…
) not a single, shall
we say “genuine” fundamental constant such as
p,e,
log 2 is known to be
b
-normal for any
b
. Artificially constructed normals are known, such as the
2-normal binary Champernowne number [9]
C
2
= (0
.
11011100101110
…
)
2
,
obtained by sheer concatenation of the binary of positive integers. Previ-
ous research that motivates the present work includes [3], where a certain
“Hypothesis A” relevant to chaotic maps is shown to imply 2-normality of
p,
log 2
,?
(3); and [4], where the historical work of Korobov, Stoneham and
others is augmented to establish
b
-normality of, shall we say, “less artificial”
constants such as the numbers
P
n
=
0
1
/
(
c
n
b
c
n
) where
b,c >
1 are coprime.
Intriguing connections with yet other fields—such as ergodic theory—are
presented in [22].
Of interest for the present work is that all real algebraic irrationals are
widely believed—shall we say suspected—to be absolutely normal (and this
belief is at least a half-century old; see for example [6, 7]). This suspicion
is based on numerical and visual evidence that the digit expansions of
algebraics do appear empirically “random.” Yet again, the mathematical
situation is as bleak as can be: Not a single algebraic real is known to
be
b
-normal, nor has a single algebraic real irrational been shown not to
be
b
-normal; all of this regardless of the base
b
. Though we expect every
irrational algebraic real is absolutely normal, for all we know it could even
Binary expansions
489
be that some algebraics are absolutely abnormal, i.e. not
b
-normal for any
b
whatsoever (absolutely abnormal numbers do exist; see [28]).
Herein we focus on the binary scenario
b
= 2, and though we do not
achieve normality results per se, we establish useful lower bounds on the
occurrence of 1-bits in positive algebraics. Our central result is that if
y
is a real algebraic of degree
D >
1, then there exists a positive number
C
(depending only on
y
) such that for sufficiently large
N
the number
#(
|
y
|
,N
) of 1’s in the binary expansion of
|
y
|
through the
N
-th bit position
satisfies
#(
|
y
|
,N
)
> CN
1
/D
.
To achieve this bound we borrow ideas from additive number theory; in
particular we employ the notion of additive representations. This notion
is combined with our own bounds on the count of 1-bits resulting from
binary operations, and also with previous observations on “BBP tails” that
arise from arbitrary left-shifts of infinite series. In Section 6 we define and
elaborate on BBP tails.
Irrational numbers
y
for which #(
|
y
|
,N
) cannot achieve the above bound
for any degree
D
are necessarily transcendental. In this way we easily re-
establish the transcendency of the Kempner–Mahler number
M
=
X
n
=
0
1
2
2
n
,
first shown to be transcendental by Kempner [19], but the transcendency
cannot be established directly from the celebrated Thue–Siegel–Roth the-
orem on rational approximations to algebraics (there are interesting anec-
dotes concerning Mahler’s approach to such an impasse, including his re-
sults on
p
-adic Thue–Siegel theory and his functional methods; see [26, 27,
29]). Incidentally, the number
M
above is sometimes called the Fredholm
number, but this attribution may be historically erroneous [35]. (See also
[1] for more on the number
M
.)
We can also handle numbers having a higher density of 1’s than does
M
.
For example, by our methods the Fibonacci binary
X
=
X
n
=
0
1
2
F
n
having 1’s at Fibonacci-number positions 0
,
1
,
1
,
2
,
3
,
5
…
is transcenden-
tal. Now
X
was proved transcendental some decades ago [27] and explicit
irrationality measures and certain continued-fraction properties are known
for
X
[36]. In the present treatment, we can handle numbers like
X
but
where the growth of the exponents is more general than the classic growth
of the
F
n
.
490
D. H.
Bailey
, J. M.
Borwein
, R. E.
Crandall
, C.
Pomerance
With our central result we establish the transcendency of numbers whose
1-bits are substantially more dense than in the above examples, an example
of such a “denser” number being
X
n
=
3
1
2
b
n
log log
n
c
.
Incidentally, in the late stages of the present research project we found
that this notion of “digital thinking” to establish results in analysis had
been foreshadowed by a specific, pedagogical proof by M. Knight [20] that
for any base
b >
1
X
n
=
0
1
b
2
n
is transcendental (note that
b
= 2 gives the number
M
above). The author
used terms such as “islands” for flocks of digits guarded on both sides by
enough zeros to avoid carry problems when integral powers of a real number
are taken. As will be seen, such notions pervade also our own treatment;
however our results pertain to general 1-bit densities and not to specific
real numbers. Other historical foreshadowings of our approach exist [34]
[25]. (See also our Section 11 on open problems.)
Aside from transcendency results, we can employ the central theorem to
establish bounds on the algebraic degree. For example, we shall see that
X
n
=
0
1
2
n
k
,
X
p
prime
1
2
p
k
must have algebraic degrees at least
k,k
+ 1 respectively. (In this context
we think of a transcendental number as having infinite degree.) Thus for
example,
P
1
/
2
p
2
must be an at-least-cubic irrational.
There are interesting numbers that do not fall under the rubric of our
central theorem, such as the “borderline” case:
z
=
X
n
=
0
1
2
n
2
=
1
2
1 +
?
3
1
2
,
where
?
3
is the standard Jacobi theta function. The problem is that
#(
z,N
)
~
v
N
, so our central theorem does not give any information on
the algebraic degree of
z
. Yet we are able to use further number-theoretical
analysis—notably the theory of representations of integers as sums of two
squares—to establish quadratic irrationality for
z
. We further argue, on
the basis of such analysis, that
z
2
has almost all 0’s, and more precisely
that the 1’s count through the
N
-th bit position has a certain asymptotic
behavior. Incidentally the number
z
, being essentially the evaluation of
a theta function at an algebraic argument, is known to be transcendental
de Bordeaux
16
(2004), 487–518
On the binary expansions of algebraic numbers
par
David H. BAILEY, Jonathan M. BORWEIN,
Richard E. CRANDALL
et
Carl POMERANCE
R
´
esum
´
e.
En combinant des concepts de th ´eorie additive des nom-
bres avec des r ´esultats sur les d ´eveloppements binaires et les s ´eries
partielles, nous ´etablissons de nouvelles bornes pour la densit ´e de
1 dans les d ´eveloppements binaires de nombres alg ´ebriques r ´eels.
Un r ´esultat clef est que si un nombre r ´eel
y
est alg ´ebrique de degr ´e
D >
1, alors le nombre #(
|
y
|
,N
) de 1 dans le d ´eveloppement de
|
y
|
parmi les
N
premiers chiffres satisfait
#(
|
y
|
,N
)
> CN
1
/D
avec un nombre positif
C
(qui d ´epend de
y
), la minoration ´etant
vraie pour tout
N
suffisamment grand. On en d ´eduit la transcen-
dance d’une classe de nombres r ´eels
P
n
=
0
1
/
2
f
(
n
)
quand la fonc-
tion
f
, `a valeurs enti`eres, crot suffisamment vite, disons plus vite
que toute puissance de
n
. Grce `a ces m ´ethodes on red ´emontre la
transcendance du nombre de Kempner–Mahler
P
n
=
0
1
/
2
2
n
; nous
consid ´erons ´egalement des nombres ayant une densit ´e sensible-
ment plus grande de 1. Bien que le nombre
z
=
P
n
=
0
1
/
2
n
2
ait
une densit ´e de 1 trop grande pour que nous puissions lui appliquer
notre r ´esultat central, nous parvenons `a d ´evelopper une analyse
fine de th ´eorie des nombres avec des calculs ´etendus pour r ´ev ´eler
des propri ´et ´es de la structure binaire du nombre
z
2
.
Abstract.
Employing concepts from additive number theory, to-
gether with results on binary evaluations and partial series, we
establish bounds on the density of 1’s in the binary expansions
of real algebraic numbers. A central result is that if a real
y
has
algebraic degree
D >
1, then the number #(
|
y
|
,N
) of 1-bits in
the expansion of
|
y
|
through bit position
N
satisfies
#(
|
y
|
,N
)
> CN
1
/D
Manuscrit re ¸cu le 20 mars 2003.
Bailey’s work is supported by the Director, Office of Computational and Technology Research,
Division of Mathematical, Information, and Computational Sciences of the U.S. Department of
Energy, under contract number DE-AC03-76SF00098.
Borwein’s work is funded by NSERC and the Canada Research Chair Program.
488
D. H.
Bailey
, J. M.
Borwein
, R. E.
Crandall
, C.
Pomerance
for a positive number
C
(depending on
y
) and sufficiently large
N
. This in itself establishes the transcendency of a class of re-
als
P
n
=
0
1
/
2
f
(
n
)
where the integer-valued function
f
grows suffi-
ciently fast; say, faster than any fixed power of
n
. By these meth-
ods we re-establish the transcendency of the Kempner–Mahler
number
P
n
=
0
1
/
2
2
n
, yet we can also handle numbers with a sub-
stantially denser occurrence of 1’s. Though the number
z
=
P
n
=
0
1
/
2
n
2
has too high a 1’s density for application of our cen-
tral result, we are able to invoke some rather intricate number-
theoretical analysis and extended computations to reveal aspects
of the binary structure of
z
2
.
1. Introduction
Research into the statistical character of digit expansions is often focused
on the concept of normality. We call a real number
b
-normal if its base-
b
digits are random in a certain technical sense (see [31], [21], [3], and refer-
ences therein). Qualitatively speaking,
b
-normality requires every string of
k
consecutive base-
b
digits to occur, in the limit, 1
/b
k
of the time, as if the
digits are generated by tossing a “fair”
b
-sided die. In spite of the known
fact that almost all numbers are
b
-normal (in fact almost all are absolutely
normal, meaning
b
-normal for
every
base
b
= 2
,
3
,…
) not a single, shall
we say “genuine” fundamental constant such as
p,e,
log 2 is known to be
b
-normal for any
b
. Artificially constructed normals are known, such as the
2-normal binary Champernowne number [9]
C
2
= (0
.
11011100101110
…
)
2
,
obtained by sheer concatenation of the binary of positive integers. Previ-
ous research that motivates the present work includes [3], where a certain
“Hypothesis A” relevant to chaotic maps is shown to imply 2-normality of
p,
log 2
,?
(3); and [4], where the historical work of Korobov, Stoneham and
others is augmented to establish
b
-normality of, shall we say, “less artificial”
constants such as the numbers
P
n
=
0
1
/
(
c
n
b
c
n
) where
b,c >
1 are coprime.
Intriguing connections with yet other fields—such as ergodic theory—are
presented in [22].
Of interest for the present work is that all real algebraic irrationals are
widely believed—shall we say suspected—to be absolutely normal (and this
belief is at least a half-century old; see for example [6, 7]). This suspicion
is based on numerical and visual evidence that the digit expansions of
algebraics do appear empirically “random.” Yet again, the mathematical
situation is as bleak as can be: Not a single algebraic real is known to
be
b
-normal, nor has a single algebraic real irrational been shown not to
be
b
-normal; all of this regardless of the base
b
. Though we expect every
irrational algebraic real is absolutely normal, for all we know it could even
Binary expansions
489
be that some algebraics are absolutely abnormal, i.e. not
b
-normal for any
b
whatsoever (absolutely abnormal numbers do exist; see [28]).
Herein we focus on the binary scenario
b
= 2, and though we do not
achieve normality results per se, we establish useful lower bounds on the
occurrence of 1-bits in positive algebraics. Our central result is that if
y
is a real algebraic of degree
D >
1, then there exists a positive number
C
(depending only on
y
) such that for sufficiently large
N
the number
#(
|
y
|
,N
) of 1’s in the binary expansion of
|
y
|
through the
N
-th bit position
satisfies
#(
|
y
|
,N
)
> CN
1
/D
.
To achieve this bound we borrow ideas from additive number theory; in
particular we employ the notion of additive representations. This notion
is combined with our own bounds on the count of 1-bits resulting from
binary operations, and also with previous observations on “BBP tails” that
arise from arbitrary left-shifts of infinite series. In Section 6 we define and
elaborate on BBP tails.
Irrational numbers
y
for which #(
|
y
|
,N
) cannot achieve the above bound
for any degree
D
are necessarily transcendental. In this way we easily re-
establish the transcendency of the Kempner–Mahler number
M
=
X
n
=
0
1
2
2
n
,
first shown to be transcendental by Kempner [19], but the transcendency
cannot be established directly from the celebrated Thue–Siegel–Roth the-
orem on rational approximations to algebraics (there are interesting anec-
dotes concerning Mahler’s approach to such an impasse, including his re-
sults on
p
-adic Thue–Siegel theory and his functional methods; see [26, 27,
29]). Incidentally, the number
M
above is sometimes called the Fredholm
number, but this attribution may be historically erroneous [35]. (See also
[1] for more on the number
M
.)
We can also handle numbers having a higher density of 1’s than does
M
.
For example, by our methods the Fibonacci binary
X
=
X
n
=
0
1
2
F
n
having 1’s at Fibonacci-number positions 0
,
1
,
1
,
2
,
3
,
5
…
is transcenden-
tal. Now
X
was proved transcendental some decades ago [27] and explicit
irrationality measures and certain continued-fraction properties are known
for
X
[36]. In the present treatment, we can handle numbers like
X
but
where the growth of the exponents is more general than the classic growth
of the
F
n
.
490
D. H.
Bailey
, J. M.
Borwein
, R. E.
Crandall
, C.
Pomerance
With our central result we establish the transcendency of numbers whose
1-bits are substantially more dense than in the above examples, an example
of such a “denser” number being
X
n
=
3
1
2
b
n
log log
n
c
.
Incidentally, in the late stages of the present research project we found
that this notion of “digital thinking” to establish results in analysis had
been foreshadowed by a specific, pedagogical proof by M. Knight [20] that
for any base
b >
1
X
n
=
0
1
b
2
n
is transcendental (note that
b
= 2 gives the number
M
above). The author
used terms such as “islands” for flocks of digits guarded on both sides by
enough zeros to avoid carry problems when integral powers of a real number
are taken. As will be seen, such notions pervade also our own treatment;
however our results pertain to general 1-bit densities and not to specific
real numbers. Other historical foreshadowings of our approach exist [34]
[25]. (See also our Section 11 on open problems.)
Aside from transcendency results, we can employ the central theorem to
establish bounds on the algebraic degree. For example, we shall see that
X
n
=
0
1
2
n
k
,
X
p
prime
1
2
p
k
must have algebraic degrees at least
k,k
+ 1 respectively. (In this context
we think of a transcendental number as having infinite degree.) Thus for
example,
P
1
/
2
p
2
must be an at-least-cubic irrational.
There are interesting numbers that do not fall under the rubric of our
central theorem, such as the “borderline” case:
z
=
X
n
=
0
1
2
n
2
=
1
2
1 +
?
3
1
2
,
where
?
3
is the standard Jacobi theta function. The problem is that
#(
z,N
)
~
v
N
, so our central theorem does not give any information on
the algebraic degree of
z
. Yet we are able to use further number-theoretical
analysis—notably the theory of representations of integers as sums of two
squares—to establish quadratic irrationality for
z
. We further argue, on
the basis of such analysis, that
z
2
has almost all 0’s, and more precisely
that the 1’s count through the
N
-th bit position has a certain asymptotic
behavior. Incidentally the number
z
, being essentially the evaluation of
a theta function at an algebraic argument, is known to be transcendental
Ramanujan J (2012) 29:409–422
DOI 10.1007/s11139-012-9417-3
Nonnormality of Stoneham constants
David H. Bailey
·
Jonathan M. Borwein
Received: 15 January 2012 / Accepted: 5 July 2012 / Published online: 24 July 2012
© Springer Science+Business Media, LLC 2012
Abstract
This paper examines “Stoneham constants,” namely real numbers of the
form
a
b,c
=
n
=
1
1
/(c
n
b
c
n
)
, for coprime integers
b
=
2 and
c
=
2. These are of
interest because, according to previous studies,
a
b,c
is known to be
b
-normal, mean-
ing that every
m
-long string of base-
b
digits appears in the base-
b
expansion of the
constant with precisely the limiting frequency
b
-
m
. So, for example, the constant
a
2
,
3
=
n
=
1
1
/(
3
n
2
3
n
)
is 2-normal. More recently it was established that
a
b,c
is
not
bc
-normal, so, for example,
a
2
,
3
is provably
not
6-normal. In this paper, we ex-
tend these findings by showing that
a
b,c
is
not
B
-normal, where
B
=
b
p
c
q
r
,for
integers
b
and
c
as above,
p,q,r
=
1, neither
b
nor
c
divide
r
, and the condition
D
=
c
q/p
r
1
/p
/b
c
-
1
<
1 is satisfied. It is not known whether or not this is a com-
plete catalog of bases to which
a
b,c
is nonnormal. We also show that the sum of two
B
-nonnormal Stoneham constants as defined above, subject to some restrictions, is
B
-nonnormal.
Keywords
Normality of irrational numbers
·
Nonnormality of irrational numbers
·
Stoneham numbers
·
Normality of sums
Mathematics Subject Classification
Primary 11K16
·
Secondary 11K31
D.H. Bailey supported in part by the Director, Office of Computational and Technology Research,
Division of Mathematical, Information, and Computational Sciences of the U.S. Department of
Energy, under contract number DE-AC02-05CH11231.
D.H. Bailey
Lawrence Berkeley National Laboratory, Berkeley, CA 94720, USA
e-mail:
DHBailey@lbl.gov
J.M. Borwein (
)
Centre for Computer Assisted Research Mathematics and its Applications (CARMA), University of
Newcastle, Callaghan, NSW 2308, Australia
e-mail:
jonathan.borwein@newcastle.edu.au
410 D.H. Bailey, J.M. Borwein
1 Introduction
The question of whether (and why) the digits of well-known constants of mathematics
are statistically random in some sense has fascinated mathematicians from the dawn
of history. Indeed, one prime motivation in computing and analyzing digits of
p
is to
explore the age-old question of whether and why these digits appear “random.” The
first computation on ENIAC in 1949 of
p
to 2037 decimal places was proposed by
John von Neumann so as to shed some light on the distribution of
p
(and of
e
)[
12
,
pp. 277–281]. Since then, numerous computer-based statistical checks of the digits of
p
, for instance, so far have failed to disclose any deviation from reasonable statistical
norms.
Analyses of the digits of
p
and related constants are discussed in greater length
in [
9
], and by using graphical tools in [
4
]. We should mention that using the graph-
ical tools described in [
4
], at least one of the results proved in this paper, namely
Theorem
2
, is visually quite compelling.
In the following, we say a real constant
a
is
b
-normal
if, given the positive in-
teger
b
=
2, every
m
-long string of base-
b
digits appears in the base-
b
expansion
of
a
with precisely the expected limiting frequency 1
/b
m
. It is a well-established
albeit counter-intuitive fact that given an integer
b
=
2, almost all real numbers, in
the measure theory sense, are
b
-normal. What’s more, almost all real numbers are
b
-
normal simultaneously for all positive integer bases (a property known as “absolutely
normal”).
Nonetheless, it has been frustratingly difficult to exhibit explicit and natural ex-
amples of normal numbers, even of numbers that are normal just to a single given
base
b
. The first constant to be proven 10-normal was the Champernowne number,
namely the constant 0
.
12345678910111213141516
…
, produced by concatenating
the decimal representation of all positive integers in order. Fine additional results of
this sort were established in the 1940s by Copeland and Erd
?
os [
18
].
The situation with regards to other, more “natural” constants of mathematics re-
mains singularly grim. Normality proofs are not available for any well-known con-
stant such as
p,e,
log 2
,
v
2. We do not even know, say, that a 1 appears 1
/
2ofthe
time, in the limit, in the binary expansion of
v
2 (although it certainly appears to,
from extensive empirical analysis). For that matter, it is widely believed that
every
ir-
rational algebraic number (i.e., every irrational root of an algebraic polynomial with
integer coefficients) is
b
-normal to all positive integer bases
b
, but there is no proof,
not for any specific algebraic number to any specific base.
Recently the present authors, together with Richard Crandall and Carl Pomer-
ance, proved the following: If a real
y
has algebraic degree
D>
1, then the number
#
(
|
y
|
,N)
of 1-bits in the binary expansion of
|
y
|
through bit position
N
satisfies
#
(
|
y
|
,N)>CN
1
/D
, for a positive number
C
(depending on
y
) and all sufficiently
large
N
[
8
]. Related results and extensions have been obtained in [
1
,
20
], and an inter-
esting extension to non-zero integers in general bases is to be found in [
2
]. However,
these results all fall far short of establishing
b
-normality for any irrational algebraic
in any base
b
, even in the single-digit sense.
It is known that whenever
a
is
b
-normal, then so is
ra
and
r
+
a
for any nonzero
positive rational
r
[
13
, pp. 165–166]. It is also easy to see that if there is a positive
Nonnormality of Stoneham constants 411
integer
n
such that integers
a
=
2 and
b
=
2 satisfy
a
=
b
n
, then any real constant that
is
a
-normal is also
b
-normal. Recently Hertling proved an interesting converse: If
there is no such
n
, then there are an uncountable number of counterexamples, namely
constants that are
a
-normal but not
b
-normal [
19
]. Moving in the other direction,
Greg Martin has succeeded in constructing an absolutely nonnormal number, namely
one which fails to be
b
-normal for any integer base
b
=
2[
21
].
2 A recent normality result
Given a real number
r
in
[
0
,
1
)
, with
r
k
denoting the
k
th binary digit of
r
,[
6
]showed
the real number
a
2
,
3
(r)
:=
8
k
=
1
1
3
k
2
3
k
+
r
k
(1)
is 2-normal. If
r
=
s
, then
a
2
,
3
(r)
=
a
2
,
3
(s)
, so these constants are all distinct; and the
class is uncountable. For example, the constant
a
2
,
3
=
a
2
,
3
(
0
)
=
k
=
1
1
/(
3
k
2
3
k
)
=
0
.
0418836808315030
…
is provably 2-normal (as proven by Stoneham in 1973 [
22
]).
A similar result applies if 2 and 3 in formula (
1
) are replaced by any pair of coprime
integers
(b, c)
with
b
=
2 and
c
=
2[
6
]. More recently, [
7
] established 2-normality of
a
2
,
3
by a simpler argument, by utilizing the “hot spot” Lemma
1
below, proven using
ergodic theory methods. In [
5
], this proof was extended to the more general case
a
b,c
,
The result itself was already [
6
].
Let
A(a, y, n, m)
denote the
count of occurrences
where the
m
-long binary string
y
is found to start at position
p
in the base-
b
expansion of
a
, where 1
=
p
=
n
.
Lemma 1
(“Hot Spot” Lemma)
If
x
is not
b
-normal
,
then there is some
y
?[
0
,
1
)
with the property
lim inf
m
?8
lim sup
n
?8
b
m
A(x,y,n,m)
n
=8
.
(2)
Conversely
,
if for all
y
?[
0
,
1
)
,
lim inf
m
?8
lim sup
n
?8
b
m
A(x,y,n,m)
n
<
8
,
(3)
then
x
is
b
-normal
.
Note that Lemma
1
implies that if t
a
is not
b
-normal, there must exist some in-
terval
[
r
1
,s
1
)
in which successive shifts of the base-
b
expansion of
a
visit
[
r
1
,s
1
)
ten times more frequently, in the limit, relative to its length
s
1
-
r
1
; there must be
another interval
[
r
2
,s
2
)
that is visited 100 times more often relative to its length; and
so on. Indeed, there is at least one real number
y
(a “hot spot”) such that sufficiently
small neighborhoods of
y
are visited too often by an arbitrarily large factor, relative
to the lengths of these neighborhoods. On the other hand, if it can be established that
412 D.H. Bailey, J.M. Borwein
no subinterval of the unit interval is visited, say, 1,000 times more often in the limit
relative to its length, this suffices to prove that the constant in question is
b
-normal.
This idea leads to:
Theorem 1
For every coprime pair of integers
(b, c)
with
b
=
2
and
c
=
2,
the con-
stant
a
b,c
=
m
=
1
1
/(c
m
b
c
m
)
is
b
-normal
.
Proof outline [
5
]
We write the fraction immediately following position
n
in the base-
b
expansion of
a
b,c
as:
b
n
a
b,c
mod 1
=
8
m
=
1
b
n
-
c
m
mod
c
m
c
m
mod 1 (4)
=
log
c
n
m
=
1
b
n
-
c
m
mod
c
m
c
m
mod 1
+
8
m
=
log
c
n
+
1
b
n
-
c
m
c
m
.
(5)
Now, the first expression can be generated by the recursion
z
0
=
0 and, for
n
=
1,
z
n
=
(bz
n
-
1
+
r
n
)
mod 1
,
(6)
where
r
n
=
1
/n
if
n
=
c
k
for some integer
k
, and zero otherwise. Consider the case
b
=
3 and
c
=
4. The first few members of the sequence (
6
)are:
0
,
0
,
0
,
(once)
1
4
,
3
4
,
(repeated 6 times)
5
16
,
15
16
,
13
16
,
7
16
,
(12 times)
,
21
64
,
63
64
,
61
64
,
55
64
,
37
64
,
47
64
,
13
64
,
39
64
,
53
64
,
31
64
,
29
64
,
23
64
,
5
64
,
15
64
,
45
64
,
7
64
,
(12 times), etc. (7)
Note that 1
/
2 is omitted in the first set, 1
/
8, 3
/
8, 5
/
8, 7
/
8 in the second, and
the fractions with 32 in the denominator in the third set. This pattern holds so long
as
b
=
2 and
c
=
2 are coprime [
6
]: if
n<c
p
+
1
then
z
n
is a multiple of 1
/c
p
, and
the set
(z
k
,
1
=
k
=
n)
contains at most
t
repetitions of any particular value. (Here
t
depends only on
b
and
c
.For
(b, c)
=
(
2
,
3
)
, the factor
t
=
3. For the case
(
3
,
4
)
,
t
=
12.) These fractions
(z
k
)
yield accurate approximations to the shifted fractions
b
n
a
b,c
mod 1 of
a
b,c
. On examining (
5
) it transpires that for
(b, c)
as above and
n
=
c
,
b
n
a
b,c
mod 1
-
z
n
<
1
9
n
(8)
(and in most cases is much smaller than this).
To establish that
a
b,c
is
b
-normal via Lemma
1
, we find an upper bound for
b
m
A(a
b,c
,y,n,m)/n
, good for all
y
?[
0
,
1
)
and all
m
=
1 and appeal to Lemma
1
to show
a
b,c
is
b
-normal.
Nonnormality of Stoneham constants 413
3 A general nonnormality result
By Theorem
1
, the Stoneham constant
a
2
,
3
=
k
=
0
1
/(
3
k
2
3
k
)
is 2-normal. Almost
as interesting is the fact that
a
2
,
3
is
not
6-normal. This was first demonstrated in [
5
].
Next, we briefly sketch why this is so. After this we prove a rigorous theorem for
general Stoneham constants.
First note that the digits immediately following position
n
in the base-6 expansion
of
a
2
,
3
can be obtained by computing 6
n
a
2
,
3
mod 1, which can be written as
6
n
a
2
,
3
mod 1
=
log
3
n
m
=
1
3
n
-
m
2
n
-
3
m
mod 1
+
8
m
=
log
3
n
+
1
3
n
-
m
2
n
-
3
m
.
(9)
Note that the first portion of this expression is
zero
, since all terms of the summation
are integers. That leaves the second expression.
Consider the case when
n
=
3
m
, where
m
=
1 is an integer, and examine just the
first term of the second summation. We see that this expression is
3
3
m
-
(m
+
1
)
2
3
m
-
3
m
+
1
=
3
3
m
-
m
-
1
2
-
2
·
3
m
=
(
3
/
4
)
3
m
/
3
m
+
1
.
(10)
We can generously bound the sum of all terms of the second summation by 1.00001
times this amount, for all
m
=
1, and by many times closer to unity for all
m
=
2, etc.
Thus, we have
6
3
m
a
2
,
3
mod 1
˜
(
3
4
)
3
m
3
m
+
1
.
(11)
This approximation is as accurate as one wishes (in ratio) for sufficiently large
m
.
Given the very small size of the expression
(
3
/
4
)
3
m
/
3
m
+
1
for even moderate-sized
m
, it is clear the base-6 expansion will have very long stretches of zeroes beginning
at positions 3
m
+
1. For example, by explicitly computing
a
2
,
3
to high precision, one
can produce the counts of consecutive zeroes
Z
m
that immediately follow position
3
m
in the base-6 expansion of
a
2
,
3
—see Tables
1
and
2
.
In total, there 14256 zeroes in the first ten segments of zeroes, which, including
the last segment, span the first 59049
+
9487
=
68536 base-6 digits of
a
2
,
3
.Inthis
tabulation we have, of course, ignored the many zeroes in the large “random” seg-
ments of the expansion. Thus, the fraction of the first 68536 digits that is zero is at
least 14256
/
68536
=
0
.
20800747
…
. This is significantly more than the expected
value 1
/
6
=
0
.
166666
…
. A careful estimate of the limiting fraction yields the de-
sired nonnormality result.
It is worth pointing out that in the parlance of Lemma
1
, zero is a “hot spot” for
the base-6 expansion of
a
2
,
3
. This is because all sufficiently small neighborhoods
of zero are visited too often, by an arbitrarily large factor, in a subsequence of the
shifted fractions of its base-6 expansion. The nonnormality of
a
2
,
3
and some related
constants is explored graphically in [
4
], where the patterns shown above in Table
1
can be seen even more clearly.
We turn to the promised generalization for general Stoneham constants
a
b,c
:
414 D.H. Bailey, J.M. Borwein
Ta b l e 1
Base-6 expansion of
a
2
,
3
0.
01301404300033342511305021300000012435550454322330115002435
25320551352 34354101043000
00000000000005141130054040555455303144250433435101241345 2351125142125134505503545015
053522052044340452151505102411552500425130 051124454001044131150032420303213000000000
0000000000000000000000000000 00000142120343111214520135254453421134122402205253010542
04423552411055 41501552043504145554003101453030335320025343404013012401
04453254343502
14202043241502555510100404330004554411450103133145115101445
14123443342 34124005513133
35045423530553151153501533452435450250055521453054234342 1530350125024205404135451231
323245353031534552304115020154242121145201 542222534340340450530123325534440443103332
4453321414150142334545424124 32031253400501341502455144043000000000000000000000000000
00000000000000 00000000000000000000000000000000000000000000000000000000
00000000000000
00000000003133505424444311110555341410520145402134123130
01424333133115
…
Ta b l e 2
Counts
Z
m
of
consecutive zeroes immediately
following position 3
m
in the
base-6 expansion of
a
2
,
3
m
3
m
Z
m
131
293
3276
48116
5 243 42
6 729 121
7 2187 356
8 6561 1058
9 19683 3166
10 59049 9487
Theorem 2
Given coprime integers
b
=
2
and
c
=
2,
and integers
p,q,r
=
1,
with neither
b
nor
c
dividing
r
,
let
B
=
b
p
c
q
r
.
Assume that the condition
D
=
c
q/p
r
1
/p
/b
c
-
1
<
1
is satisfied
.
Then the constant
a
b,c
=
k
=
0
1
/(c
k
b
c
k
)
is
B
-nonnormal
.
Proof
Let
n
=
c
m
/p
, and let
w
=
np /c
m
, so that
n
=
wc
m
/p
. Note that for even
moderately large
m
, relative to
p
, the fraction
w
is very close to one. Let
Q
m
be the
shifted fraction of
a
b,c
immediately following position
n
in its base-
B
expansion.
One can write
Q
m
=
B
n
a
b,c
mod 1
=
m
k
=
0
b
pn
-
c
k
c
qn
-
k
r
n
mod 1
+
8
k
=
m
+
1
b
pn
-
c
k
c
qn
-
k
r
n
(12)
=
8
k
=
m
+
1
b
pn
-
c
k
c
qn
-
k
r
n
=
8
k
=
m
+
1
c
qwc
m
/p
-
k
r
wc
m
/p
b
c
k
-
wc
m
.
(13)
DOI 10.1007/s11139-012-9417-3
Nonnormality of Stoneham constants
David H. Bailey
·
Jonathan M. Borwein
Received: 15 January 2012 / Accepted: 5 July 2012 / Published online: 24 July 2012
© Springer Science+Business Media, LLC 2012
Abstract
This paper examines “Stoneham constants,” namely real numbers of the
form
a
b,c
=
n
=
1
1
/(c
n
b
c
n
)
, for coprime integers
b
=
2 and
c
=
2. These are of
interest because, according to previous studies,
a
b,c
is known to be
b
-normal, mean-
ing that every
m
-long string of base-
b
digits appears in the base-
b
expansion of the
constant with precisely the limiting frequency
b
-
m
. So, for example, the constant
a
2
,
3
=
n
=
1
1
/(
3
n
2
3
n
)
is 2-normal. More recently it was established that
a
b,c
is
not
bc
-normal, so, for example,
a
2
,
3
is provably
not
6-normal. In this paper, we ex-
tend these findings by showing that
a
b,c
is
not
B
-normal, where
B
=
b
p
c
q
r
,for
integers
b
and
c
as above,
p,q,r
=
1, neither
b
nor
c
divide
r
, and the condition
D
=
c
q/p
r
1
/p
/b
c
-
1
<
1 is satisfied. It is not known whether or not this is a com-
plete catalog of bases to which
a
b,c
is nonnormal. We also show that the sum of two
B
-nonnormal Stoneham constants as defined above, subject to some restrictions, is
B
-nonnormal.
Keywords
Normality of irrational numbers
·
Nonnormality of irrational numbers
·
Stoneham numbers
·
Normality of sums
Mathematics Subject Classification
Primary 11K16
·
Secondary 11K31
D.H. Bailey supported in part by the Director, Office of Computational and Technology Research,
Division of Mathematical, Information, and Computational Sciences of the U.S. Department of
Energy, under contract number DE-AC02-05CH11231.
D.H. Bailey
Lawrence Berkeley National Laboratory, Berkeley, CA 94720, USA
e-mail:
DHBailey@lbl.gov
J.M. Borwein (
)
Centre for Computer Assisted Research Mathematics and its Applications (CARMA), University of
Newcastle, Callaghan, NSW 2308, Australia
e-mail:
jonathan.borwein@newcastle.edu.au
410 D.H. Bailey, J.M. Borwein
1 Introduction
The question of whether (and why) the digits of well-known constants of mathematics
are statistically random in some sense has fascinated mathematicians from the dawn
of history. Indeed, one prime motivation in computing and analyzing digits of
p
is to
explore the age-old question of whether and why these digits appear “random.” The
first computation on ENIAC in 1949 of
p
to 2037 decimal places was proposed by
John von Neumann so as to shed some light on the distribution of
p
(and of
e
)[
12
,
pp. 277–281]. Since then, numerous computer-based statistical checks of the digits of
p
, for instance, so far have failed to disclose any deviation from reasonable statistical
norms.
Analyses of the digits of
p
and related constants are discussed in greater length
in [
9
], and by using graphical tools in [
4
]. We should mention that using the graph-
ical tools described in [
4
], at least one of the results proved in this paper, namely
Theorem
2
, is visually quite compelling.
In the following, we say a real constant
a
is
b
-normal
if, given the positive in-
teger
b
=
2, every
m
-long string of base-
b
digits appears in the base-
b
expansion
of
a
with precisely the expected limiting frequency 1
/b
m
. It is a well-established
albeit counter-intuitive fact that given an integer
b
=
2, almost all real numbers, in
the measure theory sense, are
b
-normal. What’s more, almost all real numbers are
b
-
normal simultaneously for all positive integer bases (a property known as “absolutely
normal”).
Nonetheless, it has been frustratingly difficult to exhibit explicit and natural ex-
amples of normal numbers, even of numbers that are normal just to a single given
base
b
. The first constant to be proven 10-normal was the Champernowne number,
namely the constant 0
.
12345678910111213141516
…
, produced by concatenating
the decimal representation of all positive integers in order. Fine additional results of
this sort were established in the 1940s by Copeland and Erd
?
os [
18
].
The situation with regards to other, more “natural” constants of mathematics re-
mains singularly grim. Normality proofs are not available for any well-known con-
stant such as
p,e,
log 2
,
v
2. We do not even know, say, that a 1 appears 1
/
2ofthe
time, in the limit, in the binary expansion of
v
2 (although it certainly appears to,
from extensive empirical analysis). For that matter, it is widely believed that
every
ir-
rational algebraic number (i.e., every irrational root of an algebraic polynomial with
integer coefficients) is
b
-normal to all positive integer bases
b
, but there is no proof,
not for any specific algebraic number to any specific base.
Recently the present authors, together with Richard Crandall and Carl Pomer-
ance, proved the following: If a real
y
has algebraic degree
D>
1, then the number
#
(
|
y
|
,N)
of 1-bits in the binary expansion of
|
y
|
through bit position
N
satisfies
#
(
|
y
|
,N)>CN
1
/D
, for a positive number
C
(depending on
y
) and all sufficiently
large
N
[
8
]. Related results and extensions have been obtained in [
1
,
20
], and an inter-
esting extension to non-zero integers in general bases is to be found in [
2
]. However,
these results all fall far short of establishing
b
-normality for any irrational algebraic
in any base
b
, even in the single-digit sense.
It is known that whenever
a
is
b
-normal, then so is
ra
and
r
+
a
for any nonzero
positive rational
r
[
13
, pp. 165–166]. It is also easy to see that if there is a positive
Nonnormality of Stoneham constants 411
integer
n
such that integers
a
=
2 and
b
=
2 satisfy
a
=
b
n
, then any real constant that
is
a
-normal is also
b
-normal. Recently Hertling proved an interesting converse: If
there is no such
n
, then there are an uncountable number of counterexamples, namely
constants that are
a
-normal but not
b
-normal [
19
]. Moving in the other direction,
Greg Martin has succeeded in constructing an absolutely nonnormal number, namely
one which fails to be
b
-normal for any integer base
b
=
2[
21
].
2 A recent normality result
Given a real number
r
in
[
0
,
1
)
, with
r
k
denoting the
k
th binary digit of
r
,[
6
]showed
the real number
a
2
,
3
(r)
:=
8
k
=
1
1
3
k
2
3
k
+
r
k
(1)
is 2-normal. If
r
=
s
, then
a
2
,
3
(r)
=
a
2
,
3
(s)
, so these constants are all distinct; and the
class is uncountable. For example, the constant
a
2
,
3
=
a
2
,
3
(
0
)
=
k
=
1
1
/(
3
k
2
3
k
)
=
0
.
0418836808315030
…
is provably 2-normal (as proven by Stoneham in 1973 [
22
]).
A similar result applies if 2 and 3 in formula (
1
) are replaced by any pair of coprime
integers
(b, c)
with
b
=
2 and
c
=
2[
6
]. More recently, [
7
] established 2-normality of
a
2
,
3
by a simpler argument, by utilizing the “hot spot” Lemma
1
below, proven using
ergodic theory methods. In [
5
], this proof was extended to the more general case
a
b,c
,
The result itself was already [
6
].
Let
A(a, y, n, m)
denote the
count of occurrences
where the
m
-long binary string
y
is found to start at position
p
in the base-
b
expansion of
a
, where 1
=
p
=
n
.
Lemma 1
(“Hot Spot” Lemma)
If
x
is not
b
-normal
,
then there is some
y
?[
0
,
1
)
with the property
lim inf
m
?8
lim sup
n
?8
b
m
A(x,y,n,m)
n
=8
.
(2)
Conversely
,
if for all
y
?[
0
,
1
)
,
lim inf
m
?8
lim sup
n
?8
b
m
A(x,y,n,m)
n
<
8
,
(3)
then
x
is
b
-normal
.
Note that Lemma
1
implies that if t
a
is not
b
-normal, there must exist some in-
terval
[
r
1
,s
1
)
in which successive shifts of the base-
b
expansion of
a
visit
[
r
1
,s
1
)
ten times more frequently, in the limit, relative to its length
s
1
-
r
1
; there must be
another interval
[
r
2
,s
2
)
that is visited 100 times more often relative to its length; and
so on. Indeed, there is at least one real number
y
(a “hot spot”) such that sufficiently
small neighborhoods of
y
are visited too often by an arbitrarily large factor, relative
to the lengths of these neighborhoods. On the other hand, if it can be established that
412 D.H. Bailey, J.M. Borwein
no subinterval of the unit interval is visited, say, 1,000 times more often in the limit
relative to its length, this suffices to prove that the constant in question is
b
-normal.
This idea leads to:
Theorem 1
For every coprime pair of integers
(b, c)
with
b
=
2
and
c
=
2,
the con-
stant
a
b,c
=
m
=
1
1
/(c
m
b
c
m
)
is
b
-normal
.
Proof outline [
5
]
We write the fraction immediately following position
n
in the base-
b
expansion of
a
b,c
as:
b
n
a
b,c
mod 1
=
8
m
=
1
b
n
-
c
m
mod
c
m
c
m
mod 1 (4)
=
log
c
n
m
=
1
b
n
-
c
m
mod
c
m
c
m
mod 1
+
8
m
=
log
c
n
+
1
b
n
-
c
m
c
m
.
(5)
Now, the first expression can be generated by the recursion
z
0
=
0 and, for
n
=
1,
z
n
=
(bz
n
-
1
+
r
n
)
mod 1
,
(6)
where
r
n
=
1
/n
if
n
=
c
k
for some integer
k
, and zero otherwise. Consider the case
b
=
3 and
c
=
4. The first few members of the sequence (
6
)are:
0
,
0
,
0
,
(once)
1
4
,
3
4
,
(repeated 6 times)
5
16
,
15
16
,
13
16
,
7
16
,
(12 times)
,
21
64
,
63
64
,
61
64
,
55
64
,
37
64
,
47
64
,
13
64
,
39
64
,
53
64
,
31
64
,
29
64
,
23
64
,
5
64
,
15
64
,
45
64
,
7
64
,
(12 times), etc. (7)
Note that 1
/
2 is omitted in the first set, 1
/
8, 3
/
8, 5
/
8, 7
/
8 in the second, and
the fractions with 32 in the denominator in the third set. This pattern holds so long
as
b
=
2 and
c
=
2 are coprime [
6
]: if
n<c
p
+
1
then
z
n
is a multiple of 1
/c
p
, and
the set
(z
k
,
1
=
k
=
n)
contains at most
t
repetitions of any particular value. (Here
t
depends only on
b
and
c
.For
(b, c)
=
(
2
,
3
)
, the factor
t
=
3. For the case
(
3
,
4
)
,
t
=
12.) These fractions
(z
k
)
yield accurate approximations to the shifted fractions
b
n
a
b,c
mod 1 of
a
b,c
. On examining (
5
) it transpires that for
(b, c)
as above and
n
=
c
,
b
n
a
b,c
mod 1
-
z
n
<
1
9
n
(8)
(and in most cases is much smaller than this).
To establish that
a
b,c
is
b
-normal via Lemma
1
, we find an upper bound for
b
m
A(a
b,c
,y,n,m)/n
, good for all
y
?[
0
,
1
)
and all
m
=
1 and appeal to Lemma
1
to show
a
b,c
is
b
-normal.
Nonnormality of Stoneham constants 413
3 A general nonnormality result
By Theorem
1
, the Stoneham constant
a
2
,
3
=
k
=
0
1
/(
3
k
2
3
k
)
is 2-normal. Almost
as interesting is the fact that
a
2
,
3
is
not
6-normal. This was first demonstrated in [
5
].
Next, we briefly sketch why this is so. After this we prove a rigorous theorem for
general Stoneham constants.
First note that the digits immediately following position
n
in the base-6 expansion
of
a
2
,
3
can be obtained by computing 6
n
a
2
,
3
mod 1, which can be written as
6
n
a
2
,
3
mod 1
=
log
3
n
m
=
1
3
n
-
m
2
n
-
3
m
mod 1
+
8
m
=
log
3
n
+
1
3
n
-
m
2
n
-
3
m
.
(9)
Note that the first portion of this expression is
zero
, since all terms of the summation
are integers. That leaves the second expression.
Consider the case when
n
=
3
m
, where
m
=
1 is an integer, and examine just the
first term of the second summation. We see that this expression is
3
3
m
-
(m
+
1
)
2
3
m
-
3
m
+
1
=
3
3
m
-
m
-
1
2
-
2
·
3
m
=
(
3
/
4
)
3
m
/
3
m
+
1
.
(10)
We can generously bound the sum of all terms of the second summation by 1.00001
times this amount, for all
m
=
1, and by many times closer to unity for all
m
=
2, etc.
Thus, we have
6
3
m
a
2
,
3
mod 1
˜
(
3
4
)
3
m
3
m
+
1
.
(11)
This approximation is as accurate as one wishes (in ratio) for sufficiently large
m
.
Given the very small size of the expression
(
3
/
4
)
3
m
/
3
m
+
1
for even moderate-sized
m
, it is clear the base-6 expansion will have very long stretches of zeroes beginning
at positions 3
m
+
1. For example, by explicitly computing
a
2
,
3
to high precision, one
can produce the counts of consecutive zeroes
Z
m
that immediately follow position
3
m
in the base-6 expansion of
a
2
,
3
—see Tables
1
and
2
.
In total, there 14256 zeroes in the first ten segments of zeroes, which, including
the last segment, span the first 59049
+
9487
=
68536 base-6 digits of
a
2
,
3
.Inthis
tabulation we have, of course, ignored the many zeroes in the large “random” seg-
ments of the expansion. Thus, the fraction of the first 68536 digits that is zero is at
least 14256
/
68536
=
0
.
20800747
…
. This is significantly more than the expected
value 1
/
6
=
0
.
166666
…
. A careful estimate of the limiting fraction yields the de-
sired nonnormality result.
It is worth pointing out that in the parlance of Lemma
1
, zero is a “hot spot” for
the base-6 expansion of
a
2
,
3
. This is because all sufficiently small neighborhoods
of zero are visited too often, by an arbitrarily large factor, in a subsequence of the
shifted fractions of its base-6 expansion. The nonnormality of
a
2
,
3
and some related
constants is explored graphically in [
4
], where the patterns shown above in Table
1
can be seen even more clearly.
We turn to the promised generalization for general Stoneham constants
a
b,c
:
414 D.H. Bailey, J.M. Borwein
Ta b l e 1
Base-6 expansion of
a
2
,
3
0.
01301404300033342511305021300000012435550454322330115002435
25320551352 34354101043000
00000000000005141130054040555455303144250433435101241345 2351125142125134505503545015
053522052044340452151505102411552500425130 051124454001044131150032420303213000000000
0000000000000000000000000000 00000142120343111214520135254453421134122402205253010542
04423552411055 41501552043504145554003101453030335320025343404013012401
04453254343502
14202043241502555510100404330004554411450103133145115101445
14123443342 34124005513133
35045423530553151153501533452435450250055521453054234342 1530350125024205404135451231
323245353031534552304115020154242121145201 542222534340340450530123325534440443103332
4453321414150142334545424124 32031253400501341502455144043000000000000000000000000000
00000000000000 00000000000000000000000000000000000000000000000000000000
00000000000000
00000000003133505424444311110555341410520145402134123130
01424333133115
…
Ta b l e 2
Counts
Z
m
of
consecutive zeroes immediately
following position 3
m
in the
base-6 expansion of
a
2
,
3
m
3
m
Z
m
131
293
3276
48116
5 243 42
6 729 121
7 2187 356
8 6561 1058
9 19683 3166
10 59049 9487
Theorem 2
Given coprime integers
b
=
2
and
c
=
2,
and integers
p,q,r
=
1,
with neither
b
nor
c
dividing
r
,
let
B
=
b
p
c
q
r
.
Assume that the condition
D
=
c
q/p
r
1
/p
/b
c
-
1
<
1
is satisfied
.
Then the constant
a
b,c
=
k
=
0
1
/(c
k
b
c
k
)
is
B
-nonnormal
.
Proof
Let
n
=
c
m
/p
, and let
w
=
np /c
m
, so that
n
=
wc
m
/p
. Note that for even
moderately large
m
, relative to
p
, the fraction
w
is very close to one. Let
Q
m
be the
shifted fraction of
a
b,c
immediately following position
n
in its base-
B
expansion.
One can write
Q
m
=
B
n
a
b,c
mod 1
=
m
k
=
0
b
pn
-
c
k
c
qn
-
k
r
n
mod 1
+
8
k
=
m
+
1
b
pn
-
c
k
c
qn
-
k
r
n
(12)
=
8
k
=
m
+
1
b
pn
-
c
k
c
qn
-
k
r
n
=
8
k
=
m
+
1
c
qwc
m
/p
-
k
r
wc
m
/p
b
c
k
-
wc
m
.
(13)
412 D.H. Bailey, J.M. Borwein
no subinterval of the unit interval is visited, say, 1,000 times more often in the limit
relative to its length, this suffices to prove that the constant in question is
b
-normal.
This idea leads to:
Theorem 1
For every coprime pair of integers
(b, c)
with
b
=
2
and
c
=
2,
the con-
stant
a
b,c
=
m
=
1
1
/(c
m
b
c
m
)
is
b
-normal
.
Proof outline [
5
]
We write the fraction immediately following position
n
in the base-
b
expansion of
a
b,c
as:
b
n
a
b,c
mod 1
=
8
m
=
1
b
n
-
c
m
mod
c
m
c
m
mod 1 (4)
=
log
c
n
m
=
1
b
n
-
c
m
mod
c
m
c
m
mod 1
+
8
m
=
log
c
n
+
1
b
n
-
c
m
c
m
.
(5)
Now, the first expression can be generated by the recursion
z
0
=
0 and, for
n
=
1,
z
n
=
(bz
n
-
1
+
r
n
)
mod 1
,
(6)
where
r
n
=
1
/n
if
n
=
c
k
for some integer
k
, and zero otherwise. Consider the case
b
=
3 and
c
=
4. The first few members of the sequence (
6
)are:
0
,
0
,
0
,
(once)
1
4
,
3
4
,
(repeated 6 times)
5
16
,
15
16
,
13
16
,
7
16
,
(12 times)
,
21
64
,
63
64
,
61
64
,
55
64
,
37
64
,
47
64
,
13
64
,
39
64
,
53
64
,
31
64
,
29
64
,
23
64
,
5
64
,
15
64
,
45
64
,
7
64
,
(12 times), etc. (7)
Note that 1
/
2 is omitted in the first set, 1
/
8, 3
/
8, 5
/
8, 7
/
8 in the second, and
the fractions with 32 in the denominator in the third set. This pattern holds so long
as
b
=
2 and
c
=
2 are coprime [
6
]: if
n<c
p
+
1
then
z
n
is a multiple of 1
/c
p
, and
the set
(z
k
,
1
=
k
=
n)
contains at most
t
repetitions of any particular value. (Here
t
depends only on
b
and
c
.For
(b, c)
=
(
2
,
3
)
, the factor
t
=
3. For the case
(
3
,
4
)
,
t
=
12.) These fractions
(z
k
)
yield accurate approximations to the shifted fractions
b
n
a
b,c
mod 1 of
a
b,c
. On examining (
5
) it transpires that for
(b, c)
as above and
n
=
c
,
b
n
a
b,c
mod 1
-
z
n
<
1
9
n
(8)
(and in most cases is much smaller than this).
To establish that
a
b,c
is
b
-normal via Lemma
1
, we find an upper bound for
b
m
A(a
b,c
,y,n,m)/n
, good for all
y
?[
0
,
1
)
and all
m
=
1 and appeal to Lemma
1
to show
a
b,c
is
b
-normal.
Nonnormality of Stoneham constants 413
3 A general nonnormality result
By Theorem
1
, the Stoneham constant
a
2
,
3
=
k
=
0
1
/(
3
k
2
3
k
)
is 2-normal. Almost
as interesting is the fact that
a
2
,
3
is
not
6-normal. This was first demonstrated in [
5
].
Next, we briefly sketch why this is so. After this we prove a rigorous theorem for
general Stoneham constants.
First note that the digits immediately following position
n
in the base-6 expansion
of
a
2
,
3
can be obtained by computing 6
n
a
2
,
3
mod 1, which can be written as
6
n
a
2
,
3
mod 1
=
log
3
n
m
=
1
3
n
-
m
2
n
-
3
m
mod 1
+
8
m
=
log
3
n
+
1
3
n
-
m
2
n
-
3
m
.
(9)
Note that the first portion of this expression is
zero
, since all terms of the summation
are integers. That leaves the second expression.
Consider the case when
n
=
3
m
, where
m
=
1 is an integer, and examine just the
first term of the second summation. We see that this expression is
3
3
m
-
(m
+
1
)
2
3
m
-
3
m
+
1
=
3
3
m
-
m
-
1
2
-
2
·
3
m
=
(
3
/
4
)
3
m
/
3
m
+
1
.
(10)
We can generously bound the sum of all terms of the second summation by 1.00001
times this amount, for all
m
=
1, and by many times closer to unity for all
m
=
2, etc.
Thus, we have
6
3
m
a
2
,
3
mod 1
˜
(
3
4
)
3
m
3
m
+
1
.
(11)
This approximation is as accurate as one wishes (in ratio) for sufficiently large
m
.
Given the very small size of the expression
(
3
/
4
)
3
m
/
3
m
+
1
for even moderate-sized
m
, it is clear the base-6 expansion will have very long stretches of zeroes beginning
at positions 3
m
+
1. For example, by explicitly computing
a
2
,
3
to high precision, one
can produce the counts of consecutive zeroes
Z
m
that immediately follow position
3
m
in the base-6 expansion of
a
2
,
3
—see Tables
1
and
2
.
In total, there 14256 zeroes in the first ten segments of zeroes, which, including
the last segment, span the first 59049
+
9487
=
68536 base-6 digits of
a
2
,
3
.Inthis
tabulation we have, of course, ignored the many zeroes in the large “random” seg-
ments of the expansion. Thus, the fraction of the first 68536 digits that is zero is at
least 14256
/
68536
=
0
.
20800747
…
. This is significantly more than the expected
value 1
/
6
=
0
.
166666
…
. A careful estimate of the limiting fraction yields the de-
sired nonnormality result.
It is worth pointing out that in the parlance of Lemma
1
, zero is a “hot spot” for
the base-6 expansion of
a
2
,
3
. This is because all sufficiently small neighborhoods
of zero are visited too often, by an arbitrarily large factor, in a subsequence of the
shifted fractions of its base-6 expansion. The nonnormality of
a
2
,
3
and some related
constants is explored graphically in [
4
], where the patterns shown above in Table
1
can be seen even more clearly.
We turn to the promised generalization for general Stoneham constants
a
b,c
:
414 D.H. Bailey, J.M. Borwein
Ta b l e 1
Base-6 expansion of
a
2
,
3
0.
01301404300033342511305021300000012435550454322330115002435
25320551352 34354101043000
00000000000005141130054040555455303144250433435101241345 2351125142125134505503545015
053522052044340452151505102411552500425130 051124454001044131150032420303213000000000
0000000000000000000000000000 00000142120343111214520135254453421134122402205253010542
04423552411055 41501552043504145554003101453030335320025343404013012401
04453254343502
14202043241502555510100404330004554411450103133145115101445
14123443342 34124005513133
35045423530553151153501533452435450250055521453054234342 1530350125024205404135451231
323245353031534552304115020154242121145201 542222534340340450530123325534440443103332
4453321414150142334545424124 32031253400501341502455144043000000000000000000000000000
00000000000000 00000000000000000000000000000000000000000000000000000000
00000000000000
00000000003133505424444311110555341410520145402134123130
01424333133115
…
Ta b l e 2
Counts
Z
m
of
consecutive zeroes immediately
following position 3
m
in the
base-6 expansion of
a
2
,
3
m
3
m
Z
m
131
293
3276
48116
5 243 42
6 729 121
7 2187 356
8 6561 1058
9 19683 3166
10 59049 9487
Theorem 2
Given coprime integers
b
=
2
and
c
=
2,
and integers
p,q,r
=
1,
with neither
b
nor
c
dividing
r
,
let
B
=
b
p
c
q
r
.
Assume that the condition
D
=
c
q/p
r
1
/p
/b
c
-
1
<
1
is satisfied
.
Then the constant
a
b,c
=
k
=
0
1
/(c
k
b
c
k
)
is
B
-nonnormal
.
Proof
Let
n
=
c
m
/p
, and let
w
=
np /c
m
, so that
n
=
wc
m
/p
. Note that for even
moderately large
m
, relative to
p
, the fraction
w
is very close to one. Let
Q
m
be the
shifted fraction of
a
b,c
immediately following position
n
in its base-
B
expansion.
One can write
Q
m
=
B
n
a
b,c
mod 1
=
m
k
=
0
b
pn
-
c
k
c
qn
-
k
r
n
mod 1
+
8
k
=
m
+
1
b
pn
-
c
k
c
qn
-
k
r
n
(12)
=
8
k
=
m
+
1
b
pn
-
c
k
c
qn
-
k
r
n
=
8
k
=
m
+
1
c
qwc
m
/p
-
k
r
wc
m
/p
b
c
k
-
wc
m
.
(13)
no subinterval of the unit interval is visited, say, 1,000 times more often in the limit
relative to its length, this suffices to prove that the constant in question is
b
-normal.
This idea leads to:
Theorem 1
For every coprime pair of integers
(b, c)
with
b
=
2
and
c
=
2,
the con-
stant
a
b,c
=
m
=
1
1
/(c
m
b
c
m
)
is
b
-normal
.
Proof outline [
5
]
We write the fraction immediately following position
n
in the base-
b
expansion of
a
b,c
as:
b
n
a
b,c
mod 1
=
8
m
=
1
b
n
-
c
m
mod
c
m
c
m
mod 1 (4)
=
log
c
n
m
=
1
b
n
-
c
m
mod
c
m
c
m
mod 1
+
8
m
=
log
c
n
+
1
b
n
-
c
m
c
m
.
(5)
Now, the first expression can be generated by the recursion
z
0
=
0 and, for
n
=
1,
z
n
=
(bz
n
-
1
+
r
n
)
mod 1
,
(6)
where
r
n
=
1
/n
if
n
=
c
k
for some integer
k
, and zero otherwise. Consider the case
b
=
3 and
c
=
4. The first few members of the sequence (
6
)are:
0
,
0
,
0
,
(once)
1
4
,
3
4
,
(repeated 6 times)
5
16
,
15
16
,
13
16
,
7
16
,
(12 times)
,
21
64
,
63
64
,
61
64
,
55
64
,
37
64
,
47
64
,
13
64
,
39
64
,
53
64
,
31
64
,
29
64
,
23
64
,
5
64
,
15
64
,
45
64
,
7
64
,
(12 times), etc. (7)
Note that 1
/
2 is omitted in the first set, 1
/
8, 3
/
8, 5
/
8, 7
/
8 in the second, and
the fractions with 32 in the denominator in the third set. This pattern holds so long
as
b
=
2 and
c
=
2 are coprime [
6
]: if
n<c
p
+
1
then
z
n
is a multiple of 1
/c
p
, and
the set
(z
k
,
1
=
k
=
n)
contains at most
t
repetitions of any particular value. (Here
t
depends only on
b
and
c
.For
(b, c)
=
(
2
,
3
)
, the factor
t
=
3. For the case
(
3
,
4
)
,
t
=
12.) These fractions
(z
k
)
yield accurate approximations to the shifted fractions
b
n
a
b,c
mod 1 of
a
b,c
. On examining (
5
) it transpires that for
(b, c)
as above and
n
=
c
,
b
n
a
b,c
mod 1
-
z
n
<
1
9
n
(8)
(and in most cases is much smaller than this).
To establish that
a
b,c
is
b
-normal via Lemma
1
, we find an upper bound for
b
m
A(a
b,c
,y,n,m)/n
, good for all
y
?[
0
,
1
)
and all
m
=
1 and appeal to Lemma
1
to show
a
b,c
is
b
-normal.
Nonnormality of Stoneham constants 413
3 A general nonnormality result
By Theorem
1
, the Stoneham constant
a
2
,
3
=
k
=
0
1
/(
3
k
2
3
k
)
is 2-normal. Almost
as interesting is the fact that
a
2
,
3
is
not
6-normal. This was first demonstrated in [
5
].
Next, we briefly sketch why this is so. After this we prove a rigorous theorem for
general Stoneham constants.
First note that the digits immediately following position
n
in the base-6 expansion
of
a
2
,
3
can be obtained by computing 6
n
a
2
,
3
mod 1, which can be written as
6
n
a
2
,
3
mod 1
=
log
3
n
m
=
1
3
n
-
m
2
n
-
3
m
mod 1
+
8
m
=
log
3
n
+
1
3
n
-
m
2
n
-
3
m
.
(9)
Note that the first portion of this expression is
zero
, since all terms of the summation
are integers. That leaves the second expression.
Consider the case when
n
=
3
m
, where
m
=
1 is an integer, and examine just the
first term of the second summation. We see that this expression is
3
3
m
-
(m
+
1
)
2
3
m
-
3
m
+
1
=
3
3
m
-
m
-
1
2
-
2
·
3
m
=
(
3
/
4
)
3
m
/
3
m
+
1
.
(10)
We can generously bound the sum of all terms of the second summation by 1.00001
times this amount, for all
m
=
1, and by many times closer to unity for all
m
=
2, etc.
Thus, we have
6
3
m
a
2
,
3
mod 1
˜
(
3
4
)
3
m
3
m
+
1
.
(11)
This approximation is as accurate as one wishes (in ratio) for sufficiently large
m
.
Given the very small size of the expression
(
3
/
4
)
3
m
/
3
m
+
1
for even moderate-sized
m
, it is clear the base-6 expansion will have very long stretches of zeroes beginning
at positions 3
m
+
1. For example, by explicitly computing
a
2
,
3
to high precision, one
can produce the counts of consecutive zeroes
Z
m
that immediately follow position
3
m
in the base-6 expansion of
a
2
,
3
—see Tables
1
and
2
.
In total, there 14256 zeroes in the first ten segments of zeroes, which, including
the last segment, span the first 59049
+
9487
=
68536 base-6 digits of
a
2
,
3
.Inthis
tabulation we have, of course, ignored the many zeroes in the large “random” seg-
ments of the expansion. Thus, the fraction of the first 68536 digits that is zero is at
least 14256
/
68536
=
0
.
20800747
…
. This is significantly more than the expected
value 1
/
6
=
0
.
166666
…
. A careful estimate of the limiting fraction yields the de-
sired nonnormality result.
It is worth pointing out that in the parlance of Lemma
1
, zero is a “hot spot” for
the base-6 expansion of
a
2
,
3
. This is because all sufficiently small neighborhoods
of zero are visited too often, by an arbitrarily large factor, in a subsequence of the
shifted fractions of its base-6 expansion. The nonnormality of
a
2
,
3
and some related
constants is explored graphically in [
4
], where the patterns shown above in Table
1
can be seen even more clearly.
We turn to the promised generalization for general Stoneham constants
a
b,c
:
414 D.H. Bailey, J.M. Borwein
Ta b l e 1
Base-6 expansion of
a
2
,
3
0.
01301404300033342511305021300000012435550454322330115002435
25320551352 34354101043000
00000000000005141130054040555455303144250433435101241345 2351125142125134505503545015
053522052044340452151505102411552500425130 051124454001044131150032420303213000000000
0000000000000000000000000000 00000142120343111214520135254453421134122402205253010542
04423552411055 41501552043504145554003101453030335320025343404013012401
04453254343502
14202043241502555510100404330004554411450103133145115101445
14123443342 34124005513133
35045423530553151153501533452435450250055521453054234342 1530350125024205404135451231
323245353031534552304115020154242121145201 542222534340340450530123325534440443103332
4453321414150142334545424124 32031253400501341502455144043000000000000000000000000000
00000000000000 00000000000000000000000000000000000000000000000000000000
00000000000000
00000000003133505424444311110555341410520145402134123130
01424333133115
…
Ta b l e 2
Counts
Z
m
of
consecutive zeroes immediately
following position 3
m
in the
base-6 expansion of
a
2
,
3
m
3
m
Z
m
131
293
3276
48116
5 243 42
6 729 121
7 2187 356
8 6561 1058
9 19683 3166
10 59049 9487
Theorem 2
Given coprime integers
b
=
2
and
c
=
2,
and integers
p,q,r
=
1,
with neither
b
nor
c
dividing
r
,
let
B
=
b
p
c
q
r
.
Assume that the condition
D
=
c
q/p
r
1
/p
/b
c
-
1
<
1
is satisfied
.
Then the constant
a
b,c
=
k
=
0
1
/(c
k
b
c
k
)
is
B
-nonnormal
.
Proof
Let
n
=
c
m
/p
, and let
w
=
np /c
m
, so that
n
=
wc
m
/p
. Note that for even
moderately large
m
, relative to
p
, the fraction
w
is very close to one. Let
Q
m
be the
shifted fraction of
a
b,c
immediately following position
n
in its base-
B
expansion.
One can write
Q
m
=
B
n
a
b,c
mod 1
=
m
k
=
0
b
pn
-
c
k
c
qn
-
k
r
n
mod 1
+
8
k
=
m
+
1
b
pn
-
c
k
c
qn
-
k
r
n
(12)
=
8
k
=
m
+
1
b
pn
-
c
k
c
qn
-
k
r
n
=
8
k
=
m
+
1
c
qwc
m
/p
-
k
r
wc
m
/p
b
c
k
-
wc
m
.
(13)
This page intentionally left blank
CAMBRIDGE TRACTS IN MATHEMATICS
General Editors
B. BOLLOB
´
AS. W. FULTON, A. KATOK, F. KIRWAN, P. SARNAK, B. SIMON
160 Approximation by Algebraic Numbers
Approximation by Algebraic Numbers
YANN BUGEAUD
Universit
´
e Louis Pasteur, Strasbourg
CAMBRIDGE UNIVERSITY
PRESS
Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo
Cambridge University Press
The Edinburgh Building, Cambridge CB2 2RU, UK
First published in print format
ISBN-13 978-0-521-82329-6
ISBN-13 978-0-511-26591-4
© Cambridge University Press 2004
2004
Informatio
n
o
n
thi
s
title
:
www.cambri
d
g
e.or
g
/9780521823296
This publication is in copyright. Subject to statutory exception and to the provision of
relevant collective licensing agreements, no reproduction of any part may take place
without the written permission of Cambridge University Press.
ISBN-10 0-511-26591-3
ISBN-10 0-521-82329-3
Cambridge University Press has no responsibility for the persistence or accuracy of urls
for external or third-party internet websites referred to in this publication, and does not
guarantee that any content on such websites is, or will remain, accurate or appropriate.
Published in the United States of America by Cambridge University Press, New York
www.cambridge.org
hardback
eBook (NetLibrary)
eBook (NetLibrary)
hardback
Contents
Preface page
ix
Frequently used notation
xiv
1 Approximation by rational numbers
1
1.1 Dirichlet and Liouville
1
1.2 Continued fractions
5
1.3 The theorem of Khintchine
12
1.4 The Duffin–Schaeffer Conjecture
18
1.5 Complementary results on continued fractions
19
1.6 Exercises
21
1.7 Notes
23
2 Approximation to algebraic numbers
27
2.1 Rational approximation
27
2.2 Effective rational approximation
29
2.3 Approximation by algebraic numbers
31
2.4 Effective approximation by algebraic numbers
33
2.5 Remarks on irrationality and transcendence statements
39
2.6 Notes
40
3 The classifications of Mahler and Koksma
41
3.1 Mahler’s classification
42
3.2 Some properties of Mahler’s classification
45
3.3 Koksma’s classification
47
3.4 Comparison between both classifications
52
3.5 Some examples
61
3.6 Exponents of Diophantine approximation
62
v
vi
Contents
3.7 Exercises
68
3.8 Notes
70
4 Mahler’s Conjecture on
S
-numbers
74
4.1 Statements of the theorems
75
4.2 An auxiliary result
78
4.3 Proof of Theorem 4.3
80
4.4 Exercise
87
4.5 Notes
88
5 Hausdorff dimension of exceptional sets
90
5.1 Hausdorff measure and Hausdorff dimension
90
5.2 Upper bound for the Hausdorff dimension
93
5.3 The mass distribution principle
95
5.4 Regular systems
98
5.5 The theorem of Jarn
´
ik–Besicovitch
103
5.6 Hausdorff dimension of sets of
S
*
-numbers
105
5.7 Hausdorff dimension of sets of
S
-numbers
110
5.8 Restricted Diophantine approximation
113
5.9 Exercises
114
5.10 Notes
117
6 Deeper results on the measure of exceptional sets
122
6.1 Optimal regular systems
123
6.2 A Khintchine-type result
125
6.3 Hausdorff dimension of exceptional sets
129
6.4 Hausdorff measure of exceptional sets
130
6.5 Sets with large intersection properties
130
6.6 Application to the approximation by algebraic numbers
131
6.7 Exercises
136
6.8 Notes
137
7On
T
-numbers and
U
-numbers
139
7.1
T
-numbers do exist
140
7.2 The inductive construction
141
7.3 Completion of the proof of Theorem 7.1
149
7.4 On the gap between
w
*
n
and
w
n
151
7.5 Hausdorff dimension and Hausdorff measure
152
7.6 On
U
-numbers
153
7.7 A method of G
¨
uting
159
Contents
vii
7.8 Brief summary of the results towards the Main Problem
161
7.9 Exercises
162
7.10 Notes
163
8 Other classifications of real and complex numbers
166
8.1 Sprind
?
zuk’s classification
166
8.2 Another classification proposed by Mahler
171
8.3 Transcendence measures and measures of algebraic
approximation
180
8.4 Exercises
184
8.5 Notes
188
9 Approximation in other fields
191
9.1 Approximation in the field of complex numbers
191
9.2 Approximation in the field of Gaussian integers
193
9.3 Approximation in the
p
-adic fields
194
9.4 Approximation in fields of formal power series
199
9.5 Notes
201
10 Conjectures and open questions
204
10.1 The Littlewood Conjecture
204
10.2 Open questions
206
10.3 Notes
217
Appendix A Lemmas on polynomials
219
A.1 Definitions and useful lemmas
219
A.2 Liouville’s inequality
222
A.3 Zeros of polynomials
227
A.4 Exercises
233
A.5 Notes
233
Appendix B Geometry of numbers
235
References
240
Index
273
Preface
Und alles ist mir dann immer wieder zerfallen, auf dem Konzentrationsh
¨
ohepunkt
ist mir dann immer wieder alles zerfallen.
Thomas Bernhard
(…) il faut continuer, je vais continuer.
Samuel Beckett
The central question in Diophantine approximation is: how well can a given
real number
?
be approximated by rational numbers, that is, how small can the
difference
|
?
-
p
/
q
|
be made for varying rational numbers
p
/
q
? The accuracy
of the approximation of
?
by
p
/
q
is being compared with the ‘complexity’ of
the rational number
p
/
q
, which is measured by the size of its denominator
q
.It
follows from the theory of continued fractions (or from Dirichlet’s Theorem)
that for any irrational number
?
there exist infinitely many rational numbers
p
/
q
with
|
?
-
p
/
q
|
<
q
-
2
. This can be viewed as the first general result in
this area.
There are two natural generalizations of the central question. On the one
hand, one can treat rational numbers as algebraic numbers of degree one and
study, for a given positive integer
n
, how well
?
can be approximated by alge-
braic numbers of degree at most
n
. On the other hand,
?
-
p
/
q
can be viewed
as
q
?
-
p
, that is as
P
(?)
, where
P
(
X
)
denotes the integer polynomial
qX
-
p
.
Thus, for a given positive integer
n
, one may ask how small
|
P
(?)
|
can be made
for varying integer polynomials
P
(
X
)
of degree at most
n
. To do this properly,
one needs to define a notion of size, or ‘complexity’, for algebraic numbers
a
and for integer polynomials
P
(
X
)
, and we have to compare the accuracy of
ix
x
Preface
the approximation of
?
by
a
(
resp.
the smallness of
|
P
(?)
|
) with the size of
a
(
resp.
of
P
(
X
)
). In both cases, we use for the size the naive height H: the
height H
(
P
)
of
P
(
X
)
is the maximum of the absolute values of its coefficients
and the height H
(a)
of
a
is that of its minimal polynomial over
Z
.
In 1932, Mahler proposed to classify the real numbers (actually, the com-
plex numbers) into several classes according to the various types of answers to
the latter question, while in 1939 Koksma introduced an analogous classifica-
tion based on the former question. In both cases, the algebraic numbers form
one of the classes. Let
?
be a real number and let
n
be a positive integer. Ac-
cording to Mahler, we denote by
w
n
(?)
the supremum of the real numbers
w
for which there exist infinitely many integer polynomials
P
(
X
)
of degree at
most
n
satisfying
0
<
|
P
(?)
|=
H
(
P
)
-
w
,
and we divide the set of real numbers into four classes according to the be-
haviour of the sequence
(w
n
(?))
n
=
1
. Following Koksma, we denote by
w
*
n
(?)
the supremum of the real numbers
w
for which there exist infinitely many real
algebraic numbers
a
of degree at most
n
satisfying
0
<
|
?
-
a
|=
H
(a)
-
w
-
1
.
It turns out that both classifications coincide, inasmuch as each of the four
classes defined by Mahler corresponds to one of the four classes defined by
Koksma. However, they are not strictly equivalent, since there exist real num-
bers
?
for which
w
n
(?)
and
w
*
n
(?)
differ for any integer
n
at least equal
to 2. In addition, it is a very difficult (and, often, still open) question to
determine to which class a given ‘classical’ number like
p
,
e
,
?(
3
)
, log 2, etc.
belongs.
The present book is mainly concerned with the following problem: given
two non-decreasing sequences of real numbers
(w
n
)
n
=
1
and
(w
*
n
)
n
=
1
satisfy-
ing some necessary restrictions (e.g.
w
*
n
=
w
n
=
w
*
n
+
n
-
1), does there
exist a real number
?
with
w
n
(?)
=
w
n
and
w
*
n
(?)
=
w
*
n
for all positive in-
tegers
n
? This question is very far from being solved, although we know (see
Chapter 4) that almost all (in the sense of the Lebesgue measure on the line)
real numbers share the same approximation properties, namely they satisfy
w
n
(?)
=
w
*
n
(?)
=
n
for all positive integers
n
.
There are essentially two different points of view for investigating such a
problem. We may try to construct explicitly (or semi-explicitly) real numbers
with the required properties (Chapter 7) or, if this happens to be too diffi-
cult, we may try to prove the existence of real numbers with a given property
by showing that the set of these numbers has positive Hausdorff dimension
Preface
xi
(Chapters 5 and 6). Most often, however, we are unable to exhibit a single ex-
plicit example of such a number.
The content of the present book is as follows. Chapter 1 is devoted to the
approximation by rational numbers. We introduce the notion of continued frac-
tions and establish their main properties needed to prove the celebrated metric
theorem of Khintchine saying that, for a continuous function
:
R
=
1
?
R
>
0
such that
x
?
x
(
x
)
is non-increasing, the equation
|
q
?
-
p
|
< (
q
)
has
infinitely many integer solutions
(
p
,
q
)
with
q
positive for either almost no
or almost all real numbers
?
, according to whether the sum
+8
q
=
1
(
q
)
con-
verges or diverges.
In Chapter 2, we briefly survey the approximation to algebraic numbers by
algebraic numbers, and recall many classical results (including Roth’s Theo-
rem and Schmidt’s Theorem). We make a clear distinction between effective
and ineffective statements.
Mahler’s and Koksma’s classifications of real numbers are defined in
Chapter 3, where we show, following ideas of Wirsing, how closely they are re-
lated. Some links between simultaneous rational approximation and these clas-
sifications are also mentioned, and we introduce four other functions closely
related to
w
n
and
w
*
n
.
In Chapter 4, we establish Mahler’s Conjecture to the effect that almost all
real numbers
?
satisfy
w
n
(?)
=
w
*
n
(?)
=
n
for all positive integers
n
. This
result, first proved by Sprind
?
zuk in 1965, has been refined and extended since
that time and we state the most recent developments, essentially due to a new
approach found by Kleinbock and Margulis.
Exceptional sets are investigated from a metric point of view in Chapters
5 and 6. To this end, we introduce a classical powerful tool for discriminating
between sets of Lebesgue measure zero, namely the notion of Hausdorff di-
mension. We recall the basic definitions and some well-known results useful
in our context. This allows us to prove the theorem of Jarn
´
ik and Besicov-
itch saying that for any real number
t
=
1 the Hausdorff dimension of the
set of real numbers
?
with
w
*
1
(?)
=
2
t
-
1 is equal to 1
/t
. We also estab-
lish its generalization to any degree
n
(with
w
*
1
(?)
=
2
t
-
1 replaced by
w
*
n
(?)
=
(
n
+
1
)t
-
1) obtained in 1970 by A. Baker and Schmidt. Chapter 6
is devoted to refined statements and contains general metric theorems on sets
of real numbers which are very close to infinitely many elements of a fixed set
of points which are, in some sense, evenly distributed.
In Chapter 7, we prove, following ideas of Schmidt, that the class formed
by the real numbers
?
with lim sup
n
?+8
w
n
(?)/
n
infinite and
w
n
(?)
finite for
all positive integers
n
is not empty. At the same time, we show that there exist
real numbers
?
for which the quantities
w
n
(?)
and
w
*
n
(?)
differ by preassigned
xii
Preface
values, a result due to R. C. Baker. The real numbers
?
with the required prop-
erty are obtained as limits of sequences of algebraic numbers. This illustrates
the importance of results on approximation of algebraic numbers by algebraic
numbers. The remaining part of Chapter 7 is concerned with some other (sim-
pler) explicit constructions.
Mahler’s and Koksma’s classifications emphasize the approximation by al-
gebraic numbers of bounded degree. We may as well exchange the roles played
by degree and height or let both vary simultaneously. We tackle this ques-
tion in Chapter 8 by considering the classification introduced by Sprind
?
zuk in
1962 and the so-called ‘order functions’ defined by Mahler in 1971. Further,
some recent results of Laurent, Roy, and Waldschmidt expressed in terms of a
more involved notion of height (namely, the absolute logarithmic height) are
given.
In Chapter 9, we briefly discuss approximation in the complex field, in the
Gaussian field, in
p
-adic fields, and in fields of formal Laurent series.
Chapter 10, which begins by a brief survey on the celebrated Littlewood
Conjecture, offers a list of open questions. We hope that these will motivate
further research.
Finally, there are two appendices. Appendix A is devoted to lemmas on
zeros of polynomials: all proofs are given in detail and the statements are the
best known at the present time. Appendix B lists classical auxiliary results
from the geometry of numbers.
The Chapters are largely independent of each other.
We deliberately do not give proofs to all the theorems quoted in the main
part of the text. We have clearly indicated when this is the case (see below).
Furthermore, we try, in the end-of-chapter notes, to be as exhaustive as possible
and to quote less-known papers, which, although interesting, did not yield up
to now to further research. Of course, exhaustivity is an impossible task, and
it is clear that the choice of the references concerning works at the border of
the main topic of this book reflects the personal taste and the limits of the
knowledge of the author.
The purpose of the exercises is primarily to give complementary results,
thus they are often an adaptation of an original research work to which the
reader is directed.
There exist already many textbooks dealing, in part, with the subject of the
present one, e.g., by Schneider [517], Sprind
?
zuk [539, 540], A. Baker [44],
Schmidt [510, 512], Bernik and Melnichuk [90], Harman [273], and Bernik
and Dodson [86]. However, the intersection rarely exceeds two or three chap-
ters. Special mention should be made to the wonderful book of Koksma [332],
which contains an impressive list of references which appeared before 1936.
Preface
xiii
Maurice Mignotte and Michel Waldschmidt encouraged me constantly.
Many colleagues sent me comments, remarks, and suggestions. I am very
grateful to all of them. Special thanks are due to Guy Barat and Damien Roy,
who carefully read several parts of this book.
The present book will be regularly updated on my institutional Web page:
CAMBRIDGE TRACTS IN MATHEMATICS
General Editors
B. BOLLOB
´
AS. W. FULTON, A. KATOK, F. KIRWAN, P. SARNAK, B. SIMON
160 Approximation by Algebraic Numbers
Approximation by Algebraic Numbers
YANN BUGEAUD
Universit
´
e Louis Pasteur, Strasbourg
CAMBRIDGE UNIVERSITY
PRESS
Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo
Cambridge University Press
The Edinburgh Building, Cambridge CB2 2RU, UK
First published in print format
ISBN-13 978-0-521-82329-6
ISBN-13 978-0-511-26591-4
© Cambridge University Press 2004
2004
Informatio
n
o
n
thi
s
title
:
www.cambri
d
g
e.or
g
/9780521823296
This publication is in copyright. Subject to statutory exception and to the provision of
relevant collective licensing agreements, no reproduction of any part may take place
without the written permission of Cambridge University Press.
ISBN-10 0-511-26591-3
ISBN-10 0-521-82329-3
Cambridge University Press has no responsibility for the persistence or accuracy of urls
for external or third-party internet websites referred to in this publication, and does not
guarantee that any content on such websites is, or will remain, accurate or appropriate.
Published in the United States of America by Cambridge University Press, New York
www.cambridge.org
hardback
eBook (NetLibrary)
eBook (NetLibrary)
hardback
Contents
Preface page
ix
Frequently used notation
xiv
1 Approximation by rational numbers
1
1.1 Dirichlet and Liouville
1
1.2 Continued fractions
5
1.3 The theorem of Khintchine
12
1.4 The Duffin–Schaeffer Conjecture
18
1.5 Complementary results on continued fractions
19
1.6 Exercises
21
1.7 Notes
23
2 Approximation to algebraic numbers
27
2.1 Rational approximation
27
2.2 Effective rational approximation
29
2.3 Approximation by algebraic numbers
31
2.4 Effective approximation by algebraic numbers
33
2.5 Remarks on irrationality and transcendence statements
39
2.6 Notes
40
3 The classifications of Mahler and Koksma
41
3.1 Mahler’s classification
42
3.2 Some properties of Mahler’s classification
45
3.3 Koksma’s classification
47
3.4 Comparison between both classifications
52
3.5 Some examples
61
3.6 Exponents of Diophantine approximation
62
v
vi
Contents
3.7 Exercises
68
3.8 Notes
70
4 Mahler’s Conjecture on
S
-numbers
74
4.1 Statements of the theorems
75
4.2 An auxiliary result
78
4.3 Proof of Theorem 4.3
80
4.4 Exercise
87
4.5 Notes
88
5 Hausdorff dimension of exceptional sets
90
5.1 Hausdorff measure and Hausdorff dimension
90
5.2 Upper bound for the Hausdorff dimension
93
5.3 The mass distribution principle
95
5.4 Regular systems
98
5.5 The theorem of Jarn
´
ik–Besicovitch
103
5.6 Hausdorff dimension of sets of
S
*
-numbers
105
5.7 Hausdorff dimension of sets of
S
-numbers
110
5.8 Restricted Diophantine approximation
113
5.9 Exercises
114
5.10 Notes
117
6 Deeper results on the measure of exceptional sets
122
6.1 Optimal regular systems
123
6.2 A Khintchine-type result
125
6.3 Hausdorff dimension of exceptional sets
129
6.4 Hausdorff measure of exceptional sets
130
6.5 Sets with large intersection properties
130
6.6 Application to the approximation by algebraic numbers
131
6.7 Exercises
136
6.8 Notes
137
7On
T
-numbers and
U
-numbers
139
7.1
T
-numbers do exist
140
7.2 The inductive construction
141
7.3 Completion of the proof of Theorem 7.1
149
7.4 On the gap between
w
*
n
and
w
n
151
7.5 Hausdorff dimension and Hausdorff measure
152
7.6 On
U
-numbers
153
7.7 A method of G
¨
uting
159
Contents
vii
7.8 Brief summary of the results towards the Main Problem
161
7.9 Exercises
162
7.10 Notes
163
8 Other classifications of real and complex numbers
166
8.1 Sprind
?
zuk’s classification
166
8.2 Another classification proposed by Mahler
171
8.3 Transcendence measures and measures of algebraic
approximation
180
8.4 Exercises
184
8.5 Notes
188
9 Approximation in other fields
191
9.1 Approximation in the field of complex numbers
191
9.2 Approximation in the field of Gaussian integers
193
9.3 Approximation in the
p
-adic fields
194
9.4 Approximation in fields of formal power series
199
9.5 Notes
201
10 Conjectures and open questions
204
10.1 The Littlewood Conjecture
204
10.2 Open questions
206
10.3 Notes
217
Appendix A Lemmas on polynomials
219
A.1 Definitions and useful lemmas
219
A.2 Liouville’s inequality
222
A.3 Zeros of polynomials
227
A.4 Exercises
233
A.5 Notes
233
Appendix B Geometry of numbers
235
References
240
Index
273
Preface
Und alles ist mir dann immer wieder zerfallen, auf dem Konzentrationsh
¨
ohepunkt
ist mir dann immer wieder alles zerfallen.
Thomas Bernhard
(…) il faut continuer, je vais continuer.
Samuel Beckett
The central question in Diophantine approximation is: how well can a given
real number
?
be approximated by rational numbers, that is, how small can the
difference
|
?
-
p
/
q
|
be made for varying rational numbers
p
/
q
? The accuracy
of the approximation of
?
by
p
/
q
is being compared with the ‘complexity’ of
the rational number
p
/
q
, which is measured by the size of its denominator
q
.It
follows from the theory of continued fractions (or from Dirichlet’s Theorem)
that for any irrational number
?
there exist infinitely many rational numbers
p
/
q
with
|
?
-
p
/
q
|
<
q
-
2
. This can be viewed as the first general result in
this area.
There are two natural generalizations of the central question. On the one
hand, one can treat rational numbers as algebraic numbers of degree one and
study, for a given positive integer
n
, how well
?
can be approximated by alge-
braic numbers of degree at most
n
. On the other hand,
?
-
p
/
q
can be viewed
as
q
?
-
p
, that is as
P
(?)
, where
P
(
X
)
denotes the integer polynomial
qX
-
p
.
Thus, for a given positive integer
n
, one may ask how small
|
P
(?)
|
can be made
for varying integer polynomials
P
(
X
)
of degree at most
n
. To do this properly,
one needs to define a notion of size, or ‘complexity’, for algebraic numbers
a
and for integer polynomials
P
(
X
)
, and we have to compare the accuracy of
ix
x
Preface
the approximation of
?
by
a
(
resp.
the smallness of
|
P
(?)
|
) with the size of
a
(
resp.
of
P
(
X
)
). In both cases, we use for the size the naive height H: the
height H
(
P
)
of
P
(
X
)
is the maximum of the absolute values of its coefficients
and the height H
(a)
of
a
is that of its minimal polynomial over
Z
.
In 1932, Mahler proposed to classify the real numbers (actually, the com-
plex numbers) into several classes according to the various types of answers to
the latter question, while in 1939 Koksma introduced an analogous classifica-
tion based on the former question. In both cases, the algebraic numbers form
one of the classes. Let
?
be a real number and let
n
be a positive integer. Ac-
cording to Mahler, we denote by
w
n
(?)
the supremum of the real numbers
w
for which there exist infinitely many integer polynomials
P
(
X
)
of degree at
most
n
satisfying
0
<
|
P
(?)
|=
H
(
P
)
-
w
,
and we divide the set of real numbers into four classes according to the be-
haviour of the sequence
(w
n
(?))
n
=
1
. Following Koksma, we denote by
w
*
n
(?)
the supremum of the real numbers
w
for which there exist infinitely many real
algebraic numbers
a
of degree at most
n
satisfying
0
<
|
?
-
a
|=
H
(a)
-
w
-
1
.
It turns out that both classifications coincide, inasmuch as each of the four
classes defined by Mahler corresponds to one of the four classes defined by
Koksma. However, they are not strictly equivalent, since there exist real num-
bers
?
for which
w
n
(?)
and
w
*
n
(?)
differ for any integer
n
at least equal
to 2. In addition, it is a very difficult (and, often, still open) question to
determine to which class a given ‘classical’ number like
p
,
e
,
?(
3
)
, log 2, etc.
belongs.
The present book is mainly concerned with the following problem: given
two non-decreasing sequences of real numbers
(w
n
)
n
=
1
and
(w
*
n
)
n
=
1
satisfy-
ing some necessary restrictions (e.g.
w
*
n
=
w
n
=
w
*
n
+
n
-
1), does there
exist a real number
?
with
w
n
(?)
=
w
n
and
w
*
n
(?)
=
w
*
n
for all positive in-
tegers
n
? This question is very far from being solved, although we know (see
Chapter 4) that almost all (in the sense of the Lebesgue measure on the line)
real numbers share the same approximation properties, namely they satisfy
w
n
(?)
=
w
*
n
(?)
=
n
for all positive integers
n
.
There are essentially two different points of view for investigating such a
problem. We may try to construct explicitly (or semi-explicitly) real numbers
with the required properties (Chapter 7) or, if this happens to be too diffi-
cult, we may try to prove the existence of real numbers with a given property
by showing that the set of these numbers has positive Hausdorff dimension
Preface
xi
(Chapters 5 and 6). Most often, however, we are unable to exhibit a single ex-
plicit example of such a number.
The content of the present book is as follows. Chapter 1 is devoted to the
approximation by rational numbers. We introduce the notion of continued frac-
tions and establish their main properties needed to prove the celebrated metric
theorem of Khintchine saying that, for a continuous function
:
R
=
1
?
R
>
0
such that
x
?
x
(
x
)
is non-increasing, the equation
|
q
?
-
p
|
< (
q
)
has
infinitely many integer solutions
(
p
,
q
)
with
q
positive for either almost no
or almost all real numbers
?
, according to whether the sum
+8
q
=
1
(
q
)
con-
verges or diverges.
In Chapter 2, we briefly survey the approximation to algebraic numbers by
algebraic numbers, and recall many classical results (including Roth’s Theo-
rem and Schmidt’s Theorem). We make a clear distinction between effective
and ineffective statements.
Mahler’s and Koksma’s classifications of real numbers are defined in
Chapter 3, where we show, following ideas of Wirsing, how closely they are re-
lated. Some links between simultaneous rational approximation and these clas-
sifications are also mentioned, and we introduce four other functions closely
related to
w
n
and
w
*
n
.
In Chapter 4, we establish Mahler’s Conjecture to the effect that almost all
real numbers
?
satisfy
w
n
(?)
=
w
*
n
(?)
=
n
for all positive integers
n
. This
result, first proved by Sprind
?
zuk in 1965, has been refined and extended since
that time and we state the most recent developments, essentially due to a new
approach found by Kleinbock and Margulis.
Exceptional sets are investigated from a metric point of view in Chapters
5 and 6. To this end, we introduce a classical powerful tool for discriminating
between sets of Lebesgue measure zero, namely the notion of Hausdorff di-
mension. We recall the basic definitions and some well-known results useful
in our context. This allows us to prove the theorem of Jarn
´
ik and Besicov-
itch saying that for any real number
t
=
1 the Hausdorff dimension of the
set of real numbers
?
with
w
*
1
(?)
=
2
t
-
1 is equal to 1
/t
. We also estab-
lish its generalization to any degree
n
(with
w
*
1
(?)
=
2
t
-
1 replaced by
w
*
n
(?)
=
(
n
+
1
)t
-
1) obtained in 1970 by A. Baker and Schmidt. Chapter 6
is devoted to refined statements and contains general metric theorems on sets
of real numbers which are very close to infinitely many elements of a fixed set
of points which are, in some sense, evenly distributed.
In Chapter 7, we prove, following ideas of Schmidt, that the class formed
by the real numbers
?
with lim sup
n
?+8
w
n
(?)/
n
infinite and
w
n
(?)
finite for
all positive integers
n
is not empty. At the same time, we show that there exist
real numbers
?
for which the quantities
w
n
(?)
and
w
*
n
(?)
differ by preassigned
xii
Preface
values, a result due to R. C. Baker. The real numbers
?
with the required prop-
erty are obtained as limits of sequences of algebraic numbers. This illustrates
the importance of results on approximation of algebraic numbers by algebraic
numbers. The remaining part of Chapter 7 is concerned with some other (sim-
pler) explicit constructions.
Mahler’s and Koksma’s classifications emphasize the approximation by al-
gebraic numbers of bounded degree. We may as well exchange the roles played
by degree and height or let both vary simultaneously. We tackle this ques-
tion in Chapter 8 by considering the classification introduced by Sprind
?
zuk in
1962 and the so-called ‘order functions’ defined by Mahler in 1971. Further,
some recent results of Laurent, Roy, and Waldschmidt expressed in terms of a
more involved notion of height (namely, the absolute logarithmic height) are
given.
In Chapter 9, we briefly discuss approximation in the complex field, in the
Gaussian field, in
p
-adic fields, and in fields of formal Laurent series.
Chapter 10, which begins by a brief survey on the celebrated Littlewood
Conjecture, offers a list of open questions. We hope that these will motivate
further research.
Finally, there are two appendices. Appendix A is devoted to lemmas on
zeros of polynomials: all proofs are given in detail and the statements are the
best known at the present time. Appendix B lists classical auxiliary results
from the geometry of numbers.
The Chapters are largely independent of each other.
We deliberately do not give proofs to all the theorems quoted in the main
part of the text. We have clearly indicated when this is the case (see below).
Furthermore, we try, in the end-of-chapter notes, to be as exhaustive as possible
and to quote less-known papers, which, although interesting, did not yield up
to now to further research. Of course, exhaustivity is an impossible task, and
it is clear that the choice of the references concerning works at the border of
the main topic of this book reflects the personal taste and the limits of the
knowledge of the author.
The purpose of the exercises is primarily to give complementary results,
thus they are often an adaptation of an original research work to which the
reader is directed.
There exist already many textbooks dealing, in part, with the subject of the
present one, e.g., by Schneider [517], Sprind
?
zuk [539, 540], A. Baker [44],
Schmidt [510, 512], Bernik and Melnichuk [90], Harman [273], and Bernik
and Dodson [86]. However, the intersection rarely exceeds two or three chap-
ters. Special mention should be made to the wonderful book of Koksma [332],
which contains an impressive list of references which appeared before 1936.
Preface
xiii
Maurice Mignotte and Michel Waldschmidt encouraged me constantly.
Many colleagues sent me comments, remarks, and suggestions. I am very
grateful to all of them. Special thanks are due to Guy Barat and Damien Roy,
who carefully read several parts of this book.
The present book will be regularly updated on my institutional Web page:
http://www-irma.u-strasbg.fr/
~
bugeaud/Book
The following statements are not proved in the present book:
Theorems 1.13 to 1.15, 1.17, 1.20, 2.1 to 2.8, 3.7, 3.8, 3.10, 3.11, 4.4 to 4.7,
Proposition 5.1, Theorems 5.7, 5.9, 5.10, Proposition 6.1, Theorems 6.3 to 6.5,
8.1, 8.5, 8.8 (partially proved), 9.1 to 9.8, Lemma 10.1, Theorems 10.1, B.3,
and B.4.
The following statements are left as exercises:
Theorems 1.16, 1.18, 1.19, 5.4, 5.6, 6.2, 6.9, 6.10, 7.2, 7.3, 7.6, 8.4, 8.6,
8.12, and Proposition 8.1.
bugeaud/Book
The following statements are not proved in the present book:
Theorems 1.13 to 1.15, 1.17, 1.20, 2.1 to 2.8, 3.7, 3.8, 3.10, 3.11, 4.4 to 4.7,
Proposition 5.1, Theorems 5.7, 5.9, 5.10, Proposition 6.1, Theorems 6.3 to 6.5,
8.1, 8.5, 8.8 (partially proved), 9.1 to 9.8, Lemma 10.1, Theorems 10.1, B.3,
and B.4.
The following statements are left as exercises:
Theorems 1.16, 1.18, 1.19, 5.4, 5.6, 6.2, 6.9, 6.10, 7.2, 7.3, 7.6, 8.4, 8.6,
8.12, and Proposition 8.1.
Distribution Modulo One and Diophantine
Approximation
Yann Bugeaud
Version du 24-11-2011
Approximation
Yann Bugeaud
Version du 24-11-2011
No comments:
Post a Comment