Amir’s conjecture for random walks on groups is true

You need to know: Group, set of generators, finitely generated group, basic probability theory, independent identically distributed (i.i.d.) random variables.

Background: Let $G$ be an infinite group with finite generating set $S$ . Let $S^{-1}=\{g \in G\,|\,g^{-1}\in S\}$ , and let $|g|$ be the smallest integer $k\geq 0$ such that $g\in G$ has representation $g=\prod_{i=1}^k s_i$ with each $s_i \in S \cup S^{-1}$ . A symmetric finitely supported probability measure on $G$ is a function $\mu:G\to[0,1]$ such that set $\{g \in G\,|\,\mu(g)>0\}$ is finite, $\sum_{g\in G} \mu(g)=1$ , and $\mu(g^{-1})=\mu(g)$ for all $g \in G$ . Let $X_1, X_2, \dots$ be a sequence of i.i.d. random variables with distribution $\mu$ , that is, such that ${\mathbb P}[X_i=g]=\mu(g)$ for all $g\in G$ and all $i$ . A random walk on $G$ with step distribution $\mu$ is the sequence $W_1,W_2,\dots$ given by $W_n=\prod_{i=1}^n X_i$ . A speed function of random walk $W_n$ is $L_\mu(n) = {\mathbb E}[|W_n|] = \sum_{g\in G}|g|{\mathbb P}[W_n=g]$ . Its entropy is $H_\mu(n) = - \sum_{g\in G}{\mathbb P}[W_n=g]\log{\mathbb P}[W_n=g]$ . The exponent of a function $f$ is $\lim_{n\to\infty} \frac{\log f(n)}{\log n}$ , provided that the limit exists.

The Theorem: On 27th October 2015, Jérémie Brieussel and Tianyi Zheng submitted to arxiv a paper in which they proved that for any $\gamma\in[1/2,1]$ and $\theta\in[1/2,1]$ satisfying $\theta \leq \gamma \leq \frac{1}{2}(\theta+1)$ , there exist a finitely generated group $G$ and a symmetric probability measure $\mu$ of finite support on $G$ , such that the random walk on $G$ with step distribution $\mu$ has speed exponent $\gamma$ and entropy exponent $\theta$ .

Short context: The main research directions in studying random walks on groups are (i) given a group, establish properties of random walk on it, and, conversely (ii) given properties of a random walk, find if there exists a group with such random walk. The Theorem contributes to direction (ii). It confirms a conjecture of Amir who proved the same result for $\gamma,\theta\in[3/4,1]$ .

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

Go to the list of all theorems

For c<1/4, the chromatic number of G(n,1/2) is not concentrated on n^c consecutive values

You need to know: Graph, vertices, edges, chromatic number of a graph, limits, basic probability theory, independent events.

Background: Let $G(n,p)$ denote random graph with n vertices, such that every possible edge is included independently with probability p.

The Theorem: On 27th June 2019, Annika Heckel submitted to arxiv and the Journal of the AMS a paper in which she proved that for any constant $c<\frac{1}{4}$ , there is no sequence of intervals of length $n^c$ which contain $\chi(G(n,1/2))$ with high probability.

Short context: Chromatic number is one of the most important and well-studied invariants of a graph, and it is natural to ask what it is equal to for random graphs. In 2003, Achlioptas and Naor proved that if $p=\frac{d}{n}$ for constant d, then, with probability that tends to 1 as $n\to\infty$ , the chromatic number of $G\left(n,\frac{d}{n}\right)$ is either $k_d$ or $k_d+1$ , where $k_d$ denotes the smallest integer k such that $d<2k\log k$ . The Theorem states that if $p=\frac{1}{2}$ is a constant, then $\chi(G(n,1/2))$ is not concentrated in any interval of finite length. This answers the 1992 question of Paul Erdős.

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

Go to the list of all theorems

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

Random Bernoulli n by n matrix is singular with probability (1/2+o(1))^n

