Part B: Finding special cap sets
This is a second part in a 3-part series about variations on the cap set problem that I studied with Roy Meshulam. (The first post is here.) I will use here a different notation than in part A to make it compatible with various posts of polymath1 which consider similar objects. We write and
denotes all vectors of length
with
0’s,
1’s and
2’s.
An affine line are three vectors so that
for every
. A cap set is a subset of
without an affine line. The cap set problem asks for the maximum size of a cap set. For information on the cap set problem itself look here. For questions regarding density of sets avoiding other types of lines look here.
In the first part we considered the case that and considered “modular lines” , i.e., three vectors
so that the number of solutions to
is divisible by
for every
. When
is divisible by 9 the Frankl-Rodl theorem implies that a subset of
with more than
elements must contain a modular line, and even a modular line with two equal elements. (Question: does the same statement follow from Frankl-Rodl theorem when
is divisible by 3 and not by 9?)
10. Some propositions in the desired direction.
Proposition 6: Suppose that , and that
. If every set of size >
has a modular line, then every set of size >
has a modular line which is either an affine line, or the number of
s such that
is precisely
for
.
(So we can get rid of a few “types” of modular lines which are not really affine lines, but not all of them.)
Proposition 6 follows from the much more transparent proposition:
Proposition 7: There are sets of constant density which do not contain a modular line for which the numbers of solutions of
for
is never a permutation of
.
Proof: Consider all vectors where the sum of the coordinates is zero modulo 3. This property is preserved under sums but it does not hold for the sums we are looking at. (All the quantities: 0+m+4m, 0+0 +4m, 0+2m+2m, 0+2m+0, m, 2m are not divisible by 3.)
11. A strong variant form of the problem
Here are innocent-looking variants of Problem 1: (the existence of modular lines)
Problem 6: How large can a set in
be without three vectors x, y and z such that
for
?
Problem 7: How large can a set F in be without three vectors x, y and z such that
for every a=0,1,2,3,4,5,6?
Proposition 8: There is a set of positive density which satisfies the requirement of Problem 7.
Here is the construction: Let’s consider the case that and that
. Consider vectors in
for which
and the sum of the coordinates is zero modulo 5. Now the modulo five sum of
satisfying the required condition is:
. walla!
(This type of construction resembles the Salem-Spencer (pre-Behrend) constructions for sets without 3 term A. P.)
13. Problem 6 and a brief moment of hope
So for a moment we thought that if we can show that the answer for problem 6 is then we will be able to eliminate all the other possibilities and enforce an affine line. But then we realized that if this argument works it will kill all solutions including affine lines as well!
It looks that by playing with several (but a bounded number of) primes instead of just 5 we will be able to give a similar answer for Problem 6. But we did not check if this is indeed the case. This is left as an interesting challenge. (Question: Can this indeed be done?)
14. Sanity checks
1) Doesn’t a positive answer for problem 6 give a cap set of positive density, in contradiction to Meshulam’s theorem? No! because we eliminate very special types of affine lines.
2) Isn’t Proposition 8 in conflict with the Frankl-Rodl theorem? No, because when we look at the statement of that theorem there is an assumption which we cannot take for granted. The Frankl Rodl Theorem implies that if we take a subset of density (say) from
(again, say) then the number of configurations we are interested in goes down by no more than a multiplicative factor of
(say). But we need exponentially many configurations to start with! This is an important point regarding the Frankl-Rodl theorem.
3) Maybe we can look at all sorts of primes and give an example of a large cap set? (At some point I had a heuristic argument that suggested that such a construction will work when the density is but the same heuristic argument shows, once and for all, that when
is large
. (So this heuristic argument must be wrong…) There a general argument that Noga Alon showed us that large sets defined by a system of linear equations
where the coefficients are not too wild will contain an affine line.
15. Excluding special type of affine lines.
Examples of the form we consider here may be useful when we want to exclude special types of affine lines. Given three vectors which form an affine line, call the profile of the line the vector $(a,b,c)$ so that there are
coordinates where
,
coordinates where
, and
coordinates where
. A random affine line will have a profile close to
. We can ask and hope to solve using constructions like those considered here:
Problem:
A) How large can a set be without an affine line of profile where
,
?
B) How large can a set be without an affine line of profile where
(suppose
is divisible by 9)
etc.
16. Conclusion of part B
Using vectors with prescribed sums of coordinates modulo different primes (and variations on this construction) may lead to large sets without any affine lines of special types described in terms of their profiles.
Pingback: The Cap-Set Problem and Frankl-Rodl Theorem (C) « Combinatorics and more
Hi Gil, I don’t understand your definition of “modular line”. Typo perhaps?
thanks a lot Gabriel, corrected.
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