arXiv:1611.05911v2 [cs.DS] 24 Feb 2017

Computing Absolutely Normal Numbers in
Nearly Linear Time
Jack Lutz∗

Elvira Mayordomo†

February 27, 2017

Abstract
A real number x is absolutely normal if, for every base b ≥ 2, every
two equally long strings of digits appear with equal asymptotic frequency
in the base-b expansion of x. This paper presents an explicit algorithm
that generates the binary expansion of an absolutely normal number x,
with the nth bit of x appearing after npolylog(n) computation steps. This
speed is achieved by simultaneously computing and diagonalizing against
a martingale that incorporates Lempel-Ziv parsing algorithms in all bases.

Keywords: algorithms, computational complexity, Lempel-Ziv parsing, martingales, normal numbers

1

Introduction

In 1909 Borel [4] defined a real number α to be normal in base b (b ≥ 2) if, for
every m ≥ 1 and every length-m sequence w of base-b digits, the asymptotic,
empirical frequency of w in the base-b expansion of α is b−m . Borel defined α to
be absolutely normal if it is normal in every base b ≥ 2. (This clearly anticipated
the fact, proven a half-century later, that a real number may be normal in one
base but not in another [8, 23].) Borel’s proof that almost every real number
(i.e., every real number outside a set of Lebesgue measure 0) is absolutely normal
was an important milestone in the prehistory of Kolmogorov’s development
of the rigorous, measure-theoretic foundations of probability theory [17]. For
example, it is section 1 of Billingsley’s influential textbook [3]. The recent book
[7] provides a good exposition of the many aspects of current research on normal
numbers.
Borel’s proof shows that absolutely normal numbers are commonplace, i.e.,
that a “randomly chosen” real number is absolutely normal with probability 1.
Rational numbers cannot be normal in even a single base b, since their base-b
∗ Department of Computer Science, Iowa State University, Ames, IA 50011 USA.
lutz@cs.iastate.edu.
† Departamento de Informática e Ingenierı́a de Sistemas, Instituto de Investigación en Ingenierı́a de Aragón, Universidad de Zaragoza, 50018 Zaragoza, SPAIN. elvira@unizar.es.

1

expansions
are eventually periodic, but computer analyses of the expansions of
√
π, e, 2, ln 2, and other irrational numbers that arise in common mathematical
practice suggest that these numbers are absolutely normal [5]. Nevertheless,
no such “natural” example of a real number has been proven to be normal in
any base, let alone absolutely normal. The conjectures that every algebraic
irrational is absolutely normal and that π is absolutely normal are especially
well known open problems [5, 7, 29].
This paper concerns an old problem, namely, the complexity of explicitly
computing a real number that is provably absolutely normal, even if it is not
natural in the above informal sense. Sierpinski and Lebesgue gave explicit constructions of absolutely normal numbers in 1917 [25, 18], but these were intricate
limiting processes that offered no complexity analyses (coming two decades before the theory of computing) and little insight into the nature of the numbers
constructed. In a 1936 note that was not published in his lifetime, Turing [27]
gave a constructive proof that almost all real numbers are absolutely normal
and then derived constructions of absolutely normal numbers from this proof.
Moreover, although Turing does not mention Turing machines or computability,
the note is typed, with equations handwritten by him, on the back of a draft
of his paper on computable real numbers [26], so it is reasonable to interpret
“constructively” in a computability-theoretic sense. And in fact his proof, with
2007 corrections by Becher, Figueira, and Picchi [1], explicitly computes an absolutely normal number. In 2013, Becher, Heiber, and Slaman [2] published
an algorithm that computes an absolutely normal number in polynomial time.
Specifically, this algorithm computes the binary expansion of an absolutely normal number x, with the nth bit of x appearing after O(n2 f (n)) steps for any
computable unbounded nondecreasing function f . (Unpublished polynomialtime algorithms for computing absolutely normal numbers were also announced
independently by Mayordomo [22] and Figueira and Nies [12, 13] at about the
same time.)
In this paper we present a new algorithm that provably computes an absolutely normal in nearly linear time. Our algorithm computes the binary expansion of an absolutely normal number x, with the nth bit of x appearing
after O(npolylog(n)) steps. The term “nearly linear time” was introduced by
Gurevich and Shelah [14]. In that paper they showed that, while linear time
computability is very model-dependent, nearly linear time is very robust. For
example, they showed that random access machines, Kolmogorov-Uspensky machines, Schoenhage machines, and random-access Turing machines share exactly
the same notion of nearly linear time.
Our algorithm uses the Lempel-Ziv parsing algorithm to achieve its nearly
linear time bound. For each base b ≥ 2, we use a martingale (betting strategy)
that employs the Lempel-Ziv parsing algorithm and is implicit in the work
of Feder [11]. This base-b Lempel-Ziv martingale succeeds exponentially when
betting on the successive digits of the base-b expansion of any real number that is
not normal in base b. Our algorithm simultaneously computes and diagonalizes
against (limits the winnings of) a martingale that incorporates efficient proxies
of all these martingales, thereby efficiently computing a real number that is
2

