On Combinatorial Properties of Greedy Wasserstein Minimization

Abstract

We discuss a phenomenon where Optimal Transport leads to a remarkable amount of combinatorial regularity. Consider infinite sequences $(x_k{)}_{k=1}^{\infty }$ in $[0,1]$ constructed in a greedy manner: given $x_1,\dots ,x_n$, the new point $x_{n+1}$ is chosen so as to minimize the Wasserstein distance $W_2$ between the empirical measure of the $n+1$ points and the Lebesgue measure, $$x_{n+1}=\arg \underset{x}{\min }{W}_2\left(\frac{1}{n+1}\sum _{k=1}^n{\delta }_{x_k}+\frac{{\delta }_x}{n+1},dx\right).$$ This leads to fascinating sequences (for example: $x_{n+1}=(2k+1)/(2n+2)$ for some $k\in \mathbb{Z}$) which coincide with sequences recently introduced by Ralph Kritzinger in a different setting. Numerically, the regularity of these sequences rival the best known constructions from Combinatorics or Number Theory. We prove a regularity result below the square root barrier.