×

On combinatorial properties of greedy Wasserstein minimization. (English) Zbl 1542.11066

The theory of irregularities of distribution investigates how regular the distribution of the first \(n\) points of an infinite sequence can be. Classical examples of low discrepancy sequences are known to be more regularly distributed than sequences of i.i.d. uniformly distributed random points. While sequences in \([0,1]\) are very well understood by now, the problem of irregularities of distribution in dimensions \(d \geq 2\) is challenging.
Motivated by this the author initiated [S. Steinerberger, Monatsh. Math. 191, No. 3, 639–655 (2020; Zbl 1471.11222)] the study of new constructions of sequences with very regular distribution, i.e., given \(x_1, \ldots, x_n\), the next point, \(x_{n+1}\), is chosen so as to minimize a particular energy functional. In the paper under review, the greedy construction is based on minimizing the Wasserstein distance between the empirical measure of the first \(n\) points and the Lebesgue measure. The author points out several astonishing properties of such sequences, and, in particular, shows (Theorem 1) that this general construction can reproduce a sequence introduced by R. Kritzinger [Mosc. J. Comb. Number Theory 11, No. 3, 215–236 (2022; Zbl 1511.11069)].
This connection is interesting in two ways. First, the Kritzinger sequence is a greedy sequence that chooses its next point with the aim of minimizing the \(L_2\)-discrepancy, which is one of the main measures for the irregularity of distribution of sequences. Second, the author derives a new regularity statement for Kritzinger sequences in Theorem 2 breaking, what is known to be, the square-root barrier. In other words, it shows that Kritzinger sequences are more regular than i.i.d. uniformly distributed random variables.

MSC:

11K38 Irregularities of distribution, discrepancy
11K06 General theory of distribution modulo \(1\)
49Q99 Manifolds and measure-geometric topics

References:

[1] van Aardenne-Ehrenfest, T., Proof of the impossibility of a just distribution of an infinite sequence over an interval. Proc. K. Ned. Akad. Wet., 3-8 (1945) · Zbl 0060.13002
[2] Beck, J., A two-dimensional van Aardenne-Ehrenfest theorem in irregularities of distribution. Compos. Math., 3, 269-339 (1989) · Zbl 0691.10041
[3] Beck, J.; Chen, W., Irregularities of Distribution. Cambridge Tracts in Mathematics (1987), Cambridge University Press · Zbl 0617.10039
[4] Beck, J., The modulus of polynomials with zeros on the unit circle: a problem of Erdos. Ann. Math., 609-651 (1991) · Zbl 0747.11031
[5] Bilyk, D.; Lacey, M., On the small ball inequality in three dimensions. Duke Math. J., 1, 81-115 (2008) · Zbl 1202.42007
[6] Bilyk, D.; Lacey, M.; Vagharshakyan, A., On the small ball inequality in all dimensions. J. Funct. Anal., 9, 2470-2502 (2008) · Zbl 1214.42024
[7] Brown, L.; Steinerberger, S., Positive-definite functions, exponential sums and the Greedy algorithm: a curious phenomenon. J. Complex. (2020) · Zbl 1456.11138
[8] Brown, L.; Steinerberger, S., On the Wasserstein distance between classical sequences and the Lebesgue measure. Trans. Am. Math. Soc., 8943-8962 (2020) · Zbl 1465.11175
[9] Chazelle, B., The Discrepancy Method. Randomness and Complexity (2000), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0960.65149
[10] van der Corput, J., Verteilungsfunktionen I. Proc. Akad. Wet., 813-821 (1935) · Zbl 0012.34705
[11] van der Corput, J., Verteilungsfunktionen II. Proc. Akad. Wet., 1058-1068 (1935) · JFM 61.0203.01
[12] Dick, J.; Pillichshammer, F., Digital Nets and Sequences. Discrepancy Theory and Quasi-Monte Carlo Integration (2010), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1282.65012
[13] Drmota, M.; Tichy, R., Sequences, Discrepancies and Applications. Lecture Notes in Mathematics (1997), Springer-Verlag: Springer-Verlag Berlin · Zbl 0877.11043
[14] Erdős, P., Some unsolved problems. Mich. Math. J., 291-300 (1957) · Zbl 0081.00102
[15] Graham, C., Irregularity of distribution in Wasserstein distance. J. Fourier Anal. Appl., 1-21 (2020)
[16] Kuipers, L.; Niederreiter, H., Uniform Distribution of Sequences. Pure and Applied Mathematics (1974), Wiley-Interscience: Wiley-Interscience New York-London-Sydney · Zbl 0281.10001
[17] Kritzinger, R., Uniformly distributed sequences generated by a greedy minimization of the \(L_2\) discrepancy · Zbl 1511.11069
[18] Larcher, G.; Puchhammer, F., An improved bound for the star discrepancy of sequences in the unit interval. Unif. Distrib. Theory, 1-14 (2016) · Zbl 1455.11110
[19] Ostromoukhov, V., Recent progress in improvement of extreme discrepancy and star discrepancy of one-dimensional sequences, 561-572 · Zbl 1228.11119
[20] Pausinger, F., Greedy energy minimization can count in binary: point charges and the van der Corput sequence. Ann. Mat. Pura Appl., 165-186 (2021) · Zbl 1483.11155
[21] Roth, K. F., On irregularities of distribution. Mathematika, 73-79 (1954) · Zbl 0057.28604
[22] Schmidt, W., Irregularities of distribution. VII. Acta Arith., 45-50 (1972) · Zbl 0244.10035
[23] Steinerberger, S., A nonlocal functional promoting low-discrepancy point sets. J. Complex. (2019) · Zbl 1423.49002
[24] Steinerberger, S., Dynamically defined sequences with small discrepancy. Monatshefte Math., 639-655 (2020) · Zbl 1471.11222
[25] Steinerberger, S., Polynomials with zeros on the unit circle: regularity of Leja sequences. Mathematika, 553-568 (2021) · Zbl 1527.30005
[26] Steinerberger, S., Wasserstein distance, Fourier series and applications. Monatshefte Math., 305-338 (2021) · Zbl 1457.60005
[27] Steinerberger, S., A Wasserstein inequality and minimal Green energy on compact manifolds. J. Funct. Anal. (2021) · Zbl 1494.31016
[28] Vallender, S., Calculation of the Wasserstein distance between probability distributions on the line. Theory Probab. Appl., 435 (1974)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.