Number Theory: An Introduction to Mathematics

2 Discrepancy 459

2 Discrepancy................................................

Thestar discrepancyof a finite set of pointsξ 1 ,...,ξNin the unit intervalI=[0,1]
is defined to be

D∗N=D∗N(ξ 1 ,...,ξN)= sup

0 <α≤ 1

|φα(N)/N−α|,

whereφα(N)=φ 0 ,α(N)denotes the number of positive integersn≤Nsuch that
0 ≤ξn<α. Here we will omit the qualifier ‘star’, since we will not be concerned with
any other type of discrepancy and the notationD∗Nshould provide adequate warning.
It was discovered only in 1972, by Niederreiter, that the preceding definition may
be reformulated in the following simple way:

Proposition 11Ifξ 1 ,...,ξNare real numbers such that 0 ≤ξ 1 ≤···≤ξN≤ 1 ,then

D∗N=D∗N(ξ 1 ,...,ξN)= max

1 ≤k≤N

max(|ξk−k/N|,|ξk−(k− 1 )/N|)

=( 2 N)−^1 + max

1 ≤k≤N

|ξk−( 2 k− 1 )/ 2 N|.

Proof Putξ 0 = 0 ,ξN+ 1 =1. Since the distinctξkwith 0≤k≤N+1definea
subdivision of the unit intervalI,wehave

D∗N= max

k:ξk<ξk+ 1

sup

ξk≤α<ξk+ 1

|φα(N)/N−α|

= max

k:ξk<ξk+ 1

sup

ξk≤α<ξk+ 1

|k/N−α|.

But the functionfk(t)=|k/N−t|attains its maximum in the intervalξk≤t≤ξk+ 1
at one of the endpoints of this interval. Consequently

D∗N= max

k:ξk<ξk+ 1

max(|k/N−ξk|,|k/N−ξk+ 1 |).

We are going to show that in fact

D∗N= max

0 ≤k≤N

max(|k/N−ξk|,|k/N−ξk+ 1 |).

Supposeξk <ξk+ 1 =ξk+ 2 = ··· =ξk+r <ξk+r+ 1 for somer ≥2. By
applying the same reasoning as before to the functiongk(t)=|t−ξk+ 1 |we obtain, for
1 ≤j<r,

|(k+j)/N−ξk+j|=|(k+j)/N−ξk+j+ 1 |=|(k+j)/N−ξk+ 1 |

<max(|k/N−ξk+ 1 |,|(k+r)/N−ξk+ 1 |)

=max(|k/N−ξk+ 1 |,|(k+r)/N−ξk+r|).

Since both terms in the last maximum appear in the expression already obtained for
D∗N, it follows that this expression is not altered by dropping the restriction to thosek
for whichξk<ξk+ 1.
Since| 0 /N−ξ 0 |=|N/N−ξN+ 1 |=0, we can now also write