Ellenberg’s announcement of a solution to the cap-set problem

Jordan Ellenberg has just announced a resolution of the “cap problem” using techniques of Croot, Lev and Pach, in a self-contained three-page paper. This is a quite unexpected development for a long-standing open problem in the core of additive combinatorics.

Perhaps the right starting point for this story is 1936, when Erdos and Turan conjectured that, for every {k}, if {A} is a subset of {\{1,\ldots, N\}} without {k}-terms arithmetic progressions, then {|A|= o_k(n)}, or, equivalently, that if {A} is a subset of the integers of positive density, then it must have arbitrarily long arithmetic progressions. Their goal in stating this conjecture was that resolving it would be a stepping stone to proving that the prime numbers have arbitrarily long arithmetic progressions. This vision came true several decades later. Szemeredi proved the conjecture in 1975, and Green and Tao proved that the primes contain arbitrarily long arithmetic progressions in 2004, with Szemeredi’s theorem being a key ingredient in their proof.

Rewinding a bit, the first progress on the Erdos-Turan conjecture came from Roth, who proved the {k=3} case In 1955. Roth’s proof establishes that if {A \subseteq \{ 1,\ldots, N\}} does not have length-3 arithmetic progressions, then {|A|} is at most, roughly {N/\log\log N}. Erdos also conjectured that the bound should be {o(N/\log N)}, and if this were true it would imply that the primes have infinitely many length-3 arithmetic progressions simply because of their density.

Roth’s proof uses Fourier analysis, and Meshulam, in 1995, noted that the proof becomes much cleaner, and it leads to better bounds, if one looks at the analog problem in {{\mathbb F}_p^n}, where {{\mathbb F}_p} is a finite field (of characteristic different from 2). In this case, the question is how big can {A\subseteq {\mathbb F}_p^n} be if it does not have three points on a line. An adaptation of Roth’s techniques gives an upper bound of the order of {p^n/n}, which, for constant {p}, is of the order of {N/\log N} if {N} is the size of the universe of which {A} is a subset.

Bourgain introduced a technique to work on {{\mathbb Z}/N{\mathbb Z}} “as if” it where a vector space over a finite field, and proved upper bounds of the order of {N/\sqrt {\log N}} and then {N/(\log N)^{3/4}} to the size of a subset of {\{ 1,\ldots , N\}} without length-3 arithmetic progressions. The latest result in this line is by Sanders, who proved a bound of {(N poly\log\log N)/\log N}, very close to Erdos’s stronger conjecture.

How far can these results be pushed? A construction of Behrend’s shows that there is a set {A\subseteq \{ 1,\ldots, N\}} with no length-3 arithmetic progression and size roughly {N/2^{\sqrt {\log N}}}. The construction is simple (it is a discretization of a sphere in {\sqrt {\log N}} dimensions) and it has some unexpected other applications. This means that the right bound in Roth’s theorem is of the form {N^{1-o(1)}} and that the “only” question is what is the {N^{-o(1)}} term.

In the finite vector space case, there is no analog of Behrend’s construction, and so the size of say, the largest subset of {{\mathbb F}_3^n} without three points on a line, was completely open, with an upper bound of the order of {3^n/n} and lower bounds of the order of {c^n} for some constant {c<3}. The cap problem was the question of whether the right bound is of the form {3^{(1-o(1)) }} or not.

Two weeks ago, Croot, Lev and Pach proved that if {A} is a subset of {({\mathbb Z}/4{\mathbb Z})^n} without length-3 arithmetic progressions, then {|A|} is at most of the order of {4^{.926 \cdot n}}. This was a strong indication that the right bound in the cap problem should be sub-exponential.

This was done a couple of days ago by Ellenberg, who proved an upper bound of the form {(2.756)^n} holds in {{\mathbb F}_3^n}. The proof is not specific to {{\mathbb F}_3} and generalizes to all finite fields.

Both proofs use the polynomial method. Roughly speaking, the method is to associate a polynomial to a set of interest (for example, by finding a non-zero low-degree polynomial that is zero for all points in the set), and then to proceed with the use of simple properties of polynomials (such as the fact that the space of polynomials of a certain degree has a bounded dimension, or that the set of zeroes of a univariate non-zero polynomial is at most the degree) applied either to the polynomial that we constructed or to the terms of its factorization.

Let {P_d} be the vector space of {n}-variate polynomials over {{\mathbb F}_3} of total degree {d} that are cube-free (that is, such that all variables occur in monomials with degree 0, 1, or 2), and let {m_d} be its dimension.

If {A\subseteq {\mathbb F}_3^n} is a set such that there are no distinct {a,b,c} such that {a+b+c=0} (a different property from being on a line, but the draft claims that the same argument works for the property of not having three points on a line as well), then Ellenberg shows that

\displaystyle  m_d - 3^n + |A| \leq 3 m_{d/2}

then the bound follows from computing that {m_{2n/3} \geq 3^n - c^n} and {m_{n/3} \leq c^n} for {c \approx 2.756\cdots}.

The finite field Kakeya problem is another example of a problem that had resisted attacks from powerful Fourier-analytic proofs, and was solved by Zeev Dvir with a relatively simple application of the polynomial method. One may hope that the method has not yet exhausted its applicability.

