arXiv:1510.02004v1 [math.NT] 2 Oct 2015

M. LEVIN’S CONSTRUCTION OF ABSOLUTELY NORMAL
NUMBERS WITH VERY LOW DISCREPANCY
NICOLÁS ALVAREZ AND VERÓNICA BECHER

Abstract. Among the currently known constructions of absolutely normal
numbers, the one given by Mordechay Levin in 1979 achieves the lowest discrepancy bound. In this work we analyze this construction in terms of computability and computational complexity. We show that, under basic assumptions, it yields a computable real number. The construction does not give
the digits of the fractional expansion explicitly, but it gives a sequence of
increasing approximations whose limit is the announced absolutely normal
−n
number. The n-th approximation has an error less than 22 . To obtain the
n-th approximation the construction requires, in the worst case, a number of
mathematical operations that is double exponential in n. We consider variants
on the construction that reduce the computational complexity at the expense
of an increment in discrepancy.

1. Introduction
Normal numbers were introduced by Borel in 1909 [8]. A real number α is normal
to an integer base λ greater than or equal to 2 if its fractional expansion in base λ
given by
X dx
where each dx is in {0, 1, ..., λ − 1},
α − ⌊α⌋ =
λx
x≥1

is such that, for each positive integer k, each fixed block of digits of length k appears
in (dx )x≥1 with asymptotic frequency λ−k . Borel calls a number absolutely normal
if it is normal to every integer base greater than or equal to 2.
Let (ξx )x≥0 be an arbitrary sequence of real numbers in the unit interval. The
quantity
D(P, (ξx )x≥0 ) = sup
γ∈(0,1]

#{x : 0 ≤ x < P and ξx < γ}
−γ
P

P −1
is the discrepancy of (ξx )x=0
. The sequence (ξx )x≥0 is uniformly distributed in the
unit interval if D(P, (ξx )x≥0 ) goes to 0 when P goes to infinity. By a theorem of
D. Wall [9, Theorem 4.14], a real number α is normal to base λ if, and only if, the
sequence {αλx }x≥0 , where {ξ} = ξ − [ξ] is the fractional part of ξ, is uniformly
distributed in the unit interval.

Date: January 10, 2018.
2000 Mathematics Subject Classification. Primary 11K16, 11K38, 68-04; Secondary 11-04.
Key words and phrases. Normal numbers, Discrepancy, Algorithms.
Supported by a doctoral fellowship from CONICET, Argentina.
Supported by Agencia Nacional de Promoción Cientı́fica y Tecnológica and CONICET,
Argentina.
1

2

NICOLÁS ALVAREZ AND VERÓNICA BECHER

We use the customary notation for asymptotic growth of functions, and we say
f (n) is in O(g(n)) if ∃k > 0 ∃n0 ∀n > n0 , |f (n)| ≤ k|g(n)|.
Borel [8] proved that almost every real number (in the sense of Lebesgue measure)
is normal to every integer base and Gal and Gal [13] showed that, indeed, for almost
every r
real number α and for every integer base λ the discrepancy D(P, {αλx }x≥0 ) is
 log log P 
. For a thorough presentation of normal numbers and the theory
in O
P
of uniform distribution see the books [9, 15, 12].
In 1979 Mordechay Levin [18] considered the notion of normality for real numbers with respect to bases that are real numbers greater than 1, and he gave an
explicit construction of a number that is normal to arbitrary many real bases, with
controlled discrepancy of normality. More precisely, given a sequence (λj )j≥1 of real
numbers greater than 1, a monotone increasing sequence (tj )j≥1 of positive integers
and a non negative real number a, Levin constructs a real number α greater than
a that is normal to each of the bases λj , for j = 1, 2, . . . such that D(P, {αλx }x≥0 )

 (log P )2
√
ω(P ) , where ω(P ) is a non-decreasing function that determines
is in O
P
from (λj )j≥1 and (tj )j≥1 the collection of bases considered at position P , and
the constant in the order symbol depends on λj . Since (λj )j≥1 and (tj )j≥ can
be such that ω(P ) grows arbitrarily slow, so D(P, {αλx }x≥0 ) can end up being in
 (log P )2 
√
O
. By considering normality with respect to arbitrary sequences (λj )j≥1
P
of real numbers greater than 1, Levin extends Borel’s notion of absolute normality.
With λj = j + 1 for j = 1, 2, . . ., he obtains a number α that is absolutely normal
in Borel’s sense.
The interest in this construction by Levin is that, among the currently known
methods to construct absolutely normal numbers, it achieves the lowest discrepancy
bound. In this work we give a plain presentation of this construction and we show
that, under basic assumptions, the construction is computable and we establish its
computational complexity.
Regarding discrepancy and computational complexity, known constructions of
computable absolutely normal numbers can be classified as follows:
• Constructions that run in double exponential time, which means that to
produce the P -digit of the expansion of the constructed number α in a given
base they perform a number of operations that is double exponential in P . One
 1 
√ .
example is Alan Turing’s algorithm [24, 3] for which D(P, {αλx }x≥0 ) is in O 16
P
Another is the computable reformulation of Sierpiński’s construction [2] for which
 1 
D(P, {αλx }x≥0 ) is in O √
.
9
P
• Constructions that run in exponential time, as Wolfgang Schmidt’s algo (log P )4 
rithm [22] for which D(P, {αλx }x≥0 ) is in O
. Our variants of Schmidt’s
1/4
e(log P )
algorithm [1, 6] also require exponential time. These algorithms produce numbers
that are normal to all the bases in a given arbitrary set, while they are not (simply)
normal to any of the multiplicatively independent bases in the complement. Besides,
our algorithm [5] for computing an absolutely normal Liouville number α has at
least exponential complexity and we have not estimated the discrepancy of the
P −1
sequence {λj α}j=0
, for positive P .

LEVIN’S CONSTRUCTION OF ABSOLUTELY NORMAL NUMBERS

3

• Constructions that run in polynomial time, as our algorithm [4] that requires
just above quadratic time to compute an absolutely normal number α. Speed of
computation is obtained by sacrificing discrepancy. The algorithm deals explicitly
with the discrepancy at the intermediate steps of the construction but we have not
estimated the discrepancy of the sequence {λx α}x≥0 .
There are constructions of numbers ensuring normality to just one base which
achieve much lower discrepancy bounds than those for absolute normality. The
one with smallest discrepancy was given also by Levin [19]. Using van der Corput
type sequences. Levin constructs a number α normal to an integer base λ, such
 (log P )2 
