A few weeks ago, I e-mailed Will Sawin excitedly to tell him that I could extend the new bounds on three-term arithmetic progression free subsets of to . Will politely told me that I was the third team to get there — he and Eric Naslund already had the result, as did Fedor Petrov. But I think there might be some expository benefit in writing up the three arguments, to see how they are all really the same trick underneath.
Here is the result we are proving: Let be a prime power and let be the cyclic group of order . Let be a set which does not contain any three term arithmetic progression, except for the trivial progressions . Then
The exciting thing about this bound is that it is exponentially better than the obvious bound of . Until recently, all people could prove was bounds like , and this is still the case if is not a prime power.
All of our bounds extend to the colored version: Let be a list of triples in such that , but if are not all equal. Then the same bound applies to . To see that this is a special case of the previous problem, take . Once the problem is cast this way, if is odd, one might as well define , so our hypotheses are that but if are not all equal. We will prove our bounds in this setting.
My argument — Witt vectors
I must admit, this is the least slick of the three arguments. The reader who wants to cut to the slick versions may want to scroll down to the other sections.
We will put an abelian group structure on the set which is isomorphic to , using formulas found by Witt. I give an example first: Define an addition on by
The reader may enjoy verifying that this is an associative addition, and makes into a group isomorphic to . For example, and .
In general, Witt found formulas
For example, when , we have
So if and only if in .
We now work with variables, , and , where and . Consider the polynomial
Here each is a polynomial in variables.
So is a polynomial on . We identify this domain with . Then if and only if in the group .
We define the degree of a monomial in the , and by setting . In this section, “degree” always has this meaning, not the standard one. The degree of is ; the degree of is and the degree of is .
From each monomial in , extract whichever of , or has lowest degree. We see that we can write
where , and are monomials of degree .
The now-standard argument (I like Terry Tao’s exposition) shows that is bounded by three times the number of monomials of degree . One needs to check that the argument works when the “degree” of a variable need not be , but this is straightforward.
Except we have a problem! There are too many monomials. To solve this issue, let be the polynomial obtained from by replacing every monomial by where with if and if . So coincides with as a function on , but uses smaller monomials. For example, the reader who multiplies out the expression for when will find a term . In , this is replaced by . The polynomial does not have the nice factorization of , but it is much smaller. For example, when , has nonzero monomials and has . Replacing by can only lower degree, so . Now rerun the argument with . Our new bound is three times the number of monomials of degree , with the additional condition that all exponents are .
Now, the monomial has degree . Identify with by sending to . We can thus think of as . We get the bound , just as in the prime case.
Naslund-Sawin — binomial coefficients
Let’s be much slicker. Here is how Naslund and Sawin do it (original here).
Notice that, by Lucas’s theorem, the function is a well defined function when . Moreover, using Lucas again,
Define a function by
Here we have expanded by Vandermonde’s identity and used .
Define a function by just as before. So if and only if in the abelian group . Expanding gives a sum of terms of the form . Considering such a term to have “degree” , we see that has degree .
As in the standard proof, factor out whichever of , or , has least degree. We obtain
where , and are products of binomial coefficients and, taking , we have , and .
We derive the bound , exactly as before.
Group rings — Petrov’s argument
I have taken the most liberties in rewriting this argument, to emphasize the similarity with the other arguments. The reader can see the original here.
Let . Let be the ring of functions with pointwise operations, and let be the group ring of . We think of acting on by .
Let , , …, be generators for . Let the functions annihilated by the operators where . For example, is the functions which obey for any , and . We think of as polynomials of degree , and the dimension of is the number of monomials in variables of total degree where each variable has degree .
Define by and otherwise. Define by .
We write , and for the generators of the three factors in .
Then we have
So, if , then as a function on .
On the other hand, we can expand for , and in . We see that, if , then
We make the familiar deduction: We can write in the form
where , and run over a basis for .
Once more, we obtain the bound .
Petrov’s method has an advantage not seen in the other proofs: It generalizes well to the case that is non-abelian. For any finite group , let be a one-sided ideal in obeying . In our case, this is the ideal generated by with . Then we obtain a bound for sum free sets in .
What’s going on?
I find Petrov’s proof immensely clarifying, because it explains why the arguments all give the same bound. We are all working with functions . I write them as polynomials in variables , Naslund and Sawin use binomial coefficients . The formulas to translate between our variables are a mess: For example, my is their . However, we both agree on what it means to be a polynomial of degree : It means to be annihilated by .
In both cases, we take the indicator function of the identity and pull it back to along the addition map. The first two proofs use explicit identities to see that the result has degree . The third proof points out this is an abstract property of functions pulled back along addition of groups, and has nothing to do with how we write the functions as explicit formulas.
I sometimes think that mathematical progress consists of first finding a dozen proofs of a result, then realizing there is only one proof. My mental image is settling a wilderness — first there are many trails through the dark woods, but later there is an open field where we can run wherever we like. But can we get anywhere beyond the current bounds with this understanding? All I can say is not yet…