Gil Kalai has posted about further consequence of the results of Croot, Lev, Pach and Ellenberg.

Ancient wisdom

[I sneeze several times and then the following conversation happens]

J.Z.: In China, we say that if you sneeze once, it means that someone is thinking of you. If you sneeze twice, it means someone is cursing you.

Me: and what does it mean when I sneeze three times or more?

J.Z.: it means you have a cold.

They are perfect for each other

Now that Ted Cruz has chosen his running mate, everybody is wondering: who is going to be Trump’s pick for vice-president?

It would make sense if, to mitigate his negatives, Trump chose a person of color and someone who has a history of speaking out against income inequality.

He or she would have to be someone who is media-savvy and with some experience running a campaign, but definitely not a career politician. And of course he or she should be someone who endorsed Trump early on, like, say, in January.

Continue reading

CS294 Lecture 18: Margulis-Gabber-Galil Expanders

In which we present an algebraic construction of expanders.

1. The Marguli-Gabber-Galil Expanders

We present a construction of expander graphs due to Margulis, which was the first explicit construction of expanders, and its analysis due to Gabber and Galil. The analysis presented here includes later simplifications, and it follows an exposition of James Lee.

Continue reading

CS294 Lecture 16: Zig-Zag Graph Product

In which we give an explicit construction of expander graphs of polylogarithmic degree, state the properties of the zig-zag product of graphs, and provide an explicit construction of a family of constant-degree expanders using the zig-zag product and the polylogarithmic-degree construction.

A family of expanders is a family of graphs {G_n = (V_n,E_n)}, {|V_n|=n}, such that each graph is {d_n}-regular, and the edge-expansion of each graph is at least {h}, for an absolute constant {h} independent of {n}. Ideally, we would like to have such a construction for each {n}, although it is usually enough for most applications that, for some constant {c} and every {k}, there is an {n} for which the construction applies in the interval {\{ k, k+1, \ldots, ck \}}, or even the interval {\{ k, \ldots, ck^c\}}. We would also like the degree {d_n} to be slowly growing in {n} and, ideally, to be bounded above by an explicit constant. Today we will see a simple construction in which {d_n = O(\log^2 n)} and a more complicated one in which {d_n = O(1)}.

Continue reading

CS294 Lecture 15: Abelian Cayley graphs

In which we show how to find the eigenvalues and eigenvectors of Cayley graphs of Abelian groups, we find tight examples for various results that we proved in earlier lectures, and, along the way, we develop the general theory of harmonic analysis which includes the Fourier transform of periodic functions of a real variable, the discrete Fourier transform of periodic functions of an integer variable, and the Walsh transform of Boolean functions.

Earlier, we prove the Cheeger inequalities

\displaystyle  \frac{\lambda_2}{2} \leq \phi(G) \leq \sqrt{2 \lambda_2}

and the fact that Fiedler’s algorithm, when given an eigenvector of {\lambda_2}, finds a cut {(S,V-S)} such that {\phi(S,V-S) \leq 2\sqrt{\phi(G)}}. We will show that all such results are tight, up to constants, by proving that

  • The dimension-{d} hypercube {H_d} has {\lambda_2 = 1- \frac 2d} and {h(H_d) = \frac 1d}, giving an infinite family of graphs for which {\frac{\lambda_2}{2} = \phi(G)}, showing that the first Cheeger inequality is exactly tight.
  • The {n}-cycle {C_n} has {\lambda_2 = O(n^{-2})}, and {\phi(C_n) = \frac 2n}, giving an infinite family of graphs for which {\phi(G) = \Omega(\sqrt{\lambda_2})}, showing that the second Cheeger inequality is tight up to a constant.
  • There is an eigenvector of the 2nd eigenvalue of the hypercube {H_d}, such that Fiedler’s algorithm, given such a vector, outputs a cut {(S,V-S)} of expansion {\phi(S,V-S) = \Omega(1/\sqrt{d})}, showing that the analysis of the Fiedler’s algorithm is tight up to a constant.

In this lecture we will develop some theoretical machinery to find the eigenvalues and eigenvectors of Cayley graphs of finite Abelian groups, a class of graphs that includes the cycle and the hypercube, among several other interesting examples. This theory will also be useful later, as a starting point to talk about constructions of expanders.

For readers familiar with the Fourier analysis of Boolean functions, or the discrete Fourier analysis of functions {f: {\mathbb Z}/N{\mathbb Z} \rightarrow {\mathbb C}}, or the standard Fourier analysis of periodic real functions, this theory will give a more general, and hopefully interesting, way to look at what they already know.

Continue reading

CS 294 Lecture 14: ARV Analysis, Part 3

In which we complete the analysis of the ARV rounding algorithm

We are finally going to complete the analysis of the Arora-Rao-Vazirani rounding algorithm, which rounds a Semidefinite Programming solution of a relaxation of sparsest cut into an actual cut, with an approximation ratio {O(\sqrt {\log |V|})}.

In previous lectures, we reduced the analysis of the algorithm to the following claim.

Continue reading