## Polymath 10 Emergency Post 5: The Erdos-Szemeredi Sunflower Conjecture is Now Proven.

While slowly writing Post 5 (now planned to be Post 6) of our polymath10 project on the Erdos-Rado sunflower conjecture, the very recent proof (see this post) that cap sets have  exponentially small density has changed matters greatly! It implies a weaker version of the Erdos-Rado sunflower conjecture made by Erdos and Szemeredi. Let me remind the readers what these conjectures are:

The Erdos-Szemeredi Sunflower Conjecture: There is $\epsilon >0$ such that a family of subsets of [n] without a sunflower of size three have at most $(2-\epsilon)^n$ sets. (Erdos and Szemeredi have made a similar conjecture for larger sunflowers.)

The strong Cap Set Conjecture: There is $\delta >0$ such that a subset of $\mathbb Z_3^n$ without three distinct elements a, b, and c with a+b+c=0 contains at most $(3-\delta)^n$ elements.

Results  by Erdos and Szemeredi  give  that the Erdos Rado sunflower conjecture implies the Erdos-Szemeredi sunflower conjecture.  This implication is Theorem 2.3 in the paper  On sunflowers  and matrix multiplication by Noga Alon, Amir Shpilka, and Christopher Umans where many implications between various related conjectures are discussed (we discussed it in this post). One implication by Noga, Amir and Chris is that the  strong cap set Conjecture implies the  Erdos-Szemeredi sunflower conjecture!

In order that the post with the cap set startling news will remain prominent, I will put the rest of this post under the fold.

## Mind Boggling: Following the work of Croot, Lev, and Pach, Jordan Ellenberg settled the cap set problem!

A quote from a recent post from Jordan Ellenberg‘s blog Quomodocumque:

Briefly:  it seems to me that the idea of the Croot-Lev-Pach paper I posted about yesterday (GK: see also my last post) can indeed be used to give a new bound on the size of subsets of F_3^n with no three-term arithmetic progression! Such a set has size at most (2.756)^n. (There’s actually a closed form for the constant, I think, but I haven’t written it down yet.)

Here’s the preprint. It’s very short. I’ll post this to the arXiv in a day or two, assuming I (or you) don’t find anything wrong with it, so comment if you have comments!

This is amazing! The cap set problem was quite popular here on the blog, see also Tao’s 2007 post, and Jordan made also quite an effort over the years in proving the other direction before proving this direction. (Fortunately for our profession, success for two conflicting statements was avoided.) Congratulations to Jordan, Ernie, Seva, and Peter!

Update: Congratulations also to Dion Gijswijt who also derived a similar solution to the cap set problem based on CLP! See this comment on Quomodocumque.

Updates: See also this post by Tao (presenting a symmetric version of the proof), this post by Gowers, this post in by Luca Trevisan, and this post by Peter Cameron, and this post by Anurag Bishnoi. See also this lovely quanta article  Set proof stuns mathematicians by Erica Klarreich. See also the post Polynomial prestidigitation on GLL. There, among other things the relation to Smolensky’s early use of the “halving degree trick” for the polynomial method is noted. (See also this comment.)

Of course, there is also plenty of more to desire: Full affine lines for $q>3$, higher dimensional affine subspaces for $q\ge3$, some application to better bounds for Roth’s theorem, Szemeredi’s theorem, (for more, see this comment by Terry Tao,)… It is all very exciting.

Noga Alon also pointed out that the solution of the cap set problem also settles affirmatively the Erdos-Szemeredi weaker version of the Erdos-Rado Delta-system conjecture (via the connections discussed in this post) and also shows that a certain direction for showing that ω=2 for matrix multiplication cannot possibly work. The Erdos-Rado sunflower conjecture is still (at least for a few days) open.

Can the affine results be applied for integers or for combinatorial setting? The geometries are quite different but still… This is of great interest here (and also for other problems like the Kakeya problem). Starting from a positive density set in $Z_3^n$ considered as a subset of $Z_{3^{100}}^m$ we can find there a $10^{100}$-dimensional affine subspace contained in the set. Can’t we use it (or such a subspace with a few additional pleasant properties) to get just a single combinatorial line over $Z_3$, or, easier, just a 3-term arithmetic progression when $A$ represent a subset of {1,2,… , $3^n$ }?  A bit later: These thoughts about the relevance of finite field results to questions for the integers (or reals) are not really relevant to the new discovery.  But what seems to be relevant is the possibility to transfer the new method for the cap set problem back to the question on better lower bounds for Roth’s theorem.

