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

The Thompson Group

Update (july 2009): A detailed posting on the Thompson group appeared on “Geometry and the Imagination,” Danny Calegary’s blog. In spite of two recent preprints one claiming that the Thompson group is amenable and the other claiming the opposite, the problem appears to be open.

We had yesteday, just a day after Independence Day, the annual meeting of the Israeli Mathematical Union and Mati Rubin talked about structures with the property that the automorphism group determines the structure up to isomorphism (even conjugacy). A lovely topic between logic and algebra with relations to many other things. Mati mentioned the Thompson group:

The set of  orientation-preserving piecewise-linear homeomorphisms of the unit interval, where the slopes are powers of two and the places where the slope changes are dyadic rationals.

There are many other presentation of the Thompson group. The wikipedia article looks very nice, and there was a special AIM workshop on it in 2004. There are many problems about the Thompson group, and one famous one is: Is it amenable?

Update (May 5): today Yuval Roichman mentioned that Patrick Dehornoy has used the Thompson group in his work regarding the diameter of the graph of the associahedron. This also brings me to the fascinating issue of coincidences that we should discuss sometime.