. This discrepancy bound
that the discrepancy D(P, {αλx }x≥0 ) is in O
P
is surprisingly small, considering that for any sequence (ξx )x≥0 of reals in the unit
interval,
lim sup
P →∞

P
D(P, (ξx )x≥0 )
log P

is greater than 0 (this result was proved by W. Schmidt in 1972, see [9]). The
computational complexity of this construction has not been studied yet. Recently,
Madritsch and Tichy [20] found conditions for van der Corput sets and suggest to
use them for the construction of absolutely normal numbers.
The construction insuring normality to one base that has smallest computational
complexity coincides with the historically first construction of a number that is
normal to base 10, and it is due to Champernowne in 1933 [10]. Champernowne’s
constant is computable with logarithmic complexity, which means that the P -th
digit in the expansion can be obtained independently of all the previous digits
by performing O(log P ) elementary operations. It is also possible to compute the
first P digits of Champerowne’s constant in O(P ) operations. The discrepancy
 1 
and for every P it has
D(P, {Champernowne′ s constant λx }x≥0 ) is in O
log P
K
been proved to be greater than or equal to
, for positive K [10, 19, 21].
log P
2. Levin’s construction
In this section we give a comprehensible presentation of Levin’s construction [18].
We reorganized the original material but we kept the notation.
Definition. Let λ be a real number greater than 1 and let (λj )∞
j=1 a sequence of
real numbers, each greater than 1. A number α is normal to base λ if the sequence
{αλx }x≥0 is uniformly distributed in the unit interval, and absolutely normal to
bases λj for all positive j, if, α is normal to base λj for each positive j.
Theorem 1 (Levin [18]). Let (λj )j≥1 be sequence of real numbers greater than 1,
let (tj )j≥1 be a sequence of integers monotonically increasing at any speed and let a
be a non-negative real number. There is a real number α constructed from a and the
sequences (λj )j≥1 and (tj )j≥1 which is normal to base λj for each positive integer j
and such that for any positive integer P ,


(log P )2 ω(P )
x
√
D(P, {αλj }x≥0 ) is in O
P

4

NICOLÁS ALVAREZ AND VERÓNICA BECHER

where ω(P ) = 1 if P ∈ [1, ℓ2 ), and ω(P ) = k if P ∈ [ℓk , ℓk+1 ), with
ℓk = max(tk , max 2⌈| log2 log2 λv |⌉ + 5) and the constant in the order symbol
1≤v≤k

depends on λj .

The number α proposed by Levin is defined as
∞
X
ar
,
α=a+
2nr qr
r=ℓ1

nr = 2r − 2, and
r
qr = 22 +r+1 .
Fix (λj )j≥1 an arbitrary sequence of real numbers greater than 1, fix (tj )j≥1 a
sequence of integers monotonically increasing at any speed and fix a non-negative
real a. Along the article we refer freely to the values ℓr , nr , qr , ar and ω(r) for any
positive r as well as to the real α.
We need some further notation. For each pair of positive integers r, j we let
nr,j = ⌊nr logλj 2⌋,
τr,j = nr+1,j − nr,j , and
√
Ar,j = ⌊ τr,j ⌋.
Lemma 2. For every positive j and for every r ≥ ℓj − 1,
2r−1 logλj 2 ≤ τr,j ≤ 2r+1 logλj 2,
τr,j ≥ max(7, τr+1,j /4).

Proof. From the definitions we know that τr,j = 2r logλj 2 + θr,j , where |θr,j | ≤ 1,
while for r ≥ ℓj − 1,
8 = 2log2 log2 λj +3 logλj 2 ≤ 2r logλj 2.

The wanted inequalities follow.



Fix αℓ1 = a and for each positive integer m, let am in [0, qm ). For every r ≥ ℓ1
define
r
X
am
.
αr+1 = αℓ1 +
2nm qm
m=ℓ1

We write e(x) to denote ex . For integers c, m1 , m2 , r with r ≥ ℓj we define the
quantities,

τr,j −1 
 
X
c  nr,j +x m2 x 
λ
+
,
Sr,j (m1 , m2 , c) =
e 2πi m1 αr + nr
2 qr j
τr,j
x=0
Ar,j

|Sr,j (m1 , m2 , c)|
,
m1 m2
m1 ,m2 =−Ar,j
X′
denotes that the term with m1 = m2 = 0 is absent
where m = max(1, |m|) and
from the sum.
X′
Remark. In Levin’s paper [18] the definition of Sr,j (m1 , m2 , c) appears with
X
X′
excludes
while the definition of Dr,j (c) appears with
. However, the use of
the term m1 = m2 = 0, which only makes sense in the definition of Dr,j (c).
Dr,j (c) =

X′

LEVIN’S CONSTRUCTION OF ABSOLUTELY NORMAL NUMBERS

5

Construction: Levin’s construction of absolutely normal numbers
input : a sequence (λj )j≥1 of reals greater than 1,
an increasing sequence (tj )j≥1 of integers
a non-negative real a.
output: a sequence of rationals (αr )r≥1 such that lim αr = α and
r→∞
 (log P )2 ω(P ) 
x P
√
.
for each λj , the discrepancy of {αλj }x=0 is in O
P
Define the function ℓk = max(tk , max 2⌈| log2 log2 λv |⌉ + 5)
1≤v≤k

r = ℓ1
αr = a
repeat forever
nr = 2 r − 2
r
qr = 22 +r+1
if r in [1, ℓ2 )) then ω(r) = 1
else ω(r) = the unique k such that r in [ℓk , ℓk+1 )
for j = 1 to ω(r) do
τr,j = nr+1,j − nr,j
√
Ar,j = ⌊ τr,j ⌋
end
Find the least integer ar in [0, qr ) such that for each j in [1, ω(r)]
Dr,j (ar ) < 2
where

 λ 3/2 √
2
j
τr,j 3 + ln τr,j
λj − 1

Ar,j

|Sr,j (m1 , m2 , c)|
,
m1 m2
m1 ,m2 =−Ar,j
τr,j −1 
 
X
e 2πi m1 αr +
Sr,j (m1 , m2 , c) =

Dr,j (c) =

X′

x=0

X′



m2 x 
nr,j +x
λ
+
,
2nr qr j
τr,j
c

denotes the sum without the term with m1 = m2 = 0,
m = max(1, |m|).
αr+1 = αr +
print αr+1
r =r+1
end

ar
2nr qr

6

NICOLÁS ALVAREZ AND VERÓNICA BECHER

