The Benjamini-Schramm conjecture is true for nonunimodular graphs

You need to know: Graph, infinite graph, connected graphs, connected components of a graph, degree of a vertex in a graph, basic probability theory, almost sure convergence, infimum, notation |A| for the number of elements in any finite set A.

Background: Let $G=(V,E)$ be an infinite graph. Graph $G$ is called locally finite if every vertex $v\in V$ has finite degree. An automorphism of graph $G$ is a bijection $\sigma: V \to V$ , such that pair of vertices $(u,v)$ is an edge if and only if $(\sigma(u), \sigma(v))$ is an edge. For vertices $u,v \in V$ , let us write $u \sim v$ if there is an automorphism $\sigma$ such that $\sigma(u)=v$ . An (infinite) graph G is called quasi-transitive if its vertex set V can be partitioned into finitely many classes $V_1, \dots, V_k$ , such that $u \sim v$ if and only if vertices u and v belong to the same class $V_i$ . Let $S_u v$ be the set of vertices $w \in V$ such that there is an automorphism $\sigma$ such that $\sigma(u)=u$ and $\sigma(v)=w$ . A graph G is called unimodular if $|S_u v| = |S_v u|$ whenever $u \sim v$ , and nonunimodular otherwise.

Let $p\in[0,1]$ . The Bernoulli(p) bond percolation on $G=(V,E)$ is a subgraph of G to which each edge of G is included independently with probability p. For given G, let $p_c(G)$ be the infimum of all $p\in[0,1]$ such that the Bernoulli(p) bond percolation on G has an infinite connected component almost surely, and let $p_u(G)$ be the infimum of all p for which this infinite connected component is unique almost surely.

The Theorem: On 7th November 2017, Tom Hutchcroft submitted to the Journal of the AMS a paper in which he proved, among other results, that for any connected, locally finite, quasi-transitive, nonunimodular graph G, we have $p_c(G) < p_u(G)$ .

Short context: Inequality $p_c(G) < p_u(G)$ implies the existence of non-empty range of parameters $p\in(p_c, p_u)$ such that Bernoulli(p) bond percolation on G has many infinite connected components. Characterisation of graphs with this property is a well-known important open problem. In 1996, Benjamini and Schramm conjectured that a connected, locally finite, quasi-transitive graph $G$ has $p_c(G) < p_u(G)$ if and inly if it is nonamenable, see here for the definition. In fact, Gandolfi, Keane, and Newman proved the “only if” part in 1992, so only the “if” part remains open. The proof of this theorem can be extended to quasi-transitive graphs, and this implies the Benjamini-Schramm conjecture for planar graphs. The Theorem confirms the conjecture for nonunimodular graphs.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Hyperbolic motions of any shape exist in the Newtonian N-body problem

You need to know: Euclidean space $E={\mathbb R}^d$ of dimension $d$ , Euclidean norm $||a||$ of vector $a$ , (second) derivative of a function $x:{\mathbb R}\to E$ , small o notation $o(.)$ .

Background: Let N point particles with masses $m_i > 0$ and positions $x_i(t) \in E$ at time $t$ are moving according to Newton’s laws of motion: $m_j \frac{d^2 x_j}{dt^2} = \sum\limits_{i \neq j} \frac{m_i m_j(x_i - x j)}{r_{ij}^3}, \, 1 \leq j \leq N$ , where $r_{ij}$ is the distance between $x_i$ and $x_j$ . The motion of particles is determined by the initial conditions: their masses and their positions and velocities at time $t=0$ . Let $\Omega$ be the set of configurations such that the motion has no collisions ( $r_{ij}(t)>0$ for all $i,j$ and $t$ ). A motion is called hyperbolic if each particle has a different limit velocity vector, that is, $\lim\limits_{t\to \infty} \frac{d x_j}{dt}=a_j \in E$ and $a_i \neq a_j$ whenever $i \neq j$ .

The Theorem: On 25th August 2019, Ezequiel Maderna and Andrea Venturelli submitted to arxiv a paper in which they proved that for the Newtonian N-body problem in a space E of dimension $d\geq 2$ , there are hyperbolic motions $x:[0;+\infty) \to E^N$ such that $x(t) = \sqrt{2h} t a + o(t)$ as $t \to \infty$ for any choice of $x_0 = x(0) \in E^N$ , for any $a=(a_1, \dots, a_N) \in \Omega$ normalized by $||a||=1$ , and for any constant $h>0$ .

