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?

### Like this:

Like Loading...

*Related*

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 . 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{y}$ and $\latex \vec{z}$ are in with and , then . The corresponding thing you need for term is that, if , , $\vec{y}$ and $\latex \vec{z}$ are in with and , then .

And this just isn’t true! We can have , or $3p-2$, as long as 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!

I’d like to try to make other people curious about what happens for 4-term AP.You have succeeded in my case!

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.