An introduction to normal numbers

A thesis submitted towards partial fulfillment of BS-MS Dual Degree Programme

by

Rajesh Kumar Yadav under the guidance of

Dr. Ravindranathan Thangadurai (Reader F in Mathematics, HRI Allahabad)

Local Supervisor Dr. Anupam Kumar Singh

(Asst. Professor in Mathematics, IISER Pune)

Department of Mathematics

Indian Institute of Science Education and Research Pune

Certificate

This is to certify that this dissertation entitled “An Introduction to Normal Numbers” towards the partial fulfillment of the BS-MS Dual Degree at Indian Institute of Science Education and Research Pune, represents original research carried out by Rajesh Kumar Yadav at Harish Chandra Research Institute Allahabad under the supervision of Dr. Ravindranathan Thangadurai during the academic year 2010-2011.

Dated: April 2011

Signature of the Student:

Supervisor:

Dr. Ravindranathan Thangadurai

Head (Mathematics):

Local Supervisor:

Dr. Anupam Kumar Singh

ii

Table of Contents iv

Abstract vi

Acknowledgements vii

1 Introduction 1

2 b-ary expansion of a real number 3

3 Normal Numbers and some properties 10

3.1 Interesting Numbers . . . 10 3.2 Definition of Normality and some properties . . . 11 4 The first Borel-Cantelli lemma and Borel’s Theorem 28

5 Non-normal numbers are uncountable 32

5.1 Cantor diagonalisation technique . . . 32 6 Example of Normal and Non-normal numbers 35 6.1 Numbers Proven to be not Normal . . . 35 6.2 Numbers Proven to be Normal . . . 36 6.3 Numbers expected to be Normal . . . 40

7 Uniform distribution and Normal numbers 42

7.1 Uniform distribution in the unit interval . . . 42 7.2 Uniform distribution modulo 1 . . . 45

8 Normality in case of integers 53

8.1 Integer analogue of normality . . . 53 iv

8.2 Hanson’s construction of normal number . . . 54

9 Questions for further research 57

Bibliography 59

v

This study is about normality of real numbers. In this study we will mainly look at the expansion of real numbers to any integer base b(b ≥ 2) and depending on that we will introduce the concept of normality. We will look at frequency of digit strings in the expansion of any real number to an integer base and if all possible digit strings of length k are equally frequent for each k in the former expansion, then we say the number is normal to the base b. While it is generally believed that many familiar irrational constants and algebraic irrationals are normal, normality has been proven only for numbers which are purposefully invented to be normal. In this study we will see different criteria for proving normality and also give an overview of the main results till the date. We will also give the complete proof of Borel’s theorem i.e. Almost all real numbers are absolutely normal. Subsequently we will see some examples of normal numbers.

vi

Acknowledgements

I would like to thank Dr. R Thangadurai, my supervisor, for his many suggestions and constant support during this project.

I am also thankful to Dr. Anupam Kumar Singh for his support throughout the year as my local supervisor.

I thank Harish Chandra Research Institute Allahabad and the Institute of Mathe- matical Sciences Chennai for providing facilities and support to complete this project work. I would also like to thank my alma mater Indian Institute of Science Education and Research, Pune for providing me this opportunity even if it was a part of the curriculum.

Also, I would take this opportunity to extend my sincere regards to Bhavin Moriya, A. S. Arvind and Dr. Jagmohan Tanti. They were a constant support and provided a pleasant company, full of discussions during my stay at HRI Allahabad and IMSc Chennai.

I can’t be more grateful to my family and Almighty. But for their inspiring pres- ence in my life, this work would not have been possible.

At last, I am thankful to all my friends at IISER Pune for their painstaking efforts to sort out the official formalities for me, especially Navi Prasad (because he asked me to).

vii

Introduction

Emile Borel introduced the concept of normality in 1909 in a paper addressing the´ question of probability on a countably infinite sequence of trails[2]. Borel proved that almost all real numbers are normal in the sense that the set of real numbers which are not normal is of measure zero. If all possible digit strings of length k are equally frequent for each k in the decimal expansion of the number to the integral base b(b ≥ 2), then we say the number is normal to the base b. Below we will give precise definition of normality. Although many worked on normal numbers but there has been very little progress beyond Borel’s original work.

Progress has been limited to the discovery or rather the invention of new classes of normal numbers[1, 4, 16]. The very first of which was given by Champernowne and many people tried to give the proof of normality of this number but normality of this number has been proven only to the base 10. Also this number is proved to be transcendental. Below we will discuss about this number elaborately.

But nothing is known about the normality of algebraic irrational number nor of any well-known irrational constant. The only numbers known to be normal have been constructed purposefully for proving their normality. Some people have also tried to

