Any order-reversing involution on convex functions is, up to linear terms, Legendre transform

You need to know: Euclidean space ${\mathbb R}^n$ , scalar product $\langle x,y \rangle=\sum\limits_{i=1}^n x_iy_i$ in ${\mathbb R}^n$ , extended real line $\bar{\mathbb R} = {\mathbb R}\cup\{\pm \infty\}$ , convex function $\phi: {\mathbb R}^n \to \bar{\mathbb R}$ , lower-semi-continuous function $\phi: {\mathbb R}^n \to \bar{\mathbb R}$ , supremum.

Background: A map $B:{\mathbb R}^n \to {\mathbb R}^n$ is called linear if $B(x+y)=B(x)+B(y)$ and $B(\alpha x)=\alpha B(x)$ for all $x,y \in {\mathbb R}^n$ and $\alpha\in{\mathbb R}$ , symmetric if $\langle Ax,y \rangle = \langle x,Ay \rangle$ for all $x,y \in {\mathbb R}^n$ , and invertible if $B(x)\neq 0$ whenever $x \neq 0$ . Let ${\cal C}({\mathbb R}^n)$ denote the set of all lower-semi-continuous convex functions $\phi: {\mathbb R}^n \to \bar{\mathbb R}$ . Map ${\cal L}:{\cal C}({\mathbb R}^n) \to {\cal C}({\mathbb R}^n)$ given by $({\cal L}\phi)(x) = \sup\limits_{y \in {\mathbb R}^n}(\langle x,y \rangle -\phi(y))$ is called the Legendre transform.

The Theorem: On 1st May 2007, Shiri Artstein-Avidan and Vitali Milman submitted to the Annals of Mathematics a paper in which they proved that for every map $T :{\cal C}({\mathbb R}^n) \to {\cal C}({\mathbb R}^n)$ (defined on the whole domain ${\cal C}({\mathbb R}^n)$ ) satisfying (P1) $TTf=f$ and (P2) $f \leq g$ implies $Tf \geq Tg$ , there exists a constant $C_0 \in {\mathbb R}$ , a vector $v_0\in {\mathbb R}^n$ , and an invertible symmetric linear map B such that $(T f)(x) = ({\cal L}f)(Bx+v_0) + \langle x, v_0 \rangle + C_0$ for all $x \in {\mathbb R}^n$ .

Short context: The Legendre transform is a central tool in convex analysis and optimisation, with numerous applications. Map $T$ satisfying properties (P1) and (P2) in the Theorem is called an order-reversing involution. Is it easy to check that the Legendre transform satisfies these properties. The Theorem states a somewhat surprising converse: any order-reversing involution must in fact be the Legendre transform, up to linear terms.

Links: The original paper is available here. See also Section 9.5 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Entire function whose escaping set has only bounded path-components

You need to know: Set ${\mathbb C}$ of complex numbers, absolute value $|z|$ of $z\in{\mathbb C}$ , limits, function $f(z)$ in complex variable z, its derivative $f'(z)$ , polynomials, notation $f^n(z)$ for $f(f(...f(z)...))$ where f is applied n times, bounded subsets of ${\mathbb C}$ , path (or curve) connecting points $x \in {\mathbb C}$ and $y \in {\mathbb C}$ .

Background: A function $f:{\mathbb C}\to {\mathbb C}$ is called entire if $f'(z)$ exists for all $z\in {\mathbb C}$ . An entire function f is called transcendental if it is not a polynomial. An escaping set of a transcendental entire function f is the set $I(f)=\{z\in {\mathbb C} : \lim\limits_{n\to\infty}|f^n(z)|=\infty\}$ . A path-component of $I(f)$ is the set of all $y\in I(f)$ which can be connected by a path $P \subset I(f)$ to any fixed $x\in I(f)$ .

The Theorem: On 24th April 2007, Günter Rottenfusser, Johannes Rückert, Lasse Rempe, and Dierk Schleicher submitted to arxiv a paper in which they proved the existence of a transcendental entire function f whose escaping set $I(f)$ has only bounded path-components.

Short context: The study of limiting behaviour of sequence $f^n(z)$ for transcendental entire function f goes back to 1926 paper of Fatou. This is an example of dynamical system. In 1989, Eremenko, formalising a question of Fatou, asked whether the escaping set $I(f)$ of any transcendental entire function f has the property that every point $z\in I(f)$ can be joined with $\infty$ by a curve in $I(f)$ . The Theorem answers this question in negative.

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

Go to the list of all theorems

Entropies of multidimensional shifts of finite type may be impossible to compute

You need to know: Set ${\mathbb Z}^d$ of vectors $y=(y_1, \dots, y_d)$ with integer coordinates, countable and uncountable sets, computable real number.