Short context: The problem of describing motion of N bodies under gravitation (N-body problem) in Euclidean space is a fundamental problem in physics and mathematics, studied by many authors, see, for example, here and here. In general, the motion can be very complicated even for $N=3$ , but can we at least understand hyperbolic motions? The only explicitly known hyperbolic motions are such that the shape of the configuration does not change with time, but it is conjectured that there are only finitely many such motions for any fixed $N$ . In contrast, the Theorem states that hyperbolic motions exist for all initial configurations and all choices of the limited velocities.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Non-collision singularities exist in a planar Newtonian 4-body problem

You need to know: Euclidean plane ${\mathbb R}^2$ , (second) derivative of a function $x:{\mathbb R}\to {\mathbb R}^2$ .

Background: Let n point particles with masses $m_i > 0$ and positions $x_i \in {\mathbb R}^2$ are moving according to Newton’s laws of motion: $m_j \frac{d^2 x_j}{dt^2} = \sum\limits_{i \neq j} \frac{m_i m_j(x_i - x j)}{r_{ij}^3}, \, 1 \leq j \leq n$ , where $r_{ij}$ is the distance between $x_i$ and $x_j$ . The motion of particles is determined by the initial conditions: their masses and their positions and velocities at time $t=0$ .

The Theorem: On 29th August 2014, Jinxin Xue submitted to Acta Mathematica a paper in which he proved that, for $n=4$ , there is a non-empty set of initial conditions, such that all four points escape to infinity in a finite time, avoiding collisions.

Short context: The problem of describing motion of n bodies under gravitation (n-body problem) in space or plane is a fundamental problem in physics and mathematics, studied by many authors, see, for example, here. In general, the motion can be very complicated even for $n=3$ , but can we at least understand under what initial conditions the solution to the system of Newton equations (presented above) is well-defined for all $t\geq 0$ ? This may be not the case for two reasons: (a) collision happened, and (b) there are no collisions but a point escape to infinity in a finite time. Case (b) is known as non-collision singularity. In 1897, Painlevé proved that there are no such singularities for $n=3$ , but conjectured their existence for all $n>3$ . In 1992, Xia proved this conjecture (for motions in ${\mathbb R}^3$ ) for $n\geq 5$ . The Theorem establishes the remaining (and the hardest) case $n=4$ .

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

There exists a discrete bounded envy-free cake cutting protocol for any number of agents

You need to know: Algorithm.