1

2

discover ways of constructing new normal numbers.

Although experimental evidences strongly suggest that many, if not all familiar irra- tionals are indeed normal, for example people plotted first 10⁵ digits ofπ as a random walk and by looking at these plots people tried to predict the normality of π. But unless we have a rigorous proof of these type of predictions we can’t really say any- thing.

In this sense, this topic is completely open.

b-ary expansion of a real number

Let us define the b-ary expansion of a real number.

Definition 2.0.1. A positive b-ary expansion is a series of the form a₀ +a₁

b +a₂

b² +...+a_n bⁿ +...

denoted bya₀.a₁a₂...a_n...., whereb, a₀ ∈Z₊,b ≥2 anda_n∈ {0,1,2, ..., b−1}for each n∈N.

Theorem 2.0.1. Every positive b-ary expansion converges to a positive real number and we then say that the b-ary expansion represents the real number.

Proof. Consider the positiveb-ary form a₀.a₁a₂...a_n.... Now s₁ = a₀+a₁

b ≤a₀ +b−1 b s₂ = a₀+a₁

b + a₂ b²

≤ a₀+b−1

b + b−1 b²

. .

. .

3

4

By induction we have

sn ≤ a0 +b−1 b

µ 1 + 1

b +....+ 1 bⁿ⁻¹

¶

≤ a0 +b−1 b

µ 1 1−¹_b

¶

=a0+ 1

Then{s_n}is an increasing sequence of positive reals and is bounded above bya₀+ 1.

Hence {s_n} is convergent to a real number a ∈ R. (We then say a₀.a₁a₂...a_n....

representsa.)

Now we will prove some theorems aboutb-ary expansion of positive real numbers and the main idea behind the proofs is based on Nested Interval Theorem. So first let us prove this theorem and subsequently we shall proceed on the same line.

Theorem 2.0.2. (Nested Interval Theorem) Let Ik ⊂ R be finite intervals with endpoints ak and bk such that

• Ik+1 ⊂Ik for each k ∈N

• lim_k→∞l(I_k) =lim_k→∞b_k−a_k→0

Then there exists a unique c∈R such that a_k ≤c≤b_k for all k.

Proof. Consider the set A:={a_k :k ∈N}. This set is nonempty, bounded above by each of b_n. Hence by the least upper bound property of R, there exists c ∈ R such that c= supA. Then c≤b_n, since c is the least upper bound of A and eachb_n is an upper bound for A. Also, since c is an upper bound for A, a_n ≤ c for all n. Thus, a_n≤c≤b_n.

Now we will check the uniqueness of c. Ifd is also such that a_n ≤d≤b_n for eachn,

then,c, d∈[an, bn] for eachn. From this we conclude that|c−d| ≤bn−an for alln.

As bn−an→0, it follows that |c−d|= 0. Hence c=d and thusc is unique.

The main question here is how can we be sure that there is always a b-ary rep- resentation corresponding every positive real number. The next theorem will ensure that in fact we have a b-ary representation for every positive real number.

Theorem 2.0.3. Every positive real number has a positive b-ary representation.

Proof. Given a real number a ≥ 0, we construct a series as follows: Let a₀ be the greatest integer less than or equal to a. Let

a₁ be the greatest integer such that a₀+ ^a_b¹ ≤a < a₀+ 1 .

.

a_n be the greatest integer such that a₀+ a₁

b +...+a_n

bⁿ ≤a < a₀+a₁

b +...+a_n+ 1 bⁿ We claim that a₀.a₁a₂...a_n...represents a. For this we need to show that

1. a₀.a₁a₂...a_n...is a b-ary form, i.e., a_n ∈ {0,1, ..., b−1} for all n ∈N 2. a =a0+P_∞

n=1 an

bⁿ

1.Now a₀+ ^a_b¹ ≤ a. So a₁ ≥0. Also, ^a_b¹ ≤ a−a₀ <1, so a₁ < b or 0≤a₁ ≤b−1.

By induction, we find that 0≤a_n≤b−1.

We prove by induction that we can find integers a_n, 0≤a_n≤b−1 such that Xn−1

i=0

a_i bⁱ + a_n

bⁿ ≤a <

Xn−1

i=0

a_i

bⁱ +a_n+ 1 bⁿ

6

This integer is denoted byan.

Assume a1, ..., an−1 are chosen for n ≥1. Let an be the greatest integer k such that Xn−1

i=0

a_i bⁱ + k

bⁿ ≤a <

Xn−1

i=0

a_i

bⁱ +k+ 1 bⁿ

