Date of Award

Spring 2021

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Mathematics

First Advisor

Steinerberger, Stefan

Abstract

The purpose of this dissertation will be to examine various ways of measuring how uniformly distributed a sequence of points on compact manifolds and finite combinatorial graphs can be, providing bounds and novel explicit algorithms to pick extremely uniform points, as well as connecting disparate branches of mathematics such as Number Theory and Optimal Transport. Chapter 1 sets the stage by introducing some of the fundamental ideas and results that will be used consistently throughout the thesis: we develop and establish Weyl's Theorem, the definition of discrepancy, LeVeque's Inequality, the Erdős-Turán Inequality, Koksma-Hlawka Inequality, and Schmidt's Theorem about Irregularities of Distribution. Chapter 2 introduces the Monge-Kantorovich transport problem with special emphasis on the Benamou-Brenier Formula (from 2000) and Peyre's inequality (from 2018). Chapter 3 explores Peyre's Inequality in further depth, considering how specific bounds on the Wasserstein distance between a point measure and the uniform measure may be obtained using it, in particular in terms of the Green's function of the Laplacian on a manifold. We also show how a smoothing procedure can be applied by propagating the heat equation on probability mass in order to get stronger bounds on transport distance using well-known properties of the heat equation. In Chapter 4, we turn to the primary question of the thesis: how to select points on a space which are as uniformly distributed as possible. We consider various diverse approaches one might attempt: an ergodic approach iterating functions with good mixing properties; a dyadic approach introduced in a 1975 theorem of Kakutani on proportional splittings on intervals; and a completely novel potential theoretic approach, assigning energy to point configurations and greedily minimizing the total potential arising from pair-wise point interactions. Such energy minimization questions are certainly not new, in the static setting--physicist Thomson posed the question of how to minimize the potential of electrons on a sphere as far back as 1904. However, a greedy approach to uniform distribution via energy minimization is novel, particularly through the lens of Wasserstein, and yields provably Wasserstein-optimal point sequences using the Green's function of the Laplacian as our energy function on manifolds of dimension at least 3 (with dimension 2 losing at most a square root log factor from the optimal bound). We connect this to known results from Graham, Pausinger, and Proinov regarding best possible uniform bounds on the Wasserstein 2-distance of point sequences in the unit interval. We also present many open questions and conjectures on the optimal asymptotic bounds for total energy of point configurations and the growth of the total energy function as points are added, motivated by numerical investigations that display remarkably well-behaved qualities in the dynamical system induced by greedy minimization. In Chapter 5, we consider specific point sequences and bounds on the transport distance from the point measure they generate to the uniform measure. We provide provably optimal rates for the van der Corput sequence, the Kronecker sequence, regular grids and the measures induced by quadratic residues in a field of prime order. We also prove an upper bound for higher degree monomial residues in fields of prime order, and conjecture this to be optimal. In Chapter 6, we consider numerical integration error bounds over Lipschitz functions, asking how closely we can estimate the integral of a function by averaging its values at finitely many points. This is a rather classical question that was answered completely by Bakhalov in 1959 and has since become a standard example (`the easiest case which is perfectly understood'). Somewhat surprisingly perhaps, we show that the result is not sharp and improve it in two ways: by refining the function space and by proving that these results can be true uniformly along a subsequence. These bounds refine existing results that were widely considered to be optimal, and we show the intimate connection between transport distance and integration error. Our results are new even for the classical discrete grid. In Chapter 7, we study the case of finite graphs--we show that the fundamental question underlying this thesis can also be meaningfully posed on finite graphs where it leads to a fascinating combinatorial problem. We show that the philosophy introduced in Chapter 4 can be meaningfully adapted and obtain a potential-theoretic algorithm that produces such a sequence on graphs. We show that, using spectral techniques, we are able to obtain empirically strong bounds on the 1-Wasserstein distance between measures on subsets of vertices and the uniform measure, which for graphs of large diameter are much stronger than the trivial diameter bound.

COinS