= Triangle-removal proof of Roth theorem
Embed $A\subseteq[N]$ in the odd <cyclic group> $G=\mathbb Z/(2N+1)\mathbb Z$, so additive three-term relations in $A$ cannot wrap around. Form three copies of $G$, putting <edges> $x\!\sim\!y$ when $y-x\in A$, $y\!\sim\!z$ when $z-y\in A$, and $x\!\sim\!z$ when $(z-x)/2\in A$. A <triangle in a graph> encodes $a+b=2c$ in $A$. If $A$ has no nonconstant <arithmetic progression>, every <triangle in a graph> has $a=b=c$; there are exactly $|G||A|$ <triangles in a graph>, and they are edge-disjoint. Thus at least $|G||A|$ <edges> must be removed to eliminate them. For fixed positive <subset density> of $A$, this is a positive fraction of the squared <vertex> count, whereas the <triangle in a graph> count is only quadratic. The <triangle removal lemma> permits deletion of an arbitrarily small quadratic fraction when the cubic <triangle in a graph> <subset density> is sufficiently small. This contradiction establishes <Roth theorem on three-term arithmetic progressions>.
Back to article page
