The Cap-Set Problem and Frankl-Rodl Theorem (C)

Posted on May 18, 2009 by Gil Kalai

Update: This is a third of three posts (part I, part II) proposing some extensions of the cap set problem and some connections with the Frankl Rodl theorem. Here is a post presenting the problem on Terry Tao’s blog (March 2007). Here is an open discussion post around Roth theorem (March 2009). Here are two “open discussion” posts on the cap set problem (first, and second) from Gowers’s blog (January 2011). These posts include several interesting Fourier theoretic approaches towards improvement of the Roth-Meshulam bound. The second post describes a startling example by Seva Lev.

Suppose that the maximum size of a cap set in $\Gamma(n)=\{1,2,3\}^n$ is $n/g(n)$ . Here is an obvious fact:

The maximum size of a set $F$ in $G$ with the property that every $x,y\in G$ ( $x \ne y$ ) satisfy $x+y \notin G$ is at most the maximum size of a cap set in $G$ .

Proof: Indeed the condition for $F$ is stronger than being a cap set. We require for every $x,y \in F$ $x \ne y$ not only that $x+y \notin F$ but even $x+y \notin G$ .

Part C. A more direct relation between Frankl-Rodl’s theorem and the cap set problem and all sorts of fine gradings on subsets of {1,2,…,n}.

In part A we moved from sets avoiding affine lines (cap sets) to sets avoiding “modular lines” and used the Frankl-Rodl theorem to deal with the latter. This may look artificial. Here is a simpler connection between the cap set problem and the Frankl-Rodl theorem.

17. Why weaker forms of the Frankl-Rodl Theorem follow from upper bounds on cap sets.

Consider a subset $F$ of $\Gamma_{m,m,m}$ , where n=3m. Suppose that $F$ does not contain the following configuration: two vectors $x,y$ such that for every $a=0,1,2$ , $|\{i:x_i+y_i=a(mod~3)\}|=m$ . This is stronger than the assertion that $F$ is a cap set. The Frankl-Rodl theorem implies that the size of $F$ is at most $(3 - \epsilon)^n$ .

In other words, both the optimistic upper bound of $(3-\epsilon)^n$ for the cap set problem and the Frankl-Rodl theorem have the same weaker consequence: A subset of $\Gamma_{m,m,m}$ without two vectors whose sum is also in $\Gamma_{m,m,m}$ has size at most $(3-\epsilon)^{3m}$ .

18. Diversion: various gradings on subsets.

Let us talk a little about subsets. We have a grading on subsets by their size. Problems about sets of fixed size are usually more delicate than problems on arbitrary sets. We have a finer grading on sets according to the sum of their elements. Problems about sets whose sum of elements are fixed are even more delicate (and rare.)

We do not have to stop there: We can associate to a set $S$ the parameters

$a_k(S)= \sum_ {i \in S} {{i-1} \choose {k}}$ .

Studying extremal problems for sets where $a_1 (S),a_2 (S),\dots ,a_r (S)$ are fixed (or just $a_r(S)$ is fixed) is not common. There are a few such results, and related ideas come into play in various contexts.

Let me mention one: The Sperner property for the poset of sets with prescribed sums of coordinates is closely related to the famous Erdos-Moser problem: What is the maximum number of equal sums for subsets of $n$ distinct positive real numbers. The precise bounds (attained by {1,2,…,n}) was proved by Stanley using the Hard-Lefshetz theorem. (Simpler proofs based on elementary representation theory were subsequently found.)

We can ask if the Frankl-Rodl theorem can be extended to this setting. The type of theorem we are looking for will start with a family $\cal F$ of sets whose fine parameters are fixed and consider pairwise intersections of such sets also with presecibed parameters. Then we can conjecture that if $\cal G$ $\subset \cal F$ is a subfamily which contains a proportion $(1-\epsilon)^n$ of the sets, the number of intersections with the prescribed parameters will go down by only $(1-\delta)^n$ . (Where $\delta$ tends to 0 as $\epsilon$ does.

While at it, we can consider several subfamilies, $t$ -fold intersections, larger alphabets, etc., just like Frankl and Rodl did.

The point is that (for an alphabet of size 3) the optimistic upper bound for the cap set problem implies some weak consequences of these Frankl-Rodl hypothetical generalizations.

19. Applications of upper bounds for cap sets in the Frankl-Rodl spirit.

Consider now a vector $x\in \Gamma(n)$ . Again, we can write for $j=0,1,2$ , $a^j_k(x)= \sum_ {i: x_i=j} {{i-1} \choose {k}}$ . Let $\Gamma^r(n)$ be the set of vectors $x \in \Gamma (n)$ s so that $a^0_k(x)=a^1_k(x)=a^2_k(x)$ for every $k=1,2,\dots, t$ . (We need to assume that ${{n} \choose {k}}$ is divisible by 3 for $k=1,2,\dots, t+1$ .)

An upper bound for the cap set problem of the form $(3-\epsilon)^n$ will imply that a subset of $\Gamma^r (n)$ without two vectors $x,y$ whose sum also belongs to $\Gamma^r(n)$ has size at most $(3-\epsilon)^n$ . This looks like a strong theorem of the Frankl-Rodl type. The question is if Frankl-Rodl’s methods can be extended to our finer gradings of $\Gamma$ .

This is believable (and perhaps doable) for bounded value of $t$ . The case where $t$ goes slowly to infinity may be a good place to look for counterexamples.

20. An averaging fact worth knowing:

Suppose that the maximum size of a cap set in $latex\Gamma(n)=$ $\{0,1,2\}^n$ is $n/g(n)$ . The folllowing fact follows from a simple averaging argument.

Let $G \subset \Gamma(n)$ then

If the maximum size of a cap set in $G$ is $c(G)$ and $|G|/c(G) =u$ then $u \le g(n)$ .

As a matter of fact $G$ can be a multi-subset (elements can appear several times) or even a general distribution.

To prove this assertion consider the intersection of a cap set of maximum size in $\Gamma(n)$ with all sets of the form $G+x$ , and note that a $F$ is a cap set in $G$ iff $F+x$ is a cap set in $G+x$ .

Remark: This simple averaging trick is useful on many occasions. One example are “Elias bounds” for error-correcting codes. For the related problem of “density Hales Jewett” discussed on Gower’s blog, it turns out that while the problem is not invariant under a group action, it is still correct that its statement for various different measures on $\Gamma(n)$ are (qualitativly) equivalent using a somewhat more complicated averaging argument. This phenomenon deseves further study. (This is the third and last post in this series; The first two are here and here.)

This entry was posted in Combinatorics, Open problems and tagged Cap sets, Frankl-Rodl theorem, polymath1. Bookmark the permalink.

	Gil Kalai on To Cheer You Up in Difficult T…
	Gil Kalai on To Cheer You Up in Difficult T…
	Alexander Barvinok on To Cheer You Up in Difficult T…
	Kevin on To Cheer You Up in Difficult T…
	Gil Kalai on To Cheer You Up in Difficult T…
	Arseniy on To Cheer You Up in Difficult T…
	Alexander Barvinok on To Cheer You Up in Difficult T…
	uniform on To Cheer You Up in Difficult T…
	Arseniy on To Cheer You Up in Difficult T…
	normanstresskopf on To Cheer You Up in Difficult T…
	To Cheer You Up in D… on Beyond the g-conjecture…
	To Cheer You Up in D… on Euler’s Formula, Fibonac…