holds. Then a_n ≥ 0. Also a_n < b. For, otherwise, a_n ≥ b, so that we can write a_n=b+a_n⁰, with a_n⁰ ≥0. But then

Xn−1

i=0

a_i

bⁱ =a₀+ a₁

b +...+a_n−1 bⁿ⁻¹ + 1

bⁿ⁻¹ +a_n⁰ bⁿ ≤a.

In particular,

a₀+a₁

b +....+ a_n−1+ 1 bⁿ⁻¹ ≤a, which contradicts our induction hypothesis ona_n−1. 2.|a−¡

a₀ +^a_b¹ +...+^a_bⁿn

¢|< _b¹n and hence it follows that a =a₀+P_∞

n=1 an

bⁿ. Thus the theorem follows.

Now we are sure that we have a b-ary expansion for every positive real number.

Now we will prove the uniqueness of this b-ary expansion in the next theorem.

Theorem 2.0.4. Two distinct positive b-ary expansion a₀+

X∞

k=1

a_k b^k and

α₀+ X∞

k=1

αk

b^k

represent the same positive real number if and only if there exists N ∈N such that 1. a_k=α_k for 0≤k ≤N.

2. aN+1 =αN+1−1(or αN+1 =aN+1−1).

3. a_k=b−1 and α_k = 0 for k > N+1(orα_k=b−1 and a_k = 0 for every k >

N + 1).

Proof. Suppose that the two b-ary expansions have the specified properties. Then if s_n:=a₀+

Xn

k=1

a_k

b^k and σ_n:=α₀+ Xn

k=1

α_k b^k

then σ_n−s_n ≤ _b¹n for all n. Let σ_n→α. Thenα−σ_n ≤ _b¹n for all n and hence α_n−s_n =α_n−σ_n+σ_n−s_n≤ 2

bⁿ, for all n.

Hence sn→α, and so the two b-ary expansions represent the same real number.

Conversely, assume that the two b-ary expansions represent the same real number a.

We havea−sn ≤ _b¹n and a−σn ≤ _b¹n for all n. This implies |σn−sn| ≤ _b¹n for all n.

Let ak =αk for 0≤k ≤n for some n ∈Z+. Since |σn+1−sn+1| ≤ _bn+1¹ , we have

|α_n+1 −a_n+1| = 0 or 1. Suppose a_n+1 = α_n+1−1. Then σ_n+1 =s_n+1 +_bn+1¹ . But a ≤s_n+1+ _bn+1¹ =σ_n+1. Therefore a= σ_n+1 and hence α_k = 0 for k > n+ 1. Thus a=s_n+1+ _bn+1¹ =σ_n+1. To have a−s_n+2 ≤ _bn+2¹ , we require a_n+2 =b−1. For,

1

bⁿ⁺² ≥ a−s_n+2

= s_n+1+ 1 bⁿ⁺¹ −

³

s_n+1+a_n+2 bⁿ⁺²

´

= b

bⁿ⁺² −a_n+2

bⁿ⁺² = b−a_n+2 bⁿ⁺²

Thus, we must have b−an+2 ≤1 or b−1≥an+2 ≥b−1. Hence an+2 =b−1.

Also,a=sn+1+_bn+1¹ =sn+2+^a_bn+2ⁿ⁺² +²=sn+2+_b^b−1n+2+². So, ²= _bn+2¹ . By induction, we have a_k =b−1 fork > n+ 1.

8

Definition 2.0.2. A sequencea1, a2, ..., ak, ...in integers is calledeventually priodic if there is an N0 and p∈ N such that ak+p = ak ∀k > N0. The smallest such p is calledperiod.

Theorem 2.0.5. A real numberr ∈Rhas an eventually periodic if and only ifr∈Q.

Proof. Supposer ∈R has an eventually periodicb-ary expansion for some b≥2.

r=b₀b₁...b_k.a₁a₂...a_N.... where b_i, a_j ∈ {0,1, ..., b−1}

Now by our assumption,r =b₀b₁...b_k1.a₀a₁...a_k2c₁c₂...c_k3. Now we can expand this as r = b₀.b^k1 +b₁.b^k1−1 +...+b_k1+ a₀

b +a₁

b² +...+a_k2 b^k2

+ 1

b^k2

³c₁ b + c₂

b² +...+ c_k3

b^k3 + c₁

b^k3+1 +...+ c_k3 b^2k3 +...

´

= p q + 1

b^k2 µ³c₁

b + c₂

b² +...c_k3 b^k3

´ + 1

b^k3

³c₁ b + c₂

b² +...

´ +....

¶

= p q + p₁

q₁ µ

1 + 1 b^k3 + 1