Lemma 3 (Lemma 1 in [18]). Let integers j, r, m1 , m2 such that r ≥ ℓj and
0 < max(|m1 |, |m2 |) ≤ Ar,j . Then,
r −1
1/2
 1 qX
 λ 3/2 √
j
τr,j .
<2
|Sr,j (m1 , m2 , c)|2
qr c=0
λj − 1

Proof. Let
Tr,j (m1 , m2 ) =

r −1
1/2
 1 qX
.
|Sr,j (m1 , m2 , c)|2
qr c=0

Remark. Levin’s original paper misses the third parameter c of the function Sr,j .
In accordance with the familiar inequality


N −1
1
1 X
,
e(2πiθx) ≤ min 1,
N x=0
2N hhθii
where hhθii is the distance of θ from the nearest integer, we have
2
Tr,j
(m1 , m2 ) =
τr,j −1

r −1 
 m (x − y) 
 
X 1 qX
c  nr,j +x
n +y
2
+
λj
− λj r,j
e 2πi m1 αr + nr
q
q
2
τr,j
r
r
c=0
x,y=0


τr,j −1
X
1


min 1,
<
.
n
+x
n
+y
λj r,j −λj r,j
x,y=0
ii
2qr hhm1
2nr qr

=

If m1 equals 0 then m2 does not belong to 0( mod τr,j ), τr,j ≥ 7, 0 < |m2 | ≤ Ar,j < τr,j ,
and
Tr,j (0, m2 ) = 0.
Let |m1 | > 0. Let us show that the expression under hhii sign above has absolute
value less than 1/2. Since r ≥ ℓj , by Lemma 2,
nr+1 logλj 2

n

λj r+1,j ≤ λj

r

= 2nr+1 = 2nr 22 ,

logλj 2 = 2− log2 log2 λj < 2ℓj −3 < 2r−3 ,
q
√
Ar,j = ⌊ τ r,j ⌋ < 2r+1 logλj 2 < 2r−1 .
Hence,
n

|m1 (λj r,j

+x

n

− λj r,j

+y

n

r

)| < 2Ar,j λj r+1,j < 2r 2nr 22 = (1/2)2nr qr ,

and we can replace hhii by the absolute value sign:
X
2nr
2
.
Tr,j
(m1 , m2 ) ≤ τr,j + 2
nr,j
2|m1 |λj (λxj − λyj )
τ >x>y≥0
r,j

Using the definition of nr,j ,
n

λj r,j

+1

nr logλj 2

≥ λj

= 2nr ,

LEVIN’S CONSTRUCTION OF ABSOLUTELY NORMAL NUMBERS

7

whence,
2
Tr,j
(m1 , m2 ) ≤ τr,j +

< τr,j +
= τr,j +

1

X

λy λx−y−1 (1
τr,j >x>y≥0 j j
∞
X

− λjy−x )

1
y z
(1
− λ−1
λ
λ
j )
y,z=0 j j
 λ 3
j

λj − 1
 λ 3
j
< 4τr,j
.
λj − 1


Lemma 4 (Lemma 2 in [18]). Let r ≥ ℓ1 . There exists an integer ar in [0, qr ) such
that, given any positive integer j and with the condition r ≥ ℓj , we have
 λ 3/2 √
2
j
Dr,j (ar ) < 2
τr,j 3 + ln τr,j ω(r).
λj − 1
Proof. Using the Cauchy-Bunyakovskii-Schwarz inequality we obtain,
qr −1
1 X
Dr,j (c) =
qr c=0

Ar,j

X

′

m1 ,m2 =−Ar,j
Ar,j

≤

X

′

m1 ,m2 =−Ar,j

qX
r −1
1
|Sr,j (m1 , m2 , c)|
m1 m2 qr c=0
qr −1
1/2
1 1 X
|Sr,j (m1 , m2 )|2
.
m1 m2 qr c=0

Since the conditions of Lemma 3 are satisfied, we have
qr −1
 λ 3/2 √
1 X
j
τr,j (3 + 2 ln Ar,j )2
Dr,j (c) < 2
qr c=0
λj − 1
 λ 3/2 √
j
≤2
τr,j (3 + ln τr,j )2 .
λj − 1

Consequently, with r ≥ ℓj , the number of integers c in [0, qr ) such that
 λ 3/2 √
j
Dr,j (c) ≥ 2ω(r)
τr,j (3 + ln τr,j )2
λj − 1
is less than qr /ω(r). By the definitions of ω(r) and ℓj , conditions r ≥ ℓj and
ω(r) ≥ j are equivalent. In this case, the number of integers c in [0, qr ), such that the
above inequality holds for at least one positive integer j, with the condition r ≥ ℓj
(alternatively, j ∈ [1, ω(r)]) is less than ω(r)⌊qr /ω(r)⌋ = qr . Consequently, there
exists an integer c = ar in [0, qr ), such that the inequality in the statement of this
lemma holds for all positive j with the condition r ≥ ℓj .

For the proof of Theorem 1 Levin uses multidimensional discrepancy and applies
Koksma’s inequality [14].
Let s be a positive integer, let γv , for v = 1, . . . , s, be real numbers in the
unit interval, let (βx,v )x≥0 for v = 1, . . . , s be a set of real number sequences, and

8

NICOLÁS ALVAREZ AND VERÓNICA BECHER

let Nv (P ) be the number of solutions for x = 0, 1, . . . , P − 1, of the system of
inequalities
{βx,1 } <

γ1

{βx,2 } <
..
.
{βx,s } <

γ2

γs .

The quantity
D(P, ({βx,1 }, . . . , {βx,s })x≥0 ) =

sup
γ1 ,...,γs ∈(0,1]s

Nv (P )
− γ1 · ·γs
P

is called the discrepancy of the sequences {βx,1 }, . . . , {βx,s }, for x = 0 . . . , P − 1.
Lemma 5 (Koksma [14]). Let s be a positive integer, let γv , for v = 1, . . . , s, be real
numbers in the unit interval, let (βx,v )x≥0 for v = 1, . . . , s be a set of real number
sequences. Let P be a positive integer. Then, for every integer n,
 

PP −1 
Ps
n
e
2πi
m
β
X
v
x,v
x=0
v=1
′
1
1
.
D(P, ({βx,1 }, . . . , {βx,s })x≥0 ) ≤ 30s  +
n P m ...m =−n
m1 . . . ms
1

s

We can now present Levin’s proof of Theorem 1 [18].
Remark. In the next proof we write nℓj ,j where Levin wrote nℓj .
Proof of Theorem 1. For any three real numbers ξ, λ, γ and non-negative integers
Q and P , we denote by Nξ,λ,γ (Q, P ) the number of solutions of the inequality
{ξλx } < γ,

