Most odd degree hyperelliptic curves have no finite rational points

You need to know: Polynomial, degree of a polynomial.

Background: Let ${\cal P}$ be the set of odd-degree polynomials $P(x)=\sum\limits_{i=0}^{2g+1} a_i x^{2g+1-i}$ with rational coefficients $a_i$ and leading coefficient $a_0=1$ . With change of variables $x'=u^2x$ , $y'=u^{2g+1}y$ , we can have new coefficients $a'_i=u^{2i}a_i$ , $i=1,2,\dots,2g+1$ , and, by selecting $u$ to be the common denominator of $a_1, a_2, \dots, a_{2g+1}$ , we can make all coefficients integers. After this, define height of $P\in{\cal P}$ by $H(P) = \max\{|a_1|, |a_2|^{1/2}, \dots, |a_{2g+1}|^{1/(2g+1)}\}$ . For fixed integer $g>0$ and real $X>0$ , let $\mu(X,g)$ be a fraction of the polynomials $P\in {\cal P}$ of degree $2g+1$ and height less than $X$ for which the equation $y^2=P(x)$ has no rational solutions.

The Theorem: On 1st February 2013, Bjorn Poonen and Michael Stoll submitted to arxiv a paper in which they proved that $\lim\limits_{g\to\infty}(\lim\limits_{X\to\infty}\mu(X,g)) = 1$ .

Short context: Set of real solutions to $y^2=P(x)$ for $P \in {\cal P}$ is known as odd degree hyperelliptic curve, and rational solutions are called finite rational points on this curve. In this terminology, the Theorem states that most odd degree hyperelliptic curves have no finite rational points. Moreover, Poonen and Stoll also proved for “almost all” polynomials $P\in{\cal P}$ in the same sense as in the Theorem, there is an explicit algorithm, with polynomial P as an input, and output certifying that there are indeed no rational solutions to $y^2=P(x)$ . In other words, there exists a universal method able to solve almost all equations in the form $y^2=P(x), \, P \in {\cal P}$ at once!

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

Go to the list of all theorems

Any diagram of the unknot with c crossings may be reduced to the trivial diagram using at most (236 c)^11 Reidemeister moves

You need to know: Curve in ${\mathbb R}^3$ , closed curves, self-intersecting and non-self-intersecting curves, injective map.

Background: A knot is a closed, non-self-intersecting curve in ${\mathbb R}^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$ . A knot equivalent to a circle is called unknot. 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. A knot diagram is trivial if it has no crossings. The Reidemeister moves of a knot diagram are (i) twist and untwist in either direction, or (ii) move one strand completely over another, or (iii) move a strand completely over or under a crossing.

The Theorem: On 1st February 2013, Marc Lackenby submitted to arxiv a paper in which he proved that for every diagram D of the unknot with c crossings there is a sequence of at most $(236 c)^{11}$ Reidemeister moves that transforms D into the trivial diagram. Moreover, every diagram in this sequence has at most $(7c)^2$ crossings.

Short context: Given 2 knot diagrams, how can we know if they represent the same knot? In 1927, Reidemeister proved that this is possible if and only if one diagram can be transformed into another by a sequence of Reidemeister moves. In particular, a diagram represents unknot if and only if it can be transformed into the trivial one. But how many moves is required for this for a diagram with c crossings? Before 2013, the best upper bound was $2^{kc}$ where $k=10^{11}$ , and it was an open question whether a polynomial number of moves suffices. 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

For every e>0, there is a set of n integers with no sum-free subset of size (1/3+e)n

You need to know: Integers, addition of integers.

Background: A set B of integers is called sum-free, if there are no distinct $x,y,z \in B$ such that $x+y=z$ .

The Theorem: On 19th January 2013, Sean Eberhard, Ben Green, and Freddie Manners submitted to arxiv a paper in which they proved that for every $\epsilon > 0$ , there is a set A of n integers such that every set $B \subset A$ with at least $(\frac{1}{3}+\epsilon)n$ elements is not sum-free (that is, B contains three distinct elements $x, y, z$ with $x + y = z$ ).

Short context: In 1965, Erdős proved that every set A of n integers has a sum-free subset B of size at least $n/3$ , and asked if the constant $1/3$ in this theorem can be improved. In 2011, Lewko found a 28-element set with maximal sum-free subset of size 11, showing that the constant cannot be greater than $\frac{11}{28} \approx 0.39$ . The theorem states that no constant greater than $\frac{1}{3}$ can work, so Erdős theorem is essentially the best possible.

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