More updates: Eric Naslund and Will Sawin gave a direct proof based on the polynomial method for the Erdos-Szemeredi sunflower conjecture, and an even  stronger result is given by Naslund here. (Eric also has stronger quantitative bounds for Erdos-Szemeredi based on bounds for cap sets.)   Ben Green has studied the analogue of Sarkozy’s theorem in function fields (other results on function fields are mentioned by Bloom in this comment);  Variants on the CLPEG-arguments are described by Petrov and by Bishnoi over the comment threads here and here.  Here is a paper by Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Chris Umans, on consequences of the cap set result for fast matrix multiplication.

More updates (May 31): New applications are mentioned in a new post on quomodocumque: sumsets and sumsets of subsets including a lovely new application by Jordan, a link to a paper  by Robert Kleinberg: A nearly tight upper bound on tri-colored sum-free sets in characteristic 2. And here is a link to a new manuscript by Fedor Petrov Many Zero Divisors in a Group Ring Imply Bounds on Progression–Free Subsets.

One more: (Quoting Arnab Bhattacharyya, June 15 2016 on GLL) Another amazing result that follows from these techniques for one of my favorite problems: http://arxiv.org/pdf/1606.01230v2.pdf. Fox and LM Lovasz improve the bounds for the arithmetic triangle removal lemma dramatically, from a tower of two’s to polynomial!

More (Early July 2016) : An interesting new post on Ellenberg’s blog.

David Conlon pointed out to two remarkable papers that appeared on the arxive:

### Joel Moreira solves an old problem in Ramsey’s theory.

Monochromatic sums and products in $\mathbb N$.

Abstract: An old question in Ramsey theory asks whether any finite coloring of the natural numbers admits a monochromatic pair ${x+y,xy}.$ We answer this question affirmatively in a strong sense by exhibiting a large new class of non-linear patterns which can be found in a single cell of any finite partition of N. Our proof involves a correspondence principle which transfers the problem into the language of topological dynamics. As a corollary of our main theorem we obtain partition regularity for new types of equations, such as $x^2-y^2=z$ and $x^2+2y^2-3z^2=w$.

### Ernie Croot, Vsevolod Lev, Peter Pach gives an exponential improvement to Roth over $\mathbb Z_4^n$.!

Abstract: We show that for integer $n>0$, any subset $A$ of $Z^n_4$ free of three-term arithmetic progressions has size $|A|<2(\sqrt n +1)4^{cn}$, with an absolute constant $c$ approximately equal to 0.926.

David Ellis made a few comments: Three ‘breakthrough’ papers in one week – one in combinatorial geometry (referring to the Erdos-Szekeres breakthrough) , one in additive number theory and one in Ramsey theory – not bad!; . I’ve now read all of the proofs and am sure (beyond reasonable doubt) that they’re all correct – an unusually short time-frame, for me at any rate! The Croot-Lev-Pal Pach paper is a really beautiful application of the polynomial method – a ‘genuinely’ self-contained paper, too, and very nicely written.

I find the $Z_4^n$ result quite mind boggling! What does it say about $Z_3^n$???

### Post by Green

In another facebook post Ben Green writes:  I Wish I could just casually hand Paul Erdos a copy of Annals of Math 181-1. 4 of the 7 papers are: solution to the Erdos distance conjecture by Guth and Nets Katz, solution to the Erdos covering congruence conjecture by Hough, Maynard’s paper on bounded gaps between primes, and the Bhargava-Shankar paper proving that the average rank of elliptic curves is bounded.

## The Erdős Szekeres polygon problem – Solved asymptotically by Andrew Suk.

Here is the abstract of a recent paper by Andrew Suk. (I heard about it from a Facebook post by Yufei Zhao. I added a link to the original Erdős Szekeres’s paper.)

Let ES(n) be the smallest integer such that any set of ES(n) points in the plane in general position contains n points in convex position. In their seminal 1935 paper, Erdős and Szekeres showed that