for x = Q, . . . , Q + P − 1.

We write Nξ,λ,γ (P ), to denote Nξ,λ,γ (0, P ).
Fix any positive integer j and any positive real γ in the unit interval. Fix any
positive integer P and define an integer k from the condition nk,j ≤ P < nk+1,j .
Then,
P = nk,j + R1 , where 0 ≤ R1 < τk,j .
Observe that when P is large enough, k ≥ ℓj . Using the definition of Nα,λj ,γ ,
Nα,λj ,γ (P ) = Nα,λj ,γ (nℓj ,j ) +

k
X

′
Nα,λj ,γ (nr,j , τr,j
),

r=ℓj
′
′
where τr,j
= τr,j for r ∈ [ℓj , k) and τk,j
= R1 . Let us estimate Nα,λj ,γ (nr,j , R) for
r ≥ ℓj and 0 ≤ R ≤ τr,j . The quantity Nα,λj ,γ (nr,j , R) is equal to the number of
solutions of the system of inequalities


x
R
<
,
τr,j
τr,j
n

{αλj r,j

+x

} < γ,

LEVIN’S CONSTRUCTION OF ABSOLUTELY NORMAL NUMBERS

9

for x = 0, . . . , τr,j − 1. We apply Lemma 5 with s = 2, P = τr,j and n = Ar,j and
obtain
R
Nα,λj ,γ (nr,j , R) − γ
τr,j ≤
τr,j

Ar,j
X ′
1
τr,j
+
302 
Ar,j
m1 m2
m1 ,m2 =−Ar,j

τr,j −1

X

x=0



 
m2 x
n +x
.
e 2πi m1 αλj r,j +
τr,j

Using the definition of αr , for any r ≥ ℓ1 ,
α = αr +

ar
θr
+ nr+1 ,
2nr qr
2

where 0 ≤ θr ≤ 2, because
θr
2nr+1

=

∞
X

k=r+1

∞
∞
X
X
2
1
1
ak
1
<
≤ nr+1 .
= nr+1
2nk qk
2nk
2
2nk −nr+1
2
k=r+1

k=r+1

Ar,j

X′

Now, using the definition of Dr,j (ar ) =

m1 ,m2 =−Ar,j

Nα,λj ,γ (nr,j , R) − γR ≤

τr,j
+ Dr,j (ar ) +
302 
Ar,j


1
|U (m1 , m2 , ar )|
m1 m2

Ar,j

X

|Sr,j (m1 , m2 , ar )|
we obtain,
m1 m2

′

m1 ,m2 =−Ar,j

where
τr,j −1

|U (m1 , m2 , ar )| = Sr,j (m1 , m2 , ar ) −

X

x=0

 
m2 x 
n +x
.
e 2πi m1 αλj r,j +
τr,j

By the definition of Sr,j (m1 , m2 , ar ), the condition 0 ≤ θr ≤ 2, and the fact that
for every pair of reals ξ1 and ξ2 ,
|e(2πiξ1 ) − e(2πiξ2 )| = 2| sin(π(ξ1 − ξ2 )))| ≤ 2π|ξ1 − ξ2 |,
we find that
τr,j −1

|U (m1 , m2 , ar )| ≤ 2π

X

x=0

n

|m1 |λj r,j
n

≤ 4π|m1 |λj r+1
≤

4π|m1 |
.
λj − 1

,j

+x

θr
n
2 r+1

1
(λj − 1)2nr+1

10

NICOLÁS ALVAREZ AND VERÓNICA BECHER

√

τr,j , the upper bound for Dr,j (ar ) given in Lemma 4 for
X ′ Ar,j
1
≤ (3 + ln τr,j )2 , we obtain,
r ≥ ℓj , and the inequality
m1 ,m2 =−Ar,j
m1 m2

Then, using that Ar,j ≤

|Nα,λj ,γ (nr,j , R) − γR|


 λ 3/2 √
4π √
√
j
2
2
2
≤ 30 2 τr,j + 2
τr,j (3 + ln τr,j ) ω(r) +
τr,j (3 + ln τr,j )
λj − 1
λj − 1
 λ 3/2 √
j
≤ 302 15
τr,j (3 + ln τr,j )2 ω(r).
λj − 1

For k ≥ ℓj ,

Nα,λj ,γ (P ) = Nα,λj ,γ (nℓj ,j ) +

k
X

′
Nα,λj ,γ (nr,j , τr,j
),

r=ℓj

and
P = nk,j + R1 , where 0 ≤ R1 < τk,j .
So, we have
|Nα,λj ,γ (P )−γP | ≤ |Nα,λj ,γ (nℓj ,j )−γnℓj ,j |+

k
X

r=ℓj

302 15

 λ 3/2 √
j
τr,j (3+ln τr,j )2 ω(r).
λj − 1

and
1
τk,j .
4
It follows from Lemma 2 that
k q
k
q
X
X
√
√
τr,j ≤
2r+1 logλj 2 ≤ 3 2k+2 logλj 2 ≤ 10 τk,j .
P ≥ τk−1,j ≥

r=ℓj

r=ℓj

Let us show that, for k ≥ ℓj ,
ω(P ) ≥ ω(k).
Since ω(r) is a non-decreasing sequence, it is sufficient to show that, for k ≥ ℓj ,
P ≥ k.
In fact, using the definitions of ℓj and nk,j , and P = nk,j + R1 ,
k ≥ ℓj ≥ 5,

2

k+1
2

≥ k + 1 for k ≥ 5,

and
P − k ≥ nk,j − k

≥ (2k − 2) logλj 2 − k − 1

≥ (logλj 2)(2k−1 − (k + 1) log2 λj )
≥ (logλj 2)(2k−1 − (k + 1)2

≥2

k−3
2

≥ 0.

(logλj 2)(2

k+1
2

ℓj −3
2

− k − 1)

)

LEVIN’S CONSTRUCTION OF ABSOLUTELY NORMAL NUMBERS

11

Using the inequalities above and the obvious inequality |Nα,λj γ (nℓj ,j )−γnℓj ,j | ≤ nℓj ,j ,
we have
 λ 3/2 √
j
P (5 + ln P )2 ω(P ).
|Nα,λj ,γ (P ) − γP | ≤ nℓj ,j + 4 105
λj − 1

The above inequality also holds for k ≤ ℓj − 1, since
|Nα,λj γ (P ) − γP | ≤ P < nk+1,j ≤ nℓj ,j .

Recalling the definition of nℓj ,j we finally obtain
 λ 3/2 √