You need to know: Matrix, determinant $\text{det}(M)$ of square matrix M, singular square matrix (matrix with determinant $0$ ), basic probability theory, independent and identically distributed (i.i.d.) random variables, $o(1)$ notation.

Background: Let $M_n$ be a random $n \times n$ matrix whose entries are i.i.d. Bernoulli random variables (each entry is equal to $+1$ or $-1$ with probabilities $1/2$ ). Let $P_n = P(\text{det}(M_n) = 0)$ be the probability that $M_n$ is singular.

The Theorem: On 21st December 2018, Konstantin Tikhomirov submitted to arxiv a paper in which he proved that $P_n = \left(\frac{1}{2}+o(1)\right)^n$ as $n\to\infty$ .

Short context: The question of estimating $P_n$ has attracted considerable attention in literature. There is an obvious lower bound $P_n \geq \left(\frac{1}{2}+o(1)\right)^n$ , and it has been conjectured by many authors that equality holds. For an upper bound, Komlós proved in 1967 that $\lim\limits_{n\to\infty} P_n = 0$ . In 1995, Kahn, Komlós, and Szemerédi proved that $P_n=O(0.999^n)$ . This was later improved by Tao and Vu to $P_n=O(0.958^n)$ and then to $P_n \leq \left(\frac{3}{4}+o(1)\right)^n$ , see here. In 2010, Bourgain, Vu and Wood improved it to $P_n \leq \left(\frac{1}{\sqrt{2}}+o(1)\right)^n$ . Finally, the Theorem establishes the upper bound $P_n \leq \left(\frac{1}{2}+o(1)\right)^n$ , which matches the lower bound up to $o(1)$ term and proves the conjecture.

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

Go to the list of all theorems

Bernoulli convolution v_l has dimension 1 for all transcendental l in (1/2,1)

You need to know: Basic probability theory, random variable, distribution of a random variable, independent identically distributed (i.i.d.) random variables.

Background: For $\frac{1}{2}<\lambda<1$ , Bernoulli convolution $\nu_\lambda$ is the distribution of the real random variable $\sum\limits_{n=0}^\infty \pm \lambda^n$ , where the signs are chosen i.i.d. with equal probabilities. It is known that the limit $\lim\limits_{r\to 0+}\frac{\log \nu_\lambda([x-r,x+r])}{\log r}$ exists and is constant for $\nu_\lambda$ -almost every x. This constant is called dimension of $\nu_\lambda$ and in denoted $\text{dim}(\nu_\lambda)$ . A real number $\lambda$ is called algebraic if it is a root of a non-zero polynomial equation with rational coefficients, and is called transcendental otherwise.

The Theorem: On 21st October 2018, Péter Varjú submitted to arxiv a paper in which he proved that $\text{dim}(\nu_\lambda)=1$ for all transcendental $\lambda \in (1/2,1)$ .

Short context: Bernoulli convolutions has been introduced by Jessen and Wintner in 1935, and studied by Erdős and many others since that. The main question is for which values of $\lambda\in(1/2,1)$ the resulting probability measure $\nu_\lambda$ is “nice”, and having dimension 1 is one of the criteria for “niceness”. It follows from the 1995 Solomyak paper that the set E of exceptional $\lambda$ -s for which $\text{dim}(\nu_\lambda)<1$ has Lebesgue measure $0$ . In 2014, Hochman proved a stronger result that E must have box dimension $0$ (see here for the Theorem formulation and the definition of box dimension). The Theorem makes a step further and proves that set E is a subset of algebraic numbers and is therefore countable. In fact, there are also algebraic numbers outside E, see here.

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

Go to the list of all theorems

A version of the OSSS inequality holds for monotonic probability measures

You need to know: Basic probability theory, the notion of algorithm.

