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.

Laci Babai and Graph Isomorphism

Next Tuesday, a week from today, Laci Babai will talk at the University of Chicago about a new algorithm that solves graph isomorphism in quasipolynomial time. There should also be a follow-up talk the following Thursday that, by a lucky coincidence, I will be able to attend, and then report back.

Meanwhile, if you have any gossip on the proof, then, by any means, go ahead and share it in the comments.

Aldo Fabrizi

Today Aldo Fabrizi would turn 110. Outside of Italy, those who know him at all probably know him from Rome, Open City, one of the early movies of the Neorealismo genre. (It is available in the US in a Criterion edition.)

But, in Italy, Fabrizi is famous for being one of the giants of the first generation of Italian-style comedy, from the 1950s and 1960s. My favorite movies of his are those in which he acts as a straight man for Totò, and my absolute favorite is Guardie e Ladri, which never had an American release.

For those who understand Italian, it’s possible to find the whole movie on youtube. Here is one iconic scene.


Happy Qi Xi festival, everybody. This is the “Chinese Valentine’s day,” which falls on July 7th on the lunar calendar, which this year is August 20th. The festivity relates to a story that, like many Chinese stories, is a pretty long story.

The gist of it is that the (seventh) daughter of a goddess at some point came to earth to live as a mortal and met a cowboy (as in, a guy whose job is to herd cows). The two fell in love, got married, had two children (I told you, it’s a long story) and they were pretty happy, until the goddess mom realized what happened.

As is mothers-in-law’s wont, she did not approve, and she recalled the daughter to heaven, where she is now the star Vega. The guy was desperate, but then one of his cows suggested that he kills it, and then use its skin to fly to heaven (don’t ask) and reunite with his wife.

He does so, and it works, so that he is now the star Altair, but then the mom-in-law found out again. So she created a river, the Milky Way, to separate them once more. And now they are forever separated, except that, every year, magpies (which are a kind of crows) fly to heaven and use their bodies to create a bridge over the Milky Way, so that the two lovers can use it to meet. And this happens on the 7th day and the 7th month of the year.

What a difference thirty years make

From the majority opinions of two rulings of the Supreme Court of the United States.

Bowers v. Hardwick (1986):

The Constitution does not confer a fundamental right upon homosexuals to engage in sodomy. […] to claim that a right to engage in such conduct is “deeply rooted in this Nation’s history and tradition” or “implicit in the concept of ordered liberty” is, at best, facetious.

Obergefell v. Hodges (2015)

[Same-sex couples] ask for equal dignity in the eyes of the law. The Constitution grants them that right. The Constitution […] does not permit the State to bar same-sex couples from marriage on the same terms as accorded to couples of the opposite sex.

the future of the Conference on Computational Complexity

As you may remember, a few months ago Dieter van Melkebeek, the steering committee chair of the conference on computational complexity, started a discussion on the future of the conference and on its relation to IEEE.

A poll among CCC former participants showed that 97% of respondents favored change, and a majority wanted the conference to be independent of both IEEE and ACM. The steering committee, subsequently, voted unanimously to make the conference independent.

The steering committee is now working out the logistics, and volunteers are needed to help. Already several people have pledged to contribute in various forms, and if you are interested there will be organizational meetings in Vancouver during CCC 2014. (By the way, today is the deadline for early registration.)

I would like to publicly thank Dieter both for the effort that he put on making this change happen and for the transparency of the process. I hope that, if some big change is coming for STOC or FOCS, it will be the result of a similarly open discussion.

Ora e sempre resistenza

Today it’s my favorite of Italy’s public holidays.

To keep a long story long, at the start of WW2, Italy, which was an ally of Germany, was initially neutral, in part because its armed forces were completely unprepared for war. At some point in the May of 1940, with German troops advancing into France, and British troops evacuating the continent, Italy decided to join what looked like a soon-to-end war, in order to claim some French territories and colonies.

But then, in 1941, Germany attacked Russia and Japan attacked the US, underestimating what they were getting into, and by the beginning of 1943 the tide was clearly turning against the “axis.” Italy’s king, who was definitely not the “fight until the last man” type, had Mussolini arrested, installed a general as prime minister, and started negotiating Italy’s surrender with the allies (even as Italian troops were fighting with the Germans in Russia and in Africa). Eventually, on September 8, 1943, the king announced a cease-fire. Because of the secrecy of the negotiations, nobody knew what was going in advance, and most of the Italian troops that were fighting with the Germans were taken prisoners, while the rest of the armed forces basically disbanded. German troops came into Italy from the North to occupy it, even as allied troops landed in Sicily and took control of most of Southern Italy. The king fled to the South, and the Germans freed Mussolini and installed him as head of a puppet government in the North.

With the Italian army disbanded, and with the allies neglecting the “Southern front” in Italy as they were plotting the landing in Normandy, guerilla groups were formed in Northern Italy to fight the Germans. Eventually, in April 1945 the German troops were retreating from the Eastern and Western fronts against the advancing American and Russian forces, and the allied made another push in Italy; concurrently, the resistance organizations planned an insurrection that, on April 25, liberated Torino and Milan. All the German forces in Italy surrendered on April 29.

The resistance was the training ground of some of the first generation of politicians of the new Italian Republic (a referendum to abolish the monarchy passed in 1946, and a new Republican constitution was approved in 1948), and it brought people who were willing to die for their ideals into politics. That spirit didn’t last very long, but it remains one of the few bright spots in recent Italian history.

Holiday Readings

Now that the Winter break is coming, what to read in between decorating, cooking, eating, drinking and being merry?

The most exciting theoretical computer science development of the year was the improved efficiency of matrix multiplication by Stother and Vassilevska-Williams. Virginia’s 72-page write-up will certainly keep many people occupied.

Terence Tao is teaching a class on expanders, and posting the lecture notes, of exceptional high quality. It is hard to imagine something that would a more awesome combination, to me, than Terry Tao writing about expanders. Maybe a biopic on Turing’s life, starring Joseph Gordon-Levitt, written by Dustin Lance Black and directed by Clint Eastwood.

Meanwhile, Ryan O’Donnell has been writing a book on analysis of boolean function, by “serializing” it on a blog platform.

Now that I have done my part, you do yours. If I wanted to read a couple of books (no math, no theory) during the winter, what would you recommend. Don’t recommend what you think I would like, recommend what you like best, and why.