The growth rate for three-colored sum-free sets

Secret Blogging Seminar 2018-03-12

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.