Back to search

University of Waterloo

A survey of Roth's Theorem on progressions of length three

Abstract

dc:description.abstract

For any finite set B and a subset A⊆B, we define the density of A in B to be the value α=|A|/|B|. Roth's famous theorem, proven in 1953, states that there is a constant C>0, such that if A⊆{1,...,N} for a positive integer N and A has density α in {1,...,N} with α>C/loglog N, then A contains a non-trivial arithmetic progression of length three (3AP). The proof of this relies on the following dichotomy: either 1) A looks like a random set and the number of 3APs in A is close to the probabilistic expected value, or 2) A is more structured and consequently, there is a progression P of about length α√N on which A∩P has α(1+cα) for some c>0. If 1) occurs, then we are done. If 2) occurs, then we identify P with {1,...,|P|} and repeat the above argument, whereby the density increases at each iteration of the dichotomy. Due to the density increase in case 2), an argument of this type is called a density increment argument. The density increment is obtained by studying the Fourier transforms of the characterstic function of A and extracting a structure out of A. Improving the lower bound for α is still an active area of research and all improvements so far employ a density increment. Two of the most recent results are α>C(loglog N/log N)^{1/2} by Bourgain in 1999 and α>C(loglog N)^5/log N by Sanders in 2010. This thesis is a survey of progresses in Roth's theorem, with a focus on these last two results. Attention was given to unifying the language in which the results are discussed and simplifying the presentation.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2011

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Nishizawa, Yui

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/6406

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Nishizawa, Yui. A survey of Roth's Theorem on progressions of length three. University of Waterloo, 2011. http://hdl.handle.net/10012/6406