$ES(n)\le {{2n-4}\choose{n-2}}+1=4^{n-o(n)}$

In 1960, they showed that

$ES(n) \ge 2^{n-2}+1$,

and conjectured this to be optimal. Despite the efforts of many researchers, no improvement in the order of magnitude has ever been made on the upper bound over the last 81 years. In this paper, we nearly settle the Erdős-Szekeres conjecture by showing that

$ES(n)=2^{n+o(n)}$.

This is amazing! The proof uses a 2002 “positive-fraction” version of the Erdős-Szekeres theorem by Pór and Valtr.

Among the many beautiful results extending, applying, or inspired by the Erdős Szekeres theorem let me mention an impressive recent body of works on the number of points in $\mathbb R ^d$ which guarantee n points in cyclic position. A good place to read about it is the paper by Bárány, Matoušek and Pór Curves in $\mathbb R^d$  intersecting every hyperplane at most d+1 times, where references to earlier papers by Conlon, Eliàš,  Fox, Matoušek, Pach, Roldán-Pensado, Safernová, Sudakov, Suk, and others.

## The Quantum Computer Puzzle @ Notices of the AMS

### The Quantum Computer Puzzle

My paper “the quantum computer puzzle” has just appeared in the May 2016 issue of Notices of the AMS. Here are the beautiful drawings for the paper (representing the “optimistic view” and the “pessimistic view”) by my daughter Neta.

And the summary of my view

Understanding quantum computers in the presence of noise requires consideration of behavior at different scales. In the small scale, standard models of noise from the mid-90s are suitable, and quantum evolutions and states described by them manifest a very low-level computational power. This small-scale behavior has far-reaching consequences for the behavior of noisy quantum systems at larger scales. On the one hand, it does not allow reaching the starting points for quantum fault tolerance and quantum supremacy, making them both impossible at all scales. On the other hand, it leads to novel implicit ways for modeling noise at larger scales and to various predictions on the behavior of noisy quantum systems.

The nice thing is that my point of view is expected to be tested in various experimental efforts to demonstrate quantum computational supremacy in the next few years.

Updates (April, 24 2016): Here is an expanded version of the paper, with references, additional predictions and discussion. Here is a related post on GLL.

### Polymath10 Plans, polymath11 news, and other plans.

The plan for polymath10: I hope to come back to it soon, report on some computer experimentation  and, of course, further comments on post 4 are most welcome. I hope to be able to report on some computer experimentation regarding the various conjectures and ideas.  I am planning to launch a fifth post in May.  Overall, I consider one year as a good time span for the project. Post 4 of Polymath11 is still active on Gowers’s blog, and I think that a fifth post is also in planning.

Here on the blog,  I plan a  mathematical post about my visit to Yale on February. The visit have led to Stefan Steinerberger’s beautiful post on Ulam sequences.  There are also newer interesting things, from our combinatorics seminar at HUJI, and from the third Simons’ conference on the analysis of Boolean functions (I hoped Ryan will blog about the conference). In celebration of the recent breakthrough on sphere packing in dimensions 8 and 24  I also plan to write more on sphere packing.

Happy Passover!

Pictures with Avi Wigderson at Nogafest and with Alex Lubotzky at Yale.

## Three Conferences: Joel Spencer, April 29-30, Courant; Joel Hass May 20-22, Berkeley, Jean Bourgain May 21-24, IAS, Princeton

Dear all, I would like to advertise three  promising-to-be wonderful mathematical conferences in the very near future.

Quick TYI. See if you can guess the title and speaker for  a lecture described by  “where the mathematics of Cauchy, Fourier, Sobolev, Gelfand and Bourgain meet. (Answer at the end of the post.)”

## Random Roads – Joel Spencer’s 70 conference,  April 29-30 2016, at Courant NYC.

Joel Spencer’s 70th birthday conference is coming up on April. Here is the website

.

## Geometry, Topology and Complexity of Manifolds, and applications to Biology – Joel Hass’ 60th birthday, May 20-22, 2016 at UC Berkeley.

Joel Hass’ 60th birthday conference is coming up in May at UC Berkeley. Here is the website.

