Around the Cap-Set problem (B)

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.

About these ads