Go to the list of all theorems

Fast 1.488-approximation for the uncapacitated facility location problem

You need to know: Algorithm, polynomial-time algorithm, approximation algorithm, approximation ratio, NP-hard problems, randomised algorithm, expectation.

Background: The (metric) uncapacitated facility location (UFL) problem is: given a set F of potential facility locations, each location $i\in F$ with a facility cost $f_i$ , a set C of clients and a metric d over $F\cup C$ , the goal is to find a subset $A \subseteq F$ of locations of open facilities, so that the total cost $S=\sum\limits_{i\in A} f_i + \sum\limits_{j\in C} d(j, i_j)$ is minimized, where $j_i$ is the closest open facility to client i.

The Theorem: On 26th October 2012, Shi Li submitted to Information and Computation a paper in which he proved the existence of a randomised polynomial-time algorithm for the UFL problem which gives a solution whose expected cost is at most $1.488$ times the cost of the optimal solution.

Short context: UFL is a well-studied problem with both theoretical and practical applications, which, however, is NP-hard to solve exactly. In 2002, Sviridenko proved that even approximation with ratio better than $1.463$ is NP-hard. In 2007, Byrka presented an algorithm with approximation ratio $1.5$ . The Theorem improves it to $1.488$ .

Links: The original paper is available here.

Go to the list of all theorems

Any finite union of intervals supports a Riesz basis of exponentials

You need to know: Notations ${\mathbb Z}$ , ${\mathbb R}$ , and ${\mathbb C}$ for sets of integer, real, and complex numbers, respectively. Notation $i$ for complex number $\sqrt{-1}$ , absolute value $|z|$ and conjugate $\bar{z}$ of $z\in{\mathbb C}$ , exponent of a complex number, integral, sum of infinite series.

Background: Let $S\subseteq {\mathbb R}$ be a set (for this Theorem, we only need the case when S in a finite union of intervals). Let $L^2(S)$ be the set of functions $f:S \to {\mathbb C}$ for which the integral $\int_S |f(x)|^2dx$ exists and finite. For $f,g \in L^2(S)$ , denote $(f,g)=\int_S f(x)\bar{g}(x)dx$ and $\|f\|^2=(f,f)$ . A sequence $\{f_n\}_{n=1}^\infty$ of functions in $L^2(S)$ is called complete if the only $f \in L^2(S)$ satisfying $(f,f_n)=0$ for all n is $f=0$ . A complete sequence $\{f_n\}_{n=1}^\infty$ is called a Riesz basis if there exist positive constants c and C such that $c\sum\limits_{n=1}^\infty |a_n|^2 \leq \|\sum\limits_{n=1}^\infty a_n f_n\| \leq C\sum\limits_{n=1}^\infty |a_n|^2$ for every sequence $\{a_n\}_{n=1}^\infty$ of complex numbers such that $\sum\limits_{n=1}^\infty |a_n|^2 < \infty$ .

The Theorem: On 23th October 2012, Gady Kozma and Shahaf Nitzan submitted to arxiv a paper in which they proved that, whenever $S\subseteq {\mathbb R}$ is a finite union of intervals, there exists a set $\Lambda\subset{\mathbb R}$ such that the functions $\left\{e^{i \lambda t}\right\}_{\lambda \in \Lambda}$ form a Riesz basis in $L_2(S)$ . Moreover, if $S \subseteq [0, 2\pi]$ then $\Lambda$ may be chosen to satisfy $\Lambda \subseteq {\mathbb Z}$ .

Short context: A Riesz basis of exponential functions as in the Theorem gives each function $f \in L^2(S)$ a unique representation $f (t) = \sum c_{\lambda} e^{i\lambda t}$ , which is useful for many applications. However, there are relatively few examples of sets S for which such basis is known to exists. For example, it was known that it exists if S is an interval. The Theorem extends this to the important case when S is a finite union of intervals.

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

Go to the list of all theorems

Cardinal numbers p and t are equal

