Consider the following problems:
P3: What is the maximum density of a set A in without a 3-term AP? (AP=arithmetic progression.)
This is the celebrated Cap Set problem and we reported here in 2016 the breakthrough results by Croot-Lev-Pach-Ellenberg-Gijswijt (CLPEG) asserting that .
P4: What is the maximum density of a set A in without a 4-term AP?
P5: What is the maximum density of a set A in without a 5-term AP?
Moving from 3 term AP to 4 term AP represents a major leap for such problems. In some cases moving from 4 to 5 also represents a major leap. Usually the techniques that work for continue to work for , that is, I am not aware of cases where moving from 5 to 6 also represent a major leap. In other words, we do not have reasons to think, so far, that progress on P6 (below) will be considerably harder than progress on P5.
P6: What is the maximum density of a set A in without a 6-term AP?
And, of course, we can move on to P7, P8, P9,…. ,
It is known that the density of a set without -term AP for every fixed m goes to zero with n. This was proved by Furstenberg and Katznelson using ergodic theoretical tools. Following the CLPEG breakthrough we can certainly believe that the density that guarantees m-term AP in for every fixed m is exponentially small in n. I vaguely remember that the best known bounds for P4 are polylogarithmically small with n and were achieved by Green and Tao using tools from Gowers’ work on 4AP-free sets over the integers.
A little more before we move on
To have some general notation let denote the maximal size of a set with no k distinct elements in arithmetic progression. It is reasonable to believe that for some , that is that sets in avoiding terms AP are exponentially small. To be more precise let
We can believe that the limits exist, that , and we may also guess (wildly but safely) that they satisfy .
These problems, as well as the analogous problems over the integers, (Roth’s and Szemeredi’s theorems and later developments), and the related density Hales Jewett problem, form a holy grail of additive combinatorics and they attracted a lot of attention also on this blog.
Here is a partial list of posts: 2008 Pushing the Behrend bound; 2009A, 2009B 2009C Attempts to relate the problem to the Frankl-Wilson Theorem (and the polynomial method) and to Frankl-Rodl theorem and also to find counterexamples; 2009D polymath1; 2009P public opinion poll about the true behavior; 2010 The logarithmic bound for Roth is reached; 2011 cap sets and matrix multiplications; 2016a, 2016b The CLPEG breakthrough; 2016W A polynomial method workshop; 2020 The logarithmic bound for Roth is broken.
Let’s move on to the new result by Péter Pál Pach and Richárd Palincza
The absolutely stunning result by Péter Pál Pach and Richárd Palincza
As we already mentioned, so far we do not have reasons to expect that proving density results for 6-terms AP in (or ) will be much harder than the question over . However, what Pach and Palincza proved is as follows:
Theorem: sets avoiding 6-term arithmetic progressions in have size at most .
The big surprise is that the problem P6 over integers modulo six is much easier than P4 and P5. The proof is based on a simple combinatorial reasoning showing that
The paper arXived on September 2020 is
Click and enjoy this beautiful, stunning and very simple proof.
Congratulations to Péter and Richárd!