normal in every base.
The rest of this paper is organized as follows. Section 2 presents the baseb Lempel-Ziv martingales and their main properties. Section 3 shows how to
transform a base-b Lempel-Ziv martingale into a base-b martingale with an efficiently computable nondecreasing savings account that is unbounded whenever
the base-b Lempel-Ziv martingale succeeds exponentially. Section 4 develops
an efficient method for converting a base-b martingale with an efficiently computable savings account to a base-2 martingale that succeeds whenever the base
b savings account is unbounded. Section 5 presents an algorithm that exploits
the uniformity of these constructions to efficiently and simultaneously compute
(a) a single base-2 martingale d that succeeds on the binary expansion of every
real number x for which some base-b martingale succeeds on the base-b expansion of x and (b) a particular real number x on which binary expansion d does
not succeed. This x is, perforce, absolutely normal. Section 6 presents an open
problem related to our work.

2

Lempel-Ziv Martingales

For each base b ≥ 1 we let Σb = {0, 1, . . . , b − 1} be the alphabet of base-b digits.
We write Σ∗b for the set of all (finite) strings over Σb and Σ∞
b for the set of all
(infinite) sequences over Σb . We write |x| for the length of a string or sequence
x, and we write λ for the empty string, the string of length 0. For x ∈ Σ∗b ∪ Σ∞
b
and 0 ≤ i ≤ j < |x|, we write x[i..j] for the string consisting of the ith through
jth digits in x. For x ∈ Σ∗b ∪ Σ∞
b and 0 ≤ n < |x|, we write x ↾ n = x[0..n − 1].
For w ∈ Σ∗b and x ∈ Σ∗b ∪ Σ∞
b , we say that w is a prefix of x, and we write
w ⊑ x, if x ↾ |w| = w.
A (base-b) martingale is a function d : Σ∗b → [0, ∞) satisfying
1 X
d(wa)
(1)
d(w) =
b
a∈Σb

Σ∗b .

for all w ∈
(This is the original martingale notion introduced by Ville
[28] and implicit in earlier papers of Lévy [20, 21]. Its relationship to Doob’s
subsequent modifications [10], which are the “martingales” of probability theory,
is explained in [16] along with the reason why Ville’s original notion is still
essential for algorithmic information theory.) Intuitively, a base-b martingale d
is a strategy for betting on the subsequent digits in a sequence S ∈ Σ∞
b , with
the strategy encoded in such a way that d(S ↾ n) is the amount of money that
a gambler using the strategy d has after the first n bets. The condition (1)
says that the payoffs for these bets are fair in the sense that the conditional
expectation of d(wa), given that w has occurred (and assuming that the digits
a ∈ Σb are equally likely), is d(w).
A function g : Σ∗b → [0, ∞) (which may or may not be a martingale) succeeds
on a sequence S ∈ Σ∞
b if
lim sup g(S ↾ n) = ∞,
n→∞

3

(2)

i.e., if its winnings on S are unbounded. The success set of a function g : Σ∗b →
[0, ∞) is
S ∞ [g] = {S ∈ Σ∞
b | g succeeds on S } .

A function g : Σ∗b → [0, ∞) succeeds exponentially on a sequence S ∈ Σ∞
b if
lim sup
n→∞

log g(S ↾ n)
> 0,
n

(3)

i.e., if its winnings on S grow at some exponential rate, perhaps with recurrent
setbacks. The exponential success set of a function g : Σ∗b → [0, ∞) is
S exp[g] = {S ∈ Σ∞
b | g succeeds exponentially on S } .
The f (n) success set of a function g : Σ∗b → [0, ∞) is


log g(S ↾ n)
≥
1
.
S f (n) [g] = S ∈ Σ∞
lim
sup
b
log f (n)
n→∞
ǫn

Note that S exp [g] = ∪ǫ>0 S 2 [g].
A function g : Σ∗b → [0, ∞) succeeds strongly on a sequence S ∈ Σ∞
b if (2)
holds with the limit superior replaced by a limit inferior i.e., if the winnings
converge to ∞. A function g : Σ∗b → [0, ∞) succeeds strongly exponentially
on a sequence S ∈ Σ∞
b if (3) holds with the limit superior replaced by a limit
inferior i.e., if the winnings grow at exponential rate. The strong success sets
exp
∞
Sstr
[g] and Sstr
[g] of a function g : Σ∗b → [0, ∞) are defined in the now-obvious
manner. It is clear that the inclusions
exp
Sstr
[g] ⊆ S exp [g] ⊆ S ∞ [g]

