Number Theory: An Introduction to Mathematics

460 XI Uniform Distribution and Ergodic Theory

D∗N= max

1 ≤k≤N

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

The second expression forD∗Nfollows immediately, since

max(|k/N−α|,|(k− 1 )/N−α|)=|(k− 1 / 2 )/N−α|+ 1 / 2 N. 

Corollary 12Ifξ 1 ,...,ξNare real numbers such that 0 ≤ξ 1 ≤ ··· ≤ξN ≤ 1 ,
then D∗N ≥( 2 N)−^1. Moreover, equality holds if and only ifξk =( 2 k− 1 )/Nfor
k= 1 ,...,N.

Thus Proposition 11 says that the discrepancy of any set ofNpoints ofI is
obtained by adding to its minimal value 1/ 2 Nthe maximum deviation of the set from
the unique minimizing set, when both sets are arranged in order of magnitude.
The next result shows that the discrepancyD∗N(ξ 1 ,...,ξN)is a continuous func-
tion ofξ 1 ,...,ξN.

Proposition 13Ifξ 1 ,...,ξNandη 1 ,...,ηNare two sets of N points of I , with the
discrepancies D∗Nand E∗Nrespectively, then

|D∗N−E∗N|≤max

1 ≤k≤N

|ξk−ηk|.

Proof Letx 1 ≤ ··· ≤xNandy 1 ≤ ··· ≤yNbe the two given sets rearranged in
order of magnitude. It is enough to show that

max

1 ≤k≤N

|xk−yk|≤δ:= max

1 ≤k≤N

|ξk−ηk|,

since it then follows from Proposition 11 that

D∗N≤δ+E∗N, E∗N≤δ+D∗N.

Assume, on the contrary, that|xk−yk|>δfor somek. Then eitherxk>yk+δ
oryk >xk+δ. Without loss of generality we restrict attention to the first case. By
hypothesis, for eachyiwith 1≤i≤kthere exists anxjiwith 1≤ji≤Nsuch that
|yi−xji|≤δand such that the subscriptsjiare distinct. Sincey 1 ≤ ··· ≤yk,it
follows that

xji≤yi+δ≤yk+δ<xk.

But this is a contradiction, since there are at mostk− 1 x’s less thanxk.

We now show how the notion of discrepancy makes it possible to obtain estimates
for the accuracy of various methods of numerical integration.

Proposition 14If the function f satisfies the ‘Lipschitz condition’

|f(t 2 )−f(t 1 )|≤L|t 2 −t 1 | for all t 1 ,t 2 ∈I,

then for any finite setξ 1 ,...,ξN∈I with discrepancy D∗N,

∣

∣

∣

∣N

− 1

∑N

n= 1

f(ξn)−

∫

I

f(t)dt

∣

∣

∣

∣≤LD

∗

N.