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

There is a one-relator inverse monoid with undecidable word problem

You need to know: Group, presentation of a group in the form $<S|R>$ , where S is a set of generators and R is a set of relations.

Background: Let S be a set and let $\cdot$ be a binary operation $S \times S \to S$ . We say that pair $(S, \cdot)$ form a monoid if (i) $(a\cdot b) \cdot c = a \cdot (b \cdot c)$ holds for all $a,b,c \in S$ , and (ii) there exists an element e in S, called the identity element, such that $e\cdot a = a \cdot e = a$ holds for all $a\in S$ . A monoid is called inverse monoid, if for every $x\in S$ there exists $y\in S$ (called inverse of x) such that $x=x\cdot y \cdot x$ and $y=y\cdot x\cdot y$ . Note that every group if an inverse monoid with extra property $x\cdot y = y \cdot x = e$ whenever y is an inverse of x.

A group G is called finitely presented if it has a presentation $<S|R>$ with finite number of generators and finite set of relations. If, moreover, set R consists on just one relation, group G is called one-relator. A word in group G is any product of generators and their inverse elements. The word problem in G is the problem to decide whether a given word represents an identity element. Same definitions extends to inverse monoids and (with obvious modifications) to monoids.

The Theorem: On 18th September 2018, Robert Gray submitted to Inventiones Mathematicae a paper in which he proved the existence of a one-relator inverse monoid with undecidable word problem.

Short context: In the middle of 20th century, Markov and Post independently proved that there are finitely presented monoids for which the word problem is undecidable. Later, Novikov proved that the same is true for groups. This raises the question for which special classes of monoids and groups the word problem is decidable. In particular, it follows from results in 1932 paper of Magnus that the one-relator groups have decidable word problem. Can this result be extended to a (harder) word problem for inverse monoids? The Theorem gives a negative 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

If E is a compact set on the plane with dimension >5/4, then its distance set has positive Lebesgue measure

You need to know: Euclidean plane ${\mathbb R}^2$ , compact set on the plane, distance $|x-y|$ between points $x,y$ on the plane, Lebesgue measure, Hausdorff dimension.

Background: For a set $E \subset {\mathbb R}^2$ , define the distance set $\Delta(E) = \{|x-y|: x \in E, y \in E\}$ .

The Theorem: On 28th August 2018, Larry Guth, Alex Iosevich, Yumeng Ou, and Hong Wang submitted to arxiv a paper in which they proved that if $E \subset {\mathbb R}^2$ is a compact set with Hausdorff dimension greater than $5/4$ , then $\Delta(E)$ has positive Lebesgue measure.

Short context: In 1985, Falconer posed the following problem. What is the smallest constant $c(d)$ such that every compact set E in ${\mathbb R}^d$ with the Hausdorff dimension larger than $c(d)$ must have the distance set $\Delta(E)$ of positive Lebesgue measure? Falconer proved that $\frac{d}{2}\leq c(d) \leq \frac{d+1}{2}$ , and conjectured that in fact $c(d)=\frac{d}{2}$ . This is known as the Falconer Distance Conjecture. For the plane, it predicts that $c(2)=1$ . In 1999, Wolff proved that $c(2)\leq \frac{4}{3}$ , The Theorem improves this to $c(2)\leq \frac{5}{4}$ .

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

Go to the list of all theorems

The probabilistic Waring problem for finite simple groups has positive solution

You need to know: Group, identity element $1$ , finite group, abelian and non-abelian groups, simple group, free group, notation $|S|$ for the number of elements in finite set S.

Background: Let $F_k$ be the free group with k generators $x_1, \dots x_k$ . Any element $w\in F_k$ (which we call word) can be written as $w=\prod\limits_{j=1}^r x_{i_j}^{\epsilon_j}$ for some $1 \leq i_1 < \dots < i_r \leq k$ and $\epsilon_j = \pm 1$ , $j=1,\dots,r$ . For every group G, w induces a word map from $w:G^k \to G$ given by $w(g_1, \dots, g_k)=\prod\limits_{j=1}^r g_{i_j}^{\epsilon_j}$ . If G is a finite group and $g\in G$ , let $N_G^w(g)$ be the number of $(g_1, \dots, g_k)\in G^k$ such that $w(g_1, \dots, g_k)=g$ . Two words $w_1, w_2$ are said to be disjoint if they are words in disjoint sets of variables. For a function $f: G\to{\mathbb R}$ , we write $||f||_{L^1} = \sum\limits_{g \in G}|f(g)|$ .

