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 , as . We just don’t know it is that what we’ve found!
The preprint is here.
Let me first explain the problem. Let be an abelian group. A subset of is said to be free of three term arithmetic progressions if there are no solutions to with , , , other than the trivial solutions . I’ll write for the cyclic group of order . Ellenberg and Giswijt, building on work by Croot, Lev and Pach have recently shown that such an in can have size at most , which is . This was the first upper bound better than , 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 in , and we see that it is free of arithmetic progressions if we have if and only if . So, if , 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 , and are treated separately, if is odd, we may as well replace by and just require that if and only if 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 such that
(1) We can construct three-colored sum-free subsets of of size and
(2) For a prime power, we can show that three-colored sum-free subsets of have size at most .
So, what is ? We suspect it is the same number as in Ellenberg-Giswijt, but we don’t know!
When is prime, Ellenberg and Giswijt establish the bound . Petrov, and independently Naslund and Sawin (in preparation), have extended this argument to prime powers.
In the set , almost all the -tuples have a particular mix of components. For example, when , almost all tuples have roughly zeroes, ones and twos. The number of such tuples is roughly , where is the entropy .
In general, let be the probability distribution on which maximizes entropy, subject to the constraint that the expected value is . Then almost all -tuples in have roughly copies of , and the number of such -tuples is grows like . I’ll call the EG-distribution.
So Robert and I set out to construct three-colored sum-free sets of size
. What we were actually able to do was to construct such sets whenever there was an -symmetric probability distribution on such that was the marginal probability that the first coordinate of was , and the same for the and coordinates. For example, in the case, if we pick , and with probability and , and with probability , then the resulting distribution on each of the three coordinates is the EG-distribution , and we can realize the growth rate of the EG bound for .
Will pointed out to us that, if such a probability distribution on does not exist, then we can lower the upper bound! So, here is our result:
Consider all -symmetric probability distributions on . Let be the corresponding marginal distribution, with the probabilty that the first coordinate of will be . Let be the largest value of for such a . Then
(1) There are three-colored sum-free subsets of of size and
(2) If is a prime power, such sets have size at most .
Any marginal of an -symmetric distribution on has expected value , 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 -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 -symmetry because, if all the marginals of a distribution are equal, we can just take the average over all permutations of that distribution.
(2) Our lower bound does not need 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 on with all , 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 , there is more than one distribution on with the required marginal. One canonical choice would be the one which has largest entropy given that marginal. If the optimal solution has all , then one can show that it factors as for some function .
* One exception is that Fedor Petrov has lowered the bound for AP free sets in to , whereas the bound for sum-free is still . But, as you will see, I am chasing much rougher bounds here.