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

Posted on February 7, 2009 by Gil Kalai

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.

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 $(3-\epsilon)^n$ elements in $T(n)$ 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 $x$ and $y$ we do not have a unique choice but rather a huge number of possibilities for $z$ .

4. Some possibly relevant material (1).

The study of extremal problems for subsets of $\Omega ^n$ when $\Omega$ 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 $\Omega$ .

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 $2^{H(1/4)n(1+o(1))}$ . 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 $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 =0$ is zero modulo $m$ .

Proposition 1: When $n=3p$ and $p$ is a prime, a subset $F$ of $T(n)$ without a weak modular line satisfies $|F| < 2.9^n$ .

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 $f(x,y,z)$ be a polynomial over $Z_p$ the field of $p$ elements, in 3n variables, of degree $2(p-1)$ (recall $n=3p$ ,) so that for $(x,y,z) \in F \times F \times F$ $f(x,y,z)=0$ iff x=y=z. Then $|F| \le2.9^n$ .

To use the lemma we consider the polynomial $f$ described as follows: We write $g(x,y,z) = -\sum_{i=1}^n (x_i+y_i+z_i)^2-1$ . (This polynomial counts the number of coordinates where the sum $x_i+y_i+z_i=0.$ .) Next you let $f(x,y,z)=(g(x,y,z)-1)(g(x,y,z)-2) \dots (g(x,y,z)-(p-1))$ . This product is zero unless the number of coordinates where $x_i+y_i+z_i=0$ is zero modulo $p$ .

(The way we construct $f$ from $g$ is modeled after the riddle: Q: what is the value of $(x-a)(x-b)(x-c)\dots (x-z)$ ? A: zero because of the term (x-x).)

To prove the lemma we need another important trick: we can modify $f$ without changing the values on $F \times F\times F$ so that the degrees of the individual variables are at most 2. Then we write $f_x(y)=f(x,y,y)$ and note that the condition on $f$ implies that all these $f_x$ s are linearly independent.

Walla!

Observation: We did not really use the assumption, only that $f(x,y,z) \ne 0$ when $x =y \ne z$ . We actually proved:

Proposition 2: When, $n=3p$ and $p$ is a prime, a subset $F$ of $T(n)$ without $x, y \in F$ such that the number of 0’s entries in $x+2y =x-y$ is zero modulo p, satisfies $|F| < 2.9^n$ .

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 $F$ of $T(n)$ 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 $n=9m$ we say that x and y are completely orthogonal if for every $a$ and $b$ we have $|\{ i: x_i=a,y_i=b\}|=m$ .

Problem 4: How large can a subset $F$ of $T_b(9m)$ without containing two vectors $x$ and $y$ which are completely orthogonal?

(Note that if $x,y$ are completely orthogonal then $x,x,y$ 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 $F$ of $T(27m)$ without containing three vectors $x, y$ and $z$ which are completely orthogonal? (The same can be asked for $k$ vectors?)

8. The Frankl-Rodl Theorem to the rescue

Proposition 3: When $n=9m$ , the answer to problems 4 and hence also 3 and 1 is that the size of the set in question must be at most $(3-\epsilon)^n$ .

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 $n$ . (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 $A \subset T(7n)$ be if it has the property that you cannot find $x,y,z \in A$ such that the number of coordinates that $x_i+y_i+z_i=a$ is $n$ for $a=0,1,2,3,4,5,6$ . (This time the entries are considered as integers.)

Appendix: Two Pages From Frankl-Rodl’s Paper.

Click (and enlarge) to get it readable.

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

jozsef says:

February 8, 2009 at 3:01 am

This is very interesting! With my grad students we started a project in last Summer to understand the power of the Frankl-Rodl technique, when the spectral bound is too weak to give us the desired result. We had other, more urgent things to work on so after becoming familiar with the Frankl-Rodl paper we postponed the project to the near future. One concrete ambitious goal of the project was to improve Meshulam’s bound using the “shifting method” of Frankl-Rodl. I see now that we weren’t the only ones, and maybe there are other teams considering the same problem. Have you asked Vojta?

Reply
Gil Kalai says:

February 8, 2009 at 1:35 pm

Thanks Jozsef!

Perhaps the first thing to note is that the Frankl-Rodl theorem does not apply directly to problems like the cap set problem. The theorem allow to give upper bounds for a family of vectors in $T(n)$ say each having a ‘1’s b ‘2’s and c ‘3’s when you exclude a triple of vectors $x_1, x_2,x_3y$ so that the number of coordinates where $x_1 = a, x_2 = b, x_3 = c$ is prescribed for every $a,b,c$ . However this prescription should be “in the interior” of the range and in particular cannot have 0 entries. (Allowing 0s is an entirely different ball game.)

I did not think about Frankl-Rodl’s proof as a “shifting method” how to you see the proof in this way?

I am not sure if people tried to apply F-R’s proof or F-R’s proof technique for the cap set problem. (We also did not try that, but just noticed that the theorem applies directly to a certain variation of the cap set problem.)

Reply
jozsef says:

February 8, 2009 at 10:53 pm

Dear Gil,

To justify why did I think that Frankl-Rodl is a possible help in attacking the cap set problem (why is it called cap set?) would be a quite lengthy and probably shaky argument. I need more time to think it over again and simplify it. About calling the proof technique “shifting”; In their proof Frankl and Rodl extend the size of the forbidden intersection to an interval of forbidden intersection sizes. This interval grows and shifts left or right relative to the actual base set. At the end, when the interval has size proportional to the base set and it is a leftmost or rightmost interval in [m] (m is the size of the actual base set) one gets two set systems without small or large intersections. The sizes of these set systems are easier to handle with a Ahlswede-Katona theorem and its counterpart.

Reply
Pingback: Around the Cap-Set problem (B) « Combinatorics and more
Pingback: The Cap-Set Problem and Frankl-Rodl Theorem (C) « Combinatorics and more
Pingback: Hyper-optimistic conjecture retrospective – Part 1 « Paul Delhanty
Pingback: The new bound on cap sets | Anurag's Math Blog

	Kim on TYI 30: Expected number of Dic…
	Anonymous on Elchanan Mossel’s Amazin…
	Friendship and Sesam… on Media Item from “Haaretz…
	gowers on Elchanan Mossel’s Amazin…
	Avishay on Elchanan Mossel’s Amazin…
	Marzio De Biasi on Elchanan Mossel’s Amazin…
	Gil Kalai on Elchanan Mossel’s Amazin…
	Random Storm Thought… on Elchanan Mossel’s Amazin…
	Abi Gail on Elchanan Mossel’s Amazin…
	Kian on Elchanan Mossel’s Amazin…
	Anonymous on Elchanan Mossel’s Amazin…
	Alexey on TYI 30: Expected number of Dic…

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