## The exponent of discrepancy is at most 1.4778...

HTML articles powered by AMS MathViewer

- by Grzegorz W. Wasilkowski and Henryk Woźniakowski PDF
- Math. Comp.
**66**(1997), 1125-1132 Request permission

## 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 is*not*constructive. The known constructive bound on the exponent $p^*$ is $2.454$.

## References

- József Beck and William W. L. Chen,
*Irregularities of distribution*, Cambridge Tracts in Mathematics, vol. 89, Cambridge University Press, Cambridge, 1987. MR**903025**, DOI 10.1017/CBO9780511565984 - V. A. Bykovskij,
*On exact order of optimal quadrature formulas for spaces of functions with bounded mixed derivatives*, Report of the Dalnevostochnoi Center of Academy of Sciences, Vladivostok, USSR (in Russian), 1985. - B. Chazelle,
*Geometric discrepancy revisited*, 34th Annual Symposium on Foundations of Computer Science, 1993, pp. 392–399. - D. P. Dobkin and D. P. Mitchell,
*Random-edge discrepancy of supersampling patterns*, Graphics Interface ’93, York, Ontario, 1993. - K. K. Frolov,
*Upper bound of the discrepancy in metric $L_{p}$, $2\leq p<\infty$*, Dokl. Akad. Nauk SSSR**252**(1980), no. 4, 805–807 (Russian). MR**580823** - S. Heinrich,
*Efficient algorithms for computing the $L_2$ discrepancy*, Math. Comp.**65**(1996), 1621–1633. - S. Heinrich and A. Keller,
*Quasi-Monte Carlo methods in computer graphics*, Part I:*The*QMC-*buffer*, Report, Univ. of Kaiserslautern, Dept. Computer Science, Report No.242/1994; Part II: The radiance equation, Report, Univ. of Kaiserslautern, Dept. Computer Science, Report No.243/1994. - Harald Niederreiter,
*Quasi-Monte Carlo methods and pseudo-random numbers*, Bull. Amer. Math. Soc.**84**(1978), no. 6, 957–1041. MR**508447**, DOI 10.1090/S0002-9904-1978-14532-7 - Harald Niederreiter,
*Random number generation and quasi-Monte Carlo methods*, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR**1172997**, DOI 10.1137/1.9781611970081 - Tadasi Nakayama,
*On Frobeniusean algebras. I*, Ann. of Math. (2)**40**(1939), 611–633. MR**16**, DOI 10.2307/1968946 - K. F. Roth,
*On irregularities of distribution. IV*, Acta Arith.**37**(1980), 67–75. MR**598865**, DOI 10.4064/aa-37-1-67-75 - I. H. Sloan and S. Joe,
*Lattice methods for multiple integration*, Oxford Science Publication, Oxford, 1994. - V. N. Temlyakov,
*Approximation of functions with bounded mixed derivative*, Proc. Steklov Inst. Math.**1(178)**(1989), vi+121. A translation of Trudy Mat. Inst. Steklov 178 (1986) [ MR0847439 (87j:42006)]; Translated by H. H. McFaden. MR**1005898** - Grzegorz W. Wasilkowski and Henryk Woźniakowski,
*Explicit cost bounds of algorithms for multivariate tensor product problems*, J. Complexity**11**(1995), no. 1, 1–56. MR**1319049**, DOI 10.1006/jcom.1995.1001 - H. Woźniakowski,
*Average case complexity of multivariate integration*, Bull. Amer. Math. Soc. (N.S.)**24**(1991), no. 1, 185–194. MR**1072015**, DOI 10.1090/S0273-0979-1991-15985-9

## Additional Information

**Grzegorz W. Wasilkowski**- Affiliation: Department of Computer Science, University of Kentucky, Lexington, Kentucky 40506
- MR Author ID: 189251
- ORCID: 0000-0003-4727-7368
- Email: greg@cs.engr.uky.edu
**Henryk Woźniakowski**- Affiliation: Department of Computer Science, Columbia University, New York, New York 10027 and Institute of Applied Mathematics, University of Warsaw, ul. Banacha 2, 02-097 Warszawa, Poland
- Email: henryk@cs.columbia.edu
- Received by editor(s): December 20, 1995
- Received by editor(s) in revised form: May 1, 1996
- Additional Notes: The first author was partially supported by the National Science Foundation under Grant CCR-9420543, and the second by the National Science Foundation and the Air Force Office of Scientific Research
- © Copyright 1997 American Mathematical Society
- Journal: Math. Comp.
**66**(1997), 1125-1132 - MSC (1991): Primary 11K38, 41A55
- DOI: https://doi.org/10.1090/S0025-5718-97-00824-7
- MathSciNet review: 1397448