*[At the end of a survey paper on additive combinatorics and computational complexity which is to appear in SIGACT News, I list three major open questions in additive combinatorics which might be amenable to a “computer science proof.” They are all extremely well studied questions, by very smart people, for the past several years, so they are all very long shots. I don’t recommend anybody to start working on them, but I think it is good that as many people as possible know about these questions, because when the right technique comes along its applicability can be more quickly realized.]*

The first question is to improve the *Triangle Removal Lemma*. I have talked here about what the triangle removal lemma is, how one can prove it from the Szemerédi Regularity Lemma, and how it implies the length-3 case of Szemerédi’s Theorem.

As a short recap, the Triangle Removal Lemma states that if is an -vertex graph with triangles, then there is a set of edges such that the removal of those edges eliminates all the triangles. Equivalently, it says that if a graph has triangles which are all pair-wise edge-disjoint, then there must be triangles overall.

The connection with Szemerédi’s Theorem is that if is an abelian group with elements, and is a subset of with no length-3 arithmetic progressions (i.e., is such that there are no three distinct elements in such that ), then we can construct a graph that has vertices, pair-wise edge-disjoint triangles, and *no other triangles*. This contradicts the triangle removal lemma if , and so we must have .

This is great, until we start looking at the relationships between the constants hidden by the notation. Quantitatively, the Triangle Removal Lemma states that for every there is a such that if a graph has at least pair-wise edge-disjoint triangles, then it has at least triangles. The only known proof, however, has incredibly small: grows like a tower of exponentials of height polynomial in . The proof uses the Szemerédi Regularity Lemma, and the Regularity Lemma is known to require such very bad dependencies.

63 years ago, Behrend showed that , prime, has a subset that contains no length-3 arithmetic progression and whose size is . (Last year, Elkin gave the first improvement in 62 years to Behrend’s bound, but the improvement is only a multiplicative polylog factor.) Combined with the graph construction mentioned above, this gives a graph with vertices, edge-disjoint triangles, and no other triangle. Thus, the graph has triangles where , but one needs to remove edges to make it triangle-free, where . This shows that, in the Triangle Removal Lemma, must grow super-polynomially in , and be at least .

The question is to shorten the gap between the tower-of-exponential relationship between and coming from the proof via the Szemerédi Regularity Lemma and the mildly super-polynomial lower bound coming from the above argument.

Continue reading →