and

exp
∞
Sstr
[g] ⊆ Sstr
[g] ⊆ S ∞ [g]

hold for all g : Σ∗b → [0, ∞).
For each base b ≥ 2 the base-b Lempel-Ziv martingale is a particular martingale dLZ(b) based on the Lempel-Ziv parsing algorithm [19], as we now explain.
Formally, dLZ(b) is computed by the algorithm in Figure 1, but some explanation is appropriate here. The algorithm is written with several instances of
parallel assignment. For example, the second line initializes x, L(x), and d to
the values λ, 1, and 1, respectively. The items T , j, and x(j) are not needed
for the computation of dLZ(b) (w), but they are useful for understanding and
analyzing the algorithm.

4

i n p u t w ∈ Σ∗b ;
x, L(x), d = λ, 1, 1 ;
T, j = {λ}, 0 ;
while true do
begin
i f w = λ then o utput d and h a l t ;
i f L(x) = 1 then
begin
L(x) = b ;
for ea ch 0 ≤ a < b do L(xa) = 1 ;
T, x(j), j = T ∪ {x}Σb , x, j + 1 ;
x = λ;
end
else
begin
a, w = head(w), tail(w) ;
L(x), x, d = L(x) + b − 1, xa, bL(xa)
L(x) d
end
end
Figure 1: Algorithm for computing dLZ(b) (w).
The growing set T of strings in Σ∗b always contains all the prefixes of all its
elements, so it is a tree. We envision this tree as being oriented with its root at
the top and the immediate children v0, v1, . . . , v(b − 1) of each interior vertex
v of T displayed left-to-right below T . The dictionary of the algorithm is the
current set of leaves of T .
The string x in the algorithm is always an element of (i.e., location in) the
tree T , and L(x) is always the number of leaves of T that are descendants of x.
We regard x as a descendant of itself, so x is a leaf if and only if L(x) = 1.
It is clear that dLZ(b) (λ) = 1. In fact, the algorithm’s successive values of
d are the values dLZ(b) (u) for successive prefixes u of the input string w. More
precisely, if wt and dt are the values of w and d after t executions of the elseblock, then w = (w ↾ t)wt and dt = dLZ(b) (w ↾ t).
For w ∈ Σ∗b we define the tree T (w) as follows. If w = λ, then T (w) = {λ}.
If w = w′ a, where w′ ∈ Σ∗b and a ∈ Σb , then T (wa) is the value of T when
the algorithm terminates on input w′ . (Note that this is one step before it
terminates on input w′ a.) For w ∈ Σ∗b we define D(w) to be the number of
leaves in T (w).
The computation is divided into “epochs”. At the beginning of each epoch,
the string x is λ, i.e., it is located at the root of T . The string x then takes
successive digits from whatever is left of w (because a, w = head(w), tail(w)
removes the first digit of w and stores it in a), following this path down the
tree and updating d at each step, until w is empty (the end of the last epoch)

5

or x is a leaf if T . In the latter case, the jth epoch is over, the b children
x0, x1, . . . , x(b − 1) are added to T as new leaves, x is the jth phrase x(j) of w,
and x is reset to the root λ of T .
When the algorithm terminates, it is clear that exactly one of the following
things must hold.
(a) w = λ.
(b) w = x(1) . . . x(j).
(c) w = x(1) . . . x(j)u for some nonempty interior vertex u of T (w).
In case (a) or (b) we call w a full parse. In case (b) or (c) we call x(1), . . . , x(j)
the full phrases of w. In case (c) we call u the partial phrase of w.
Define the set Ab = {1 + (b − 1)r | r ∈ N } and the generalized factorial function f actb : Ab → Ab by
f actb (1 + (b − 1)r) =

r
Y

k=1

(1 + (b − 1)k)

for all r ∈ N.
Observation 2.1 For all n ∈ Ab ,
1≤

f actb (n)
 n ≤ n.
1
n b−1

e b−1

(4)

e

Lemma 2.2 (Feder [11]) Let w ∈ Σ∗b .
1. If w is a full parse, then

dLZ(b) (w) =

b|w|
.
f actb (D(w))

2. If w is not a full parse and u is its partial phrase, then
dLZ(b) (w) =

b|w|
L(u),
f actb (D(w))

where L(u) is the number of leaves below u in T (w).
Lemma 2.3 For S ∈ Σ∞
b and α ∈ (0, 1) the following three conditions are
equivalent.
(1−α)n

(a) S ∈ S b

[dLZ(b) ].

