To cheer you up in difficult times 20: Ben Green presents super-polynomial lower bounds for off-diagonal van der Waerden numbers W(3,k)

What will be the next polymath project? click here for our post about it. 

New lower bounds for van der Waerden numbers by Ben Green

Abstract: We show that there is a red-blue colouring of [N] with no blue 3-term arithmetic progression and no red arithmetic progression of length e^{C(\log N)^{3/4}(\log \log N)^{1/4}}. Consequently, the two-colour van der Waerden number w(3,k) is bounded below by k^{b(k)}, where b(k)=c(\frac{\log k}{\log \log k})^{1/3}. Previously it had been speculated, supported by data, that w(3,k)=O(k^2).

The left side of the picture shows the world record holders for W(3,k). On the left Ben Green (LB) and in the centre Tomasz Schoen (UB). The pictures on the right shows protective mittens for people who make bold mathematical conjectures (see Igor Pak’s post

The two-colour van der Waerden number w(m,k) is the smallest  N such that however [N] = {1, . . . , N} is coloured blue and red, there is either a blue m-term arithmetic progression or a red k-term arithmetic progression. The celebrated theorem of van der Waerden implies that w(m, k) is finite.

The van der Waerden number w(m,k) is analogous to the Ramsey number R(m,k). Finding the behaviors of R(m,k) is an important problem in Ramsey theory and much attention is given to R(k,k) and of R(3,k). Similarly, understanding the values of W(m,k), and especially of W(k,k) and W(3,k)  are also  central problems in Ramsey theory. A big difference between van der Waerden number and Ramsey numbers is that there are density theorems for the existence of k-terms arithmetic progressions. (Roth’s theorem for k=3 and Szemeredi’s theorem for general k.) There are several important methods to derive those density theorems (including Fourier methods, ergodic methods, and Szemeredi-type regularity) and these methods, as far as I know, do not apply for ordinary Ramsey numbers. (But correct me if I am wrong here, and if I am right and you have some insights as to why ergodic methods or Fourier methods do not apply to “ordinary” Ramsey, please share.)

Green’s paper  studies the values of w(3,k). The best known upper bound is of Tomasz Schoen, w(3, k)<e^{k^{1-c}} for some constant c > 0. The best known lower bound until the new paper, was by Li and Shu: w(3, k) \gg (k/ log k)^2. (This result, as the earlier bound by Robertson, used a probabilistic argument and relied on Lovasz’s local lemma.)

Several people conjectured, also based on empirical data, that w(3,k) = O(k^2) but now Green proved a super-polynomial lower bound! This is amazing! Congratulations, Ben!

It is largely conjectured that the Behrend-type bounds give the correct quantitative behaviour for Roth’s theorem (and Szemeredi theorem). In rough terms what we see from Green’s example is that this might be true also for van der Waerden numbers.

The proof is rather involved and long, so, naturally, there is  little I can say about it, which only slightly exceeds the little I actually know about it. The overview and other fragments of the paper I looked at are very illuminating. Here are a few things that caught my eyes.

1) A word about Tomasz Schoen’s upper bound and important paper: A subexponential upper bound for van der Waerden numbers W(3,k).  Among other things Schoen’s proof relies on a lemma developed by Schoen for improved Roth bound. This relies on a structure theory of Bateman and Katz.  The paper gives a nice description of the state of the art regarding the diagonal values w(k,k). (Schoen’s upper bound on w(3,k) follows also from the more recent bound for Roth’s theorem by Bloom and Sisask.)

2) Among the people that speculated that w(3,k) behaves like k^2 is Ben Green himself. This is recorded in reference [9] of the paper. However, Green’s first reaction to this possibility was that it must be false. But he realized that some ideas for showing that it is false are themselves false.

3) Reference [9] in the paper is: B. J. Green, 100 open problems, manuscript, available on request. If you are curious about the list, request it!

4) New lower bounds in Ramsey theory are nor frequent. Thirteen years ago I described Elkin’s improvement to Behrend’s bound and a few days ago I mentioned Linial and Shraibman’s new lower bounds for the corner problem.  Green’s study started by looking at complements of 3-AP free sets. An example by Green and Julia Wolf (that followed Elkin’s result) turned out to be important for reaching some parts of Green’s strategy.

5) In some sense, something about the k^2 prediction is not entirely lost. The construction gives a sort of a multi-scale behaviour where in the rth scale the example’s cardinality is k^r.  (So all the empirical data comes from the r=2 regime.) Ben Green boldly suggests that the true values of w(3,k) might exhibit such multi-scale behaviour. He conjectures that the true value of w(3, k) is quasi-polynomial, namely it lies somewhere in between the bound given by his construction and  something like k^{c\log k} (which is Behrend-bound behaviour on the nose) .

6) Until Ben’s list of 100 problems becomes available to you, you may find interest in Francis Su’s 100 questions about mathematics for discussion and reflection.

7) In connection with Linial and Shraibman’s new lower bounds for the corner problem, let me mention that the best upper bound is by I.D. Shkredov. The paper is:  On a two-dimensional analog of Szemeredi’s Theorem in Abelian groups, Izvestiya of Russian Academy of Sciences, 73 (2009), 455–505.

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

2 Responses to To cheer you up in difficult times 20: Ben Green presents super-polynomial lower bounds for off-diagonal van der Waerden numbers W(3,k)

  1. davidellis2 says:

    Ben’s idea of considering (the pull-back, under an ergodic map of) a union of random translates of ellipsoidal annuli to ‘break’ all the long red APs, reminds me slightly of the Kindler-Rao-O’Donnell-Wigderson technique of taking a union of random translates of a ‘nice’ set in the torus T^d, to eliminate the topologically non-trivial cycles in the complement – https://www.cs.cmu.edu/~odonnell/papers/spherical-cubes-conference.pdf – also used by Alon in the discrete case – https://arxiv.org/abs/0809.3169 – though Ben’s proof has many other difficult and beautiful ingredients – from random matrix theory, Fourier analysis & number theory, of course…

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