As you know I love the affine cap problem: how big can a subset of (Z/3Z)^n be that contains no three elements summing to 0 — or, in other words, that contains no 3-term arithmetic progression? The best upper bounds, due to Bateman and Katz, are on order 3^n / n^(1+epsilon). And I think it’s fair to say that all progress on this problem, since Meshulam’s initial results, have come from Fourier-analytic arguments.

So I’m charmed by this paper of Ernie Croot, Vsevolod Lev, and Peter Pach which proves a much stronger result for A = (Z/4Z)^n: a subset with no 3-term arithmetic progression has size at most c^n for c strictly less than 4. Better still (for an algebraic geometer) the argument has no harmonic analysis at all, but proceeds via the polynomial method!

This is surprising for two reasons. First, it’s hard to make the polynomial method work well for rings, like Z/4Z, that aren’t fields; extending our knowledge about additive combinatorics to such settings is a long-standing interest of mine. Second, the polynomial method over finite fields usually works in the “fixed dimension large field” regime; problems like affine cap, where the base ring is fixed and the dimension are growing, have so far been mostly untouched.

As for the first issue, here’s the deal. This *looks* like a problem over Z/4Z but is really a problem over F_2, because the condition for being a 3-term AP

a – 2b + c = 0

has a 2 in it. In other words: the two outer terms have to lie in the same coset of 2A, and the middle term is only determined up to 2A.

So CLP recast the problem as follows. Let S be a large subset of A with no 3-term AP. Let V be 2A, which is an n-dimensional vector space over F_2. For each v in V, there’s a coset of V consisting of the solutions to 2a = v, and we can let S_v be the intersection of S with this coset.

We want to make this a problem about V, not about A. So write T_v for a translate of S_v by some element of the coset, so T_v now sits in V. Which element? Doesn’t matter!

We can now write the “no 3-term AP” condition strictly in terms of these subsets of V. Write (T_v – T_v)^* for the set of differences between *distinct* elements of T_v. Write U for the set of v in V such that T_v is nonempty. Then the union over all v in U of

(T_v – T_v)^* + v

is disjoint from U.

I leave it as an exercise to check the equivalence.

Now we have a combinatorial question about vector spaces over F_2; we want to show that, under the condition above, the sum of |T_v| over all v in U can’t be too large.

This is where the polynomial method comes in! CLP show that (over any field, not just F_2), a polynomial of low degree vanishing on (T_v – T_v)^* has to vanish at 0 as well; this is Lemma 1 in their paper. So write down a polynomial P vanishing on V – U; by dimension considerations we can choose one which doesn’t vanish on all of V. (This uses the fact that the squarefree monomials of degree up to d are linearly independent functions on F_2^n.) If U is big, we can choose P to have lowish degree.

Since P vanishes on V-U, P has to vanish on (T_v – T_v)^* + v for all v. Since P has low degree, it has to vanish on v too, for all v. But then P vanishes everywhere, contrary to our assumption.

The magic of the paper is in Lemma 1, in my view, which is where you really see the polynomial method applied in this unusual fixed-field-large-dimension regime. Let me say a vague word about how it works. (The actual proof is less than a page, by the way, so I’m not hiding much!) Let P be your polynomial and d its degee. You send your vector space into a subvariety of a much larger vector space W via degree-d Veronese embedding F_d. In fact you do this twice, writing

V x V -> W x W.

Now if P is your polynomial of degree-d, you can think of P(v_1 – v_2) as a bilinear form <,> on W x W. Suppose S is a subset of V such that P(s_1 – s_2) vanishes for all distinct s_1, s_2 in S. That means

<F_d(s_1), F_d(s_2)> = 0

for all distinct s_1, s_2 in S. On the other hand,

<F_d(s_1), F_d(s_1)>

doesn’t depend on s_1; it just takes the value P(0). So if P(0) is not equal to 0, you have |S| vectors of nonzero norm which are mutually orthogonal under this bilinear form, and so there can be at most dim W of these, and that’s the bound on |S| you need.

This is very slick and I hope the idea is more generally applicable!

“In other words: the middle term of every arithmetic progression lies in 2A” – This is a bit confusing. If you have 2A = {2x : x \in A}, then this does not hold. We just have 2b = a + c, for a, b, c \in A. I don’t see how that implies b \in 2A. Take A = (Z/4Z)^2, a = (1, 0), b = (3, 1), c = (1, 2) as an example. Did you mean to say something else? (I haven’t read further than this).

Right you are! I changed it to what I mean to say.

[…] it seems to me that the idea of the Croot-Lev-Pach paper I posted about yesterday can indeed be used to give a new bound on the size of subsets of F_3^n with no three-term […]

[…] it seems to me that the idea of the Croot-Lev-Pach paper I posted about yesterday (GK: see also my last post) can indeed be used to give a new bound on the size of subsets of F_3^n […]

[…] it seems to me that the idea of the Croot-Lev-Pach paper I posted about yesterday can indeed be used to give a new bound on the size of subsets of F_3^n with no three-term […]