The Theorem: On 14th August 2018, Michael Larsen, Aner Shalev, and Pham Tiep
submitted to the Annals of Mathematics a paper in which they proved the following result. Let $w_1, w_2 \neq 1$ be disjoint words and let $w = w_1w_2$ . Then $\lim\limits_{|G|\to\infty}\left\|\frac{N_G^w(g)}{|G|^k}-\frac{1}{|G|}\right\|_{L^1}=0$ , where G ranges over all finite non-abelian simple groups.

Short context: In an earlier work, Larsen, Shalev, and Tiep proved that, for every word w as in the Theorem, and for every sufficiently large finite non-abelian simple group G, we have $N_G^w(g)>0$ for every $g\in G$ . In the language of probability theory, this means that if we select $g_1, \dots, g_k$ from G at random, and compute $w(g_1, \dots, g_k)$ , we can get any element $g\in G$ in this way with non-zero probability. In 2013, Shalev further asked whether $w(g_1, \dots, g_k)$ has almost uniform distribution in G with respect to the $L^1$ norm. This question became known as the probabilistic Waring problem for finite simple groups. The Theorem answers this question affirmatively.

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

Go to the list of all theorems

The Conway knot is not slice

You need to know: Euclidean space ${\mathbb R}^4$ , unit ball $B^4=\{x\in {\mathbb R}^4 : |x|\leq 1\}$ in ${\mathbb R}^4$ , unit sphere $S^3=\{x\in {\mathbb R}^4 : |x|=1\}$ in ${\mathbb R}^4$ , closed curves in $S^3$ , self-intersecting and non-self-intersecting curves, smoothly embedded 2-dimensional disk in $B^4$ .

Background: A knot is a closed, non-self-intersecting curve in $S^3$ . Two knots $K_1$ and $K_2$ are equivalent if $K_1$ can be transformed smoothly, without intersecting itself, to coincide with $K_2$ . There are tables which lists some knots up to equivalence, which are called the Rolfsen tables. The Conway knot is the knot labelled 11n34 in these tables. A knot $K \subset S^3$ is called slice if it bounds a smoothly embedded 2-dimensional disk in $B^4$ .

The Theorem: On 8th August 2018, Lisa Piccirillo submitted to arxiv a paper in which she proved that the Conway knot is not slice.

Short context: A knot diagram is a projection of a knot into a plane, which (i) is injective everywhere, except at a finite number of crossing points, which are the projections of only two points of the knot, and (ii) records over/under information at each crossing. We say that the knot K has n crossings if n is the minimal number of crossing a knot diagram of a knot equivalent to K may have. The notion of slice knot is a central notion in 4-dimensional theory of knots, originated by Fox in 1962. By 2005, all knots of under 13 crossings were classified whether they are slice knots or not, with the only exception of the Conway knot (which has 11 crossings). The Theorem completes this classification.

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

Go to the list of all theorems

There exist finitely generated infinite simple left orderable groups

You need to know: Group, finite and infinite group, simple group, total order $\leq$ on a set.

Background: A generating set of a group G is a subset $S \subset G$ such that every $g\in G$ can be written as a finite product of elements of S and their inverses. Group G is called finitely generated if it has a finite generating set S. A group G with group operation + is called left orderable if there exists a total order $\leq$ on G such that $a\leq b$ implies $c+a \leq c+b$ for all $a,b,c \in G$ .

The Theorem: On 17th July 2018, James Hyde and Yash Lodha submitted to arxiv a paper in which they proved the existence of finitely generated infinite simple left orderable groups.

Short context: The Theorem answered a long-standing open question posed by Rhemtulla in 1980. In fact, the authors proved the existence of continuum many isomorphism types of such groups. The same is true for right orderable groups (groups G with a total order $\leq$ such that $a\leq b$ implies $a+c \leq b+c$ for all $a,b,c \in G$ ).

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

Go to the list of all theorems

There exists an oracle A relative to which BQP is not contained in PH

You need to know: Notations for all $\forall$ and exists $\exists$ , computer program and number of operations it takes to run, quantum computer.

