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 $\Gamma(n) = \{0,1,2\}^n$ and $\Gamma_{a,b,c}$ denotes all vectors of length $n$ with $a$ 0’s, $b$ 1’s and $c$ 2’s.

An affine line are three vectors $x,y,z$ so that $x_i + y_i + z_i = 0 (mod~3)$ for every $i$ . A cap set is a subset of $\Gamma(n)$ 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 $n=3m$ and considered “modular lines” , i.e., three vectors $x,y,z$ so that the number of solutions to $x_i+y_i+z_i=a(mod~3)$ is divisible by $m$ for every $a$ . When $n$ is divisible by 9 the Frankl-Rodl theorem implies that a subset of $\Gamma$ with more than $(3-\epsilon)^n$ 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 $n$ is divisible by 3 and not by 9?)

10. Some propositions in the desired direction.

Proposition 6: Suppose that $n=3m$ , and that $m=1 (mod~3)$ . If every set of size > $(3-\epsilon)^n$ has a modular line, then every set of size > $(3-\epsilon)^n$ has a modular line which is either an affine line, or the number of $i$ s such that $x_i + y_i + z_i =a$ is precisely $m$ for $a=0,1,2$ .

(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 $\{x,y,z\}$ for which the numbers of solutions of $x_i + y_i + z_i =a(mod~3)$ for $a=0,1,2$ is never a permutation of $(0,m,2m)$ .

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 $F$ in $\Gamma(7m)$ be without three vectors x, y and z such that $|\{i:x_i+y_i+z_i=a\}|=o(mod~m)$ for $a=0,1,2,3,4,5,6$ ?

Problem 7: How large can a set F in $\Gamma (7m)$ be without three vectors x, y and z such that $|\{i: x_1+y_i+z_i=a\}| = m$ 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 $n=7p$ and that $p=3 (mod~5)$ . Consider vectors in $\Gamma (n)$ for which $x_1=0$ and the sum of the coordinates is zero modulo 5. Now the modulo five sum of $x,y,z$ satisfying the required condition is: $2p+2p+3p+4p=3(mod~5)$ . 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 $(3-\epsilon)^n$ 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 $0.9999^n$ (say) from $\Gamma_{a,b,c}$ (again, say) then the number of configurations we are interested in goes down by no more than a multiplicative factor of $0.99^n$ (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 $3^n/n^2$ but the same heuristic argument shows, once and for all, that when $n$ is large $n^6 > 2^n$ . (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 $Ax \in B$ 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 $x,y,z$ which form an affine line, call the profile of the line the vector $(a,b,c)$ so that there are $a$ coordinates where $x_i+y_i+z_i=0$ , $b$ coordinates where $x_i+y_i+z_i=3$ , and $c$ coordinates where $x_i+y_i+z_i=9$ . A random affine line will have a profile close to $n/9, 7n/9, n/9$ . 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 $(a,b,c)$ where $|a-n/9|< n^{1/5}$ , $|c-n/9| < n^{1/5}$ ?

B) How large can a set be without an affine line of profile $(a,b,c)$ where $b=7n/9$ (suppose $n$ 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

2 Responses to Around the Cap-Set problem (B)

Pingback: The Cap-Set Problem and Frankl-Rodl Theorem (C) « Combinatorics and more
Gabriel says:

March 5, 2010 at 3:31 pm

Hi Gil, I don’t understand your definition of “modular line”. Typo perhaps?

thanks a lot Gabriel, corrected.

	Gil Kalai on זה הזמן לשינוי
	Yiftach on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	Yiftach on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	קוסמופוליט on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	Eli_B on זה הזמן לשינוי
	Michael Elkin on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	Eli_B on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי

Around the Cap-Set problem (B)

Part B: Finding special cap sets