b^2k3 +....

¶

= p q + p₁

q₁. 1 1−_b¹k3

= p q + p₁

q1

. b^k3

b^k3 −1 ∈Q

wherep, q, p₁, q₁ ∈Z₊. So we are done with one part.

Now conversely suppose that r= ^p_q, wherep, q ∈Z₊ and (p, q) = 1.

Without loss of generality assume thatp < q or r= integer + ^p_q, where p < q.

If (q, b)6= 1, thenq=q₁^r1q₂^r2...q_n^rnq⁰whereq_i’s are prime factors ofq,r_i’s are positive integers and (q⁰, b) = 1. Lett = max{r₁, r₂, ..., r_n}. Note that ^p_q is eventually periodic if and only ifb^{t p}_q is eventually periodic.

So without loss of generality we can assume that (q, b) = 1, By Euler’s theorem, there

exists an integer k≥1 such that

b^k ≡1(modq) So we can write

b^k = 1 +qd for some d∈Z₊ So notice that

p q = pd

qd = pd

b^k−1 = pd b^k¡

1− _b¹k

¢

= pd b^k

µ 1 + 1

b^k + 1

b^2k +...+...

¶

Since pd < qd < b^k, the number of non-zero digits in the b-ary expansion of ^pd_bk is at most k. So ^p_q has b-ary expansion which is periodic as (q, b) = 1 and eventually periodic if (q, b)6= 1.

Chapter 3

Normal Numbers and some properties

3.1 Interesting Numbers

In the view of describing the theory of normal numbers it will be very useful to introduce the concept of interesting numbers. We can define interesting numbers as follows:

Definition 3.1.1. (Interesting Number) A real number α is called interesting if for any natural baseb≥2, the base-brepresentation ofαcontains every finite pattern of digits 0,1,2, ..., b−1 infinitely many times.

In the previous chapter we defined b-ary expansion of real numbers. We also proved the result that any rational number α in any natural base b has an infinitely repeating pattern of some or all digits 0,1, ..., b−1 in their b-ary expansions. No rational number is interesting because it misses many patterns.

Definition 3.1.2. (Lebesgue measure) The Lebesgue measure onR is a set func- tion µ:R→[0,∞) such that for any interval I = [a, b] in R, we have µ(I) = b−a.

10

We know that the set of rational numbers is countable, so its Lebesgue measure is zero. So in this sense we can say that all real numbers are irrationals. From the previous chapter we know that any irrational number represented in any natural base b(b ≥ 2) has a nonterminating and non-repeating b-ary expansion. Some irrational numbers contains only a finite number of some of the digits in theirb-ary expansion.

This has been proven that these irrational numbers make a set of Lebesgue measure zero[11]. Hence, almost all real numbers when written in base b have an infinite number of every digit 0,1, . . . ., b−1. Therefore almost all real numbers are interesting numbers.

Remark:We stated the above result about interesting numbers since this is analogous to the result proved by ´Emile Borel in 1909 about normal numbers. We will give complete proof of Borel’s result in the coming chapters.

3.2 Definition of Normality and some properties

Let b be an integer and b ≥ 2. For a given real number α, there is a unique b-ary expansion of the form

α= [α] + X∞

n=1

anb⁻ⁿ (3.2.1)

where [x] denotes integer part of x, 0 ≤ a_n < b, and a_n 6= 0 infinitely often. This second condition on a_n i.e., a_n 6= 0 is to ensure the unique representation of certain rational numbers.

Notation: For a fixed real number α, we write A(d, b, N) to denote the number of occurrences of the integerd in the set {a₁, a₂, .., a_N}with the a_n given by (3.2.1).

Now we will introduce some basic definitions based on the above notation,

12

Definition 3.2.1. (Simply Normal)We call a real number αto be simply normal in the baseb if

limN→∞

A(d, b, N)

N = 1

b for every d with 0≤d ≤b−1.

Finally we give the definition of normality which is as follows;

Definition 3.2.2. (Absolutely Normal)A real number is called absolutely normal if it is simply normal to all the basesbⁿwheren = 1,2,3, . . . .for every baseb greater than 1.

Definition 3.2.3. (Entirely Normal)A real number is calledentirely normal to base b if it is simply normal to all bases bⁿ, n = 1,2, . . . .

We notice that it is very easy to produce a simply normal number to any given base. For example, 0.0123456789 in the base 10 is simply normal. Further we will see that almost all real numbers are absolutely normal, which will be the main focus of this thesis. This result was first proved by Borel in 1909.

Here we would give a criterion to decide Non-normality of a number, which will give us the motivation to prove some further results.