Background: Let $[n]=\{1,2,\dots,n\}$ , and let $X=\{0,1\}^n$ be the set of vectors $w=(w_1,\dots,w_n)$ with each $w_i$ being either $0$ or $1$ . Assume that we select each $w\in X$ with some probability ${\mathbb P}(w)\geq 0$ , such that $\sum\limits_{w\in X}{\mathbb P}(w)=1$ . For $A \subseteq X$ , define ${\mathbb P}[A]=\sum\limits_{w\in A}{\mathbb P}(w)$ . For any function $f:X\to {\mathbb R}$ , define expectation $E_{\mathbb P}(f)=\sum\limits_{w\in X}{\mathbb P}(w)f(w)$ and variance $\text{Var}_{\mathbb P}(f)=E_{\mathbb P}(f^2)-E_{\mathbb P}(f)^2$ . For $f,g:X\to {\mathbb R}$ , let $\text{Cov}_{\mathbb P}(f,g)=E_{\mathbb P}(fg)-E_{\mathbb P}(f)E_{\mathbb P}(g)$ . A function $f:X\to{\mathbb R}$ is called increasing if $f(x)\geq f(y)$ whenever $x\geq y$ coordinate-wise. A probability ${\mathbb P}$ is monotonic if for any $i\in[n]$ , any $F\subset [n]$ , and any $x,y \in \{0,1\}^F$ satisfying $x\leq y$ , ${\mathbb P}[w_j=x_j, \, \forall j \in F]>0$ and ${\mathbb P}[w_j=y_j, \, \forall j \in F]>0$ , we have ${\mathbb P}[w_i=1 | w_j=x_j, \, \forall j \in F] \leq {\mathbb P}[w_i=1 | w_j=y_j, \, \forall j \in F]$ .

A decision tree T is an algorithm that takes $w\in X$ as an input, and then tries to determine $f(w)$ by querying the values of $w_i$ , $i\in[n]$ , one bit after the other. The bit it queries on step k may depends on the values of the bits obtained on steps $1,\dots,k-1$ . The algorithm stops when it can determine $f(\omega)$ from the bits it has. Let $\delta_i(f,T)$ be the probability that T, starting from random input $\omega$ , queries bit $w_i$ before it stops.

The Theorem: On 8th May 2017, Hugo Duminil-Copin, Aran Raoufi, and Vincent Tassion submitted to arxiv a paper in which they proved that for every increasing function $f:X\to[0,1]$ , any monotonic probability ${\mathbb P}$ , and any decision tree T, we have $\text{Var}_{\mathbb P}(f) \leq \sum\limits_{i=1}^n \delta_i(f,T)\text{Cov}_{\mathbb P}(f,w_i)$ .

Short context: The Theorem generalises the inequality proved in 2005 by O’Donnell, Saks, Schramm, and Servedio (known as the OSSS inequality) for the case when each bit $w_i$ of $w\in X$ is selected independently. The Theorem allows bit of $w$ to depend on each other, and instead imposes much weaker condition that the probability ${\mathbb P}$ is monotonic. The Theorem has applications in mathematical physics, specifically in the analysis of so-called lattice spin models and their random-cluster representations.

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

Go to the list of all theorems

Bernoulli convolution is absolutely continuous for l=1-10^(-50) and 3/4>=p>=1/4

You need to know: Basic probability theory, notation $\text{Pr}$ for probability, random variable, distribution of a random variable, independent identically distributed (i.i.d.) random variables, polynomial, degree of a polynomial, monic polynomial. You also need Lebesgue measure and Hausdorff dimension to understand the context.

Background: Let $\lambda,p\in(0,1)$ be real numbers, and let $\xi_0, \xi_1, \xi_2, \dots$ be a sequence of i.i.d. random variables with $\text{Pr}(\xi_n=1)=p$ and $\text{Pr}(\xi_n=-1)=1-p$ for all n. By Bernoulli convolution we mean the random variable $X_{\lambda,p}=\sum\limits_{n=0}^\infty \xi_n \lambda^n$ . $X_{\lambda,p}$ is called absolutely continuous if there exists function $f:{\mathbb R}\to{\mathbb R}$ such that $\text{Pr}(a\leq X_{\lambda,p}\leq b)=\int_a^b f(x)dx$ whenever $a\leq b$ . The Mahler measure of any polynomial $P(x)=a\prod\limits_{i=1}^d(x-z_i)$ is $M(P)=a\prod\limits_{j:|z_j|>1}|z_j|$ . A real number $r$ is called algebraic if $P(r)=0$ for some polynomial P with rational coefficients. The (unique) monic polynomial $P_r$ of smallest degree with this property is called the minimal polynomial of r. The Mahler measure of r is $M_r=M(P_r)$ .

