The exponent of discrepancy is at most 1.4778...

Open Access

1 July 1997

journal article
Published by American Mathematical Society (AMS) in Mathematics of Computation

Vol. 66 (219) , 1125-1132
https://doi.org/10.1090/s0025-5718-97-00824-7

Abstract

We study discrepancy with arbitrary weights in the

L_2

norm over the

d

-dimensional unit cube. The exponent

p^*

of discrepancy is defined as the smallest

p

for which there exists a positive number

K

such that for all

d

and all

\varepsilon \le 1

there exist

K\varepsilon ^{-p}

points with discrepancy at most

\varepsilon

. It is well known that

p^*\in (1,2]

. We improve the upper bound by showing that\[

p^*\le 1.4778842.

\]This is done by using relations between discrepancy and integration in the average case setting with the Wiener sheet measure. Our proof isnotconstructive. The known constructive bound on the exponent

p^*

2.454

Keywords

This publication has 11 references indexed in Scilit:

Efficient algorithms for computing the $L_2$-discrepancy
Mathematics of Computation, 1996
Explicit Cost Bounds of Algorithms for Multivariate Tensor Product Problems
Journal of Complexity, 1995
Lattice Methods for Multiple Integration
Published by Oxford University Press (OUP) ,1994
Random Number Generation and Quasi-Monte Carlo Methods
Published by Society for Industrial & Applied Mathematics (SIAM) ,1992
Average case complexity of multivariate integration
Bulletin of the American Mathematical Society, 1991
Irregularities of Distribution
Published by Cambridge University Press (CUP) ,1987
On irregularities of distribution, IV
Acta Arithmetica, 1980
Quasi-Monte Carlo methods and pseudo-random numbers
Bulletin of the American Mathematical Society, 1978
On irregularities of distribution
Mathematika, 1954
On Frobeniusean Algebras. I
Annals of Mathematics, 1939