By the definition of simply normal number we see that if α is not a simply normal number, then there is some ² >0 for which

¯¯

¯¯A(d, b, N)

N − 1

b

¯¯

¯¯> ²

for infinitely manyN. We will first prove some elementary properties of normality to the given base. Let us start with a theorem.

Theorem 3.2.1. [10] Let b and n both be integers ≥2. Then, if α is simply normal to base bⁿ, it is simply normal to the base b.

Proof. Writec=bⁿ. Since α is simply normal to the base bⁿ, A(d, c, N)

N = 1

c +o(1) (3.2.2)

for all d with 0≤d≤c−1. We notice that every integerd between 0 andc−1 can be written in the form

Xn−1

j=0

c_j(d)b^j with 0≤c_j(d)≤b−1. (3.2.3) Now assume that

{α}= X∞

m=1

a_mb^−m = X∞

r=1

d_rc^−r. where{x} denotes the fractional part of x.

Now we can rewrite the above equation using equation (3.2.3) as follows:

{α}= X∞

m=1

amb^−m = X∞

r=1

Ã_n−1 X

j=0

cj(dr)b^j

! b^−nr

By the above expression we can conclude that ifais given, with 0≤a≤b−1, then the integera appears exactlyk times among the numbers a_m withtn+ 1≤m ≤(t+ 1)n if and only if the equation

c_j(d_t) = a has exactlyk solutions. Now we write

D(k) ={d: 0≤d≤c−1, c_j(d) = a has k solutions}.

Clearly D(k) has ¡_n

k

¢(b−1)^n−k members since we have chosen k values out of n and for each of the remaining n−k positions there are b −1 possibilities. Let N be a

14

positive integer. We then have A(a, b, Nn)

Nn =

Xn

k=0

k n

X

d∈D(k)

A(d, c, N) N

= Xn

k=0

k n

µn k

¶

(b−1)^n−k(c⁻¹+o(1))

= Xn−1

r=0

µn−1 r

¶

(b−1)^n−1−r(c⁻¹+o(1))

= 1

b +o(1)

by equation (3.2.2) and binomial theorem. Because A(a, b, N +r)−A(a, b, N)< r, moreover, letN =nM +r where r < n, then

A(a, b, N)

N = A(a, b, nM +r)

nM +r < A(a, b, nM +r) nM

< A(a, b, nM)

nM + r

nM < A(a, b, nM)

nM + 1

M asN → ∞, nM → ∞ and M → ∞. So we get

lim_N→∞A(a, b, N)

N = 1

b,

Since this holds for each a, we conclude that α is simply normal to the base b.

Corollary 3.2.2. The statements ’α is simply normal to all bases bⁿ, n= 1,2, . . . .’

and ’α is simply normal to all base b^nt, t= 1,2, . . . . and n∈Z₊’ are equivalent.

Proof. It is very much clear from the statement itself. Both the statements imply each other clearly.

Remark.. We notice that the theorem (3.2.1) is not true in the reverse direction.

As an example, 0.0123456789 is simply normal to base 10 but not simply normal in base 100. Borel calls a numberentir´ement normalif each of α, αb, αb², ...is simply normal to every base b, b², b³, .... From the definition of entirely normal number we can see that entirement normal and entirely normal are equivalent. The next theorem which we will prove, was first demonstrated by S.S.Pillai[14, 15].

Theorem 3.2.3. [10] If α is simply normal to all bases bⁿ, n = 1,2, . . . ., then each of α, αb, αb², ... is simply normal to every base bⁿ, b²ⁿ, b³ⁿ, ...

Proof. We only need to show thatαbis simply normal to all basesbⁿ,wheren= 1,2, ...

because once we show that αb is simply normal to all bases bⁿ, from the corollary it will be simply normal to every basebⁿ, b²ⁿ, b³ⁿ, ..and rest will follow from the theorem itself. We shall writeA^∗(d, c, N) to denote the number of occurrences of digitdamong the numbers a1, a2, ..., aN where

bα= [bα] + X∞

j=1

ajc^−j

andA(d, c, N) for the corresponding function forα. Since multiplying byb just shifts one digit of b-ary expansion of α to the right. We have |A^∗(d, b, N)−A(d, b, N)| ≤1.

Since α is simply normal to all bases bⁿ, n = 1,2, ..., αb is simply normal to base b.

Now we shall prove that αb is simply normal to every base b^j(j ≥ 2) by using the fact thatα is simply normal to every base b^jr with r arbitrary large.

Now letabe an integer between 0 andb^j−1, and suppose thatr is a positive integer.

Given an integer d with 0≤d≤b^jr−1, define g_m =g_m(d) by bd−[db^1−jr]b^jr=