The Theorem: On 31st January 2016, Péter Varjú submitted to arxiv a paper in which he proved that for every $\epsilon>0$ and $p\in(0,1)$ , there is a constant $c=c(\epsilon,p)>0$ such that for any algebraic number $\lambda$ satisfying $1>\lambda>1 - c\min(\log M_\lambda, (\log M_\lambda)^{-1-\epsilon})$ , the Bernoulli convolution $X_{\lambda,p}$ is absolutely continuous.

Short context: Bernoulli convolutions has been introduced by Jessen and Wintner in 1935, and studied by Erdős and many others since that. The main research question is for which values of $\lambda$ and $p$ the Bernoulli convolution is absolutely continuous. In 1939, Erdős noticed that $X_{\lambda,1/2}$ is not absolutely continuous for $\lambda<1/2$ , and also for $\lambda \in E$ for some non-empty set $E \subset [1/2,1)$ . However, Solomyak proved in 1995 that set E has Lebesgue measure $0$ . Moreover, Shmerkin, building on this theorem, proved in 2014 that E has Hausdorff dimension $0$ . Despite on this, it was known very few explicit examples of $\lambda$ -s for which $X_{\lambda,p}$ is absolutely continuous, and none such examples was known for $p\neq 1/2$ . The Theorem (with explicit $c=c(\epsilon,p)$ ) provides a lot of such examples. For example, it implies that $X_{\lambda,p}$ is absolutely continuous for $\lambda=1-10^{-50}$ and $\frac{1}{4}\leq p \leq \frac{3}{4}$ .

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

Go to the list of all theorems

Bernoulli convolution v_l has dimension 1 outside a set of l of dimension 0

You need to know: Basic probability theory, random variable, distribution of a random variable, independent identically distributed (i.i.d.) random variables, infimum $\inf$ , supremum $\sup$ , limit superior $\limsup$ .

Background: For $\frac{1}{2}<\lambda<1$ , Bernoulli convolution $\nu_\lambda$ is the distribution of the real random variable $\sum\limits_{n=0}^\infty \pm \lambda^n$ , where the signs are chosen i.i.d. with equal probabilities. It is known that the limit $\lim\limits_{r\to 0+}\frac{\log \nu_\lambda([x-r,x+r])}{\log r}$ exists and is constant for $\nu_\lambda$ -almost every x. This constant is called dimension of $\nu_\lambda$ and in denoted $\text{dim}(\nu_\lambda)$ . The box dimension of set $S$ of real numbers is $\text{bdim}(S)=\limsup\limits_{r\to 0+}\frac{\log N_S(r)}{\log(1/r)}=0$ , where $N_S(r)$ is the minimal number of intervals of length $r$ needed to cover S. The packing dimension of S is $\text{pdim}(S)=\inf\left\{\sup\limits_n \text{bdim}(S_n) : S \subseteq \bigcup\limits_{n=1}^\infty S_n\right\}$ .

The Theorem: On 9th December 2012, Michael Hochman submitted to arxiv a paper in which he proved, among other results, that the set $\{\lambda \in (1/2,1) : \text{dim}(\nu_\lambda) <1\}$ has packing dimension $0$ . In other words, $\text{dim}(\nu_\lambda)=1$ outside a set of $\lambda$ of packing dimension $0$ .

