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?

Tagged , , ,

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.

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

%d bloggers like this: