Search

The Kaczmarz method is a way to iteratively solve a linear system of equations $Ax = b$. One interprets the solution $x$ as the point where hyperplanes intersect and then iteratively projects an approximate solution onto these hyperplanes to get better and better approximations. We note a somewhat related idea: one could take two random hyperplanes and project one into the orthogonal complement of the other. This leads to a sequence of linear systems $A^{(k)} x = b^{(k)}$ which is fast to compute, preserves the original solution and whose small singular values grow like $\sigma_{\ell}(A^{(k)}) \sim \exp(k/n^2) \cdot \sigma_{\ell}(A)$.

For any irrational $\alpha > 0$ and any initial value $z_{-1} \in \mathbb{C}$, we define a sequence of complex numbers $(z_n)_{n=0}^{\infty}$ as follows: $z_n$ is $z_{n-1} + e^{2 \pi i \alpha n}$ or $z_{n-1} - e^{2 \pi i \alpha n}$, whichever has the smaller absolute value. If both numbers have the same absolute value, the sequence terminates at $z_{n-1}$ but this happens rarely. This dynamical system has astonishingly intricate behavior: the choice of signs in $z_{n-1} \pm e^{2 \pi i \alpha n}$ appears to eventually become periodic (though the period can be large). We prove that if one observes periodic signs for a sufficiently long time (depending on $z_{-1}, \alpha$), the signs remain periodic for all time. The surprising complexity of the system is illustrated through examples., Comment: 19 pages, 9 figures

Let $\Omega \subset \mathbb{R}^d$ be a bounded domain and let $\lambda_1, \lambda_2, \dots$ denote the sequence of eigenvalues of the Laplacian subject to Dirichlet boundary conditions. We consider inequalities for $\lambda_n$ that are independent of the domain $\Omega$. A well--known such inequality follows from the Berezin--Li--Yau approach. The purpose of this paper is to point out a certain degree of flexibility in the Li--Yau approach. We use it to prove a new type of two-point inequality which are strictly stronger than what is implied by Berezin-Li-Yau itself. For example, when $d=2$, one has $ 2 \lambda_n + \lambda_{2n} \geq 10 \pi n/|\Omega|.$

We prove that the existence of infinitely many $(m_k, n_k) \in \mathbb{N}^2$ such that the difference of harmonic numbers $H_{m_k} - H_{n_k}$ approximates 1 well $$ \lim_{k \rightarrow \infty} \left| \sum_{\ell = n}^{m_k} \frac{1}{\ell} - 1 \right|\cdot n_k^2 = 0.$$ This answers a question of Erd\H{o}s and Graham. The construction uses asymptotics for harmonic numbers, the precise nature of the continued fraction expansion of $e$ and a suitable rescaling of a subsequence of convergents. We also prove a quantitative rate by appealing to techniques of Heilbronn, Danicic, Harman, Hooley and others regarding $\min_{1 \leq n \leq N} \min_{m \in \mathbb{N}}\| n^2 \theta - m\|$.

We prove the existence of a positive semidefinite matrix $A \in \mathbb{R}^{n \times n}$ such that any decomposition into rank-1 matrices has to have factors with a large $\ell^1-$norm, more precisely $$ \sum_{k} x_k x_k^*=A \quad \implies \quad \sum_k \|x_k\|^2_{1} \geq c \sqrt{n} \|A\|_{1},$$ where $c$ is independent of $n$. This provides a lower bound for the Balan--Jiang matrix problem. The construction is probabilistic.

We consider the problem of finding good low rank approximations of symmetric, positive-definite $A \in \mathbb{R}^{n \times n}$. Chen-Epperly-Tropp-Webber showed, among many other things, that the randomly pivoted partial Cholesky algorithm that chooses the $i-$th row with probability proportional to the diagonal entry $A_{ii}$ leads to a universal contraction of the trace norm (the Schatten 1-norm) in expectation for each step. We show that if one chooses the $i-$th row with likelihood proportional to $A_{ii}^2$ one obtains the same result in the Frobenius norm (the Schatten 2-norm). Implications for the greedy pivoting rule and pivot selection strategies are discussed.