Background: Let $\Sigma=\{0,1\}$ , ${\Sigma}^n$ be the set of words $\sigma_1\dots\sigma_n$ with each $\sigma_i$ being $0$ or $1$ , and let $\Sigma^*=\bigcup\limits_{n=0}^\infty \Sigma^n$ . Let $|x|$ denote the length of any word $x\in \Sigma^*$ . Let $A:\Sigma^*\to \Sigma$ be an arbitrary function which we call oracle. Imagine a computer which can do everything a regular computer can do, but, in addition, can instantly compute $A(x)$ for any $x\in \Sigma^*$ . Let $P_k^A$ be the set of functions $F(x_1, \dots, x_k)$ in k variables $x_i\in \Sigma^*$ , for which there is a polynomial P and a program on such a computer which computes $F$ in at most $P\left(\sum\limits_{i=1}^k|x_i|\right)$ operations. Let $\text{PH}^A$ be the set of functions $f:\Sigma^*\to \Sigma$ for which there exists integer $k\geq 0$ , polynomial P, and function $F\in P_{2k+1}^A$ such that $f(x)=1$ if and only if $\forall y_1 \in \Sigma^{P(|x|)}\,\exists z_1 \in \Sigma^{P(|x|)} \dots \forall y_k \in \Sigma^{P(|x|)}\,\exists z_k \in \Sigma^{P(|x|)}$ such that $F(y_1,z_1,\dots,f_k,z_k,x)=1$ . Let $\text{BQP}^A$ be the set of all functions $g:\Sigma^*\to \Sigma$ for which there is a polynomial P and a program on a quantum computer (again with extra ability to instantly compute A) which computes $g(x)$ in at most $P(|x|)$ operations.

The Theorem: On 31st May 2018, Ran Raz and Avishay Tal submitted to the Electronic Colloquium on Computational Complexity a paper in which they proved the existence of oracle $A:\Sigma^*\to \Sigma$ such that $\text{BQP}^A \not\subseteq \text{PH}^A$ .

Short context: It is widely believed that quantum computers, when/if they will be build, will be able to efficiently solve a large class of problems than regular computers can do. More formally, it is believed that $\text{BQP} \not\subseteq \text{P}$ , and, moreover, $\text{BQP} \not\subseteq \text{PH}$ , where the definitions of P, PH, and BQP are as above but without oracle A. However, proving such separation results in well out of reach of the current techniques. Such problems often become easier with oracle, for example, it is not known whether $\text{P} \neq \text{PH}$ , but it is known that $\text{P}^A \neq \text{PH}^A$ for some oracle A. In 1993, Bernstein and Vazirani conjectured (at least verbally) the existence of oracle A such that $\text{BQP}^A \not\subseteq \text{PH}^A$ . The Theorem confirms this conjecture.

Links: The free version of the original paper is available here.

Go to the list of all theorems

The 2-to-2-Games Conjecture with imperfect completeness is true

You need to know: Class P, class NP, NP-hard problems, notation ${\mathbb Z}_m$ for set $\{0,1,2,\dots,m-1\}$ with addition and multiplication defined modulo m.

Background: For a fixed parameters $0\leq c \leq s \leq 1$ and integer m, consider the following problem. The input is a system of k linear equations in n variables $x_1, x_2, \dots, x_n$ over ${\mathbb Z}_m$ , each equation having the form $a \cdot x_i + b \cdot x_j = c$ , $a,b,c \in {\mathbb Z}_m$ , such that either (i) there is an assignment satisfying at least $s k$ of the equations, or (ii) every assignment satisfies fewer than $c k$ of the equations. The problem $\text{UG}(c,s,m)$ is to decide which of the cases (i) or (ii) is true.

The Theorem: On 10th January 2018, Subhash Khot, Dor Minzer, and Shmuel Safra submitted to the Electronic Colloquium on Computational Complexity a paper in which they proved that for every $0< c \leq s < 1/2$ there exists m such that $\text{UG}(c,s,m)$ is NP-hard.

Short context: The statement of the Theorem was known as “the 2-to-2-Games Conjecture with imperfect completeness”. It is a partial result towards proving famous Unique Games Conjecture (UGC) which predicts that the same statement remains correct for every $0< c \leq s < 1$ . The UGC is one of the fundamental conjectures in the theory of algorithms, which implies, in particular, various hardness of approximation results. For example, important minimum vertex cover problem was known to be NP-hard to approximate within any factor better than $c=10\sqrt{5}-21=1.3606...$ , see here. The Theorem implies this with better constant $c=\sqrt{2}=1.4142...$ . The full UGC would imply that the same is true with $c=2$ , which would be optimal.