Xr−1

m=0

b^mjg_m, 0≤g_m ≤b^j (3.2.4)

16

Here we can notice that when integer d is between 0 and b^jr−1−1, we can write db=

Xr−1

m=0

g_mb^mj, 0≤g_m ≤b^j−1

and whenb^jr−1 ≤d≤b^jr, calculate xsuch that db−xb^jr < b^jr, then we can see that this x is nothing but [bd^1−jr] which verifies the significance of equation (3.2.4). We defineD(k) to be the set

D(k) ={d: 0≤d≤b^jr−1, g_m =a has exactlyk solutions for m≥1}

We note that the cardinality of D(k) is µr−1

k

¶

b^j(b^j −1)^r−k−1. It follows that the definition of D(k) that

A^∗(a, b^j, Nr)≥ Xr−1

k=0

k X

d∈D(k)

A(d, b^jr, N) Hence, since α is simply normal to base b^jr,

A^∗(a, b^j, Nr)

Nr ≥

Xr−1

k=0

k r

µr−1 k

¶

b^j(b^j−1)^r−k−1(b^−jr+o(1))

= (1−1/r)b^−j(1 +o(1)).

Thus for any integerM we have A^∗(a, b^j, M)

M ≥(1−1/r)b^−j(1 +o(1)).

It follows that

liminf_N→∞A^∗(a, b^j, N)

N ≥b^−j(1−1/r). (3.2.5)

Since this holds for every a and

bX^j−1

a=0

A^∗(a, b^j, N)

N = 1

we must also have

limsup_N→∞A^∗(a, b^j, N)

N ≤b^−j(1 + 1/r) for all a. (3.2.6) For otherwise, suppose for some a we have

limsup_N→∞A^∗(a, b^j, N) N > 1

b^j µ

1 + 1 r

¶

Then

limsup_N→∞

bX^j−1

a=0

A^∗(a, b^j, N)

N >

bX^j−1

a=0

1 b^j

µ 1 + 1

r

¶

> b^j b^j

µ 1 + 1

r

¶

= µ

1 + 1 r

¶

which is a contradiction.

Since (3.2.5) and (3.2.6) hold for arbitrary large r, we get liminf_N→∞A^∗(a, b^j, N)

N ≥b^−j and limsup_N→∞A^∗(a, b^j, N)

N ≤b^−j

Since

liminfN→∞

A^∗(a, b^j, N)

N <limsup_N→∞A^∗(a, b^j, N) N We get

liminf_N→∞A^∗(a, b^j, N)

N = limsup_N→∞A^∗(a, b^j, N)

N = lim_N→∞A^∗(a, b^j, N)

N =b^−j

we may deduce that

lim_N→∞A^∗(a, b^j, N)

N =b^−j, for 0 ≤a≤b^j −1.

We thus completes the proof of the fact thatαbis simply normal to every baseb^j. Now we will introduce another definition of normality, given for example by Hardy and Wright[9], Niven and Zuckerman[12]. which is as follows:

18

Definition 3.2.4. (Normality of a number) Given a blockBk of k digits in base b, we then writeA(Bk, b, N) for the number of occurrences ofBkin the block of digits a1, a2, .., aN. We call a number normal to base bif

lim_N→∞A(B_k, b, N)

N =b^−k for all k ≥1, and all B_k.

The next theorem shows that this is equivalent to the definition we chosen for an entirely normal number. Before proving the theorem we will prove one very important lemma which will give us a criterion to decide non-normality. If α is not a normal number, then there is some ² >0 for which

¯¯

¯¯A(d, b, N)

N − 1

b

¯¯

¯¯> ²

On the line of the above equation we will proceed towards a lemma.

Letb ≥2 be an integer. Let k be an integer such that k ≥b+ 2. Let B_k denote the block of k-digits, say, B_k = a_na_n+1...a_n+k−1 where 0 ≤ a_i ≤ b−1. Let d be a given digit in the baseb such that 0≤d≤b−1.

Let n_d denote the number of times the given digit d occurs in B_k. Since the total number of digits inB_k is k, the expected number of timesd occurs in B_k is ^k_b i.e. the average. The following lemma computes the number of differentB_k’s such that if the difference between the expected number and actual number is≥²k, then the number of different such blocks B_k ≤²b^k. Note that the number of distinct blocks B_k isb^k. Lemma 3.2.4. The number of distinct blocks B_k for which |n_d−^k_b| ≥²k holds is at most ²b^k for every k > k₀(²) or k À0.

Proof. First consider those blocks Bk for which k

b −n_d ≥ ²k

