Frankl-Rodl’s Theorem and Variations on the Cap Set Problem: A Recent Research Project with Roy Meshulam (A)

Voita Rodl

I would like to tell you about a research project in progress with Roy Meshulam. (We started it in the summer, but then moved to other things;  so far there are interesting insights, and perhaps problems, but not substantial results. Noga Alon contributed an important observation, and Jeff Kahn and Gabor Simonyi helpful comments.)  

Roy and I are friends and have been discussing various mathematical problems for decades. In the last few years we have studied together topological Helly-type theorems and have written several papers together. Our most recent success was finding a topological version of a Helly-type theorem by Nina Amenta. This post is on another problem.

As always, and more so in the spirit of Nielsen’s and Gowers’s recent suggestions:  comments, ideas, related problems, lemmas, and discussions  are welcome.  Links or references to earlier works (published and unpublished) are also welcome.  I thought to wait with this story after I discuss the Frankl-Wilson theorem and the Frankl-Rodl theorem in my extremal combinatorics series. But as this project is somewhat related to the density Hales-Jewett project discussed over Gowers’s blog (and even more to this thread at Tao’s blog), I decided to go ahead with it.


Part A: Finding generalized solutions for the cap set problem

1. Modular-lines-free-subsets

Let n=3m. A modular line in T(n)= \{0,1,2\}^n is a set of  three elements x,y,z such that the number of coordinates i for which x_i + y_i + z_i =a is zero modulo m for a=0,1,2. (The sum x_i+y_i+z_i is taken modulo 3.)

Problem 1:  How large can a subset F of T(n) be without containing a modular line? Prove that |F| < (3-\epsilon)^n, for some constant \epsilon >0.

2. Why? avoiding lines (3-term arithmetic progressions) in Z_3^n..

The following is a well-known problem:

Problem 2: Find the largest size f(n) of a set A \subset Z_3^n without an arithmetic progression of size 3. In this case an arithmetic progression of size three is simply a sequence of three elements x, y and z such that x+y+z=0. In other words, an arithmetic progression is simply an affine line.

This problem was discussed by Frankl, Graham, and Rodl in 1987 (and perhaps was posed even earlier) and they showed that f(n)=o(3^n). Roy Meshulam proved that f(n) \le 3^n/n. This is a beautiful and clear application of Roth’s argument (for his famous theorem on the density of sets without 3-term arithmetic progressions,) for the case of subsets of \{1,2,\dots,n\}. Ten years ago Roy and I tried quite hard to push this Fourier-theoretic argument and to get a better bound, even slightly, even very slightly. We did not succeed. (And so far, nobody else has; a recent impressive result of Tom Sanders for 3-term arithmetic progressions without a repeated element for subsets of  Z_4^n gives reason for optimism.) Let us write f(n)=3^n/g(n). The best lower bound on g(n) is n. There is a construction of Edell showing that f(n) \ge2.2^n and thus the best upper bound for g(n) is more than 1.3^n. The gap is huge! What is the true value? Terry Tao wrote a lovely post on this problem. A set in Z_3^n without a 3-term arithmetic progression (or alternatively not containing an affine line) is called a cap set.

Let me mention that the set of 0-1 vectors of length n is a very simple example of a cap set of size 2^n; choosing a set at random works if the size is less than 3^{n/3}.   Problem 1 is a variation on problem 2.  Continue reading