Background: Let us call interval $[0,1]$ a cake, and any finite union of subintervals of $[0,1]$ – a piece of cake. Let ${\cal X}$ be the set of all pieces of cake. Let $N=\{1,\dots,n\}$ be the set of agents, each agent i having its own valuation function $V_i:{\cal X}\to[0,\infty)$ such that (i) $V_i(X\cup X')=V_i(X)+V_i(X')$ for all disjoint $X, X' \in {\cal X}$ , and (ii) for every $X\in {\cal X}$ and $0\leq \lambda\leq 1$ , there exists $X'\subset X$ in ${\cal X}$ with $V_i(X') = \lambda V_i(X)$ . A cake allocation is a partition $[0,1]=\bigcup\limits_{i=1}^n X_i$ into disjoint pieces $X_i\in{\cal X}$ . We say that agent i is envious if $V_i(X_i)<V_i(X_j)$ for some j. A discrete protocol is an algorithm which returns an allocation after a sequence of queries which either (1) for given $x \in [0,1]$ and $r \geq 0$ , ask agent i to return a point $y\in[0,1]$ such that $V_i([x,y])=r$ (CUT query), or (2) for given $x,y\in[0,1]$ , ask agent i to return $V_i([x,y])$ (EVALUATE query). A protocol is called envy-free if no agent is envious if he/she follows the protocol truthfully. A protocol is bounded if the number of queries required to return a solution is bounded by a constant $C=C(n)$ depending only on n but not on $V_i$ .

The Theorem: On 13th April 2016, Haris Aziz and Simon Mackenzie submitted to arxiv a paper in which they proved the existence of a discrete bounded envy-free cake cutting protocol for any number of agents.

Short context: Cake cutting is a metaphor for the allocation of a heterogeneous divisible good among multiple agents with possibly different preferences over different parts of the cake. The existence of a discrete and bounded envy-free cake cutting protocol was the central open problem in this area. Such protocol is easy to $n\leq 3$ . In 2015, Aziz and Mackenzie solved the problem for $n=4$ . The Theorem solves it for all n.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Fast (1-1/e-epsilon)-approximation for the infuence maximization problem

You need to know: Directed graph, algorithm, approximation algorithm, polynomial-time algorithm, NP-hard problem.

Background: Let $G$ be a directed graph, in which each directed edge $w\to v$ has a weight $b_{vw}\in[0,1]$ . Each vertex v has a threshold $\theta_v$ , and the thresholds $\theta_v$ are chosen independently and uniformly at random from the interval $[0,1]$ . At time $0$ , we select some set A of vertices at mark them as “active”. At times $t=1,2,\dots$ , vertex v become active if $\sum\limits_{w\to v, \, w \text{ active}} b_{vw} \geq \theta_v$ , and if vertex become active at stays active forever. This process ends if no activations occur from round $t$ to $t+1$ . The influence $\sigma(A)$ of a set A of vertices is the expected number of active nodes at the end of the process. The influence maximization problem asks, given graph G, weights $b_{vw}$ , and parameter k, to find a k-vertex set A with maximal $\sigma(A)$ .

The Theorem: On 17th April 2014, David Kempe, Jon Kleinberg, and Éva Tardos submitted to arxiv a paper in which they proved that for any $\epsilon>0$ , there is a polynomial-time algorithm approximating the maximum influence to within a factor of $1-1/e-\epsilon$ , where $e=2.718...$ is the base of the natural logarithm.

Short context: The influence maximization problem has important practical applications. For example, G may model a social network, the “activation process” is when people start to use some product or service because their friends do, and the influence maximization problem asks which set A of individuals should we initially convince to use it, to maximize the “cascade effect”. The problem is NP-hard to solve exactly, but the Theorem provides an efficient approximation algorithm.

Links: The original paper is available here.

Go to the list of all theorems

Fast recovery of n-component vector from O(n log n) random magnitude measurements

You need to know: Set of complex numbers ${\mathbb C}$ , absolute value $|z|$ of $z \in {\mathbb C}$ , set ${\mathbb C}^n$ of vectors with n complex coordinates, inner product $(x,y)=\sum\limits_{i=1}^n x_iy_i$ in ${\mathbb C}^n$ , unit sphere in ${\mathbb C}^n$ , polynomial-time algorithm, probability, sampling independently and uniformly from a set, big O notation.

Background: Let $x \in {\mathbb C}^n$ , and let $z_1, \dots z_m$ be vectors independently and uniformly sampled from the unit sphere in ${\mathbb C}^n$ . Numbers $b_i=|(x,z_i)|^2, \, i=1,2,\dots,m$ are called magnitude measurements of x.

The Theorem: In September 2011, Emmanuel Candes, Thomas Strohmer, and Vladislav Voroninski submitted to Communications on Pure and Applied Mathematics a paper in which they proved the existence of positive constants $c_0$ and $\gamma$ such that an arbitrary $x \in {\mathbb C}^n$ can be exactly recovered from $m \geq c_0 n \log n$ magnitude measurements in polynomial time with probability at least $1-3e^{-\gamma m/n}$ .

Short context: In applications, x represents a signal, and $(x,z_i)$ represent measurements. In many applications, only the absolute value of $(x,z_i)$ can be measured – this is called “magnitude measurements”. If vectors $z_i$ are fixed and given, the problem of recovering x from $b_i$ may be computationally infeasible. The Theorem states, however, that we can select $z_i$ at random, and recover x efficiently with high probability after the number of measurements not much higher than the dimension.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

A convergent algorithm for non-smooth convex saddle-point problems

You need to know: Euclidean space ${\mathbb R}^n$ , inner product $(x,y)$ for $x,y\in {\mathbb R}^n$ , norm $||x||=\sqrt{(x,x)}$ , proper convex lower-semicontinuous (l.s.c.) function $F:{\mathbb R}^n \to [0,+\infty]$ , continuous linear operator $K:{\mathbb R}^n \to {\mathbb R}^m$ , its norm $||K||=\max\limits_{x\in{\mathbb R}^n}\frac{||Kx||}{||x||}$ .

Background: Let $G:{\mathbb R}^n \to [0,+\infty]$ and $F:{\mathbb R}^m \to [0,+\infty]$ be proper convex l.s.c. functions, and let $F^*(y)=\sup\limits_{x\in{\mathbb R}^m}((y,x)-F(x))$ be the convex conjugate of F. Let $K:{\mathbb R}^n \to {\mathbb R}^m$ be a continuous linear operator, and let $K^*:{\mathbb R}^m \to {\mathbb R}^n$ be such that $(Kx,y)=(x,K^*y)$ for all $x\in {\mathbb R}^n$ , $y\in {\mathbb R}^m$ . Let $H(x,y)=(Kx,y)+G(x)-F^*(y)$ . By saddle-point problem we mean the problem of the form $\min\limits_{x\in {\mathbb R}^n}\max\limits_{y\in {\mathbb R}^m}H(x,y)$ . A pair $(x^*,y^*)$ is called a saddle-point of this problem if $H(x,y^*)\geq H(x^*,y^*)$ for all $x\in{\mathbb R}^n$ and $H(x^*,y)\leq H(x^*,y^*)$ for all $y\in{\mathbb R}^m$ . For any $V:{\mathbb R}^n \to [0,+\infty]$ , $y\in{\mathbb R}^n$ , and $\tau>0$ , denote $d_{V,\tau}(x)=\arg\min\limits_{x\in{\mathbb R}^n}\left(\frac{||x-y||^2}{2\tau}+V(x)\right)$ . For $\tau>0$ , $\sigma>0$ , $\theta\in[0,1]$ , initial points $x^0 \in {\mathbb R}^n$ , $y^0 \in {\mathbb R}^m$ , and $\bar{x}^0=x^0$ , define sequences $x^n, y^n, \bar{x}^n$ iteratively as follows: $y^{n+1}=d_{F^*,\sigma}(y^n+\sigma K \bar{x}^n)$ , $x^{n+1}=d_{G,\tau}(x^n-\tau K^* y^{n+1})$ , $\bar{x}^{n+1} = x^{n+1}+\theta(x^{n+1}-x^n)$ , $n \geq 0$ .

The Theorem: On 21st December 2010, Antonin Chambolle and Thomas Pock published in the Journal of Mathematical Imaging and Vision a paper in which they proved that if $\theta=1$ and $\tau\sigma(||K||)^2<1$ , then there exist a saddle-point $(x^*,y^*)$ such that $\lim\limits_{n\to\infty}x^n = x^*$ and $\lim\limits_{n\to\infty}y^n = y^*$ .

Short context: Saddle-point problems of the form as above arise in many applications, for example in image denoising and segmentation. The Theorem proves that a simple algorithm converges to a saddle-point. Practical experiments suggests that the convergence is in fact fast, which makes the algorithm widely applicable.

Links: The original paper is available here.

Go to the list of all theorems

The connective constant of the honeycomb lattice is equal to (2+2^0.5)^0.5

You need to know: Limits.

Background: The honeycomb lattice (or the hexagonal lattice) is the partition of the plane into same-size regular hexagons. Denote by $c_n$ the number of n-step self-avoiding (that is, visiting every vertex at most once) walks on the honeycomb lattice H started from some fixed vertex. It is known that there exists $\mu \in (0,+\infty)$ such that $\mu=\lim\limits_{n\to\infty} \sqrt[n]{c_n}$ . This constant $\mu$ is called the connective constant of the honeycomb lattice.

The Theorem: On 4th July 2010, Hugo Duminil-Copin and Stanislav Smirnov submitted to arxiv a paper in which they proved that the connective constant of the honeycomb lattice is $\mu=\sqrt{2+\sqrt{2}}$ .

Short context: Self-avoiding walks on a lattice were proposed by a famous chemist Flory in 1953 as a model for spatial position of polymer chains. In 1982, Nienhuis, using non-rigorous methods from theoretical physics, predicted that the connective constant of the honeycomb lattice is equal to $\sqrt{2+\sqrt{2}}$ . The Theorem confirms this prediction.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Principal component analysis with large but sparse noise can be done fast

You need to know: Euclidean space ${\mathbb R}^n$ , norm $||x||=\sqrt{\sum x_i^2}$ of $x=(x_1,\dots, x_n) \in {\mathbb R}^n$ , real matrix L (matrix with real entries $L_{ij}$ ), matrix multiplication, square matrix, l1 norm $||L||_1=\sum_{i,j}|L_{ij}|$ of matrix L, support set of L (set of pairs $(i,j)$ such that $L_{ij}\neq 0$ ), diagonal matrix D, identity matrix I, transpose $L^T$ of matrix L, orthonormal matrix (such that $L^TL=LL^T=I$ ) singular value decomposition of a square matrix L (writing $L=UDV^T$ where D is the diagonal matrix and $U,V$ are orthonormal matrices), rank of the matrix L (the number of non-zero entries of D), nuclear norm $||L||_*$ of L (sum of all entries of D).

Background: Let $\mu>0$ be a fixed real number. Let $e_i \in {\mathbb R}^n$ be a vector with $i$ -th component $1$ and others $0$ . Let $L_0$ be a real $n \times n$ matrix of rank r whose singular value decomposition $L_0=UDV^T$ satisfies (i) $\max_i ||U^Te_i||\leq \frac{\mu r}{n}$ , (ii) $\max_i ||V^Te_i||\leq \frac{\mu r}{n}$ , and (iii) $\max_{i,j}|w_{ij}|\leq \frac{\sqrt{\mu r}}{n}$ , where $w_{ij}$ are entries of matrix $UV^T$ . Let $\Sigma$ be a fixed $n\times n$ matrix with $\pm 1$ entries $\Sigma_{ij}$ . Choose integer $0<m<n^2$ . Let $S_0$ be $n\times n$ matrix with entries $[S_0]_{ij}$ whose support set $\Omega$ is uniformly distributed among all sets of cardinality m, and such that the sign of $[S_0]_{ij}$ is $\Sigma_{ij}$ for all $(i,j)\in \Omega$ . Let $M=L_0+S_0$ . Let $\hat{L}$ , $\hat{S}$ be the solution to optimization problem $\min\limits_{L,S}(||L||_*+\frac{1}{\sqrt{n}}||S||_1)$ subject to $L+S=M$ .

The Theorem: On 18th December 2009, Emmanuel Candes, Xiaodong Li, Yi Ma, and John Wright submitted to arxiv a paper in which they proved the following result. Suppose that $L_0$ and $S_0$ are as above. Then, there are positive constants $c$ , $c_r$ , $c_s$ such that with probability at least $1-cn^{-10}$ (over the choice of support of $S_0$ ), we have $\hat{L}=L_0$ and $\hat{S}=S_0$ provided that $\text{rank}(L_0) \leq c_r n \mu^{-1}(\log n)^{-2}$ and $m \leq c_s n^2$ .

Short context: Many real life data has the form of matrix $M=L_0+S_0$ , where $L_0$ is a low-rank matrix and $S_0$ is some perturbation. A fundamental problem, known as “principal component analysis” is to recover $L_0$ from M. Most known method works if $S_0$ is small, but this assumption often fails in applications. The Theorem states that $L_0$ can be efficiently recovered if $S_0$ is sparse, that is, has not too many non-zero entries (which, however, can be arbitrary large!). Conditions (i)-(iii) for $L_0$ are needed to ensure that $L_0$ is not sparse. The Theorem can be extended to rectangular matrices $L_0, S_0$ as well.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

There exists a fully homomorphic encryption scheme

You need to know: Basic cryptography: circuits, encryption, decryption, etc.

Background: A fully homomorphic encryption scheme is a procedure that allows one to evaluate circuits over encrypted data without being able to decrypt.

The Theorem: On 31th May 2009, Craig Gentry submitted to the Proceedings of the forty-first annual ACM symposium a paper in which he showed that fully homomorphic encryption scheme exists and can be actually constructed.

Short context: The notion of a fully homomorphic encryption (FHE) scheme was introduced by Rivest, Adleman, and Dertouzos in 1978. FHE would allow to perform arbitrary computations on encrypted data without decripting them, and would therefore lead to the possibility of more secure cloud computing. For example, a program could help with preparation of tax return forms using encrypted financial information. However, the existence of FHE was a long standing open problem, and many experts believed that it does not exist. The Theorem proves that FTE exists and can be actually constructed. This makes a revolution in cryptography.

Links: The original paper is available here.

Go to the list of all theorems