Background: Let $F \subset {\mathbb Z}^d$ be a finite set of $|F|$ points in ${\mathbb Z}^d$ , and let $\Sigma$ be a finite set of $|\Sigma|$ colours. Let L be any subset of $|F|^{|\Sigma|}$ colourings of F. A translate of F by $x \in {\mathbb Z}^d$ is the set $\{x + y, \,|\, y \in F\}$ . A colouring of ${\mathbb Z}^d$ in colours from $\Sigma$ is called admissible for L if all translates of F are coloured according to a pattern belonging to L. The shift of finite type (SFT) defined by L is the set X of all admissible colourings of ${\mathbb Z}^d$ .

For every positive integer n, let $F_n$ be the set of points $(y_1, \dots, y_d) \in {\mathbb Z}^d$ such that $1 \leq y_i \leq n$ for all $i=1,2,\dots, d$ . For the SFT X, let $f_X(n)$ be the number of different colourings of $F_n$ which can appear in some colouring $x \in X$ . The (topological) entropy of X is then defined as $h(X) = \lim\limits_{n \to \infty} \frac{1}{n^d}\log_2 f_X(n)$ .

The Theorem: On 7th March 2007, Michael Hochman and Tom Meyerovitch submitted to arxiv a paper in which they proved the existence of SFT X such that real number $y=h(X)$ is not computable.

Short context: Because there are uncountably many real numbers and only countably many algorithms, there exist real numbers which are not computable. However, important real numbers naturally arising in mathematics and applications, such as $\pi=3.14159...$ and $e=2.71828...$ , are computable. The Theorem provides examples of real numbers which are not computable but quite meaningful, because SFTs are important objects of study in symbolic dynamics, and the entropy is their most studied invariant. The Theorem is a corollary of a more general result stating that a real number $h\geq 0$ is the entropy of some SFT if and only if it is right recursively enumerable, that is, there is a computable sequence of rational numbers converging to h from above.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 10.9 of this book for an accessible description of the Theorem.

Go to the list of all theorems

There exists an outer billiards system with an unbounded orbit

You need to know: Euclidean plane ${\mathbb R}^2$ , convex set in ${\mathbb R}^2$ , bounded set or sequence in ${\mathbb R}^2$ , the notion of (Lebesgue) almost every point in ${\mathbb R}^2$ .

Background: Given a bounded convex set $S \subset {\mathbb R}^2$ , and a point $x_0 \in {\mathbb R}^2$ outside S, let $x_1 \in {\mathbb R}^2$ be the point such that the segment $x_0x_1$ is tangent to S at its midpoint and a person walking from $x_0$ to $x_1$ would see S on the right. Such $x_1$ exists and unique for almost every $x_0 \in {\mathbb R}^2$ , and the map $x_0 \to x_1$ is called the outer billiards map. Iterating this maps starting from $x_0$ , we get an infinite sequence $x_0 \to x_1 \to x_2 \to \dots$ , which is called an outer billiards orbit of $x_0$ .

The Theorem: On 3rd February 2007, Richard Schwartz submitted to arxiv a paper in which he proved the existence of set $S \subset {\mathbb R}^2$ and $x_0 \in {\mathbb R}^2$ such that the outer billiards orbit of $x_0$ is well-defined and unbounded.

Short context: The question whether an outer billiards orbit can be unbounded was asked by Neumann in the 1950s, and since then has been a guiding question in the field. The Theorem answers this question affirmatively. In fact, Schwartz provides an explicit example of set S in the Theorem: this is the convex quadrilateral known as the Penrose kite.

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

Go to the list of all theorems

Littlewood’s question about zeros of cosine polynomials has a negative answer

You need to know: Cosine function $\cos$ , logarithm $\log$ .

Background: For integer $N>0$ , let $f(N)$ be the minimal number of solutions in $[0,2\pi)$ of the equation $\sum\limits_{i=1}^{N} \cos(n_ix)=0$ , where $n_1, n_2,\dots, n_N$ are integers which are all different.

The Theorem: On 26th November 2006, Peter Borwein, Tamás Erdélyi, Ron Ferguson, and Richard Lockhart submitted to the Annals of Mathematics a paper in which they proved the existence of a constant $C>0$ , a sequence of integers $N_1<N_2<\dots<N_m<\dots$ , such that $f(N_m) \leq CN_m^{5/6}\log N_m$ for all m.

Short context: In 1968, Littlewood asked to estimate $f(N)$ and guessed that the answer is “Possibly $f(N)=N-1$ , or not much less”. The Theorem proves that in fact $f(N)$ can be much less that $N-1$ .

Links: The original paper is available here. See also Section 8.7 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Characterization of stability-preserving linear operators on polynomials

You need to know: Polynomials, degree of a polynomial, linear operator.

