The growth rate for three-colored sum-free sets

There seems to be a rule that all progress on the cap set problem should be announced on blogs, so let me continue the tradition. Robert Kleinberg, Will Sawin and I have found the rate of growth of three-colored sum-free subsets of (\mathbb{Z}/q \mathbb{Z})^n, as n \to \infty. We just don’t know it is that what we’ve found!

The preprint is here.

Let me first explain the problem. Let H be an abelian group. A subset A of H is said to be free of three term arithmetic progressions if there are no solutions to a-2b+c=0 with a, b, c \in A, other than the trivial solutions (a,a,a). I’ll write C_q for the cyclic group of order q. Ellenberg and Giswijt, building on work by Croot, Lev and Pach have recently shown that such an A in C_3^n can have size at most 3 \cdot \# \{ (a_1, a_2, \ldots, a_n) \in  \{0,1,2 \}^n : \sum a_i \leq 2n/3 \}, which is \approx 2.755^n. This was the first upper bound better than 3^n/n^c, and has set off a storm of activity on related questions.

Robert Kleinberg pointed out the argument extends just as well to bound colored-sets without arithmetic progressions. A colored set is a collection of triples (a_i, b_i, c_i) in H^3, and we see that it is free of arithmetic progressions if we have a_i - 2 b_j + c_k = 0 if and only if i=j=k. So, if a_i = b_i = c_i, then this is the same as a set free of three term arithmetic progressions, but the colored version allows us the freedom to set the three coordinates separately.

Moreover, once a, b and c are treated separately, if \# H is odd, we may as well replace b_i by -2b_i and just require that a_i+b_i+c_i=0 if and only if i is odd. This is the three-colored sum-free set problem. Three-colored sum-free sets are easier to construct than three-term arithmetic-progression free sets, but the Croot-Lev-Pach/Ellenberg-Giswijt bounds apply to them as well*.

Our result is a matching of upper and lower bounds: There is a constant \gamma(q) such that

(1) We can construct three-colored sum-free subsets of C_q^n of size \exp(\gamma n-o(n)) and

(2) For q a prime power, we can show that three-colored sum-free subsets of C_q^n have size at most \exp(\gamma n).

So, what is \gamma? We suspect it is the same number as in Ellenberg-Giswijt, but we don’t know!

When q is prime, Ellenberg and Giswijt establish the bound 3 \cdot \{ (a_1, a_2, \ldots, a_n) \in \mathbb{Z}_{\geq 0}^n : \sum a_i \leq (q-1)n/3 \}. Petrov, and independently Naslund and Sawin (in preparation), have extended this argument to prime powers.

In the set \{ (a_1, a_2, \ldots, a_n) \in \{0,1,\ldots,q-1 \}^n : \sum a_i \leq (q-1)n/3 \}, almost all the n-tuples have a particular mix of components. For example, when q=3, almost all n tuples have roughly 0.514n zeroes, 0.305 n ones and 0.181 n twos. The number of such n tuples is roughly \exp(n \eta(0.514, 0.305, 0.181)), where \eta(p_0, p_1, \ldots, p_k) is the entropy - \sum p_k \log p_k.

In general, let (p_0, p_1, \ldots, p_{q-1}) be the probability distribution on \{ 0,1,\ldots, q-1 \} which maximizes entropy, subject to the constraint that the expected value \sum j p_j is (q-1)/3. Then almost all n-tuples in \{ (a_1, a_2, \ldots, a_n) \in \{0,1,\ldots,q-1 \}^n : \sum a_i \leq (q-1)n/3 \} have roughly p_j n copies of j, and the number of such n-tuples is grows like \exp(n \cdot \eta(p_0, \ldots, p_{q-1})). I’ll call (p_0, \ldots, p_{q-1}) the EG-distribution.

