GILA 0: Roth’s proof of Roth’s theorem

I’m returning from my unplanned, unannounced hiatus from blogging with a series on the standard (Fourier-theoretic) proof of Roth’s theorem on arithmetic progressions, otherwise known as the k = 3 case of Szemeredi’s theorem. I’d like to start out by noting that there’s no shortage of good expositions on the topic; a quick Google search will turn up several. This series will differ from these expositions, however, in two key ways.

First, I’ll try to highlight the key ideas of the proof, rather than get bogged down in the calculations. Although, by the end of the series, we should have at least a sketch of a complete proof of Roth’s theorem, I want to make it easy to separate the real insights from the straightfoward calculational machinery. So I’ll likely present a high-level overview of the proof in the main body of these posts, with one or several appendices fleshing out the computations needed to ensure that the overview works.

Second, and more importantly, this is to be a piece of historical fiction. Although I don’t know how Roth came upon his original proof, he was a number theorist and an expert in Diophantine approximation, and was therefore familiar with things like Fourier analysis. I want to approach the problem from the perspective of a combinatorialist roughly contemporaneous with Roth, who’d be familiar with standard combinatorial methods but not with some of the more technical tools, and attempt to re-derive the proof from that viewpoint.

The real meat of the series will start this weekend (which is why this post is numbered 0), but since this is targeted toward a Generally Interested Lay Audience, I’d like to introduce a few topics which a layman might not be familiar with below the cut.

Throughout this series, I’ll assume familiarity with standard mathematical terminology and ideas such as modular arithmetic, complex arithmetic, basic notions of probability, etc.

So the first question: what, exactly, does Roth’s theorem say? Well, it says that every subset of the positive integers with positive density must contain a length-3 arithmetic progression. Let’s break that down: I assume you know what the positive integers are, and what “subset” means. Intuitively, density is also pretty easy: the density of a set $S$ is the limit as n goes to infinity of $\frac{S(n)}{n}$, where $S(n)$ is defined to be the number of elements of $S$ less than or equal to n. (For technical reasons, we often replace the limit in the above definition by the infimum, giving us what’s called the Schnirelmann density, but that’s not important for our purposes.) A k-term arithmetic progression is a set of the form $a, a+b, a+2b, \ldots, a+(k-1)b$; in other words, it’s a sequence in which every two consecutive terms have the same difference.

We’ll go ahead and note a few more basic facts that will be of importance. First, we can define a 3-term arithmetic progression by a single equation: $x, y, z$ is an arithmetic progression if and only if $x + z = 2y$. (This is easy to check.) Second: Fix a density $\delta > 0$. Then Roth’s theorem for that density is equivalent to the statement that, for some $N$, every subset of $\{1, 2, \ldots, N\}$ with at least $\delta N$ elements contains a three-term arithmetic progression. (As a matter of fact, we can further reduce it to the statement that there is a three-term arithmetic progression (mod N), but this is neither immediately obvious nor of immediate importance — although it will be important later on.)

Everything else I plan to cover as we get to it — but if you aren’t familiar with, say, the union bound or the discrete Fourier transform, it will likely pay off to review those topics ahead of time.

Tags: , , ,

5 Responses to “GILA 0: Roth’s proof of Roth’s theorem”

1. Anonymous Rex Says:

How is the finitary/infinitary equivalence following “Second: Fix a density ..” established?

• Harrison Says:

Hmm, now that I think about it, I’m not 100% sure — I think that standard compactness arguments are supposed to work, but I don’t know the standard compactness arguments! The important direction, though (the finitary implies infinitary direction) is obvious.

Yes, of course, the arithmetic progressions should be nontrivial (or else the theorem is trivial), so b > 0 is required.

2. Anonymous Rex Says:

Also, a trivial remark: you probably want your arithmetic progressions to be nontrivial.

3. Carnival of Mathematics #56 « Reasonable Deviations Says:

[…] Brown has a post on Roth’s proof of Roth’s theorem on arithmetic progressions from a combinatorial […]

4. Daniel Feller Says:

You made some really points there. I did a search on that topic additionally found most people will agree with your blog.