Short context: Bernoulli convolutions has been introduced by Jessen and Wintner in 1935, and studied by Erdős and many others since that. The main question is for which values of $\lambda \in (1/2,1)$ the resulting probability measure $\nu_\lambda$ is “nice”, and having dimension 1 is one of the criteria for “niceness”. The Theorem states that the set of exceptional $\lambda$ -s for which $\nu_\lambda$ may be “not nice” is very small in a strong sense. For readers familiar with Hausdorff dimension, we note that having packing dimension $0$ implies Hausdorff dimension $0$ but not vice versa.

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

Go to the list of all theorems

The Gaussian correlation conjecture is true

You need to know: Euclidean space ${\mathbb R}^n$ , origin in ${\mathbb R}^n$ , convex set in ${\mathbb R}^n$ , centrally symmetric set in ${\mathbb R}^n$ (set symmetric with respect to the origin), integration in ${\mathbb R}^n$ , $n \times n$ matrix, matrix multiplication, determinant $\text{det}(A)$ of a matrix A, inverse $A^{-1}$ of a matrix A with $\text{det}(A)\neq 0$ , symmetric matrix, transpose $A^T$ of matrix A.

Background: A symmetric $n\times n$ matrix $\Sigma$ is called positive definite, if $x^T\Sigma x > 0$ for all non-zero $x \in {\mathbb R}^n$ . Given a positive definite $n\times n$ matrix $\Sigma$ , let $f:{\mathbb R}^n \to {\mathbb R}$ be a function given by $f(x)=(2\pi)^{-n/2}\text{det}(\Sigma)^{-1/2}\exp(-\frac{1}{2}x^T\Sigma^{-1} x)$ , $x\in {\mathbb R}^n$ . For a subset $A\subset{\mathbb R}^n$ , let $\mu(A)=\int_A f(x)dx$ . $\mu$ is called an n-dimensional Gaussian probability measure on ${\mathbb R}^n$ , centred at the origin.

The Theorem: On 5th August 2014, Thomas Royen submitted to arxiv and Far East Journal of Theoretical Statistics a paper in which he proved that inequality $\mu(A \cap B) \geq \mu(A) \cdot \mu(B)$ holds for all convex and centrally symmetric sets $A,B \subset {\mathbb R}^n$ .

Short context: The statement of the Theorem was known as Gaussian correlation conjecture, and was an important conjecture in probability theory. A special case of the conjecture was formulated by Dunnett and Sobel in 1955, the general case was stated in 1972. Despite simple-looking formulation and efforts of many researchers, the conjecture remained open until 2014. The Theorem proves the conjecture, and it is now called Gaussian correlation inequality.

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

Go to the list of all theorems

There exist 1-dependent 4-colouring and 2-dependent 3-colouring of the integers

You need to know: Notation ${\mathbb Z}$ for the set of integers, basic probability theory, independence, random variable, stochastic process, almost surely.

Background: We say that a stochastic process $(X_i)_{i\in{\mathbb Z}}$ is k-dependent if the random sequences $(\dots, X_{i-2}, X_{i-1})$ and $(X_{i+k}, X_{i+k+1}, \dots)$ are independent of each other, for each $i \in {\mathbb Z}$ . We call a stochastic process $(X_i)_{i\in{\mathbb Z}}$ a q-coloring (of ${\mathbb Z}$ ) if each $X_i$ takes values in $\{1,\dots,q\}$ , and almost surely we have $X_i \neq X_{i+1}$ for all $i\in{\mathbb Z}$ .

The Theorem: On 11th March 2014, Alexander Holroyd and Thomas Liggett submitted to arxiv a paper in which they proved the existence of 1-dependent 4-colouring and of 2-dependent 3-colouring of the integers.

Short context: An important research direction in probability theory is the study of stochastic processes with little or no dependence between random variables at distant locations. k-dependent process indexed by integers is one of the simplest examples of this phenomenon. In 2008, Schramm proved that no stationary 1-dependent 3-colouring of the integers exists, and asked whether a k-dependent q-coloring exists for any positive integers $k$ and $q$ . The Theorem gives a complete answer to this question.

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

Go to the list of all theorems