(b) There exist infinitely many full parses w ⊑ S for which
D(w) logb |w| < α(b − 1)|w|.
6

(c) There exist infinitely many full parses w ⊑ S for which
D(w) log b D(w) < α(b − 1)|w|.
Corollary 2.4 For S ∈ Σ∞
b the following three conditions are equivalent.
(a) S ∈ S exp [dLZ(b) ].
(b) There exist α < 1 and infinitely many full parses w ⊑ S for which
D(w) logb |w| < α(b − 1)|w|.
(c) There exist α < 1 and infinitely many full parses w ⊑ S for which
D(w) log b D(w) < α(b − 1)|w|.
We conclude this section by explaining the connection between the LempelZiv martingales and normality. First, Schnorr and Stimm [24] defined (implicitly) a notion of finite-state base-b martingale and proved that every sequence
S ∈ Σ∞
b obeys the following dichotomy.
1. If S is normal, then no finite-state base-b martingale succeeds on S. (In
fact, every finite-state base-b martingale decays exponentially on S.)
2. If S is not normal, then some finite-state base-b martingale succeeds exponentially on S.
Some twenty years later, Feder [11] defined (implicitly) the Lempel-Ziv martingale dLZ(b) and proved (implicitly) that dLZ(b) is at least as successful on
every sequence as every finite-state base-b martingale. That is, for finite-state
base-b martingale d, the inclusions
∞
S ∞ [d] ⊆ S ∞ [dLZ(b) ], Sstr
[d] ⊆ S ∞ [dLZ(b) ],
exp
exp
S exp [d] ⊆ S exp [dLZ(b) ], Sstr
[d] ⊆ Sstr
[dLZ(b) ]

all hold. This, together with Schnorr and Stimm’s dichotomy result, implies
that dLZ(b) succeeds exponentially on every non-normal sequence in Σ∞
b . Hence
a real number x is absolutely normal if none of the martingales dLZ(b) succeed
exponentially on the base-b expansion of x.

3

Savings Accounts

In this section we construct a conservative version of the the Lempel-Ziv martingale dLZ(b) consisting of a new martingale d′ that can be smaller than dLZ(b)
but that has a savings account in the following sense.
Definition. A nondecreasing function g : Σ∗b → [0, ∞) is a savings account of
a martingale d : Σ∗b → [0, ∞) if, for every w ∈ Σ∗b , d(w) ≥ g(w).
7

Construction 3.1 Let d = dLZ(b) be the base-b-Lempel-Ziv martingale. We
define a new martingale d′ = e′ + g ′ as follows.
We first define e′ . e′ (λ) = b, goal(λ) = −1, taken(λ) = −1. For w ∈ Σ∗b ,
let w = x(1) . . . x(j)u, for z = x(1) . . . x(j) a full parse and u a partial or full
phrase of w. Let
goal(w)

= |w| − ⌈D(z)(logb (D(z)))/(b − 1)⌉ + ⌊D(z)(logb (e))/(b − 1)⌋
1

−⌈logb (D(z))⌉ − ⌈logb e b−1 ⌉ − 1,

taken(w) =



taken(z) if goal(w) ≤ taken(z)
goal(w) if goal(w) > taken(z)},

e′ (w) = e′ (z) ·

d(w) −taken(w)+taken(z)
b
.
d(z)

Let g ′ be defined as follows. g ′ (λ) = 1 and for y ∈ Σ∗b , a ∈ Σb , if ya = w, let
w = x(1) . . . x(j)u, for z = x(1) . . . x(j) a full parse and u a partial phrase of w.
 ′
g (y)
if goal(w) ≤ taken(z)
g ′ (ya) =
if
goal(w) > taken(z)
g ′ (y) + e′ (y) b−1
b
Theorem 3.2 Let d′ and g ′ be as defined in Construction 3.1. Then d′ is a
martingale and g ′ is its savings account,
S exp [dLZ(b) ] ⊆ S ∞ [g ′ ],
d′ is bounded by a polynomial, and d′ is computable in a nearly linear time bound
that does not depend on b.
Proof of Theorem 3.2.
Claim 3.3 d′ = e′ + g ′ is a martingale and g ′ is a savings account for d′ .
Proof. Let us prove that d′ is a martingale. When goal(w) ≤ taken(z) we have
that
′
1 X ′
(z) 1 P
e (wa) = ed(z)
a∈Σb d(wa) =
b
b
a∈Σb

e′ (z)
d(z)

· d(w) = e′ (w)

with that last equality holding both when w = z and when z is a proper substring
of w. Since g ′ (wa) is constant the martingale equality holds in this case.
In the second case, when goal(w) > taken(z), we have that
e′ (ya) = e′ (y)d(ya)/d(y)1/b, so
X
P
P
d′ (wa)
= a∈Σb e′ (ya) + a∈Σb g ′ (ya)
a∈Σb