You need to know: Notation ${\mathbb N}$ for the set of natural numbers. Cardinality of a set: sets A and B have the same cardinality (we write $|A|=|B|$ ) if there exists a bijection from A to B. We write $|A|\leq |B|$ if there exists a bijection from A to a subset of B. It is known that $|A|\leq |B|$ or $|B|\leq |A|$ for every $A,B$ .

Background: Let $A\subseteq^*B$ mean that set $\{x: x\in A, x\not\in B\}$ is finite. Let ${\mathbb N}^{\mathbb N}$ be the family of all infinite sequences of natural numbers, and let $D\subset {\mathbb N}^{\mathbb N}$ . We say that D has a pseudo-intersection if there is an infinite $A \subseteq {\mathbb N}$ such that $A\subseteq^*B$ for all $B \in D$ . We say that D has the strong finite intersection property (s.f.i.p. in short) if every nonempty finite subfamily of D has infinite intersection. D is called well ordered by $\subseteq^*$ if $A\subseteq^*B$ or $B\subseteq^*A$ for all $A,B \in D$ . D is called a tower if it is well ordered by $\subseteq^*$ and has no pseudo-intersection. Let $\textbf{p}$ be the smallest cardinality of $D\subset {\mathbb N}^{\mathbb N}$ which has the s.f.i.p. but has no pseudo-intersection. Let $\textbf{t}$ be the smallest cardinality of $D\subset {\mathbb N}^{\mathbb N}$ which is a tower.

The Theorem: On 27th August 2012, Maryanthe Malliaris and Saharon Shelah submitted to arxiv and the Journal of the AMS a paper in which they proved that $\textbf{p}=\textbf{t}$ .

Short context: Cantor proved in 1874 that the cardinality of set of integers (denoted $\aleph_0$ ) is strinctly less than the cardinality of set of real numbers (denoted $2^{\aleph_0}$ ). Clearly, both $\textbf{p}$ and $\textbf{t}$ are at least $\aleph_0$ and no more than $2^{\aleph_0}$ . It is easy to see that $\textbf{p}\leq\textbf{t}$ , since a tower has the s.f.i.p. An old open question asks whether equality holds. The Theorem asnwers 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 Waring rank of any monomial x_1^(a_1)…x_n^(a_n) with a_1<=…<=a_n is (a_2+1)…(a_n+1)

You need to know: Complex numbers, polynomials in n variables and their multiplication.

Background: The linear form in n variables in an expression in the form $L=c_1x_1+\dots+c_nx_n$ , where $c_1,c_2, \dots, c_n$ are come complex coefficients. The Waring rank $\text{rk}(M)$ of monomial $M=x_1^{a_1}x_2^{a_2}\dots x_n^{a_n}$ of degree $d=\sum\limits_{i=1}^n a_i$ is the least value of s for which there exist linear forms $L_1,\dots,L_s$ such that $M=\sum\limits_{i=1}^s L_i^d$ .

The Theorem: On 2nd July 2012, Enrico Carlini, Maria Catalisano, and Anthony Geramita submitted to the Journal of Algebra a paper in which they proved the following result. Let $M=x_1^{a_1}x_2^{a_2}\dots x_n^{a_n}$ be a monomial in $n\geq 2$ variables, and let $1 \leq a_1 \leq \dots \leq a_n$ . Then $\text{rk}(M)=\prod\limits_{i=2}^n(a_i+1)$ .

Short context: Every natural number is the sum of at most 4 squares, or 9 cubes, or 19 fourth powers, etc. Waring’s problem asks whether for each positive integer k there exists positive integer $g(k)$ such that every natural number is the sum of at most $g(k)$ k-th powers. The Hilbert–Waring theorem, proved by Hilbert in 1909, gives a positive answer, and the exact formula for $g(k)$ has been derived in later works. The Theorem solves a similar problem for monomials.

Links: The original paper is available here.

Go to the list of all theorems

Unitary perturbation of any matrix is well invertible with high probability

You need to know: Square matrix with complex entries, eigenvalue of a square matrix, identity matrix I, conjugate transpose $U^*$ of matrix $U$ , unitary matrix (matrix $U$ such that $U^*U=UU^*=I$ ), group, unitary group $U(n)$ (group of all unitary matrices with matrix multiplication as group operation), notation ${\mathbb P}$ for probability, uniform distribution in the unitary group.

Background: For any $n \times n$ matrix A, the eigenvalues of $A^*A$ are real and non-negative. The square roots of these eigenvalues are called singular values of A. Let $s_{\text{min}}(A)$ be the smallest singular value.

