4.3 Roth's theorem and its proof

Roth's theorem is a game-changer in arithmetic progressions. It says that if you have a bunch of integers that make up a decent chunk of all integers, you'll always find three numbers in a row with the same spacing between them.

This theorem connects the dots between how dense a set is and the patterns it contains. It's like saying if you have enough sprinkles on a cake, you're bound to find some that line up perfectly, no matter how randomly you tossed them on.

Roth's Theorem on Arithmetic Progressions

Statement and Interpretation

• Roth's theorem states any subset of integers with positive upper density contains infinitely many arithmetic progressions of length 3
  • Upper density of set A of integers defined as $\limsup_{n \to \infty} \frac{|A \cap [1, n]|}{n}$, where $|A \cap [1, n]|$ denotes number of elements of A in interval $[1, n]$
  • Arithmetic progression of length 3 is sequence of form $(a, a + d, a + 2d)$, where $a$ and $d$ are integers, and $d \neq 0$ (e.g., $(3, 7, 11)$ or $(5, 2, -1)$)
• Roth's theorem implies any sufficiently dense subset of integers must contain many evenly spaced triples of elements
  • For example, if a set contains at least 1% of all positive integers, it must contain infinitely many triples of the form $(a, a+d, a+2d)$

Density and Structure

• Roth's theorem establishes strong connection between density of a set and existence of arithmetic structure within it
  • Higher density sets are guaranteed to have more arithmetic progressions
  • Sets with zero upper density may not contain any arithmetic progressions
• Theorem highlights interplay between global density of a set (measured by upper density) and local arithmetic structure (presence of evenly spaced elements)
  • Dense subsets of integers cannot avoid having regular patterns, even if the set is constructed in an irregular or random manner

Proof of Roth's Theorem

Density Increment Argument

• Proof of Roth's theorem relies on density increment argument, which iteratively increases density of set A on a subprogression of integers
  • Density increment lemma: If A does not contain many 3-term arithmetic progressions, then there exists a long arithmetic progression on which A has significantly higher density than its global density
  • Iteratively apply density increment lemma until density of A on a subprogression exceeds 1, leading to a contradiction
• Key idea: If A is dense but does not contain many arithmetic progressions, then it must be "concentrated" on a smaller subprogression where its density is even higher

Fourier-Analytic Techniques

• Define function $f(n)$ as indicator function of set A, i.e., $f(n) = 1$ if $n \in A$ and $f(n) = 0$ otherwise
• Apply Hardy-Littlewood circle method to express number of 3-term arithmetic progressions in A in terms of Fourier coefficients of $f$
  • Fourier coefficients measure how well $f$ correlates with exponential functions $e^{2\pi i n x}$ for different frequencies $x$
• Show if A does not contain many 3-term arithmetic progressions, then Fourier coefficients of $f$ must be small on average
  • Smallness of Fourier coefficients implies $f$ is "pseudorandom" and does not correlate well with structured functions
• Use Fourier-analytic techniques to locate a subprogression on which $f$ has large correlation with an exponential function, leading to a density increment

Significance of Roth's Theorem

Generalizations and Extensions

• Roth's theorem has inspired numerous generalizations and extensions in additive combinatorics
  • Szemerédi's theorem: Any set of integers with positive upper density contains arithmetic progressions of arbitrary length (generalization of Roth's theorem to longer progressions)
  • Green-Tao theorem: The set of prime numbers contains arbitrarily long arithmetic progressions (application of Szemerédi's theorem to the primes)
• Techniques used in the proof of Roth's theorem, such as the density increment argument and Fourier-analytic methods, have become essential tools in modern additive combinatorics
  • These techniques have been adapted and refined to prove many other important results in the field

Interdisciplinary Connections

• Roth's theorem has applications in various areas of mathematics beyond additive combinatorics
  • Number theory: Studying patterns and structures in subsets of integers, such as the distribution of prime numbers or the behavior of arithmetic functions
  • Ergodic theory: Analyzing the statistical properties of measure-preserving dynamical systems and their connections to combinatorial problems
  • Theoretical computer science: Investigating the computational complexity of finding patterns in dense graphs or subsets of the integers
• The interdisciplinary nature of Roth's theorem highlights the deep connections between different branches of mathematics and the unifying role of additive combinatorics

Applications of Roth's Theorem

Proving Structural Results

• Use the contrapositive of Roth's theorem to prove certain sets must have zero upper density by showing they do not contain 3-term arithmetic progressions
  • Example: The set of perfect squares $\{1, 4, 9, 16, \ldots\}$ has zero upper density because it does not contain any 3-term arithmetic progressions
• Combine Roth's theorem with other tools from additive combinatorics to derive stronger structural results about dense sets
  • Freiman-Ruzsa theorem: If a set $A$ has small doubling (i.e., $|A+A| \leq C|A|$ for some constant $C$), then $A$ is contained in a generalized arithmetic progression of bounded dimension
  • Balog-Szemerédi-Gowers theorem: If a set $A$ has many additive quadruples (i.e., solutions to $a+b=c+d$ with $a,b,c,d \in A$), then $A$ contains a large subset with small doubling

Solving Arithmetic Problems

• Apply Roth's theorem to solve problems related to finding patterns in subsets of the integers or analyzing the behavior of arithmetic functions
  • Example: Prove that any subset of the integers with positive density must contain two elements whose sum is a perfect square
  • Example: Show that for any irrational number $\alpha$, the set $\{\lfloor n\alpha \rfloor : n \in \mathbb{N}\}$ contains infinitely many 3-term arithmetic progressions
• Use Roth's theorem in conjunction with other number-theoretic tools to study the distribution of prime numbers or the properties of specific arithmetic sequences
  • Example: Prove that any sufficiently large subset of the primes must contain a 3-term arithmetic progression (a special case of the Green-Tao theorem)