Background: Let ${\cal P}_k$ , $k=1,2$ , be the set of all polynomials in k variables with real coefficients. A polynomial $P \in {\cal P}_1$ of degree n is called stable (or hyperbolic) if it has n real roots (counting multiplicity). We say that stable polynomials $P, Q \in {\cal P}_1$ are interlacing if either $\alpha_1 \leq \beta_1 \leq \alpha_2 \leq \beta_2 \leq \dots$ or $\beta_1 \leq \alpha_1 \leq \beta_2 \leq \alpha_2 \leq \dots$ , where $\alpha_1 \leq \alpha_2 \leq \dots \leq \alpha_n$ and $\beta_1 \leq \beta_2 \leq \dots \leq \beta_m$ are roots of $P(x)$ and $Q(x)$ , respectively.

A polynomial $P \in {\cal P}_2$ is stable if $Q(t)=P(a+bt, c+dt)\in {\cal P}_1$ is stable for any real $a,b,c,d$ such that $b>0$ and $d>0$ . For a linear operator $T:{\cal P}_1\to {\cal P}_1$ , let $S_T:{\cal P}_2\to {\cal P}_2$ be a linear operator such that $S_T(x^ky^l) = T(x^k)y^l$ , for all $k\geq 0$ and $l\geq 0$ . We say that linear operator $T:{\cal P}_1\to {\cal P}_1$ preserves stability if $T(P)$ is a stable polynomial whenever $P$ is stable.

The Theorem: On 18th July 2006, Julius Borcea and Petter Brändén submitted to arxiv a paper in which they proved that a linear operator $T:{\cal P}_1\to {\cal P}_1$ preserves stability if and only if either (a) $T(x^k)=a_k P(x)+ b_k Q(x)$ , where $a_k,b_k$ , $k=0,1,2,\dots$ are real numbers, and $P(x)$ and $Q(x)$ are some fixed (independent of k) stable interlacing polynomials; or (b) $S_T[(x+y)^k]\in {\cal P}_2$ is a stable polynomial for all $k=0,1,2,\dots$ ; or (c) $S_T[(x-y)^k]\in {\cal P}_2$ is a stable polynomial for all $k=0,1,2,\dots$ .

Short context: Examples of linear operators $T:{\cal P}_1\to {\cal P}_1$ which preserves stability are differentiation and multiplication by a fixed stable polynomial. A fundamental long-standing open problem was to describe all such operators. In 1914, Pólya and Schur did this for operators such that $T(x^k) = \lambda_k x^k, k\geq 0$ , where $\{\lambda_k\}_{k=0}^\infty$ is a given sequence of numbers. The Theorem provides a characterization of all stability-preserving operators.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 9.8 of this book for an accessible description of the Theorem.

Go to the list of all theorems

There exist quadratic polynomials that have a Julia set of positive area

You need to know: Basic complex analysis, set ${\mathbb C}$ of complex numbers, absolute value $|z|$ of complex number z, boundary of a set, area (that is, Lebesgue measure) of a set $A \subset {\mathbb C}$ , the notion of (Lebesgue) almost all.

Background: For polynomial $f:{\mathbb C} \to {\mathbb C}$ , let $K_f \subset {\mathbb C}$ be the set of points $z_0\in {\mathbb C}$ such that the sequence $z_0, z_1=f(z_0), z_2=f(z_1), \dots, z_{n+1}=f(z_n), \dots$ is bounded, that is, $|z_n|\leq B, \, \forall n$ for some $B \in {\mathbb R}$ . The boundary $J_f$ of $K_f$ is called the Julia set of f.

The Theorem: On 18th May 2006, Xavier Buff and Arnaud Cheritat submitted to arxiv a paper in which they proved the existence of quadratic polynomials that have a Julia set of positive area.

Short context: Julia set is a fundamental concept in the theory of complex dynamics, because it consists of values $z_0$ such that an arbitrarily small perturbation can cause significant changes in the sequence of iterated function values. The Julia set is known to have zero area for many families of quadratic polynomials, including a family which contains almost all such polynomials. The Theorem proves, however, the existence of exceptional quadratic polynomials whose Julia set has positive area.

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

Go to the list of all theorems

There exists an exhaustive submeasure that is not equivalent to a measure

You need to know: Boolean algebra of sets.

Background: Let ${\cal B}$ be a Boolean algebra of sets. A map $\nu:{\cal B} \to {\mathbb R}$ is called a submeasure if the following holds: (i) $\nu(\emptyset) = 0$ , (ii) $\nu(A) \leq \nu(B)$ for every $A,B \in {\cal B}$ such that $A \subset B$ , and (iii) $\nu(A \cup B) \leq \nu(A) + \nu(B)$ for every $A,B \in {\cal B}$ . A submeasure $\nu$ is called a (finitely additive) measure if $\nu(A \cup B) = \nu(A) + \nu(B)$ whenever sets $A,B \in {\cal B}$ are disjoint. A submeasure $\nu$ is called exhaustive if $\lim\limits_{n\to \infty}\nu(E_n)=0$ for every sequence $\{E_n\}_{n=1}^\infty$ of elements of ${\cal B}$ such that $E_n \cap E_m = \emptyset$ whenever $n\neq m$ . We say that submeasure $\nu_1$ is absolutely continuous with respect to a submeasure $\nu_2$ if for every $\epsilon>0$ there exists an $\alpha>0$ such that $\nu_1(A) \leq \epsilon$ for every $A \in {\cal B}$ with $\nu_2(A) \leq \alpha$ .

