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 is
. Here is an obvious fact:
The maximum size of a set
in
with the property that every
(
) satisfy
is at most the maximum size of a cap set in
.
Proof: Indeed the condition for is stronger than being a cap set. We require for every
not only that
but even
.
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 of
, where n=3m. Suppose that
does not contain the following configuration: two vectors
such that for every
,
. This is stronger than the assertion that
is a cap set. The Frankl-Rodl theorem implies that the size of
is at most
.
In other words, both the optimistic upper bound of for the cap set problem and the Frankl-Rodl theorem have the same weaker consequence: A subset of
without two vectors whose sum is also in
has size at most
.
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 the parameters
.
Studying extremal problems for sets where are fixed (or just
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 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 of sets whose fine parameters are fixed and consider pairwise intersections of such sets also with presecibed parameters. Then we can conjecture that if
is a subfamily which contains a proportion
of the sets, the number of intersections with the prescribed parameters will go down by only
. (Where
tends to 0 as
does.
While at it, we can consider several subfamilies, -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 . Again, we can write for
,
. Let
be the set of vectors
s so that
for every
. (We need to assume that
is divisible by 3 for
.)
An upper bound for the cap set problem of the form will imply that a subset of
without two vectors
whose sum also belongs to
has size at most
. 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
.
This is believable (and perhaps doable) for bounded value of . The case where
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)=$ is
. The folllowing fact follows from a simple averaging argument.
Let then
If the maximum size of a cap set in
is
and
then
.
As a matter of fact 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 with all sets of the form
, and note that a
is a cap set in
iff
is a cap set in
.
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 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.)
Pingback: Peter Keevash and Eoin Long: Forbidden vector-valued intersections | Combinatorics and more
Pingback: Péter Pál Pach and Richárd Palincza: a Glimpse Beyond the Horizon | Combinatorics and more