## Analysis and Beyond: Celebrating Jean Bourgain’s Work and Impact, May 21-24, I.A.S., Princeton.

A conference celebrating Jean Bourgain’s work is coming up in May at Princeton. Here is the conference page.

Answer:  Speaker: Haim Brezis; TitleOld-new perspectives on the winding number;

## Math and Physics Activities at HUJI

Between 11-15 of September 2016 there will be a special mathematical workshop for excellent undergraduate students at the Hebrew University of Jerusalem. In parallel there will also be a workshop in physics. These workshops are aimed for second and third year undergraduate students. Here is the list of speakers! You need to register before June 15, 2016. More details below.

## Open day, April 20, 2016

Two days from now on Wednesday April 20 there will be a splendid open day at the math department.  Do not miss it!!

## Stefan Steinerberger: The Ulam Sequence

This post is authored by Stefan Steinerberger.

The Ulam sequence

$1,2,3,4,6,8,11,13, 16, 18, \dots$

is defined by starting with 1,2 and then repeatedly adding the smallest integer that is (1) larger than the last element and (2) can be written as the sum of two distinct earlier terms in a unique way. It was introduced by Stanislaw Ulam in a 1962 paper (On some mathematical problems connected with patterns of growth of figures’) where he vaguely describes this as a one-dimensional object related to the growth of patterns. He also remarks (in a later 1964 paper) that simple questions that come to mind about the properties of a sequence of integers thus obtained are notoriously hard to answer.’ The main question seems to have been whether the sequence has asymptotic density 0 (numerical experiments suggests it to be roughly 0.07) but no rigorous results of any kind have been proven so far.

A much stranger phenomenon seems to be hiding underneath (and one is tempted to speculate whether Ulam knew about it). A standard approach in additive cominatorics is to associate to the first $N$ elements of a sequence $a_1, a_2, \dots, a_N$ a
function

$f_N(\theta) = \exp{(a_1 i \theta)} + \exp{(a_2 i \theta)} + \dots + \exp{(a_N i \theta)}$

and work with properties of $f_N$. If we do this with the elements of the Ulam sequence and plot the real part of the function, we get a most curious picture with a peak around
$\theta \sim 2.571447\dots$

Such spikes are generally not too mysterious: if we take the squares $1,4,9,16, ...$ we can observe a comparable peak at $\theta = 2\pi/4$ for the simple reason that squares are $\equiv 0, 1$ (mod 4). However, here things seem to be very different: numerically, the Ulam sequence does seem to be equidistributed in every residue class. Due to $2\pi-$periodicity, the function $f_N$ only sees the set of numbers

$\left\{ \theta a_n~\mbox{mod}~ 2\pi: 1 \leq n \leq N\right\}$

and it makes sense to look at the distribution of that sequence on the torus for that special value $\theta \sim 2.571447\dots$. A plot of the first 10 million terms reveals a very strange distribution function.

The distribution function seems to be compactly supported (among the first 10 million terms only the four elements $2, 3, 47, 69$ give rise to elements on the torus that lie outside $[\pi/2, 3\pi/2]$.) The same phenomenon seems to happen for some other initial conditions (for example, 2,3 instead of 1,2) as well and the arising distribution functions seem to vary greatly.

Question 1: What is causing this?

