A Simple Combinatorial Proof of Szemerédi’s Theorem via Three Levels of Infinities

A simple combinatorial proof of Szemerédi’s theorem via three levels of infinities, Discrete Analysis 2023:15, 27 pp.

Szemerédi’s theorem, a cornerstone of additive combinatorics, states that for every $\delta>0$ and every positive integer $k$ there exists a positive integer $n$ such that every subset $A$ of $\{1,2,\dots,n\}$ of size at least $\delta n$ contains an arithmetic progression of length $k$. One of the reasons that the result has the status it has is that it has had a number of different proofs, and those proofs, or sometimes ingredients from those proofs, have subsequently led to many further interesting mathematical developments.

For example, an important ingredient of Szemerédi’s original proof, which he later generalized and which is now called the Szemerédi regularity lemma, was quickly recognised as a fundamental new tool for proving results about graphs and has had a huge number of applications. However, the proof as a whole has been less influential, because it is an extremely intricate combinatorial argument that few people have ever understood .

One exception to that is Terence Tao, who made the effort to understand it and wrote his own presentation of the argument in 2005. He wrote later (in blog posts referred to in the paper) that he was not entirely satisfied with his simplification, which still involved many parameters with delicate dependencies between them, and suggested that it might be possible to simplify the argument further by using nonstandard analysis, which often has the effect of replacing complicated quantitative arguments by cleaner qualitative ones. However, he did not himself carry out such a simplification, after coming to the conclusion that a single extension of the standard universe would not be enough and judging that it would be difficult to obtain an argument that was in any meaningful sense simpler than what he already had, though in an interesting twist his attempts led him to the discovery that Szemerédi’s proof did not in fact require the full strength of the regularity lemma, but could be carried out using a weaker version due to Frieze and Kannan (which comes with much better bounds).

This paper bites the bullet, recasts Szemerédi’s argument using nonstandard analysis, extending the standard universe not just once but three times. That is, roughly speaking, the author introduces level-1 numbers that are infinitely large relative to the standard universe, then level-2 numbers that are infinitely large relative to the level-1 universe, and finally level-3 numbers that are infinitely large relative to the level-2 universe. And this turns out to be sufficient to carry out all the epsilon-delta management that the proof requires.

Given that multiple extensions are required, the fact that one can get away with only three comes as a pleasant surprise, and while the paper is not in the end all that much shorter than Tao’s presentation of the standard proof, a significant proportion of it is spent developing the necessary nonstandard machinery. Thus, the “actual proof” of Szemerédi’s theorem is a simplification, but those unfamiliar with nonstandard analysis need to make a certain investment in order to get to the stage where they can follow it. The reader prepared to make that investment will be rewarded with not just a clean proof of Szemerédi’s theorem but also an understanding of a technique that has many other uses.