2 Discrepancy 463Propositions 14 and 15 show that in a formula for numerical integration the nodes
(ξn)should be chosen to have as small a discrepancy as possible. For a given finite
numberNof nodes Corollary 12 shows how this can be achieved. In practice, how-
ever, one does not know in advance an appropriate choice ofN, since universal error
bounds may grossly overestimate the error in a specific case. Consequently it is also of
interest to consider the problem of choosing an infinite sequence (ξn) of nodes so that
the discrepancyδNofξ 1 ,...,ξNtends to zero as rapidly as possible whenN→∞.
There is a limit to what can be achieved in this way. W. Schmidt (1972), improving
earlier results of van Aardenne-Ehrenfest (1949) and Roth (1954), showed that there
exists an absolute constantC>0suchthat
lim
N→∞NδN/logN≥Cforeveryinfinite sequence (ξn). Kuipers and Niederreiter (1974) showed that a pos-
sible value forCwas(132 log 2)−^1 = 0. 0109 ..., which Bejian (1979) improved to
(24 log 2)−^1 = 0. 0601 ....
Schmidt’s result is best possible, apart from the value of the constant. Ostrowski
(1922) had already shown that for the sequence({nα}),whereα∈( 0 , 1 )is irrational,
one has
s∗(α):= lim
N→∞NδN/logN<∞if in the continued fraction expansion
α=[0;a 1 ,a 2 ,...]=1
a 1 +1
a 2 +···the partial quotientsakare bounded. Dupain and S ́os (1984) have shown that the mini-
mum value ofs∗(α), for all suchα,is(4log( 1 +
√
2 ))−^1 = 0. 283 ...and the minimum
is attained forα=
√
2 − 1 =[0; 2 , 2 ,...]. Schoessengeier (1984) has proved that, for
any irrationalα∈( 0 , 1 ), one hasNδN=O(logN)if and only if the partial quotients
aksatisfy
∑n
k= 1 ak=O(n).
There are other low discrepancy sequences. Haber (1966) showed that, for a
sequence(ξn)constructed by van der Corput (1935),
lim
N→∞NδN/logN=(3log2)−^1 = 0. 481 ....van der Corput’s sequence is defined as follows: ifn− 1 =am 2 m+···+a 121 +a 0 ,
whereak ∈{ 0 , 1 },thenξn =a 02 −^1 +a 12 −^2 +···+am 2 −m−^1 .Inotherwords,
the expression forξnin the base 2 is obtained from that forn−1byreflection
in the ‘decimal’ point, a construction which is easily implemented on a computer.
Various generalizations of this construction have been given, and Faure (1981) defined
in this way a sequence(ξn)for which
lim
N→∞NδN/logN=( 1919 )(3454 log 12)−^1 = 0. 223 ....