′
′
′
= e′ (y) + b(g ′ (y) + e′ (y) b−1
b ) = b(e (y) + g (y)) = bd (w).

8

Since e′ is nonnegative, by definition g ′ is a nondecreasing function. Therefore g ′ is a savings account of d′ .

Claim 3.4 There is a C > 0 such that for every w ∈ Σ∗b ,
d(w)b−taken(w) ≤ C · D(z) · L(u).
d(w)b−goal(w) ≥ b
Proof. Use that taken(w) ≥ goal(w), Lemma 2.2, and Observation 2.1.



Claim 3.5 If w ∈ Σ∗b then e′ (w) = d(w)b−taken(w) .
Proof. By induction on |w|, let w = x(1) . . . x(j)u, z = x(1) . . . x(j)x(j + 1)
e′ (w)

d(w) −taken(w)+taken(z)
b
d(z)
d(w) −taken(w)+taken(z)
b
= d(w)b−taken(w) .
d(z)b−taken(z) ·
d(z)
e′ (z) ·

=
=


∞ ′
Claim 3.6 If y ∈ Σ∞
b and goal(y ↾ n) is unbounded then y ∈ S [g ].

Proof.
If goal(y ↾ n) is unbounded then infinitely often we use the second case
in the definitions of taken and g ′ and have that taken(y ↾ n) = goal(y ↾ n),
e′ (y ↾ n) = d(y ↾ n)b−goal(y↾n) , and g ′ (y ↾ na) = g ′ (y ↾ n) + e′ (y ↾ n) b−1
b .
For those n, by Claim 3.4, e′ (y ↾ n) ≥ b, therefore g ′ (y ↾ na) ≥ g ′ (y ↾
n) + b − 1.
Since g ′ is monotonic, y ∈ S ∞ [g ′ ].

(1−α)n

Claim 3.7 S b

[dLZ(b) ] ⊆ S ∞ [g ′ ].

(1−α)n

Proof. If y ∈ S b
[dLZ(b) ] then by Lemma 2.3 for infinitely many n, D(y ↾
n) logb (D(y ↾ n)) < α(b − 1)n.
Notice that therefore goal(y ↾ n) is unbounded and by Claim 3.6 y ∈ S ∞ [g ′ ].

