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
Let . A modular line in is a set of three elements such that the number of coordinates for which is zero modulo for . (The sum is taken modulo 3.)
Problem 1: How large can a subset of be without containing a modular line? Prove that , for some constant .
2. Why? avoiding lines (3-term arithmetic progressions) in ..
The following is a well-known problem:
Problem 2: Find the largest size of a set without an arithmetic progression of size 3. In this case an arithmetic progression of size three is simply a sequence of three elements and such that . 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 . Roy Meshulam proved that . 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 . 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 gives reason for optimism.) Let us write . The best lower bound on is . There is a construction of Edell showing that and thus the best upper bound for is more than . The gap is huge! What is the true value? Terry Tao wrote a lovely post on this problem. A set in 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 is a very simple example of a cap set of size ; choosing a set at random works if the size is less than . Problem 1 is a variation on problem 2.
This time Roy and I thought to attack the problem from a different direction.
3. The fantastic plan: step A and step B
Our tentative program to attack Problem 2 was this:
Step A: Show that a subset of more than elements in contains a certain form of “modular line”.
Step B: Somehow exclude all the other cases to conclude that this “modular line” is actually a line.
This post will be divided into three parts. The first is around Step A, the second around Step B. Don’t hold your breath; there is nothing new here on the cap set problem itself. As a matter of fact, avoiding a modular line looks a priori much harder than avoiding a line since given and we do not have a unique choice but rather a huge number of possibilities for .
4. Some possibly relevant material (1).
The study of extremal problems for subsets of when is an alphabet of more than two elements is a natural extension of extremal problems in set theory. A recent survey by Janos Korner and Alon Orlitsky describes a lot of things, including early contributions of Korner, Simonyi and others. In particular, various analogs of Erdos-Ko-Rado-type theorems were studied. There are various new phenomena and new difficult problems when we move from a 2-letter alphabet to a larger alphabet .
5. Frankl-Wilson and the polynomial/rank methods.
Problem 1 looks quite similar to the Frankl-Wilson theorem. One version of the Frankl-Wilson theorem asserts that when n is divisible by 4, a family of vectors of length n not containing a pair of vectors x and y which differ in precisely 2n coordinates is smaller than . This bound is even tight. So we tried to apply the simple ”polynomial method” proof of the Frankl-Wilson theorem. It does not give “modular lines” but something weaker.
6. Using the polynomial method: weak modular lines
A weak modular line in is a set of three elements such that the number of coordinates for which is zero modulo .
Proposition 1: When and is a prime, a subset of without a weak modular line satisfies .
The proof is a simple application of the polynomial method. However, it is not strong enough to apply to “modular lines” instead of “weak modular lines”.
But looking carefully at the proof, we see that it gives more in an undesirable direction.
7. A slight disappointment, and a strong form of the problem.
The proof of Proposition 1 follows rather easily the polynomial-method-proof (due to Alon, Babai, and Suzuki) of Frankl-Wison’s theorem.
The following lemma is needed:
Lemma:Let be a polynomial over the field of elements, in 3n variables, of degree (recall ,) so that for iff x=y=z. Then .
To use the lemma we consider the polynomial described as follows: We write . (This polynomial counts the number of coordinates where the sum .) Next you let . This product is zero unless the number of coordinates where is zero modulo .
(The way we construct from is modeled after the riddle: Q: what is the value of ? A: zero because of the term (x-x).)
To prove the lemma we need another important trick: we can modify without changing the values on so that the degrees of the individual variables are at most 2. Then we write and note that the condition on implies that all these s are linearly independent.
Observation: We did not really use the assumption, only that when . We actually proved:
Proposition 2: When, and is a prime, a subset of without such that the number of 0′s entries in is zero modulo p, satisfies .
Why is this strengthening disappointing? Because it shows that the problem with which we started is unlikely to be related to the cap set problem. Also we realize that we do not know how to exploit the condition of the Lemma and we only use them for triplets with at least two equal elements.
So we can go back to the original problem and ask:
Problem 3 : How large can a subset of be without a modular line with two equal elements?
Somehow the polynomial method does not give the expected answer to Problems 1 or 3. (At least we did not succeed.)
We can ask more difficult questions:
If we say that x and y are completely orthogonal if for every and we have .
Problem 4: How large can a subset of without containing two vectors and which are completely orthogonal?
(Note that if are completely orthogonal then is a modular line.)
While we are at it let us try to ask a genuine question regarding 3 elements.
Problem 5: How large can a subset of without containing three vectors and which are completely orthogonal? (The same can be asked for vectors?)
8. The Frankl-Rodl Theorem to the rescue
Proposition 3: When , the answer to problems 4 and hence also 3 and 1 is that the size of the set in question must be at most .
Proposition 4: This is also the case for problem 5.
Propositions 3 and 4 follow rather directly from the Frankl-Rodl theorem. Walla!
9. Conclusion for part A:
Frankl-Rodl’s theorem allows us to find modular lines with two equal elements and even more special configurations of two and more vectors. In these problems there is much more freedom compared to the original cap set problem. The fact that we can find modular lines even with two equal vectors demonstrates this freedom and indeed shows that it is unlikely that the results have bearing on the cap set problem.
We had to update the way we looked at Frankl-Rodl’s theorem. Before, we thought that the difference between the Frankl-Wilson method and the Frankl-Rodl method is that the latter gives weaker results but the former works only for specific values of . (Well, we knew also that the Frankl-Rodl results apply to “two families theorems” where it is not known how to make the polynomial method work.)
But now, it seems that the Frankl-Rodl method gives in many cases results that the polynomial/linear algebra method cannot match (even for a single family). Adapting the polynomial method to match the results obtained using Frankl-Rodl is an interesting problem in and of itself. In part C we will describe a simpler connection between the cap set problem and Frankl-Rodl’s theorem and possible extensions of this theorem.
Appetizer for part B: How large can a subset be if it has the property that you cannot find such that the number of coordinates that is for . (This time the entries are considered as integers.)
Appendix: Two Pages From Frankl-Rodl’s Paper.
Click (and enlarge) to get it readable.