j
P (5 + ln P )2 ω(P ).
|Nα,λj ,γ (P ) − γP | ≤ 2ℓj logλj 2 + 4 105
λj − 1

Thus, the discrepancy of the sequence {αλxj }x≥0 , for any given positive integer P ,
 (log P )2

Nα,λj ,γ (P )
√
D(P, {αλxj }x≥0 ) = sup
− γ is in O
ω(P ) .
P
P
γ∈(0,1]

Corollary 6 ([18]). Let λj = j + 1, tj = 2j for j = 1, 2, . . ., so ℓj ≤ 2j+1 + 1 and
ω(P ) ≤ 2(5+ln P ). Then, the constructed number α is absolutely normal in Borel’s
sense, and for any integer j ≥ 2, the discrepancy of {αj x }, for x = 0, . . . , P − 1 is
D(P, {αj x }x≥0 ) ≤
which is in O

(5 + ln P )3
22j+1
√
logj 2 + 3 106
,
P
P

 (log P )3 
√
.
P

Levin asserts that a similar method can be used for constructing a number α
P −1
such that, given any integer j, the discrepancy of the sequence {αλxj }x=0
, is
 (log P )3/2

√
O
ω(P ) , where the constant in the order symbol O depends on λj ,
P
and he gives as reference Section 2 of [17].
3. About Levin’s construction and its possible variants
3.1. Possible variants on the construction. Here we consider other possible
values for nr and qr to run Levin’s construction. This is interesting because smaller
values of nr imply a faster computation at step r, due to the fact that ar is searched
in a smaller range. However, smaller values of nr imply a larger discrepancy of the
sequence {λxj α}x≥0 .
The next Lemma 7 gives a sufficient condition for nr and qr to ensure that the
construction works. Then, Lemma 8 gives a sufficient condition on nr to ensure
that the construction yields an absolutely normal number: the value nr must be
polynomial in r, with degree greater than 1.
Lemma 7. If λj ≥ 2 and the sequences n1 , n2 , . . . and q1 , q2 , . . . satisfy for every
positive r,
1

2nr+1 −nr +1+ 2 log(nr+1 −nr +1) ≤ qr
then the statement of Lemma 3 holds.

12

NICOLÁS ALVAREZ AND VERÓNICA BECHER

Proof. In Lemma 3, every step of the proof is valid disregarding the values chosen
for n1 , n2 , . . . and q1 , q2 , . . . except for the statement
1
n +x
n +y
|m1 |(λj r,j − λj r,j ) ≤ 2nr qr .
2
We show that the condition given by this lemma is sufficient to make the above inequality true. Let us recall that nr,j = ⌊nr logλj 2⌋, τr,j = nr+1,j −nr,j , 0 ≤ x, y < τr,j
√
and |m1 | ≤ Ar,j = ⌊ τr,j ⌋. Then,
qr

1

=

2nr+1 −nr +1+ 2 log2 (nr+1 −nr +1)
p
nr+1 − nr + 1 2nr+1 −nr +1
q
(nr+1 logλj 2 − nr logλj 2) + 1 2nr+1 −nr +1
p
nr+1,j − nr,j 2nr+1 −nr +1
√
τr,j 2nr+1 −nr +1

≥

|m1 |2nr+1 −nr +1

≥

=

≥
≥

=

2|m1 |2nr+1 2−nr

−(nr,j +1)

n

>

2|m1 |λj r+1,j λj

=

2|m1 |λj r+1,j

=

2|m1 |λj r,j

>

2|m1 |(λj r,j

≥
≥
=

n

τ

−1

τ

n
λj r,j
2|m1 | nr
2
n
λj r,j
2|m1 | nr
2

2
2nr,j

−nr,j −1

−1

− 1)

τ

(λj r,j

−1

− 1)

(λxj − λyj )
n

|m1 |(λj r,j

+x

n

− λj r,j

+y

).


In what follows we use customary asymptotic notation to describe the growth
rate of the functions. We write,
f (n) is in Θ(g(n)) if ∃k1 > 0 ∃k2 > 0 ∃n0 ∀n > n0 , k1 g(n) ≤ f (n) ≤ k2 g(n),
f (n) is in o(g(n)) if ∀k > 0 ∃n0 ∀n > n0 ,
|f (n)| ≤ k|g(n)|.
Lemma 8. Let j and P be positive integers and let k be such that nk,j ≤ P < nk+1,j .
k


X
p
P
If
nr+1,j − nr,j is in o
then Levin’s construction yields an
(log P )2 ω(P )
r=1
absolutely normal number.
Proof. See proof of Theorem 1 for the upper bound of |Nα,λj ,γ (P ) − γP |.



The next proposition shows that if nr dominates any linear function on r, and
qr is increasing in r according to a condition in the the growth of nr , then Levin’s
construction yields an absolutely normal number,
Proposition 9. Let (λj )j≥1 be a sequence or real numbers greater than 1 and
let (tj )j≥1 be a sequence of reals such that the function ω(P ) has sub-polynomial

LEVIN’S CONSTRUCTION OF ABSOLUTELY NORMAL NUMBERS

13

growth. If nr is any polynomial on r with degree greater than 1, and qr is such
that
nr+1 − nr + 1 +

1
log(nr+1 − nr + 1) ≤ log qr ,
2

then Levin’s construction yields an absolutely normal number. However, if nr is
linear in r, Levin’s arguments do not prove that the discrepancy goes to 0.
Proof. Suppose nr is polynomial on r. Then, there is some h such that nr in Θ(rh ).
By definition of nr,j , we have nr,j = ⌊nr logλj 2⌋ is in Θ(rh ). Hence, nr+1,j − nr,j
p
h−1
is in Θ(rh−1 ); therefore, nr+1,j − nr,j in Θ(r 2 ). Furthermore, if P and k are
√
h
such that nk,j ≤ P < nk+1,j , then k is in Θ( P ). Thus,
k
 √  h+1 
X
p
h+1 
h
= Θ P 2h .
nr+1,j − nr,j is in Θ
P 2
r=1

If nr were a linear function on r,
k
X
p
nr+1,j − nr,j is in Θ(P ),
r=1

k

X
p
nr+1,j − nr,j would not be in the required class o


P
. We
2
(log P ) ω(P )
r=1
conclude that, to obtain a normal number with Levin’s construction, nr can not
be linear in r. Instead, nr can be any polynomial on r with degree greater than 1
provided that ω(P ) is chosen to have sub-polynomial growth.

hence