The Theorem: On 22nd June 2012, Mark Rudelson and Roman Vershynin submitted to arxiv and the Journal of the AMS a paper in which they proved the following result. Let D be an arbitrary fixed $n \times n$ matrix, $n\geq 2$ . Let U be a random matrix uniformly distributed in the unitary group $U(n)$ . Then ${\mathbb P}\left(s_{\text{min}}(D+U)\leq t\right) \leq t^c n^C$ for all $t>0$ and some positive constants $C,c$ .

Short context: The smallest singular value of a square matrix A is inverse proportional to the norm of $A^{-1}$ , and therefore provides a quantitative measure of invertibility of A. In earlier works (see here and here), Rudelson and Vershynin analyse invertibility of random matrices with independent entries. The Theorem did the same for random unitary perturbation of a fixed matrix D. It is important that the estimate in the Theorem does not depend on D.

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

Go to the list of all theorems

Random n by n matrix (with 4 moments of entries Gaussian) has (2n/pi)^(1/2)+o(n^(1/2)) real eigenvalues

You need to know: Know: $n \times n$ matrix with real entries, eigenvalues, probability, random variable, jointly independent random variables, standard normal distribution, notation $E$ for expectation, almost sure convergence, small o notation.

Background: For positive integer n, let $M_n$ be $n \times n$ matrix whose entries $\xi_{ij}$ are jointly independent real random variables which (i) have exponential decay, i.e., $P(|\xi_{ij}|\geq t) \leq C \exp(-t^c)$ for some constants $C,c>0$ (independent of n) and all $i,j$ , and (ii) $E[\xi_{ij}^k]=E[Z^k]$ for $k=1,2,3,4$ and all $i,j$ , where Z is the random variable having standard normal distribution.

The Theorem: On 9th June 2012, Terence Tao and Van Vu submitted to arxiv a paper in which they proved that $M_n$ has $\sqrt{\frac{2n}{\pi}}+o(\sqrt{n})$ real eigenvalues asymptotically almost surely.

Short context: The study of eigenvalues of large random matrices is one of the central themes in probability theory. The Theorem estimates how many of the eigenvalues are real. Earlier, this result was known to hold only for the special case when all $\xi_{ij}$ has standard normal distribution. In fact, the Theorem is just one out of many corollaries of a much more general theorem, which, very roughly speaking, states that many properties of the eigenvalues of a random matrix with independent entries depend only on the first four moments of the entries. Unlike previous results in the literature, this theorem does not require matrix $M_n$ to be symmetric. It also does not require entries $\xi_{ij}$ to be identically distributed.

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

Go to the list of all theorems

The probability that the random walk in a bounded degree planar graph avoids its initial location for T steps is at most C/log T

You need to know: Graph, finite graph, planar graph, degree of a vertex in a graph, probability, selection uniformly at random.

Background: A simple random walk on graph G is the process which starts at some vertex $v_0$ at time $t=0$ , and then at times $t=1,2,\dots$ moves to an adjacent vertex selected uniformly at random. Assuming that initial vertex $v_0$ is selected uniformly at random from vertices of G, denote $\phi(T,G)$ the probability that the walk does not return to $v_0$ for T steps. Let ${\cal G}(D)$ be the set of all finite planar graphs with degrees of all vertices bounded by D, and let $\phi_D(T)=\sup\limits_{G \in {\cal G}(D)} \phi(T,G)$ .

The Theorem: On 4th June 2012, Ori Gurel-Gurevich and Asaf Nachmias submitted to arxiv and the Annals of Mathematics a paper in which they proved that for any $D\geq 1$ , there exists a constant $C=C(D)<\infty$ such that $\phi_D(T) \leq \frac{C}{\log T}$ for any $T \geq 2$ .

Short context: The study of random walks on graphs is one of the central research directions in probability theory with numerous applications, and walks on bounded-degree planar graphs form an important special case. In 2001, Benjamini and Schramm proved that $\phi_D(T) \to 0$ as $T\to\infty$ , but left the rate of decay of $\phi_D(T)$ as an open question. Because it is known that $\phi_D(T) \geq \frac{c}{\log T}$ for some constant $c>0$ , the Theorem answers this question up to a constant factor.

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

Go to the list of all theorems