Distribution of Korobov-Hlawka sequences

A. A. Illarionov

Sbornik. Mathematics, Tome 213 (2022) no. 9, pp. 1222-1249

Résumé

Let $a_1, \dots, a_s$ be integers and $N$ be a positive integer. Korobov (1959) and Hlawka (1962) proposed to use the points $$ x^{(k)}=\biggl(\biggl\{\frac{a_1 k}N\biggr\}, \dots, \biggl\{\frac{a_1 k}N\biggr\}\biggr), \qquad k=1,\dots, N, $$ as nodes of multidimensional quadrature formulae. We obtain some new results related to the distribution of the sequence $K_N(a)=\{x^{(1)},\dots,x^{(N)}\}$. In particular, we prove that $$ \frac{\ln^{s-1} N}{N \ln\ln N} \underset{s}\ll D(K_N(a)) \underset{s}\ll \frac{\ln^{s-1} N}{N} \ln\ln N $$ for ‘almost all’ $a\in (\mathbb Z_N^*)^s$, where $D(K_N(a))$ is the discrepancy of the sequence $K_N(a)$ from the uniform distribution and $\mathbb Z^*_N$ is the reduced system of residues modulo $N$. Bibliography: 18 titles.

Détail

Keywords: uniform distribution, discrepancy from the uniform distribution, Korobov-Hlawka sequences, Korobov grids.

Bibliographie

[1] N. M. Korobov, “Approximate evaluation of repeated integrals”, Dokl. Akad. Nauk. SSSR, 124:6 (1959), 1207–1210 (Russian) | MR | Zbl

[2] E. Hlawka, “Zur angenäherten Berechnung mehrfacher Integrale”, Monatsh. Math., 66:2 (1962), 140–151 | DOI | MR | Zbl

[3] N. M. Korobov, Number-theoretic methods in approximate analysis, 2nd ed., Moscow Center for Continuous Mathematical Education, Moscow, 2004, 285 pp. (Russian) | MR | Zbl

[4] Hua Loo Keng and Wang Yuan, Applications of number theory to numerical analysis, Springer-Verlag, Berlin–New York; Kexue Chubanshe (Science Press), Beijing, 1981, ix+241 pp. | DOI | MR | Zbl

[5] H. Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conf. Ser. in Appl. Math., 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992, vi+241 pp. | DOI | MR | Zbl

[6] H. Niederreiter, “Existence of good lattice points in the sense of Hlawka”, Monatsh. Math., 86:3 (1978/79), 203–219 | DOI | MR | Zbl

[7] G. Larcher, “On the distribution of sequences connected with good lattice points”, Monatsh. Math., 101:2 (1986), 135–150 | DOI | MR | Zbl

[8] V. A. Bykovskii, “The discrepancy of the Korobov lattice points”, Izv. Ross. Akad. Nauk Ser. Mat., 76:3 (2012), 19–38 ; English transl. in Izv. Math., 76:3 (2012), 446–465 | DOI | MR | Zbl | DOI

[9] W. M. Schmidt, “Irregularities of distribution. VII”, Acta Arith., 21 (1972), 45–50 | DOI | MR | Zbl

[10] D. Bilyk, M. T. Lacey and A. Vagharshakyan, “On the small ball inequality in all dimensions”, J. Funct. Anal., 254:9 (2008), 2470–2502 | DOI | MR | Zbl

[11] N. S. Bakhvalov, “Approximate computation of multiple integrals”, Vestn. Moskov. Univ. Ser. Mat. Mekh. Astronom. Fiz. Khim., 1959, no. 4, 3–18 (Russian) | MR | Zbl

[12] E. Hlawka, “Uniform distribution modulo 1 and numerical analysis”, Compositio Math., 16 (1964), 92–105 | MR | Zbl

[13] S. K. Zaremba, “Good lattice points modulo composite numbers”, Monatsh. Math., 78 (1974), 446–460 | DOI | MR | Zbl

[14] M. G. Rukavishnikova, “The law of large numbers for the sum of the partial quotients of a rational number with fixed denominator”, Mat. Zametki, 90:3 (2011), 431–444 ; English transl. in Math. Notes, 90:3 (2011), 418–430 | DOI | MR | Zbl | DOI

[15] N. G. Moshchevitin, “Sets of the form $\mathscr A+\mathscr B$ and finite continued fractions”, Mat. Sb., 198:4 (2007), 95–116 ; English transl. in Sb. Math., 198:4 (2007), 537–557 | DOI | MR | Zbl | DOI

[16] A. A. Illarionov, “A probability estimate for the discrepancy of Korobov lattice points”, Mat. Sb., 212:11 (2021), 73–88 ; English transl. in Sb. Math., 212:11 (2021), 1571–1587 | DOI | MR | Zbl | DOI

[17] J. Beck, “Probabilistic Diophantine approximation. I. Kronecker sequences”, Ann. of Math. (2), 140:2 (1994), 449+451–502 | DOI | MR | Zbl

[18] J. W. S. Cassels, An introduction to the geometry of numbers, Grundlehren Math. Wiss., 99, Springer-Verlag, Berlin–Göttingen–Heidelberg, 1959, viii+344 pp. | DOI | MR | Zbl