So Robert and I set out to construct three-colored sum-free sets of size
\exp(n \cdot \eta(p_0, \ldots, p_{q-1})). What we were actually able to do was to construct such sets whenever there was an S_3-symmetric probability distribution on T:= \{ (a,b,c) \in \mathbb{Z}_{\geq 0} : a+b+c = q-1 \} such that p_j was the marginal probability that the first coordinate of (a,b,c) was j, and the same for the b and c coordinates. For example, in the q=3 case, if we pick (2,0,0), (0,2,0) and (0,0,2) with probability 0.181 and (1,1,0), (1,0,1) and (0,1,0) with probability 0.152, then the resulting distribution on each of the three coordinates is the EG-distribution (0.514, 0.305, 0.181), and we can realize the growth rate of the EG bound for q=3.

Will pointed out to us that, if such a probability distribution on T does not exist, then we can lower the upper bound! So, here is our result:

Consider all S_3-symmetric probability distributions on T. Let (\psi_0, \psi_1,\ldots, \psi_{q-1}) be the corresponding marginal distribution, with \psi_j the probabilty that the first coordinate of (a,b,c) will be j. Let \gamma be the largest value of \eta(\psi_0, \ldots, \psi_{q-1}) for such a \psi. Then

(1) There are three-colored sum-free subsets of C_q^n of size \exp(\gamma n - o(n)) and

(2) If q is a prime power, such sets have size at most \exp(\gamma n).

Any marginal of an S_3-symmetric distribution on T has expected value (q-1)/3, so our upper bound is at least as strong as the Ellenberg-Gisjwijt/Petrov-Naslund-Sawin bound. We suspect they are the same: That their optimal probability distribution is such a marginal. But we don’t know!


Here are a few remarks:

(1) The restriction to S_3-symmetric distributions is a notational convenience. Really, all we need is that all three marginals are equal to each other. But we might as well impose S_3-symmetry because, if all the marginals of a distribution are equal, we can just take the average over all S_3 permutations of that distribution.

(2) Our lower bound does not need q to be a prime power. I’d love to know whether the upper bound can also remove that restriction.

(3) If the largest entropy of a marginal comes from a distribution \pi_{abc} on T with all \pi_{abc}>0, then the marginal distribution is the EG distribution. The problem is about the distributions at the boundary; it seems hard to show that it is always beneficial to perturb inwards.

(4) For q \geq 7, there is more than one distribution on T with the required marginal. One canonical choice would be the one which has largest entropy given that marginal. If the optimal solution has all \pi_{abc}>0, then one can show that it factors as \pi_{abc} = \beta(a) \beta(b) \beta(c) for some function \beta:\{0,1,\ldots,q-1\} \to \mathbb{R}_{>0}.

* One exception is that Fedor Petrov has lowered the bound for AP free sets in C_3^n to 2 \cdot \{ (a_1, a_2, \ldots, a_n) \in \mathbb{Z}_{\geq 0}^n : \sum a_i \leq 2n/3 \}+1, whereas the bound for sum-free is still 3 \cdot \{ (a_1, a_2, \ldots, a_n) \in \mathbb{Z}_{\geq 0}^n : \sum a_i \leq 2n/3 \}. But, as you will see, I am chasing much rougher bounds here.

3 thoughts on “The growth rate for three-colored sum-free sets

  1. Continuing the tradition of announcing things on blogs further, I have proved your conjecture, so EG is the correct bound (up to (1+eps)^n). Will write up in the next couple of days.

  2. Sorry, my mother-in-law has been visiting and it is my week on the early morning support rota at work, so I haven’t fully written it up. Basically I show that any distribution on (0,1,…,q-1) with p_0>p_1>…>p_{q-1} and with mean (q-1)/3 is the marginal of an S3-symmetric distribution.

    These distributions form a convex region bounded by hyperplanes, so I just need to prove it for the vertices. For each such vertex, I express it as a linear combination of “triple distributions” (prob distributions on the region with mean (q-1)/3 and all probabilites equal to 0, 1/3, 2/3 or 1) and “reducible distributions” (ones where p_0=p_{q-2}=p_{q-1}=0 and p_1>=p_2>=…>=p_{q-3}).

    Since triple distributions are clearly S3-symmetric marginals, and reducible distributions can be converted to things from the q-3 case (by subtracting 1 from everything) we are done by induction.

    Devil’s in the details, of course. Hope to write it up this weekend.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s