Péter Pál Pach and Richárd Palincza: a Glimpse Beyond the Horizon

 

Prologue

Consider the following problems:

P3: What is the maximum density of a set A in (\mathbb Z/3\mathbb Z)^n 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 |A| \le 2.755..^n.

P4: What is the maximum density of a set A in  (\mathbb Z/4\mathbb Z)^n without a 4-term AP?

P5: What is the maximum density of a set A in  (\mathbb Z/5\mathbb Z)^n 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 k=5 continue to work for k>5, 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 (\mathbb Z/6\mathbb Z)^n 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 A \subset (\mathbb Z_m)^n without m-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 \mathbb Z_m^n 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 r_k(\mathbb Z_m^n) denote the maximal size of a set A \subset \mathbb Z_m^n with no k distinct elements in arithmetic progression. It is reasonable to believe that r_m(\mathbb Z_m^n) \le \delta_m^n m^n for some \delta_m < 1, that is that sets in \mathbb Z_m^n avoiding m terms AP are exponentially small. To be more precise let

\delta_m= \frac {1}{m} \lim r_k(\mathbb Z_m^n)^{1/n}

We can believe that the limits exist,  that \delta_m<1, and we may also guess (wildly but safely) that they satisfy {\delta_3} < {\delta_4} < {\delta_5} \cdots  .

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 \mathbb Z_6^n (or \mathbb Z) will be much harder than the question over \mathbb Z_5^n. However, what Pach and Palincza proved is as follows:

Theorem:  sets avoiding 6-term arithmetic progressions in \mathbb Z_6^n have size at most 5.709^n.

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

r_6(\mathbb Z_6^n) \le 2^{n+1} \sqrt {3^nr_3(\mathbb Z_3^n).}

The paper arXived on September 2020 is

Péter Pál Pach and Richárd Palincza: Sets avoiding six-term arithmetic progressions in \mathbb Z^n_6 are exponentially small

Click and enjoy this beautiful, stunning and very simple proof.

Congratulations to Péter and Richárd!

This entry was posted in Combinatorics, Geometry, Number theory, Open problems and tagged , . Bookmark the permalink.

6 Responses to Péter Pál Pach and Richárd Palincza: a Glimpse Beyond the Horizon

  1. kodlu says:

    Very nice. Is your statement of “much easier” simply referring to the fact
    that $5.709/6\approx 0.95$ for P6 while the corresponding ratio is more like $0.9$ for P4 and P5?

    • Gil Kalai says:

      Dear Kodlu, the statement “much easier” refers to the difficulty of proving an upper bound (or even exponentially-small upper bound). We have reasons to think that this is considerably harder for 4 compared to 3. And that it is as hard or harder for 5 compared to 4. And until the new result we could have thought that this is at least as hard for 6 compared to 4 and 5. I don’t think the difficulty of finding a proof is very related to the precis value of the upper bound.

      (I also edited the wording of the post to make the point clearer.)

  2. Spelling says:

    Tau –> Tao ……

    GK: thanks

  3. eitan bachmat says:

    Kind of reminds of the situation in topology, the following is quoted from the wikipedia entry on the h-cobordism theorem:
    “Before Smale proved this theorem, mathematicians became stuck while trying to understand manifolds of dimension 3 or 4, and assumed that the higher-dimensional cases were even harder. The h-cobordism theorem showed that (simply connected) manifolds of dimension at least 5 are much easier than those of dimension 3 or 4. The proof of the theorem depends on the “Whitney trick” of Hassler Whitney, which geometrically untangles homologically-tangled spheres of complementary dimension in a manifold of dimension >4. An informal reason why manifolds of dimension 3 or 4 are unusually hard is that the trick fails to work in lower dimensions, which have no room for untanglement.”

    • Gil Kalai says:

      Thanks for your comment, Eitan! This is a nice case to remember. Here the situation is somewhat different since AP of length 6 (over (Z/mZ)^n when 6|m) are ( in view of the new result) surprisingly easy (as easy as 3) but this does not say that AP of length larger than 6 are easy. (So we do not have statements about AP of length 10 over Z/10Z or of length 15 over Z/15Z reducing these problems to questions about smaller length AP). Regarding AP of length 4,5 and 6 the results give exponential improvement over (Z/mZ)^n when m is 0 mod 6. Now we know exponential improvement in (Z/6Z)^n for the cases of 4- 5- and 6- terms AP. Are 5-terms AP over (Z/5Z)^n and 4-term AP over (Z/4Z)^n so much harder? (And by “harder” I refer to how hard it is to prove things). BTW I plan a series of posts based on our open problem session so I’ll probably ask you more details about your probךem.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s