The Theorem: On 27th January 2006, Michel Talagrand submitted to arxiv a paper in which he proved the existence of a Boolean algebra ${\cal B}$ of sets, and a nonzero exhaustive submeasure $\nu$ on it, which is not absolutely continuous with respect to any measure.

Short context: Any measure is exhaustive. Moreover, if a submeasure is absolutely continuous with respect to a measure, it is exhaustive. One of the many equivalent formulations of famous Maharam’s problem is whether the converse is true. The Theorem gives a negative answer to this question.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 8.13 of this book for an accessible description of the Theorem.

Go to the list of all theorems

The B. and M. Shapiro conjecture in real algebraic geometry is true

You need to know: Set ${\mathbb C}$ of complex numbers, polynomials in complex variable, root of a polynomial, derivative, notation $P^{(j)}(z)$ for j-th derivative of polynomial $P(z)$ , matrix, determinant of a matrix, vector space, basis of a vector space.

Background: Let ${\cal P}=\{P_1(z), P_2(z), \dots, P_k(z)\}$ be a finite set of polynomials in complex variable z with complex coefficients. The complex span S of ${\cal P}$ is the set of polynomials $P(z)$ of the form $P(z)=\sum\limits_{i=1}^k \lambda_i P_i(z)$ for some $\lambda_i \in {\mathbb C}, \, i=1,\dots,k$ . The Wronskian $W(z)$ of ${\cal P}$ is the determinant of the $k \times k$ matrix with entries $P^{(j-1)}_i(z), \, i=1,\dots,k, \, j=1,\dots,k$ .

The Theorem: On 14th December 2005, Evgeny Mukhin, Vitaly Tarasov, and Alexander Varchenko submitted to arxiv a paper in which they proved that if all roots of the Wronskian of a set ${\cal P}$ of polynomials are real, then the complex span of ${\cal P}$ has a basis consisting of polynomials with real coefficients.

Short context: The Theorem confirms the 1995 conjecture known as the B. and M. Shapiro conjecture in real algebraic geometry. Earlier, it was known only in the case $k=2$ .

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 9.10 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Fast algorithm to approximately fit a C^m-smooth function to data

You need to know: Euclidean space ${\mathbb R}^n$ , space of functions $C^m({\mathbb R}^n)$ (see this previous theorem description), notation $||F||_{C^m({\mathbb R}^n)}$ for the norm in this space, algorithm, its running time and memory use.

Background: Let $E \subset {\mathbb R}^n$ be a finite set of cardinality N. Let $f:E \to {\mathbb R}$ and $\sigma: E \to [0, \infty)$ be given functions on E. Let $||f||_{C^m(E,\sigma)}$ denote the infimum of all $M>0$ for which there exists $F \in C^m({\mathbb R}^n)$ such that $||F||_{C^m({\mathbb R}^n)}\leq M$ and $|F(x)-f(x)| \leq M \sigma(x)$ for all $x \in E$ . We say that two numbers $X, Y \geq 0$ determined by $E, f, \sigma, m, n$ have the same order of magnitude if $cX \leq Y \leq CX$ , where constants c and C depends only on m and n. By “compute the order of magnitude of X” we mean compute some Y such that X and Y have the same order of magnitude.

The Theorem: On 6th October 2005, Charles Fefferman and Bo’az Klartag submitted to the Annals of Mathematics a paper in which they presented an algorithm and proved that it computes, given $E, f, \sigma, m, n$ , the order of magnitude of $||f||_{C^m(E,\sigma)}$ in time at most $CN \log N$ and using memory at most $CN$ , where the constant C depends only on m and n.

Short context: Function $f:E \to {\mathbb R}$ represents N data points, to which we want to feet a smooth function F with smallest possible $C^m({\mathbb R}^n)$ norm. We may want the exact feet to data (case $\sigma=0$ ), or approximate one ( $\sigma \neq 0$ ). The Theorem proves the existence of efficient algorithm which approximately computes the smallest possible $C^m({\mathbb R}^n)$ norm of F we can achieve. In the subsequent paper, we same authors also presented algorithm which computes F itself.

Links: The original paper is available here. See also Section 9.2 of this book for an accessible description of the Theorem.

Go to the list of all theorems