Claim 3.8 There is a C > 0 such that for everyP
w, e′ (w) ≤ C · D(z) · L(u) (for
′
u a partial or the last full phrase of w). g (w) ≤ v⊑w e′ (v)(b − 1)/b. Therefore
there is a c > 0 such that for every w, d′ (w) ≤ |w|c .
Claim 3.9 d′ can be computed in nearly linear time (in time n logc n for c not
depending on b.

9

Proof.
Again, for w ∈ Σ∗b , let w = x(1) . . . x(j)u, for z = x(1) . . . x(j) a full parse
and u a partial or full phrase of w. If goal(w) > taken(z), let t be such that
t ⊑ u and goal(zt) = taken(z).
Notice that

′

g (w) =



g ′ (z) P
if goal(w) ≤ taken(z)
g ′ (z) + v⊑u,|zv|>|zt| e′ (zt) b−1
L(v)
if goal(w) > taken(z),
b

where L(v) isPthe number of leaves below v in T (w). Given precomputed values
′
for f (u) =
v⊑u L(v), the value of g (w) can be easily computed in nearly
linear time. The precomputed value of f (u) will be stored in the u node of the
LZ tree for z.

This completes the proof of Theorem 3.2.


4

Base change

We use infinite sequences over Σb to represent real numbers in [0,1). For this,
we associate each string w ∈ Σ∗b with the half-open interval [w]b defined by
|w|
P
[w]b = [x, x + b−|w| ), for x =
w[i − 1]b−i . Each real number α ∈ [0, 1) is then
i=1

represented by the unique sequence seqb (α) ∈ Σ∞
b satisfying
w ⊑ seqb (α) ⇐⇒ α ∈ [w]b
for all w ∈ Σ∗b . We have
α=

∞
X
i=1

seqb (α)[i − 1]b−i

and the mapping seqb : [0, 1) → Σ∞
b is a bijection. (Notice that [w]b being
half-open prevents double representations.) We define realb : Σ∞
b → [0, ∞) to
be the inverse of seqb . A set of real numbers A ⊆ [0, 1) is represented by the set
seqb (A) = {seqb (α) | α ∈ A}
of sequences. If X ⊆ Σ∞
b then
realb (X) = {realb (x) | x ∈ X}.
For a positive number x we use the notation logb (x) = ⌈logb (x)⌉.
Construction 4.1 Let d : Σ∗b → [0, ∞) be a polynomially-bounded martingale
with a savings account g.
We define γ : Σ∗b → [0, 1] a probability measure γ(w) := b−|w| d(w).
10

Using the Carathéodory extension to Borel sets, γ can be extended to any
interval [a, c]; we denote with γ̂ this extension. (In fact if we consider all U ⊆ Σ∗b
such that all u, v ∈ U,
Pu 6= v are incomparable and [u]b ⊆ [a, c] for all u ∈ U ,
then γ̂([a, c]) = supU u∈U γ(u)).
We define µ : {0, 1}∗ → [0, 1] by µ(y) = γ̂([y]2 ).
Finally we define d(2) : {0, 1}∗ → [0, ∞) by d(2) (y) = 2|y| µ(y).
Theorem 4.2 Assume that d is a base-b martingale that is polynomially bounded
and g is a savings account of d, and let d(2) be defined from d and g as in Construction 4.1. Then
realb (S ∞ [g]) ⊆ real2 (S ∞ [d(2) ]).
Moreover, if d is computable in a nearly linear time bound not depending on b,
then so is d(2) .
Proof of Theorem 4.2.
Property 4.3 Let α ∈ [0, 1). If seqb (α) ∈ S ∞ [g], then seq2 (α) ∈ S ∞ [d(2) ].
Proof. Let x = seqb (α) ∈ S ∞ [g]. Let y = seq2 (α).
We use here that d has a savings account g, so if g(x ↾ n) > m then for all
w with x ↾ n ⊑ w, g(w) > m.
Let m ∈ N and choose n such that g(x ↾ n) > m. Let q be such that
[y ↾ q]2 ⊆ [x ↾ n]b . Let us see that d(2) (y ↾ q) > m.
Let r ∈ N. Let Aqr = {w ∈ Σ∗b | |w| = r and [w]b ⊆ [y ↾ q]2 }. Then
d(2) (y ↾ q) =
≥

2q γ̂([y ↾ q]2 ) = 2q lim
r

2q m lim
r

X

X

d(w)b−|w|

w∈Aqr

b−|w| = 2q m2−q = m.

w∈Aqr

The last chain of equations holds because [y ↾ q]2 ⊆ [x ↾ n]b and for every
w ∈ Aqr , [w]b ⊆ [y ↾ q]2 , so x ↾ n ⊑ w for any w ∈ Aqr .

We next compute d(2) . For each m ∈ N we define µm : {0, 1}∗ → [0, 1] by
X
γ(w).
µm (y) =
|w|=m,[w]b∩[y]2 6=∅

Claim 4.4 For every y ∈ {0, 1}∗ and m ∈ N, |µ(y) − µm (y)| ≤ 2b−m mc .
Proof. Let c be such that d(w) ≤ |w|c for every w (using that d is polynomially
bounded). Then since at most two strings w with |w| = m have the property
that [w]b ∩ [y]2 6= ∅ and [w]b 6⊆ [y]2 , we have
|µ(y) − µm (y)| ≤ 2b−m mc .

(2)

(2)

For each m ∈ N we define dm : {0, 1}∗ → [0, ∞) by dm (y) = 2|y| µm (y).
11



Claim 4.5 For some c > 0, for every y ∈ {0, 1}∗, for every m ∈ N,
|y| −m log b+c log m
|d(2) (y) − d(2)
.
m (y)| ≤ 2 2

Corollary 4.6 For some c′ > 0, for every y ∈ {0, 1}∗,
(2)

|d(2) (y) − d|y|/ log b+c′ log |y| (y)| ≤ 1/|y|3 .
Proof. Take c′ = (4 + c)/ log b and use the previous claim.

Notice that the approximation of d(2) is slow, but it is enough for the diagonalization performed in the next section.
(2)

Property 4.7 For m ∈ N, y ∈ {0, 1}∗, dm (y) can be computed by considering
a maximum of 2b neighbor strings w ∈ Σrb for r = |y|/ log b to m, computing
d(w) for each of them and doing an addition and a multiplication for each.
Proof. Consider P , the smallest prefix free set of strings w ∈ Σ∗b such that
[w]b ⊆ [y]2 , and notice that |w| ≥ |y|/ log b for each such string. For each r
there are at most 2b − 2 strings of length r in P (otherwise we can replace some
of them by a single string of length r − 1). For length m we may need two more
strings |w| = m, [w]b ∩ [y]2 6= ∅.

(2)

Corollary 4.8 For y ∈ {0, 1}∗, d|y|/ log b+c′ log |y| (y) can be computed by considering a maximum of 2b neighbor strings w ∈ Σrb for r = |y|/ log b to |y|/ log b +
c′ log |y|, computing d(w) for each of them and doing an addition and a multiplication for each.
(2)

By Corollary 4.6 f (y) = d|y|/ log b+c′ log |y| (y) approximates d(2) (y) within a
1/|y|3 bound, and by the last corollary f can be computed in nearly linear time.
In order to have a nearly linear time bound independent of b consider only y for
which log|y| ≥ 2b.
This concludes the proof of Theorem 4.2.


5

Absolutely Normal Numbers

In this section we give an algorithm that diagonalizes against the Lempel-Ziv
martingales for all bases in nearly linear time.
We use the following theorem
Theorem 5.1 Let (dk )k∈N be a sequence of base-2 martingales such that for
ck : {0, 1}∗ → [0, ∞) with the following two
each of them there exists a function d
properties
1. For every y ∈ {0, 1}∗
ck (y)| ≤ 1 .
|dk (y) − d
|y|3
12

ck is computable in a nearly linear time bound that does not depend on k.
2. d

Then we can compute in nearly linear time a binary sequence x such that, for
every k, x 6∈ S ∞ [dk ].
Proof. Without loss of generality we assume that dk (λ) = 1 for all k.
Let d : {0, 1}∗ → [0, ∞) be defined by
log2 |w|

X

d(w) =

√

2−k−2

k

k=1

ck (w).
d

Our algorithm will diagonalize against d, constructing a binary sequence x
as follows. If x ↾ n has been defined then choose the next bit of x as c ∈ {0, 1}
that minimizes d((x ↾ n)c).
Claim 5.2 If x 6∈ S ∞ [d] then for every k, x 6∈ S ∞ [dk ].
Let n ∈ N, k ∈ N, n ≥ 2

√
k

.

dk (x ↾ n) ≤ c
dk (x ↾ n) + 1/n3 ≤
√

≤ 2k+2

k

d(x ↾ n) + 1/n3

Claim 5.3 x 6∈ S ∞ [d].
Let w ∈ {0, 1}∗. We prove that there exists c ∈ {0, 1} such that d(wc) ≤
d(w) + 1/|w|2 .
log2 (|w|+1)

d(wc)

X

=

√

k

ck (wc)
d

√

k

(dk (wc) + 1/(|w| + 1)3 )

√

k

(dk (w) + 1/(|w| + 1)3 )

2−k−2

k=1

log2 (|w|+1)

X

≤

2−k−2

k=1

log2 (|w|+1)

X

≤

2−k−2

k=1

log2 (|w|)

X

≤

2

√

−k−2

k=1
log2 (|w|+1)

+

X

log2 (|w|+1)
k

ck (w) + 1/|w| ) +
(d
3

√

2−k−2

k

X

√

2−k−2

k

1/(|w| + 1)3 )