Links: The free version of the original paper is available here.

Go to the list of all theorems

The u-invariant of any field of transcendence degree 2 over R is at most 4

You need to know: Field, subfield, field ${\mathbb R}$ of real numbers, matrix, symmetric matrix, matrix mupliplication, trasnpose $A^T$ of matrix A, determinant $\text{det}(A)$ of $n\times n$ matrix A.

Background: A subset S of a field K is algebraically independent over a subfield F if the elements of S do not satisfy any non-trivial polynomial equation with coefficients in F. The largest cardinality of such S is called the transcendence degree of K over F, which we denote $d_F(K)$ . If $K \neq F$ but $d_F(K)=0$ , K is called proper algebraic extension of F. A field F is called formally real if there is a total order $<$ on F such that, for all $a,b,c \in F$ , (i) if $a<b$ then $a+c < b+c$ and (ii) if $0<a$ and $0<b$ , then $0<a\cdot b$ . A formally real field is real-closed if it admits no proper formally real algebraic extensions. Any formally real field F with given ordering $<$ has a unique real-closed algebraic extension K preserving $<,$ which we denote $\text{cl}(F,<)$ .

Every symmetric $n\times n$ matrix A with entries $a_{ij}\in F$ generates a quadratic form $f=\sum\limits_{i=1}^n \sum\limits_{j=1}^n a_{ij} x_i x_j$ of dimension n over F. This form is called nondegenerate if $\text{det}(A)\neq 0$ . It is called anisotropic if there is no non-zero vector $(x_1,\dots,x_n)$ on which the form evaluates to zero. Let $K(F)$ be the set of all nondegenerate anisotropic forms over F. Quadratic forms generated by matrices A and B are equivalent if $A=MBM^T$ for some $n\times n$ matrix M over F with $\text{det}(M)\neq 0$ . If F is real-closed, any $f\in K(F)$ is equivalent to a form $\sum\limits_{i=1}^r x_i^2 - \sum\limits_{i=r+1}^{r+s} x_i^2$ for some positive integers $r,s$ . The difference $r-s$ is called the signature of f. If F is formally real, the signature of $f\in K(F)$ with respect to ordering $<$ is the signature of f as a form over $\text{cl}(F,<)$ . Let $K_0(F)$ be the set of all $f\in K(F)$ whose signature with respect to any ordering $<$ of F is $0$ . If F is not formally real, define $K_0(F)=K(F)$ . The general u-invariant $u(F)$ of field F is the maximal dimension of any form $f\in K_0(F)$ .

The Theorem: On 10th April 2018, Olivier Benoist submitted to arxiv a paper in which he proved that if F is any field of transcendence degree 2 over ${\mathbb R}$ , then $u(F)\leq 4$ .

Short context: The u-invariant of a field, usually defined as the maximal dimension of any form $f\in K(F)$ , is an important and well-studied concept, see here. However, with this definition it is infinite for any formally real field. The general u-invariant, introduced by Elman and Lam in 1973, coincides with the “usual” one when it is finite, but makes sense for formally real fields as well. In 1981, Pfister conjectured that if a field F has transcendence degree d over ${\mathbb R}$ , then $u(F)\leq 2^d$ . The Theorem verifies the $d=2$ case of this conjecture.

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

Go to the list of all theorems

The chromatic number of the plane is at least 5

You need to know: Distance between points on the plane.

Background: The chromatic number of the plane is the minimum number of colours that are needed to colour the plane so that no two points at distance exactly 1 from each other have the same colour.

The Theorem: On 8th April 2018, Aubrey de Grey submitted to arxiv a paper in which he proved that the chromatic number of the plane is at least 5.

Short context: The problem of determining the chromatic number of the plane was posed by Nelson in 1950, and is one of the beautiful problems that are easy to understand but difficult to solve. Because the vertices of any equilateral triangle with side length 1 should receive different colours, at least 3 colours in needed, and it is not much harder to see that in fact at least 4 colours is required. As observed by Isbell also in 1950, 7 colours suffices. These trivial bounds have not been improved for almost 70 years, until de Grey proved that 4 colours are not enough and at least 5 is needed.

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

Go to the list of all theorems