## Luke Pebody on sharp bounds for tri-colored sum-free sets

Quick update on this post, where I listed three variations on the problem of finding large subsets of an abelian group A with no three terms in arithmetic progression.  The quantities I called G_2(F_q^n) and G_3(F_q^n) in that post are both bounded above by M(F_q^n), the number of monomials of total degree at most (q-1)n/3 and degree at most q-1 in each variable.  There’s already been a lot of motion in the few weeks since I wrote that post!  A result of Kleinberg, Sawin, and Speyer shows that G_2(F_q^n) is bounded between c_q^n and c_q^{n-epsilon} for some constant c_q, which they explicitly describe but which is kind of hard to compute.  But it’s kind of a win-win.  Either c_q^n is less than M(F_q^n), in which case, great, improvement over the results of CLP/EG, or not, in which case, great, the bounds on tri-colored sum-free sets in CLP/EG are tight up to subexponential factors!  And now Luke Pebody has posted a preprint showing that the latter is the case.

To sum up:  the quantities G_2(F_q^n) and G_3(F_q^n) which I alluded to in the original post are now bounded above by M(F_q^n) and below by M(F_q^n)^{1-epsilon}.  Wonderful!

This only heightens the interest in the original problem of estimating G_1(F_q^n), the size of the largest subset of F_q^n containing no three-term arithmetic progession.  Is the bound M(F_q^n) essentially sharp?  Or is G_1(F_q^n) much smaller?

## 3 thoughts on “Luke Pebody on sharp bounds for tri-colored sum-free sets”

1. David Speyer says:

I’d like to try to make other people curious about what happens for 4-term AP. If you follow the logic of the 3-term bounds, all of the formal steps work, but, when you look to see what bound you’ve obtained, it is the trivial bound $p^n$. And Sawin and Tao have pretty thoroughly worked through whether there is anywhere to make a minor improvement to the argument and get a better bound out, with the conclusion that there isn’t. (See https://terrytao.wordpress.com/2016/08/24/notes-on-the-slice-rank-of-tensors/ .)

So, maybe this means that there really are large 4-term AP free sets!

But, when one tries to copy our argument to build them, one fails completely. In the 3-term proof, we need the basic observation that, if $\vec{x}$, $\vec{y}$ and $\latex \vec{z}$ are in $\{ 0,1,2,\ldots,p-1 \}^n$ with $\vec{x}+\vec{y}+\vec{z} \equiv (p-1,p-1,\cdots,p-1) \bmod p$ and $\sum x_i = \sum y_i = \sum z_i = (p-1)n/3$, then $\vec{x}+\vec{y}+\vec{z} = (p-1,p-1,\cdots,p-1)$. The corresponding thing you need for $4$ term is that, if $\vec{w}$, $\vec{x}$, $\vec{y}$ and $\latex \vec{z}$ are in $\{ 0,1,2,\ldots,p-1 \}^n$ with $\vec{w}+\vec{x}+\vec{y}+\vec{z} \equiv (2p-2,2p-2,\cdots,2p-2) \bmod p$ and $\sum w_i = \sum x_i = \sum y_i = \sum z_i = (p-1)n/4$, then $\vec{w}+\vec{x}+\vec{y}+\vec{z} = (2p-2,2p-2,\cdots,2p-2)$.

And this just isn’t true! We can have $w_i+x_i+y_i+z_i = p-2$, $2p-2$ or $3p-2$, as long as $p-2$ and $3p-2$ occur equally often. I can’t find any sort of dumb trick to dodge this issue. But maybe I’m missing something!

2. JSE says:

I’d like to try to make other people curious about what happens for 4-term AP.

You have succeeded in my case!

3. Luke Pebody says:

As a response to David’s Comment, assuming p is odd, if you can restrict the parity of w_i+x_i+y_i+z_i to be even, then you are done. But then you’re going to lose a factor of 2^n, which is pretty awful.