In Levin’s construction smaller values of nr imply a larger upper bound on
discrepancy of the sequence {αλx }. The following table shows the bound for the
discrepancy of the sequence {λxj α}P
x=0 , obtained using Levin’s proof for different
choices of nr . In each case the constant behind the O symbol depends on λj .
nr

Discrepancy bound given by Levin’s proof

r

O(log(P )2 ω(P )) —it does not go to 0 when P goes to ∞—

rh

O

 log(P )2 ω(P ) 
P

h−1
2h

 log(P )2 ω(P ) 
√
P
In all these cases, the upper bound for discrepancy contains ω(P ), as in Levin’s
formulation and the constant hidden in the O symbol depends on the base λj .
Although Levin states that for any nondecreasing function ω(P ) his construction
produces an absolutely normal real number,√the growth of ω(P ) cannot be arbitrary.
For example, when nr is 2r − 2, ω(P ) = P does not give a discrepancy bound
going to 0.
2r − 2 O

14

NICOLÁS ALVAREZ AND VERÓNICA BECHER

3.2. Necessary conditions on the construction. Levin’s construction is not
conceived as the concatenation of the binary expansions of the ar for r = 1, 2, . . ..
This means that the expansion in base 2 of αr+1 is not obtained as a concatenation
of the expansion of αr with the base-2 representation of ar . Recall the definition
of αr+1 : αℓ1 is equal to a starting real number a (argument for the construction)
and for every r ≥ ℓ1 ,
αr+1 = αℓ1 +

r
X

m=ℓ1

am
,
2nm qm

where am is an integer in [0, qm ) satisfying the conditions of Lemma 4,
m

nm = 2m − 2 and qm = 22

+m+1

.

Since log qr = 2r + r + 1 > nr+1 − nr = 2r we have
αr+1 − ⌊2nr+1 αr+1 ⌋2−nr+1 > 0.

The next Lemma 10 shows that if qr is unbounded, then it is necessary for Levin’s
proof that qr > 2nr+1 −nr . This condition is implied by the sufficient condition on
nr and qr we identified in Lemma 7.
Then, Lemma 11 proves that if qr id bounded then Levin’s construction does
not yield an absolutely normal number.
Lemma 10. If qr is unbounded then it is necessary that qr > 2nr+1 −nr .
1
n +x
n +y
Proof. For Lemma 3 to hold, we need that |m1 |(λj r,j − λj r,j ) ≤ 2nr qr . In
2
particular, when m1 = Ar,j , x = τr,j − 1, y = 0 and λj = 2, we need that the
following inequality holds:
Ar,j (2nr+1 −1 − 2nr ) ≤

1 nr
2 qr .
2

Equivalently,
Ar,j (2nr+1 −nr − 2) ≤ qr .
Now suppose that, qr is unbounded, non-decreasing in r but, contrary to the
statement of the Lemma, qr ≤ 2nr+1 −nr . So, the above condition becomes
qr
Ar,j ≤
.
(qr − 2)

Since qr is unbounded, there is r0 such that for every r ≥ r0 , qr ≥ 1000, and each
of the following inequalities should hold.
1000
qr
≤
<2
qr − 2
998
p
= ⌊ nr+1 − nr ⌋ <2
p
nr+1 − nr <3
nr+1 − nr <9

Ar,j ≤
Ar,j

2nr+1 −nr <512.

Then, using the assumption qr ≤ 2nr+1 −nr , we conclude qr < 512, contradicting
that qr ≥ 1000.


LEVIN’S CONSTRUCTION OF ABSOLUTELY NORMAL NUMBERS

15

The following lemma shows that if qr is bounded by a constant, then Levin’s
construction yields a number α which might not be absolutely normal.
Lemma 11. If qr is bounded by a constant and log qr ≤ nr+1 − nr then Levin’s
construction does not ensure absolute normality.
Proof. For ease of presentation assume the argument a in Levin’s construction is a
non-negative rational number of the form r + p/2ℓ1 for some non-negative integers
r and p with p less than ℓ1 . So, the expansion of a in base 2 has at most 2ℓ1
significant digits. The case where a is not of this form can be proved similarly.
Suppose that qr is bounded, then log2 qr will be bounded too. That is, there is a
constant C such that for all r, log2 qr ≤ C. Since ar is in [0, qr ), at step r, the choice
of ar requires at most C binary digits. Suppose also that log2 qr ≤ nr+1 − nr , which
ar
implies that the fractions nr have binary expansions that not overlap. Therefore,
2 qr
the first nr bits of α will be correctly computed on the r-th step of the construction,
that is the first nr bits of α will coincide with those of αr .
Let 0.b0 b1 b2 . . . be the binary expansion of α and let count(α, n, b) be the number
of bits equal to b within b0 , b1 , . . . , bn−1 . Assuming α is absolutely normal, it must
1
count(α, n, b)
= for b in {0, 1}. Using
be simply normal in base 2. Therefore lim
n→∞
n
2
the definition of limit, for all positive ǫ, for every sufficiently large r,
C(r − 1)
count(α, nr , 1)
1
≤
.
−ǫ<
2
nr
nr
So,
Cr − C
nr < 1
.
2 −ǫ
Since this holds all positive ǫ, we conclude
nr in O(r).
On the other hand, we can safely assume that log2 qr ≥ 1 because at least 1 bit
should be computed on each step of the algorithm. Given that nr+1 −nr ≥ log2 qr ≥ 1
we obtain that nr must be in Θ(r). As we stated on Proposition 9, a linear growth
of nr does not ensure that discrepancy goes to 0. So we cannot ensure absolute
normality of the generated number α.

More importantly, this necessary condition on nr and qr determines that Levin’s
construction of the number α is not doable as a concatenation of the ar , for
r = 1, 2, . . ..
Proposition 12. If qr and nr are such that log qr > nr+1 − nr then Levin’s
construction of α is not doable as the concatenation of the ar , for r = 1, 2, 3 . . ..
Proof. To run the construction as a concatenation of the ar , for r = 1, 2, 3, . . ., we
need that
r−1
X
log qm ≤ nr .
m=0

But
r−1
X

m=0

log qm >

r−1
X

m=0

nm+1 − nm = nr − n0 = nr .

16

NICOLÁS ALVAREZ AND VERÓNICA BECHER