k=1

(dk (w))

k=log2 (|w|)+1
∞
X

≤

d(w) +

≤

d(w) + 1/|w|2 .

2

√

−k−2

log2 (|w|+1)
k

3

2/(|w|) ) +

X

k=log2 (|w|)+1

k=1

13

√
k

2−k−2

2|w|

Therefore
and x 6∈ S ∞ [d].

6

d(x ↾ n) ≤ d(x ↾ (n − 1)) + 1/n2 ≤ C


Open Problem

Many questions arise naturally from this work, but the following problem appears to be especially likely to demand new and useful methods.
As we have seen, normal numbers are closely connected to the theory of
finite automata. Schnorr and Stimm [24] proved that normality is exactly the
finite-state case of randomness. That is, a real number α is normal in a base
b ≥ 2 if and only if no finite-state automaton can make unbounded money
betting on the successive digits of the base-b expansion of α with fair payoffs.
The theory of finite-state dimension [9], which constrains Hausdorff dimension
[15] to finite-state automata, assigns each real number α a finite-state dimension
(b)
dimFS (α) ∈ [0, 1] in each base b. A real number α then turns out to be normal
(b)
in base b if and only if dimFS (α) = 1 [6]. Do there exist absolutely dimensioned
(b)
numbers, i.e., real numbers α for which dimFS (α) = dimFS (α) does not depend
on b, and 0 < dimFS (α) < 1?

Acknowledgments
The first author’s research was supported in part by National Science Foundation Grants 0652569, 1143830, 1247051, and 1545028. Part of this author’s
work was done during a sabbatical at Caltech and the Isaac Newton Institute
for Mathematical Sciences at the University of Cambridge, part was done during three weeks at Heidelberg University, with support from the Mathematics
Center Heidelberg and the Heidelberg University Institute of Computer Science,
and part was done during the workshop “Normal Numbers: Arithmetical, Computational and Probabilistic Aspects” at the Erwin Schrödinger International
Institute for Mathematics and Physics at the University of Vienna.
The second author’s research was supported in part by Spanish Government MEC Grants TIN2011-27479-C04-01 and TIN2016-80347-R. Part of this
author’s work was done during a research stay at the Isaac Newton Institute
for Mathematical Sciences at the University of Cambridge, part was done during three weeks at Heidelberg University, with support from the Mathematics
Center Heidelberg and the Heidelberg University Institute of Computer Science,
and part was done during the workshop “Normal Numbers: Arithmetical, Computational and Probabilistic Aspects” at the Erwin Schrödinger International
Institute for Mathematics and Physics at the University of Vienna.

