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? Continue reading