# 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. Luke Pebody says:

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. Luke Pebody says:

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.