Explicit constructions in the classical mean squares problem in irregularities of point distribution. (English) Zbl 1083.11049

Chen, W. W. L.; Skriganov, M. M.

J. Reine Angew. Math. 545, 67-95 (2002).

In this paper an explicit construction of distributions \(\mathcal{D}_N\) of \(N\) points in the \(k\)-dimensional unit cube \(U^k\) with the minimal order of the \(L_2\)-discrepancy \(\mathcal{L}_2[\mathcal{D}_N]<C_k(\log N)^{\frac{1}{2}(k-1)}\), where the constant \(C_k\) is independent of \(N\). As an essential tool ideas from coding theory are used. In particular, the authors consider codes over finite fields with large weights simultaneously in two different metrics – the well-known Hamming metric and a new non-Hamming metric arising recently in coding theory.
First constructions of such distributions were given in dimensions \(k=2\) and \(k=3\) by Davenport (1956) and Roth (1979) and in arbitrary dimensions by Roth (1980). Until recently apart from Davenport’s construction for dimension \(k=2\) all known constructions involve probabilistic arguments and are therefore not explicit. Very recently Larcher and Pillichshammer have studied the problem for the dimension \(k=3\) by an approach using point sets constructed by Faure (1982).
The method of the present paper is a breakthrough in the theory of point distributions since it gives a complete and explicit solution of the problem. The proofs depend on a delicate analysis of Walsh series expansions.

Reviewer: Robert F. Tichy (Graz)

MSC:

11K38	Irregularities of distribution, discrepancy
11K06	General theory of distribution modulo \(1\)
94B27	Geometric methods (including applications of algebraic geometry) applied to coding theory

References:

[1]	J. Beck, W. W. L. Chen, Irregularities of Distribution, Cambridge University Press, Cambridge1987. · Zbl 0617.10039
[2]	M. S. Birman, M. Z. Solomyak, Spectral Theory of Self-Adjoint Operators in Hilbert Space, Leningrad State University, Leningrad, 1980; english translation: Reidel, Dordrecht 1987. · Zbl 0744.47017
[3]	W. W., Mathematika 27 pp 153– (1980)
[4]	W. W., Quart. J. Math. Oxford 34 pp 257– (1983)
[5]	Chen W. W. L., Zapiski Nauch. Sem. POMI 269 pp 339– (2000)
[6]	Mathematika 3 pp 131– (1956)
[7]	Dobrovol’skii? N. M., Uspekhi Mat. Nauk 39 pp 155– (1984)
[8]	Acta Arith. 41 pp 337– (1982)
[9]	Fine N. J., Trans. Amer. Math. Soc. 65 pp 373– (1949)
[10]	K., Dokl. Acad. Nauk SSSR 252 (4) pp 805– (1980)
[11]	B. I. Golubov, A. V. Efimov, V. A. Skvorcov, The Walsh Series and Transformations Theory and Applications, Nauka, Moscow1987; english translation: Kluwer, Dordrecht 1991.
[12]	R. Lidl, H. Niederreiter, Finite fields, Addison-Wesley 1983.
[13]	F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam1977. · Zbl 0369.94008
[14]	Martin W. J., Canadian J. Math. 51 pp 326– (1999)
[15]	Monatsh. Math. 104 pp 273– (1987)
[16]	H. Niederreiter, Nets, t; s -sequences, and algebraic curves over finite fields with many rational points, International Congress of Mathematicians in Berlin, Extra Volume III, Documenta Mathematica (1998), 337-386. · Zbl 0899.11038
[17]	J., Canadian J. Math. 9 pp 413– (1957)
[18]	Yu M., Problemi Peredachi Inf. 33 (1) pp 55– (1997)
[19]	K., Mathematika 1 pp 73– (1954)
[20]	K., Acta Arith. 35 pp 373– (1979)
[21]	K., Acta Arith. 37 pp 67– (1980)
[22]	F. Schipp, W. R. Wade, P. Simon, Walsh Functions An Introduction to Dyadic Harmonic Analysis, Adam Hilger, Bristol and New York 1990. · Zbl 0727.42017
[23]	M., J. 1 pp 535– (1990)
[24]	M., Petersburg Math. J. 6 pp 635– (1995)
[25]	M. M. Skriganov, Coding theory and uniform distributions, Algebra i Analiz 13 (2) (2001), 191-239; english translation: St. Petersburg Math. J., to appear.
[26]	I., Fiz. 7 pp 784– (1967)
[27]	Steklov Mathematical Institute, Fontanka 27 pp 191011–