On combinatorial properties of greedy Wasserstein minimization (Q6140904)

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 \textit{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 [\textit{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 reviewed paper, 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 \textit{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 \textit{square-root barrier}. In other words, it shows that Kritzinger sequences are more regular than i.i.d. uniformly distributed random variables.