Sunday, July 19, 2020

Erdos-Turan for k=3 is True!

(All of the math in this post is summarized (without proofs) in a writeup by Erik Metz and myself which you can find here. It is a pdf file so you can click on links in it to get to the papers it refers to. There have been posts on this topic by Gil Kalai and  Luca Trevisan. If you know of others then let me know so I can add them to this post.)

This is a sequel to A BREAKTHROUGH result on density and 3-AP's and Big news on W(3,r)!

For this post N is large, and all inequalites have a big-O or a big-Omega.

For this post [N] is {1,...,N}


r(N) be the least w such that if A is a subset of [N] and |A|  >  w, then A has a 3-AP.

There has been a long sequence of results getting smaller and smaller upper bounds on r(N).

The motivation for getting these results is that if r(N) is < N/(log N)^{1+\delta} with delta>0 then the following holds:

If sum_{x\in A} 1/x diverges then A has a 3-AP.

This is the k=3 case of one of the Erdos-Turan Conjectures.

Bloom and Sisack HAVE gotten N/(log N)^{1+delta} so they HAVE gotten ET k=3. Wow!

1) I am NOT surprised that its true.

2) I am SHOCKED and DELIGHTED that it was proven.  Shocked because the results leading up to it (see the write up referenced at the beginning of this post) seemed Zeno-like, approaching the result needed got but not getting there. Delighted because... uh, as the kids say, just cause.

I've heard that k=4 really is much harder (see my comments and Gil's response on his blog post, pointed to at the beginning of this post)  and it is true that there has been far less progress on that case (the write up I pointed to at the beginning of this post says what is known). Hence I will again be shocked if it is proven.  So, unlike The Who (see here) I CAN be fooled again. That's okay--- I will  be delighted. (ADDED LATER- there are more comments no Gil's website, from Thomas Bloom and Ben Green about what is likely to happen in the next 10 years.)

Erdos offered a prize of $3000 for a proof that A has, for all k, a k-AP.  The prize is now $5000. After Erdos passed away Ronald Graham became the Erdos-Bank and paid out the money when people solved a problem Erdos put a bounty on. What happens now? (If I have the facts wrong and/or if you know the answer, please leave a polite and enlightening comment.)


  1. The definition of r(N) has the inequality reversed - it should be:

    if A is a subset of [N] and |A| > r(N), then A has a 3-AP

  2. Also, this is excellent news! Thanks for sharing.

    1. (response to both comments)
      Thanks for correction, I have made it.

      Andy- At first I was surprised you didn't already know the result (since two other people blogged on it) but I will turn that around: How do you get most of your math news? If its from my blog you WILL get the latest breakthroughs in Ramsey theory, but might miss out on other fields.