Erd\H{o}s and Graham proposed to determine the number of subsets $S \subseteq \left\{1,2,\dots,n\right\}$ with $\sum_{s \in S} 1/s = 1$ and asked, among other things, whether that number could be as large as $2^{n - o(n)}$. We show that the number of subsets $S \subseteq \left\{1,2,\dots,n\right\}$ with $\sum_{s \in S} 1/s \leq 1$ is smaller than $2^{0.93n}$.

Given a finite, simple, connected graph $G=(V,E)$ with $|V|=n$, we consider the associated graph Laplacian matrix $L = D - A$ with eigenvalues $0 = \lambda_1 < \lambda_2 \leq \dots \leq \lambda_n$. One can also consider the same graph equipped with positive edge weights $w:E \rightarrow \mathbb{R}_{> 0}$ normalized to $\sum_{e \in E} w_e = |E|$ and the associated weighted Laplacian matrix $L_w$. We say that $G$ is conformally rigid if constant edge-weights maximize the second eigenvalue $\lambda_2(w)$ of $L_w$ over all $w$, and minimize $\lambda_n(w')$ of $L_{w'}$ over all $w'$, i.e., for all $w,w'$, $$ \lambda_2(w) \leq \lambda_2(1) \leq \lambda_n(1) \leq \lambda_n(w').$$ Conformal rigidity requires an extraordinary amount of symmetry in $G$. Every edge-transitive graph is conformally rigid. We prove that every distance-regular graph, and hence every strongly-regular graph, is conformally rigid. Certain special graph embeddings can be used to characterize conformal rigidity. Cayley graphs can be conformally rigid but need not be, we prove a sufficient criterion. We also find a small set of conformally rigid graphs that do not belong into any of the above categories; these include the Hoffman graph, the crossing number graph 6B and others. Conformal rigidity can be certified via semidefinite programming, we provide explicit examples.

Inspired by the bad scientist who keeps repeating an experiment 20 times to get a single outcome with $p < 0.05$, we consider matrices $A \in \mathbb{R}^{n \times n}$ whose rows are normalized in $\ell^2$ and for which $2^{-n}\sum_{x \in \left\{-1,1\right\}^n} \|Ax\|_{\ell^{\infty}}$ is large. They correspond to affine transformations of the discrete unit cube to points with, on average, at least one large coordinate. Such matrices can be seen as a collection of fair tests on a fair coin where at least one outcome is typically atypical. We prove that, as $n \rightarrow \infty$, the quantity can scale as $$ \max_{A \in \mathbb{R}^{n \times n}} \frac{1}{2^{n}}\sum_{x \in \left\{-1,1\right\}^n} \|Ax\|_{\ell^{\infty}} = (1+o(1)) \cdot \sqrt{2\log{n}}.$$ We also present candidate maximizers up to dimension $n \leq 8$ which appear to be highly structured and have nice closed-form solutions.

Let $k \in \mathbb{N}$ and suppose we are given $k$ integers $1 \leq a_1, \dots, a_k \leq n$. If $\sqrt{a_1} + \dots + \sqrt{a_k}$ is not an integer, how close can it be to one? When $k=1$, the distance to the nearest integer is $\gtrsim n^{-1/2}$. Angluin-Eisenstat observed the bound $\gtrsim n^{-3/2}$ when $k=2$. We prove there is a universal $c>0$ such that, for all $k \geq 2$, there exists a $c_k > 0$ and $k$ integers in $\left\{1,2,\dots, n\right\}$ with $$ 0 <\|\sqrt{a_1} + \dots + \sqrt{a_k} \| \leq c_k\cdot n^{-c \cdot k^{1/3}},$$ where $\| \cdot \|$ denotes the distance to the nearest integer. This is a case of the square-root sum problem in numerical analysis where the usual cancellation constructions do not apply: even for $k=3$, constructing explicit examples of integers whose square root sum is nearly an integer appears to be nontrivial.

We study sequences $(x_n)_{n=1}^{\infty}$ of reals given by $x_{n+1} = f(x)$ where $$f(x) = x - \sum_{i=1}^{m} \frac{\alpha_i}{x - \beta_i},$$ where $\alpha_1, \dots, \alpha_m \in \mathbb{R}_{>0}$ and $\beta_1, \dots, \beta_m \in \mathbb{R}$ are arbitrary. A special case is $x_{n+1} = x_n - 1/x_n$ due to Ronald Graham for which Chamberland \& Martelli showed that the dynamics is chaotic (topologically conjugate to the doubling map). We prove that the general nonlinear recursion, despite being potentially chaotic, is effective at ensuring that most iterates end up close to one of the poles $\beta_i$ relatively quickly. More precisely, for a positive proportion of initial values $x \in \mathbb{R}$, the sequence gets very close (distance $\lesssim |x|^{-1}$) to one of the poles $\beta_i$ within a relatively small ($\lesssim x^2$) number of iteration steps.

We consider Laplacian eigenfunctions on a domain $\Omega \subset \mathbb{R}^d$. Under Neumann boundary conditions, the first eigenfunction is constant and the others have mean value 0. The situation is different for Dirichlet boundary conditions: on generic domains, one would expect that every eigenfunction has nonzero mean value. The other extreme is the ball in $\mathbb{R}^d$, where among the first $n$ eigenfunctions only $\sim n^{1/d}$ have a mean value different from zero. We prove that in any domain~$\Omega$, among the first $n$ Dirichlet eigenfunctions at least $ (\log{n})^{-1/2d} n^{1/2d} $ do \textit{not} have vanishing mean value.

We study optimal transport plans from $m$ equally weighted points (with weights $1/m$) to $n$ equally weighted points (with weights $1/n$). The Birkhoff-von Neumann Theorem implies that if $m=n$, then the optimal transport plan can be realized by a bijective map: the mass from each $x_i$ is sent to a unique $y_j$. This is impossible when $m \neq n$, however, a certain degree of rigidity prevails. We prove, assuming w.l.o.g. $m < n$, that for generic transport costs the optimal transport plan sends mass from each source $x_i$ to $n/m \leq \mbox{different targets} \leq n/m + m-1$. Moreover, the average target receives mass from $\leq 1 + m/\sqrt{n}$ sources. Stronger results might be true: in experiments, one observes that each source tends to distribute its mass over roughly $n/m +c$ different targets where $c$ appears to be rather small., Comment: We discovered that the result is implied by a known fact (details on page 1). This manuscript is not submitted anywhere

The celebrated Almgren monotonicity formula for harmonic functions $u:\mathbb{R}^n \rightarrow \mathbb{R}$ says that its $L^2-$energy concentrated on a sphere of radius $r$, when measured in a suitable sense, is non-decreasing: if $u$ oscillates at a certain scale, it has even larger oscillations at a larger scale. We prove a discrete analogue of the Almgren monotonicity formula for harmonic functions on infinite combinatorial graphs $G=(V,E)$. Some applications are discussed.

We introduce Gradient Flow Aggregation (GFA), a random growth model. Given a set of existing particles $\left\{x_1, \dots, x_n\right\} \subset \mathbb{R}^2$, a new particle arrives from a random direction at $\infty$ and flows in direction $\nabla E$ where $$ E(x) = \sum_{i=1}^{n} \frac{1}{\|x-x_i\|^{\alpha}} \qquad \mbox{where} ~0 < \alpha < \infty.$$ The case $\alpha = 0$ will refer to the logarithmic energy $- \sum\log \|x-x_i\|$. Particles stop once they are at distance 1 of one of the existing particles at which point they are added to the set and remain fixed for all time. We prove, under a non-degeneracy assumption, a Beurling-type estimate which, via Kesten's method, can be used to deduce sub-ballistic growth for $0 \leq \alpha < 1$ $$\mbox{diam}(\left\{x_1, \dots, x_n\right\}) \leq c_{\alpha} \cdot n^{\frac{3 \alpha +1}{2\alpha + 2}}.$$ This is optimal when $\alpha =0$. The case $\alpha = 0$ leads to a `round' full-dimensional tree. The larger the value of $\alpha$ the sparser the tree. Some instances of the higher-dimensional setting are also discussed.

Let $\Omega \subset \mathbb{R}^d$ and consider the magnetic Laplace operator given by $ H(A) = \left(- i\nabla - A(x)\right)^2$, where $A:\Omega \rightarrow \mathbb{R}^d$, subject to Dirichlet eigenfunction. This operator can, for certain vector fields $A$, have eigenfunctions $H(A) \psi = \lambda \psi$ that are highly localized in a small region of $\Omega$. The main goal of this paper is to show that if $|\psi|$ assumes its maximum in $x_0 \in \Omega$, then $A$ behaves `almost' like a conservative vector field in a $1/\sqrt{\lambda}-$neighborhood of $x_0$ in a precise sense: we expect localization in regions where $\left|\mbox{curl} A \right|$ is small. The result is illustrated with numerical examples.

A celebrated result of Beck shows that for any set of $N$ points on $\mathbb{S}^d$ there always exists a spherical cap $B \subset \mathbb{S}^d$ such that number of points in the cap deviates from the expected value $\sigma(B) \cdot N$ by at least $N^{1/2 - 1/2d}$, where $\sigma$ is the normalized surface measure. We refine the result and show that, when $d \not\equiv 1 ~(\mbox{mod}~4)$, there exists a (small and very specific) set of real numbers such that for every $r>0$ from the set one is always guaranteed to find a spherical cap $C_r$ with the given radius $r$ for which the result holds. The main new ingredient is a generalization of the notion of badly approximable numbers to the setting of Gegenbauer polynomials: these are fixed numbers $ x \in (-1,1)$ such that the sequence of Gegenbauer polynomials $(C_n^{\lambda}(x))_{n=1}^{\infty}$ avoids being close to 0 in a precise quantitative sense.

We consider random lines in $\mathbb{R}^3$ (random with respect to the kinematic measure) and how they intersect $\mathbb{S}^2$. It is known that the entry point and the exit point behave like \textit{independent} uniformly distributed random variables. We give a new proof using bilinear integral geometry and use this approach to show that this property is extremely rare: if $K \subset \mathbb{R}^n$ is a bounded, convex domain with smooth boundary with this property (i.e., the intersection points with a random line are independent), then $n=3$ and $K$ is a ball.

We consider the optimal transport problem between a set of $n$ red points and a set of $n$ blue points subject to a concave cost function such as $c(x,y) = \|x-y\|^{p}$ for $0< p < 1$. Our focus is on a particularly simple matching algorithm: match the closest red and blue point, remove them both and repeat. We prove that it provides good results in any metric space $(X,d)$ when the cost function is $c(x,y) = d(x,y)^{p}$ with $0 < p < 1/2$. Empirically, the algorithm produces results that are remarkably close to optimal -- especially as the cost function gets more concave; this suggests that greedy matching may be a good toy model for Optimal Transport for very concave transport cost.

We propose an approach to graph sparsification based on the idea of preserving the smallest $k$ eigenvalues and eigenvectors of the Graph Laplacian. This is motivated by the fact that small eigenvalues and their associated eigenvectors tend to be more informative of the global structure and geometry of the graph than larger eigenvalues and their eigenvectors. The set of all weighted subgraphs of a graph $G$ that have the same first $k$ eigenvalues (and eigenvectors) as $G$ is the intersection of a polyhedron with a cone of positive semidefinite matrices. We discuss the geometry of these sets and deduce the natural scale of $k$. Various families of graphs illustrate our construction., Comment: 34 pages, 17 figures, 3 tables

We prove that among all 1-periodic configurations $\Gamma$ of points on the real line $\mathbb{R}$ the quantities $$ \min_{x \in \mathbb{R}} \sum_{\gamma \in \Gamma} e^{- \pi \alpha (x - \gamma)^2} \quad \text{and} \quad \max_{x \in \mathbb{R}} \sum_{\gamma \in \Gamma} e^{- \pi \alpha (x - \gamma)^2}$$ are maximized and minimized, respectively, if and only if the points are equispaced and whenever the number of points $n$ per period is sufficiently large (depending on $\alpha$). This solves the polarization problem for periodic configurations with a Gaussian weight on $\mathbb{R}$ for large $n$. The first result is shown using Fourier series. The second result follows from work of Cohn and Kumar on universal optimality and holds for all $n$ (independent of $\alpha$)., Comment: 32 pages, 2 figures, 49 references; to appear in International Mathematics Research Notices (IMRN)

We consider Erd\H{o}s-R\'enyi graphs $G(n,p)$ for $0 < p < 1$ fixed and $n \rightarrow \infty$ and study the expected number of steps, $H_{wv}$, that a random walk started in $w$ needs to first arrive in $v$. A natural guess is that an Erd\H{o}s-R\'enyi random graph is so homogeneous that it does not really distinguish between vertices and $H_{wv} = (1+o(1)) n$. L\"owe-Terveer established a CLT for the Mean Starting Hitting Time suggesting $H_{w v} = n \pm \mathcal{O}(\sqrt{n})$. We prove the existence of a strong concentration phenomenon: $H_{w v}$ is given, up to a very small error of size $\lesssim \sqrt{\log{n}}/\sqrt{n}$, by an explicit simple formula involving only the total number of edges $|E|$, the degree of $v$ and the distance $d(v,w)$., Comment: 2 figures

We investigate the behavior of a greedy sequence on the sphere $\mathbb{S}^d$ defined so that at each step the point that minimizes the Riesz $s$-energy is added to the existing set of points. We show that for $0

Let $G=(V,E)$ be a finite, combinatorial graph. We define a notion of curvature on the vertices $V$ via the inverse of the resistance distance matrix. We prove that this notion of curvature has a number of desirable properties. Graphs with curvature bounded from below by $K>0$ have diameter bounded from above. The Laplacian $L=D-A$ satisfies a Lichnerowicz estimate, there is a spectral gap $\lambda_2 \geq 2K$. We obtain matching two-sided bounds on the maximal commute time between any two vertices in terms of $|E| \cdot |V|^{-1} \cdot K^{-1}$. Moreover, we derive quantitative rates for the mixing time of the corresponding Markov chain and prove a general equilibrium result., Comment: 15 pages, 2 figures

The trigonometric monomial $\cos(\left\langle k, x \right\rangle)$ on $\mathbb{T}^d$, a harmonic polynomial $p: \mathbb{S}^{d-1} \rightarrow \mathbb{R}$ of degree $k$ and a Laplacian eigenfunction $-\Delta f = k^2 f$ have root in each ball of radius $\sim \|k\|^{-1}$ or $\sim k^{-1}$, respectively. We extend this to linear combinations and show that for any trigonometric polynomials on $\mathbb{T}^d$, any polynomial $p \in \mathbb{R}[x_1, \dots, x_d]$ restricted to $\mathbb{S}^{d-1}$ and any linear combination of global Laplacian eigenfunctions on $ \mathbb{R}^d$ with $d \in \left\{2,3\right\}$ the same property holds for any ball whose radius is given by the sum of the inverse constituent frequencies. We also refine the fact that an eigenfunction $- \Delta \phi = \lambda \phi$ in $\Omega \subset \mathbb{R}^n$ has a root in each $B(x, \alpha_n \lambda^{-1/2})$ ball: the positive and negative mass in each $B(x,\beta_n \lambda^{-1/2})$ ball cancel when integrated against $\|x-y\|^{2-n}$.

The Polya-Szeg\H{o} inequality in $\mathbb{R}^n$ states that, given a non-negative function $f:\mathbb{R}^{n} \rightarrow \mathbb{R}_{}$, its spherically symmetric decreasing rearrangement $f^*:\mathbb{R}^{n} \rightarrow \mathbb{R}_{}$ is `smoother' in the sense of $\| \nabla f^*\|_{L^p} \leq \| \nabla f\|_{L^p}$ for all $1 \leq p \leq \infty$. We study analogues on the lattice grid graph $\mathbb{Z}^2$. The spiral rearrangement is known to satisfy the Polya-Szeg\H{o} inequality for $p=1$, the Wang-Wang rearrangement satisfies it for $p=\infty$ and no rearrangement can satisfy it for $p=2$. We develop a robust approach to show that both these rearrangements satisfy the Polya-Szeg\H{o} inequality up to a constant for all $1 \leq p \leq \infty$. In particular, the Wang-Wang rearrangement satisfies $\| \nabla f^*\|_{L^p} \leq 2^{1/p} \| \nabla f\|_{L^p}$ for all $1 \leq p \leq \infty$. We also show the existence of (many) rearrangements on $\mathbb{Z}^d$ such that $\| \nabla f^*\|_{L^p} \leq c_d \cdot \| \nabla f\|_{L^p}$ for all $1 \leq p \leq \infty$.

We consider the following game that has been used as a way of testing claims of extrasensory perception (ESP). One is given a deck of $mn$ cards comprised of $n$ distinct types each of which appears exactly $m$ times: this deck is shuffled and then cards are discarded from the deck one at a time from top to bottom. At each step, a player (whose psychic powers are being tested) tries to guess the type of the card currently on top, which is then revealed to the player before being discarded. We study the expected number $S_{n,m}$ of correct predictions a player can make: one could always guess the exact same type of card which shows that one can achieve $S_{n,m}>m$. We prove that the optimal (non-psychic) strategy is just slightly better than that and find the first order correction when $n, m$ grows at suitable rates. This is very different from the case where $m$ is fixed and $n$ is large (He & Ottolini) and similar to the case of fixed $n$ and $m$ is large (Graham & Diaconis). The case $m=n$ answers a question of Diaconis.

Let $\Omega \subset \mathbb{R}^2$ and let $\mathcal{L} \subset \Omega$ be a one-dimensional set with finite length $L =|\mathcal{L}|$. We are interested in minimizers of an energy functional that measures the size of a set projected onto itself in all directions: we are thus asking for sets that see themselves as little as possible (suitably interpreted). Obvious minimizers of the functional are subsets of a straight line but this is only possible for $L \leq \mbox{diam}(\Omega)$. The problem has an equivalent formulation: the expected number of intersections between a random line and $\mathcal{L}$ depends only on the length of $\mathcal{L}$ (Crofton's formula). We are interested in sets $\mathcal{L}$ that minimize the variance of the expected number of intersections. We solve the problem for convex $\Omega$ and slightly less than half of all values of $L$: there, a minimizing set is the union of copies of the boundary and a line segment.

We study localization properties of low-lying eigenfunctions of magnetic Schr\"odinger operators $$\frac{1}{2} \left(- i\nabla - A(x)\right)^2 \phi + V(x) \phi = \lambda \phi,$$ where $V:\Omega \rightarrow \mathbb{R}_{\geq 0}$ is a given potential and $A:\Omega \rightarrow \mathbb{R}^d$ induces a magnetic field. We extend the Filoche-Mayboroda inequality and prove a refined inequality in the magnetic setting which can predict the points where low-energy eigenfunctions are localized. This result is new even in the case of vanishing magnetic field. Numerical examples illustrate the results.

A property of smooth convex domains $\Omega \subset \mathbb{R}^n$ is that if two points on the boundary $x, y \in \partial \Omega$ are close to each other, then their normal vectors $n(x), n(y)$ point roughly in the same direction and this direction is almost orthogonal to $x-y$ (for `nearby' $x$ and $y$). We prove there exists a constant $c_n > 0$ such that if $\Omega \subset \mathbb{R}^n$ is a bounded domain with $C^1-$boundary $\partial \Omega$, then $$ \int_{\partial \Omega \times \partial \Omega} \frac{\left|\left\langle n(x), y - x \right\rangle \left\langle y - x, n(y) \right\rangle \right| }{\|x - y\|^{n+1}}~d \sigma(x) d\sigma(y) \geq c_n |\partial \Omega|$$ and equality occurs if and only if the domain $\Omega$ is convex.

For any $f: \mathbb{R}^n \rightarrow \mathbb{R}_{\geq 0}$ the symmetric decreasing rearrangement $f^*$ satisfies the Polya-Szeg\H{o} inequality $\| \nabla f^*\|_{L^p} \leq \| \nabla f\|_{L^p}$. The goal of this paper is to establish analogous results in the discrete setting for graphs satisfying suitable conditions. We prove that if the edge-isoperimetric problem on a graph has a sequence of nested minimizers, then this sequence gives rise to a rearrangement satisfying the Polya-Szeg\H{o} inequality in $L^1$. This shows, for example, that a specific rearrangement on the grid graph $\mathbb{Z}^2$, going around the origin in a spiral-like manner, satisfies $\| \nabla f^*\|_{L^1} \leq \| \nabla f\|_{L^1}$. The $L^{\infty}-$case is implied by an optimal ordering condition in vertex-isoperimetry. We use these ideas to prove that the canonical rearrangement on the infinite $d-$regular tree satisfies the Polya-Szeg\H{o} inequality for all $1 \leq p \leq \infty$.

We discuss the propagation of kinetic energy through billiard balls fixed in place along a one-dimensional segment. The number of billiard balls is assumed to be large but finite and we assume kinetic energy propagates following the usual collision laws of physics. Assuming an underlying stochastic mean-field for the expectation and the variance of the kinetic energy, we derive a coupled system of nonlinear partial differential equations assuming a stochastic energy re-distribution procedure. The system of PDEs has a number of interesting dynamical properties some of which are numerically simulated.

Let $\left\{a_1, \dots, a_n\right\} \subset \mathbb{N}$ be a set of positive integers, $a_n$ denoting the largest element, so that for any two of the $2^n$ subsets the sum of all elements is distinct. Erd\H{o}s asked whether this implies $a_n \geq c \cdot 2^n$ for some universal $c>0$. We prove, slightly extending a result of Elkies, that for any $a_1, \dots, a_n \in \mathbb{R}_{>0}$ $$ \int_{\mathbb{R}} \left( \frac{\sin{ x}}{ x} \right)^2 \prod_{i=1}^{n} \cos{( a_i x)^2} dx \geq \frac{\pi}{2^{n}}$$ with equality if and only if all subset sums are $1-$separated. This leads to a new proof of the currently best lower bound $a_n \geq \sqrt{2/\pi n} \cdot 2^n$. The main new insight is that having distinct subset sums and $a_n$ small requires the random variable $X = \pm a_1 \pm a_2 \pm \dots \pm a_n$ to be close to Gaussian in a precise sense.

Modern methods in dimensionality reduction are dominated by nonlinear attraction-repulsion force-based methods (this includes t-SNE, UMAP, ForceAtlas2, LargeVis, and many more). The purpose of this paper is to demonstrate that all such methods, by design, come with an additional feature that is being automatically computed along the way, namely the vector field associated with these forces. We show how this vector field gives additional high-quality information and propose a general refinement strategy based on ideas from Morse theory. The efficiency of these ideas is illustrated specifically using t-SNE on synthetic and real-life data sets., Comment: 23 pages, 17 figures

A central problem in discrepancy theory is the challenge of evenly distributing points $\left\{x_1, \dots, x_n \right\}$ in $[0,1]^d$. Suppose a set is so regular that for some $\varepsilon> 0$ and all $y \in [0,1]^d$ the sub-region $[0,y] = [0,y_1] \times \dots \times [0,y_d]$ contains a number of points nearly proportional to its volume and $$\forall~y \in [0,1]^d \qquad \left| \frac{1}{n} \# \left\{1 \leq i \leq n: x_i \in [0,y] \right\} - \mbox{vol}([0,y]) \right| \leq \varepsilon,$$ how large does $n$ have to be depending on $d$ and $\varepsilon$? We give an elementary proof of the currently best known result, due to Hinrichs, showing that $n \gtrsim d \cdot \varepsilon^{-1}$.

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\min_x ~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.

Let $A \in \mathbb{R}^{n \times n}$ be invertible, $x \in \mathbb{R}^n$ unknown and $b =Ax $ given. We are interested in approximate solutions: vectors $y \in \mathbb{R}^n$ such that $\|Ay - b\|$ is small. We prove that for all $0< \varepsilon <1 $ there is a composition of $k$ orthogonal projections onto the $n$ hyperplanes generated by the rows of $A$, where $$k \leq 2 \log\left(\frac{1}{\varepsilon} \right) \frac{ n}{ \varepsilon^{2}}$$ which maps the origin to a vector $y\in \mathbb{R}^n$ satisfying $\| A y - Ax\| \leq \varepsilon \cdot \|A\| \cdot \| x\|$. We note that this upper bound on $k$ is independent of the matrix $A$. This procedure is stable in the sense that $\|y\| \leq 2\|x\|$. The existence proof is based on a probabilistically refined analysis of the Random Kaczmarz method which seems to achieve this rate when solving for $A x = b$ with high likelihood.

The Agmon estimate shows that eigenfunctions of Schr\"odinger operators, $ -\Delta \phi + V \phi = E \phi$, decay exponentially in the `classically forbidden' region where the potential exceeds the energy level $\left\{x: V(x) > E \right\}$. Moreover, the size of $|\phi(x)|$ is bounded in terms of a weighted (Agmon) distance between $x$ and the allowed region. We derive such a statement on graphs when $-\Delta$ is replaced by the Graph Laplacian $L = D-A$: we identify an explicit Agmon metric and prove a pointwise decay estimate in terms of the Agmon distance.

Let $G=(V,E)$ be a $d$-regular graph on $n$ vertices and let $\mu_0$ be a probability measure on $V$. The act of moving to a randomly chosen neighbor leads to a sequence of probability measures supported on $V$ given by $\mu_{k+1} = A D^{-1} \mu_k$, where $A$ is the adjacency matrix and $D$ is the diagonal matrix of vertex degrees of $G$. Ordering the eigenvalues of $ A D^{-1}$ as $1 = \lambda_1 \geq |\lambda_2| \geq \dots \geq |\lambda_n| \geq 0$, it is well-known that the graphs for which $|\lambda_2|$ is small are those in which the random walk process converges quickly to the uniform distribution: for all initial probability measures $\mu_0$ and all $k \geq 0$, $$ \sum_{v \in V} \left| \mu_k(v) - \frac{1}{n} \right|^2 \leq \lambda_2^{2k}.$$ One could wonder whether this rate can be improved for specific initial probability measures $\mu_0$. We show that if $G$ is regular, then for any $1 \leq \ell \leq n$, there exists a probability measure $\mu_0$ supported on at most $\ell$ vertices so that $$ \sum_{v \in V} \left| \mu_k(v) - \frac{1}{n} \right|^2 \leq \lambda_{\ell+1}^{2k}.$$ The result has applications in the graph sampling problem: we show that these measures have good sampling properties for reconstructing global averages.

Let $x_1, \dots, x_n$ be points in a metric space and define the distance matrix $D \in \mathbb{R}^{n \times n}$ by ${D}_{ij} = d(x_i, x_j)$. The Perron-Frobenius Theorem implies that there is an eigenvector $v \in \mathbb{R}^n_{}$ with non-negative entries associated to the largest eigenvalue. We prove that this eigenvector is nearly constant in the sense that the inner product with the constant vector $\mathbb{1} \in \mathbb{R}^n$ is large $$ \left\langle v, \mathbb{1} \right\rangle \geq \frac{1}{\sqrt{2}} \cdot \| v\|_{\ell^2} \cdot \|\mathbb{1} \|_{\ell^2}$$ and that each entry satisfies $v_i \geq \|v\|_{\ell^2}/\sqrt{4n}$. Both inequalities are sharp.

Gabor phase retrieval is the problem of reconstructing a signal from only the magnitudes of its Gabor transform. Previous findings suggest a possible link between unique solvability of the discrete problem (recovery from measurements on a lattice) and stability of the continuous problem (recovery from measurements on an open subset of $\mathbb{R}^2$). In this paper, we close this gap by proving that such a link cannot be made. More precisely, we establish the existence of functions which break uniqueness from samples without affecting stability of the continuous problem. Furthermore, we prove the novel result that counterexamples to unique recovery from samples are dense in $L^2(\mathbb{R})$. Finally, we develop an intuitive argument on the connection between directions of instability in phase retrieval and certain Laplacian eigenfunctions associated to small eigenvalues., Comment: 36 pages, 6 figures; major revision to improve readability, correction of typos

Let $G=(V,E)$ be a finite, connected graph. We consider a greedy selection of vertices: given a list of vertices $x_1, \dots, x_k$, take $x_{k+1}$ to be any vertex maximizing the sum of distances to the existing vertices and iterate: we keep adding the `most remote' vertex. The frequency with which the vertices of the graph appear in this sequence converges to a set of probability measures with nice properties. The support of these measures is, generically, given by a rather small number of vertices $m \ll |V|$. We prove that this suggests that the graph $G$ is at most '$m$-dimensional' by exhibiting an explicit $1-$Lipschitz embedding $\phi: G \rightarrow \ell^1(\mathbb{R}^m)$ with good properties.

We introduce a notion of curvature on finite, combinatorial graphs. It can be easily computed by solving a linear system of equations. We show that graphs with curvature bounded below by $K>0$ have diameter bounded by $\mbox{diam}(G) \leq 2/K$ (a Bonnet-Myers theorem), that $\mbox{diam}(G) = 2/K$ implies that $G$ has constant curvature (a Cheng theorem) and that there is a spectral gap $\lambda_1 \geq K/(2n)$ (a Lichnerowicz theorem). It is computed for several families of graphs and often coincides with Ollivier curvature or Lin-Lu-Yau curvature. The von Neumann minimax theorem features prominently in the proofs.