4. Levin’s normal numbers are computable
The theory of computability defines a computable function from non-negative
integers to non-negative integers as one which can be effectively calculated by some
algorithm. The definition extends to functions from one countable set to another,
by fixing enumerations of those sets. A real number x is computable if there is a base
and a computable function that gives the digit at each position of the expansion of
x in that base. Equivalently, a real number is computable if there is a computable
sequence of rational numbers (rn )n≥0 such that |x − rn | < 2−n for each n ≥ 0.
Theorem 13 (Turing [11, Theorem 5.1.2]). The following are equivalent:
(1) The real x is computable.
(2) There is a computable sequence of rationals (rn )n≥0 that tends to x such
that |x − rn | < 2−n for all n.
(3) There is a computable sequence of rationals (rn )n≥0 that converges to x and
a computable function f : N → N such that |x − rf (n) | < 2−n for all n.
Theorem 14. Let (λj )j≥1 be computable sequence of integers greater than 2 let
(tj )j≥1 be a computable sequence of integers monotonically increasing at any speed
and let the starting value a be a rational number, Then, the number α defined by
Levin, proved to be absolutely normal in Theorem 1, is computable.
Proof. The number α is the limit of αr for r going to infinity, where aℓ1 = a with
ℓ1 = max(t1 , 2⌈| log2 log2 λ1 |⌉ + 5), and for r ≥ 1,
ar
αr+1 = αr + nr ,
2 qr
where ar is an integer in [0, qr ) satisfying the inequalities of Lemma 4, nr = 2r − 2
r
and qr = 22 +r+1 . Lemma 4 proves that such ar exists. Since Dr,j (c) is a
computable function it is possible to find ar by an exhaustive search among all
integers in [0, qr ) and all bases λj for j = 1, 2, . . . , ω(r), where ω(r) = 1 if r
in [1, ℓ2 )), otherwise ω(r) is the unique index k such that r in [ℓk , ℓk+1 ), with
ℓk = max(tk , max 2⌈| log2 log2 λv |⌉ + 5). At each step r, we can compute bitwise
1≤v≤k

approximations of Dr,j from above, for each of the possible candidate values of
ar until we find one that satisfies the requires inequality for all j between 1 and
ω(r). Thus, the sequence of rationals α1 , α2 , . . . is computable and converges to
an absolutely normal number α. From the proof of Theorem 1 we know that, for
each r,

2
.
2nr
Since α is an absolutely normal number, and therefore an irrational number, by
Theorem 13 we conclude that α is computable.

|α − αr | <

5. The computational complexity of Levin’s construction
Theorem 14 proves that under some assumptions of the sequences (λj )j≥1 and
(tj )j≥1 , and the starting value a, Levin’s construction is indeed an algorithm to
compute the number α. The algorithm is recursive.

LEVIN’S CONSTRUCTION OF ABSOLUTELY NORMAL NUMBERS

17

The standard computational model is the Turing machine model, which works
just with finite representations, so it only deals with numbers that are the limit
of a computable sequence of finite approximations. In this model, at step r, the
number of elementary operations needed to find out the number ar can not be easily
determined. This is because to find out ar the algorithm must compute sums of
exponential sums. The terms in these sums are transcendental numbers, which can
only be computed as limits of finite approximations. It is impossible to determine
how many approximations to each term of the exponential sums must be computed
to find out that a candidate ar is conclusive.
So, instead of counting the number of elementary operations needed to compute
the number ar at step r, here we give the number of mathematical operations needed
in an idealized computational model over the real numbers, based on machines with
infinite-precision real numbers. A canonical model for this form of computation
over the reals is Blum-Shub-Smale machine [7], abbreviated BSS machine. This is
a machine with registers that can store arbitrary real numbers and can compute
rational functions over reals at unit cost. Since elementary trascendental functions,
as exponential function or trigonometric functions, are not computable by a BSS
machine we need to consider the extended BSS machine which includes exponential
and trigonometric functions as primitive operations. For our purpose, the extended
BSS model is identical to considering Boolean arithmetic circuits augmented with
trigonometric functions.
Of course, for any given real valued function, its complexity in the BSS model
gives just a lower bound of its complexity in the classical Turing machine model,
where the cost for arithmetic (and trigonometric) operations over the real numbers
is not constant.
Theorem 15. Let (λj )j≥1 be a computable sequence of reals greater than 1 and let
(tj )j≥1 be a computable sequence of integers. Levin’s algorithm requires
ω(r)

 r
X
(logλj 2)2
O 22 +3r+1
j=1

mathematical operations to compute αr , for each r.
Proof. Assume a BSS machine which includes exponential and trigonometric functions as primitive operations. The expression Sr,j (m1 , m2 , c) is the sum of τr,j
terms, each of them can be computed in constant time in our machine. Hence the
time needed to compute each value of Sr,j is in O(τr,j ).
To obtain a value of Dr,j we must calculate O(Ar,j 2 ) = O(τr,j ) values of Sr,j .
Therefore, the computation of Dr,j is in O(τr,j 2 ) = O((2r logλj 2)2 ).
Finding the value of ar requires to compute Dr,j (c) for each j between 1 and
ω(r) until we find a value of c in [0, qr ) which satisfies the inequalities of Lemma 4.
In the worst case, it will be necessary to try all possible values for c. In this worst
case, the required time is in
O

r −1 ω(r)
 qX
X

c=0 j=1

ω(r)


 r

 ω(r)
X
X
(logλj 2)2 .
(2r logλj 2)2 = O 22 +3r+1
(2r logλj 2)2 = O qr
j=1

j=1

18

NICOLÁS ALVAREZ AND VERÓNICA BECHER

Let Ck be the time required to compute ak ,
ω(k)

Ck = 2

2k +3k+1

X

(logλj 2)2

j=1

Then, the time to compute αr is

r
X

Ck . We now show that the time needed to

k=1

compute αr is essentially the time spent on the search of ar . We need to show that
r
X
Ck is in O(Cr ), because
k=1

r−1
X

k=1

ω(r−1)
r−1

Ck ≤ (r − 1)Cr−1 = (r − 1)22

+3(r−1)+1

X

(logλj 2)2

j=1

ω(r)


 r
X
(logλj 2)2 .
which is in O 22 +3r+1



j=1

Notice that Theorem 15 estimates the complexity of obtaining a rational approximation αr with an error bounded by 2−(nr+1 −1) . Since αr is just an approximation
to α, it is not determined how many bits in the expansion of αr are conclusive so
as to conform the expansion of α. One would like that the first nr+1 − 1 bits of αr
determine those of α. As we showed in Proposition 12 Levin’s construction is not
ar
doable as the concatenation of the values ar . An overlapping of the fractions nr
2 qr
may occur, causing carries and changing some of the first bits of αr .
Theorem 15 proves that the complexity of computing αr with Levin’s original
formulation for nr and qr , is double exponential in r. Since nr is the number of bits
of αr that are obtained at step r, and in Levin’s original formulation nr is 2r − 2,
it is fair to say that the complexity of Levin’s algorithm is simply exponential in
the number of bits computed at step r.
We now prove that, in case nr is quadratic in r, then Levin’s algorithm requires
a number of operations that is is simply exponential in the square root of number
of bits computed at step r.
Theorem 16. The alternative of Levin’s construction with nr = r2 takes
ω(r)
3 2r