14

References
[1] V. Becher, S. Figueira, and R. Picchi. Turing’s unpublished algorithm for
normal numbers. Theoretical Computer Science, 377:126–138, 2007.
[2] V. Becher, P. A. Heiber, and T. A. Slaman. A polynomial-time algorithm
for computing absolutely normal numbers. Information and Computation,
232:1–9, 2013.
[3] P. Billingsley. Probability and Measure, third edition. John Wiley and Sons,
New York, N.Y., 1995.
[4] E. Borel.
Sur les probabilités dénombrables et leurs applications
arithmétiques. Rendiconti del Circolo Matematico di Palermo, 27(1):247–
271, 1909.
[5] J. Borwein and D. Bailey. Mathematics by Experiment: Plausible Reasoning
in the 21st Century, second edition. A. K. Peters, 2008.
[6] C. Bourke, J. M. Hitchcock, and N. V. Vinodchandran. Entropy rates
and finite-state dimension. Theoretical Computer Science, 349(3):392–406,
2005.
[7] Y. Bugeaud. Distribution modulo one and Diophantine approximation, volume 193. Cambridge University Press, 2012.
[8] J. W. S. Cassels. On a problem of Steinhaus about normal numbers. Colloquium Mathematicum, 7:95–101, 1959.
[9] J. J. Dai, J. I. Lathrop, J. H. Lutz, and E. Mayordomo. Finite-state dimension. Theoretical Computer Science, 310:1–33, 2004.
[10] J. Doob. Regularity properties of certain families of chance variables.
Transactions of the American Mathematical Society, 47:455–486, 1940.
[11] M. Feder. Gambling using a finite state machine. IEEE Transactions on
Information Theory, 37:1459–1461, 1991.
[12] S. Figueira and A. Nies. Feasible analysis and randomness. Manuscript,
2013.
[13] S. Figueira and A. Nies. Feasible analysis, randomness, and base invariance.
Theory of Computing Systems, 56:439–464, 2015.
[14] Y. Gurevich and S. Shelah. Nearly linear time. In Proceedings of the First
Symposium on Logical Foundations of Computer Science. Springer, 1989.
[15] F. Hausdorff. Dimension und äußeres Maß. Math. Ann., 79:157–179, 1919.
[16] J. Hitchcock and J. Lutz. Why computational complexity requires stricter
martingales. Theory of Computing Systems, 39:277–296, 2006.
15

[17] A. N. Kolmogorov. Foundations of the Theory of Probability. Chelsea,
1950.
[18] H. Lebesgue. Sur certaines demonstrations d’existence. Bull. Soc. Math.
de France, 45:132–144, 1917.
[19] A. Lempel and J. Ziv. Compression of individual sequences via variable
rate coding. IEEE Transaction on Information Theory, 24:530–536, 1978.
[20] P. Lévy. Propriétés asymptotiques des sommes de variables indépendantes
ou enchainées. Journal des mathématiques pures et appliquées. Series 9.,
14(4):347–402, 1935.
[21] P. Lévy. Théorie de l’Addition des Variables Aleatoires. Gauthier-Villars,
1937 (second edition 1954).
[22] E. Mayordomo. Construction of an absolutely normal real number in polynomial time. Manuscript, 2013.
[23] W. M. Schmidt. On normal numbers. Pacific J. Math, 10(2):661–672, 1960.
[24] C.-P. Schnorr and H. Stimm. Endliche automaten und zufallsfolgen. Acta
Informatica, 1(4):345–359, 1972.
[25] W. Sierpinski. Démonstration élémentaire du théorème de M. borel sur les
nombres absolument normaux et détermination effective d’une tel nombre.
Bull. Soc. Math. France, 45:125–132, 1917.
[26] A. M. Turing. On computable numbers with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42:230–
265, 1936-1937.
[27] A. M. Turing. A note on normal numbers. In S. B. Cooper and J. van
Leeuwen, editors, Alan Turing: His Work and Impact. Elsevier Science,
2013.
[28] J. Ville. Étude Critique de la Notion de Collectif. Gauthier–Villars, Paris,
1939.
[29] S. Wagon. Is π normal? Math. Intelligencer, 7:65–67, 1985.

16