⇒ n_d ≤ k

b −²k = µ1

b −²

¶ k The number of such blocks is

X

0≤j<k(¹_b−²)

µk j

¶

(b−1)^k−j =Y (say) and we know

Xk

j=0

µk j

¶

(b−1)^k−j =b^k But we can notice that

¡_k

j

¢(b−1)^k−j

¡ _k

j+1

¢(b−1)^k−j−1 =

k!

j!(k−j)!

k!

(j+1)!(k−j−1)!

= (j+ 1)(b−1) k−j −1 Putj = ^k_b −θ. Then we get

(j + 1)(b−1)

k−j−1 = (^k_b −θ+ 1)(b−1) k− ^k_b +θ−1 Sincej = ^k_b −θ∈Z, we see that θ ∈Q.

Now we notice that µk

b −θ+ 1

¶

(b−1) = k−θb+b− µk

b −θ+ 1

¶

= k+b−θ− µk

b −θ+ 1

¶

So we have

(^k_b −θ+ 1)(b−1)

k−(^k_b −θ+ 1) = k−θb+b−(^k_b −θ+ 1) k−(^k_b −θ+ 1)

= b(1−θ)

k−(^k_b −θ+ 1) + 1

20

Now we want to prove that

b(1−θ)

k−(^k_b −θ+ 1 + 1 < 1− b(θ−1) k

⇔ kbθ+k+ (θ−1)b(θ−1) < 2kb

Since θ < ^k_b and k² < θ; we see that k²−1< θ−1 and L.H.S. is much smaller than R.H.S.

Moreover,

1− b(θ−1)

k < 1−b(k²−1)

k <1−²b+ b k

⇒1− b(θ−1)

k < 1−²b 3 After getting the above inequality we can write

µk j

¶

(b−1)^k−j <

µ 1−²b

3

¶ µ k j+ 1

¶

(b−1)^k−j−1 ∀j (3.2.7) We know that

Y = X

0≤j<^k_b−k²

µk j

¶

(b−1)^k−j and b^k= X

0≤j≤k

µk j

¶

(b−1)^k−j

Other than the terms in Y, we have k−^k_b +²k terms in b^k. Moreover

b^k ≥

k−X^k_b+^²k₂

j=k−^²k₂

µk j

¶

(b−1)^k−j

So we have µ

1− ²b 3

¶^²k

2

b^k ≥ µ

1− ²b 3

¶^²k

2 k−X^k_b+^²k₂

j=k−^²k₂

µk j

¶

(b−1)^k−j

=

k−X^k_b+^²k₂

j=k−^²k₂

µ 1− ²b

3

¶^²k

2 µ k j

¶

(b−1)^k−j

≥

k b−k²

X

j=0

µk j

¶

(b−1)^k−j By (3.2.7)

= Y

The estimate in equation (3.2.7) is valid for large k’s.

The number of blocks B_k satisfying ^k_b −n_d ≥²k is less than or equal to (1−^²b₃)^²k2 b^k. Now we have to prove that (1− ^²b₃)^²k2 < ² ∀ k > k₀(²).

Since (1− ^²b₃)^²k2 →0 as k → ∞, this is indeed true for allk > k₀(²).

So finally we can conclude that the number of blocks B_k satisfying ^k_b −n_d≥²k is at most ²b^k.

Analogously one can do the same calculations for the other case which isn_d−^k_b > ²k.

Thus the lemma is proved.

Now we will prove a theorem which shows the equivalence of the definition (3.2.4) of normality and our definition of entirely normal numbers. We will use the above lemma to prove this theorem.

Suppose E and F are two blocks of digits to base b and F is not shorter than E, say,

F =a₁a₂...a_ka_k+1...a_k+s and E =b₁b₂...b_k

then R_j(E, F), where 1 ≤ j ≤ k, denotes the number of times E occurs in F with

22

the first digit ofE appears in the position h≡j(modk). For instance, F = a₁a₂...a_ka_k+1...a_k+h...a_k+s

= a₁a₂...a_ka_k+1...a_2ka_2k+1...a_3k....a_lk+m where s=lk+m and m < k then

F =a1...akak+1...ak+j−1b1b2...bk...

if E appears inF with the first digit at k+j ≡j(modk).

Theorem 3.2.5. [10] A real number α is entirely normal to the base b if and only if lim_N→∞A(Bk, b, N)

N =b^−k for all k ≥1, and all B_k.

Proof. Suppose that α is entirely normal to base b and let B_k be given block of k digits. Therefore from the definition we know that each of α, bα, ..., b^k−1α is simply normal to base b^k. Now we can write B_k as a single digit, say d, to base b^k. The occurrence of the blockB_k as

a_kr+j+1...a_kr+k+j,

for somej with 0 ≤j ≤k−1, is then equivalent to the digitd being in the (r−1)th position in the expansion of b^jα to base b^k. Write A_j(d, b^k, N) for the number of occurrences of d among the first N digits in the expansion of b^jα to base b^k. Then

A(B_k, b, N k)

Nk = 1

k Xk−1

j=0

A_j(d, b^k, N) N

= b^−k(1 +o(1)), since b^jα is simply normal to base b^k. Thus

lim_N→∞A(B_k, b, N)

N =b^−k

and this establish the only if part of the proof.

If Bk denotes a block of k digits of α in base b and A(Bk, b, N) denotes the number of times Bk appears in the first N digits of α. Assume that

lim_N→∞A(B_k, b, N)

N = 1

b^k ∀ k ≥1 and ∀ B_k. We need to prove that

lim_N→∞A(d, b^r, N)

N = 1

b^r ∀ r ≥1 ∀ d digit in base b^r.

sinceris arbitrary, it will follow thatαis entirely normal to base b. Notice that when r = 1, the assertion is trivial by our assumption, take k = 1 and B₁ = d is a given digit in baseb.

1

b = lim_N→∞A(B₁, b, N)

N = lim_N→∞A(d, b, N) N

So assume that r > 1. Let d be a digit in base b^r. Then we can write d as a block of r digits to base b as B = b₁b₂...b_r. Let B = B(s, ²) be the set of all blocks H of s(s > r) digits to the baseb such that

max_j|R_j(B, H)−

s r

b^r| ≥²s.

By Lemma (3.2.4), with given d and ² > 0, the number of different blocks H of ^s_r digits to the baseb^r(or in other words H of s digits to the base b) for which

¯¯

¯nd− s rb^r

¯¯

¯≥²s

is less than or equal to²b^rsr =²b^s for every s > s₀(²), here n_d denotes the number of times doccurs in H. That is, we have |B| ≤²b^s∀s > s₀(²)

24

Let s = max(s0,^r_²) and let H ∈ B of s digit block. Then A(H, b, N) denotes the number of times the blockH appears in firstN digits of α. By our assumption,

lim_N→∞A(H, b, N)

N = 1

b^s which is equivalent to say that

A(H, b, N) = N

b^s +o(N) for all sufficiently large N’s So we can write

X

H∈B

A(H, b, N) = X

H∈B

µN

b^s +o(N)

¶

= N

b^s|B|+o(N|B|)

≤ N

b^s²b^s+o(N)

= ²N +o(N)≤2²N for all sufficiently large N’s.

We now write D_t for the block of digits a_t...a_t+s−1 in the expansion of α in base b.

Let

S(N) ={t :D_t∈B, t≤N −s+ 1}

Then from above we can see that|S(N)| ≤2²N for all largeN. Suppose that N is a multiple ofr. For a givenj such that 1≤j ≤r, suppose Rj(B, Dt)≥1 i.e.

b1 =at, b2 =at+1, ..., br =at+r−1

has solution. Then

R_j(B, D_t+a)≥1 for all a= 0,−1,−2, ...,−(s−r),

this is because of the reason that,

Dt = b1b2. . . .brat+r+1. . . .at+s−1

D_t−1 = a_t−1b₁b₂. . . .b_ra_t+r+1. . . .a_t+s−2 Dt−2 = at−2at−1b1b2. . . .brat+r+1. . . .at+s−3

. .

D_t−(s−r) = a_t−s+ra_t−s+r+1. . . .b₁b₂. . . .b_r which implies that

R_j(B, D_t)≥1, . . . , R_j(B, D_t−s+r)≥1.

For a fixedj, 1≤j ≤r, one solution to

b₁ =a_t, b₂ =a_t+1, ..., b_r =a_t+r−1 give rise to (s−r+ 1) counting to P_N−s+1

t=1 R_j(B, D_t).

If R_j(B, D_t) ≥ 1, then A(d, b^r, N/r) ≥ 1 as B = b₁b₂. . . .b_r = d in the base b^r (by assumption).

So (s−r+ 1)A(d, b^r, N/r) counts d at least (s−r+ 1) times. Then

|(s−r+ 1)A(d, b^r, N/r)−

NX−s+1

t=1

R_j(B, D_t)| ≤2s². (3.2.8) We already know that S(N)≤2²N and for any t∈S(N), we have

o≤R_j(B, D_t)≤s−r+ 1 ∀ 1≤j ≤r Fort6∈S(N) we have

|R_j(B, D_t)− s/r

b^r | ≤²s.