O r 2

X

(logλj 2)2

j=1



mathematical operations in an extended BSS machine to compute αr .
Proof. First, we need to choose values for qr that ensure normality. As we showed
1
in Lemma 7, 2nr+1 −nr +1+ 2 log(nr+1 −nr +1) ≤ qr is a sufficient condition. We choose
qr = 22r+2+⌈log(2r+2)⌉ . By Theorem 15, to find ar , in the worst case it is necessary
to compute Dr,j (c) for each j between 1 and ω(r) and for each c between 0 and
2
qr − 1 and each Dr,j requires O(τr,j
) operations. Then, the number of operations
ω(r)
X
2
τr,j
), because
to find ar is in O(qr
j=1

2r

qr is in O(r2 ),

LEVIN’S CONSTRUCTION OF ABSOLUTELY NORMAL NUMBERS

19

τr,j is in O(r logλj 2), and
ω(r)



 ω(r)
X
X
2
(logλj 2)2 .
τr,j
= O r3 22r
O qr
j=1

j=1

The time to compute αr is essentially the time required to find ar because
r
X

k=1

ω(r)

ω(k)
3 2k

k 2

X
j=1

2

3 2r+2

(logλj 2) ≤ r 2

X

(logλj 2)2

j=1

ω(r)



X
(logλj 2)2 .
which is in O r3 22r



j=1

Acknowledgements. The authors are grateful to Igor Shparlinski for suggesting
us in 2013 (email communication) to determine the computational complexity
of Levin’s constructions of absolutely normal numbers and he explicitely asked
whether the delivery of digits was in polynomial time. The two authors are members of the Laboratoire International Associé INFINIS, CONICET/Universidad de
Buenos AiresCNRS/Université Paris Diderot.
References
[1] V. Becher, Y. Bugeaud, and T. Slaman. On simply normal numbers to different bases.
Mathematische Annalen, page in press, 2015. http://dx.doi.org/10.1007/s00208-015-1209-9.
[2] V. Becher and S. Figueira. An example of a computable absolutely normal number.
Theoretical Computer Science, 270:947–958, 2002.
[3] V. Becher, S. Figueira, and R. Picchi. Turing’s unpublished algorithm for normal numbers.
Theoretical Computer Science, 377:126–138, 2007.
[4] V. Becher, P.A. Heiber, and T. Slaman. A polynomial-time algorithm for computing
absolutely normal numbers. Information and Computation, 232:1–9, 2013.
[5] V. Becher, P.A. Heiber, and T. Slaman. A computable absolutely normal Liouville number.
Mathematics of Computation, 84(294), 2015.
[6] V. Becher and T. Slaman. On the normality of numbers to different bases. Journal of the
London Mathematical Society, 90(2):472–494, 2014.
[7] Lenore Blum, Mike Shub, and Steve Smale. On a theory of computation and complexity over
the real numbers: NP- completeness, recursive functions and universal machines. Bull. Amer.
Math. Soc. (N.S.), 21(1):1–46, 07 1989.
[8] É. Borel. Les probabilités d’enombrables et leurs applications arithmétiques. Supplemento di
Rendiconti del Circolo Matematico di Palermo, 27:247–271, 1909.
[9] Yann Bugeaud. Distribution Modulo One and Diophantine Approximation. Number 193 in
Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, UK, 2012.
[10] D. Champernowne. The construction of decimals normal in the scale of ten. J. London Math.
Soc., s1-8(4):254–260, 1933.
[11] Rodney Downey and Denis Hirschfeldt. Algorithmic Randomness and Complexity. Springer,
2010.
[12] M. Drmota and R. Tichy. Sequences, Discrepancies and Applications. Lecture Notes in
Mathematics, Vol. 1651. Springer-Verlag, 1997.
[13] I. S. Gal and L. Gal. The discrepancy of the sequence (2n x). Indag. Math., 26:129–143, 1964.
[14] J.F.Koksma. Some theorems on Diophantine inequalities. Math. Cent. Amsterdam Scriptum,
5, 1950.
[15] L. Kuipers and H. Niederreiter. Uniform distribution of sequences. Dover Publications, Inc.,
New York, 2006.
[16] H. Lebesgue. Sur certains démonstrations d’ existence. Bulletin de la Société Mathématique
de France, 45:127–132, 1917.

20

NICOLÁS ALVAREZ AND VERÓNICA BECHER

[17] M. B. Levin. On uniform distribution of the sequence {αλx }. Matem Sb. (N.S.), 98(140):207–
222, 1975. Translation: Math. USSR-Sb. 27(2): 183–197, (1975).
[18] M. B. Levin. On absoluteley normal numbers. Vestnik Moscov. Univ. ser. I, Mat-Meh, 1:31–
37, 87, 1979. English translation in Moscow Univ. Math. Bull., 34 (1979), no. 1, 32-39.
[19] M. B. Levin. On the discrepancy estimate of normal numbers absoluteley normal numbers.
Acta Arithmetica Warzawa, 88:99–111, 1999.
[20] Manfred Madritsch and Robert Tichy. Dynamical systems and uniform distribution of
sequences. arXiv:1501.07411v1, 2015.
[21] J. Schiffer. Discrepancy of normal numbers. Acta Arith., 47:175–186, 1986.
[22] W. M. Schmidt. Über die Normalität von Zahlen zu verschiedenen Basen. Acta Arithmetica,
7:299–309, 1961/1962.
[23] W. Sierpiński. Démonstration élémentaire du théorème de M. Borel sur les nombres
absolument normaux et détermination effective d’un tel nombre. Bulletin de la Société
Mathématique de France, 45:132–144, 1917.
[24] Alan Turing. A note on normal numbers. In J.L.Britton, editor, Collected Works of A.M.
Turing: Pure Mathematics, pages 117–119. North Holland, Amsterdam, 1992. with notes of
the editor in 263–265.
Departamento de Ciencias e Ingenierı́a de la Computación, Universidad Nacional del
Sur, Argentina
E-mail address: naa@cs.uns.edu.ar
Departmento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires & CONICET, Argentina
E-mail address: vbecher@dc.uba.ar