Question 2: Are there other `natural’ sequences of integers with that property?

See also Stefan’s paper  A Hidden Signal in the Ulam sequence .

Update: See also Daniel Ross’  subsequent study of Ulam’s sequence, presented in Daniel’s sort of public ongoing “research log”.  (“It includes a summary at the top of the most interesting observations to date, which usually lags a couple weeks behind the most current stuff.”)

Posted in Guest blogger, Open problems | | 8 Comments

## TYI 26: Attaining the Maximum

(Thanks, Dani!) Given a random sequence $a_1,a_2,\dots , a_n$, ***$a_i \in \{-1,1\}$***, $n>2$, let $S_k=a_1+a_2+\cdots +a_k$. and assume that $S_n=0$.  What is the probability that the maximum value of $S_k$ is attained only for a single value of $k$?

Test your intuition: is this probability bounded away from 0? tends to 0 like $1/\sqrt n$? Quicker? Slower? Is there a nice formula?

Posted in Combinatorics, Probability, Test your intuition | Tagged | 21 Comments

Maryna Viazovska

## The news

Maryna Viazovska has solved the densest packing problem in dimension eight! Subsequently, Maryna Viazovska with Henry Cohn, Steve Miller, Abhinav Kumar, and Danilo Radchenko solved the densest packing problem in 24 dimensions!

Here are the links to the papers:

Maryna Viazovska, The sphere packing problem in dimension 8

Henry Cohn, Abhinav Kumar, Stephen D. Miller, Danylo Radchenko, Maryna Viazovska,
The sphere packing problem in dimension 24

(I thank Steve Miller and Peter Sarnak for telling me about it.)

Update: The February 2017 issue of the Notices of the AMS has a beautiful paper by Henry Cohn  entitled A conceptual breakthrough in sphere packing about the developments described in the post.

## Some Background

Kepler, Gauss, Hales, Cohn and Kumar. A central mathematical problem is to find the densest sphere packing in $R^d$. The case $d=3$ is known as the Kepler conjecture. Gauss solved it for lattice packings, and Thomas Hales proved it for general packing using a massive use of computations. Cohn and Kumar settled the lattice case for dimensions 8 and 24.

Conway and Sloane. The “bible” regarding sphere packing is the classic book by two major player of the theory John Conway and Neil Sloane.

Hales and Fejes Toth.  Announced in 1998 and published a few years later, Hales’ proof  relies on some early work of Laszlo Fejes Toth. Since a full verification would require developing much of  the whole project from scratch, Hales himself led a team of researchers to find a formal proof which was published in 2015.

Lie and  Leech.   Lower bounds for higher dimensions. For some dimensions, special lattices of Lie type give surprisingly dense lattice packings. The Leech lattice gives a remarkably dense packing in dimension 24.

Minkowski,…, Ball, Vance and Venkatesh,  For asymptotically large dimensions a probabilistic method by Minkowski gives the best known lower bound up to small (but exciting) improvements. It gives a packing of density $2 \cdot 2^{-n}$.  Here is a slide from a lecture by Henry Cohn on the state of the art for the asymptotic question. (And here is the link to the slides of the full lecture.)

Delsartes, Kabatiansky and Levenshtein. Upper bounds via linear programming. Delsartes’ linear programming method (that can be seen as a Fourier/spectral attack with special features,) had led to important results towards general upper bounds by Kabatiansky and Levenshtein.

Cohn and Elkies developed related spectral methods applying directly to sphere packing, which allow to improve the upper bounds in dimensions 4–31 and give strikingly good results in dimensions 8 and 24.  Cohn and Kumar used these linear programming methods to settle the densest lattice problem in dimensions 8 and 24 and to give extremely good numerical upper bounds for the non-lattice case.

This is the starting point for Viazovska’s breakthrough.

Related problems/issues  to keep in mind: The densest packing problem in other dimensions and when the dimension tends to infinity; Kissing numbers and spherical codes; Upper bounds for error correcting codes; packing in other symmetric spaces; packing covering and tiling in combinatorics and geometry.

## Viazovska’s breakthrough

The little I can tell you is that for a solution one needs to identify certain functions to plug in to the spectral machine. And Maryna’s starting point was some familiar extraordinary elliptic functions and modular forms.  More details on the comment section are most welcome.  (Update:) John Baez wrote on the n-Category Cafe some elementary comments on the proofs: E8 is the best.

## The 24-dimensional case

A key ingredient for the result in dimension 24 is the earlier numerical rationality conjectures by Cohn and Miller.  Those now appear in the preprint: Henry Cohn, Stephen D. Miller, Some properties of optimal functions for sphere packing in dimensions 8 and 24 .

Congratulations to Maryna, Abhinav,  Danilo,  Henry, and Steve!

I remember a decade ago that Steve Miller explained to me some developments, ideas, and dreams  regarding two problems. One was the sphere packing problem in dimensions 8 and 24 that he now took part in solving, and the other was the irrationality questions regarding zeta functions at odd integers (and maybe also the Euler constant.)  Time to move to the second problem, Steve 🙂

(And a trivia question: name a player in both these stories. As usual if you answer in the comment section please give a zero-knowledge answer demonstrating that you know the solution without revealing it.)