RUS  ENG
Full version
VIDEO LIBRARY

Memorial Conference on Analytic Number Theory and Applications Dedicated to the 130th Anniversary of I. M. Vinogradov
September 14, 2021 12:00, Moscow, Steklov Mathematical Institute, 8, Gubkina str, room 110 + online


The discrepancy of the Korobov-Hlawka sequences

A. A. Illarionov

Khabarovsk Division of the Institute for Applied Mathematics, Far Eastern Branch, Russian Academy of Sciences



Abstract: Let $N\in \Bbb N$, $a=(a_1,\ldots,a_s)\in \Bbb Z^s$. Korobov (1959) and Hlawka (1962) suggested independently using points of the form
$$ x^{(k)} = \left( \left\{a_1k/N\right\},\ldots, \left\{a_sk/N\right\} \right)\quad (k=1,\ldots,N) $$
as nodes of multidimensional quadrature formulae. This idea gave rise to a whole direction on the borders of number theory and computational mathematics.
Let $D_N(a)$ be the discrepancy of the sequence $\left\{x^{(k)}\right\}_{k=1}^N$ (from uniform distribution). From the theoretical and the practical points of view, it is reasonable to construct low-discrepancy sequences. If $s=1$, $\text{gcd}(a_1,N)=1$, then $D_N(a_1)= 1/N$. Let $s\ge 2$. The best upper bound is
$$ \mathfrak{D}^{(s)}_{N} \equiv \min_{a\in\Bbb Z_N^s} D_N(a) \underset{s}\ll \frac{\ln^{s-1} N}{N} \ln\ln N $$
(Bykovskii, 2012). It is possible that
$$ \mathfrak{D}^{(s)}_{N} \underset{s} \gg \frac{\ln^{s-1} N}{N}. $$
If $s=2$, then this inequality follows from Schmidt's Theorem. If $s\ge 3$, then the best lower bound is
$$ \mathfrak{D}^{(s)}_{N}\underset{s}\gg\frac{(\ln N)^{(s-1)/2 + \eta(s)}}{N} $$
(Bilyk, Lacey, Vagharshakyan; 2008), where $\eta(s)$ is a positive constant depending only on $s$.
We obtain some results related to the distribution of the sequence $\left\{x^{(k)}\right\}_{k=1}^N$. In particular, we prove that
$$ \frac{\ln^{s-1}N}{N\ln\ln N} \underset{s} \ll D_N(a) \underset{s}\ll \frac{\ln^{s-1}N}{N}\ln\ln N $$
for “almost all” $a\in (\Bbb Z_N^*)^s$, where $\Bbb Z^*_N$ is a reduced residue system modulo $N$.


© Steklov Math. Inst. of RAS, 2024