= Solution
We derive the <triangle removal lemma> from the permitted <Szemerédi regularity lemma>, then turn a <corner in an integer grid> into a <triangle in a graph>.
The <triangle removal lemma> says that for every $\eta>0$ there are $\rho>0$ and $N_0$ such that a <graph> on $N\geq N_0$ <vertices> with fewer than $\rho N^3$ <triangles in a graph> can be made <triangle-free> by deleting at most $\eta N^2$ <edges>. Here <triangles in a graph> are unordered triples of distinct <vertices>. We prove this consequence with the necessary quantitative dependence.
We may assume $0<\eta<1$. Put $d=\eta/4$, choose an integer $m_0\geq4/\eta$, and choose
$$
0<\varepsilon\leq\min\{\eta/8,d/4,1/4\}.
$$
Apply the <Szemerédi regularity lemma> to obtain an exceptional class $V_0$ of size at most $\varepsilon N$ and equal-sized classes $V_1,\ldots,V_k$ of size $L$, where $m_0\leq k\leq M$, and at most $\varepsilon k^2$ pairs are not <regular pairs of vertex sets>. The constant $M$ depends only on these chosen parameters. Delete all <edges> incident with $V_0$, all <edges> within a class, all <edges> between irregular pairs, and all <edges> between pairs whose <edge density of a bipartite graph> is less than $d$. The respective costs are at most
$$
\varepsilon N^2,\qquad \frac{N^2}{2m_0},\qquad \varepsilon N^2,\qquad \frac d2N^2.
$$
Their sum is at most $\eta N^2/2$, hence certainly at most $\eta N^2$.
If a <triangle in a graph> survives, it lies in three distinct classes whose three pairs are $\varepsilon$-<regular pairs of vertex sets> of <edge density of a bipartite graph> at least $d$ in the original <graph>. We now check the needed <regular triangle counting lemma>. In the first class all but at most $2\varepsilon L$ <vertices> have at least $(d-\varepsilon)L$ neighbours in each of the other two classes; otherwise the definition of a <regular pair of vertex sets> would be violated. For each such <vertex> $v$, its two neighbour sets each have size at least $\varepsilon L$, so their mutual <edge density of a bipartite graph> is at least $d-\varepsilon$. It follows that the original three classes contain at least
$$
(1-2\varepsilon)(d-\varepsilon)^3L^3\geq\frac{d^3}{8}L^3
$$
<triangles in a graph>. The elementary lower bound holds because $\varepsilon\leq1/4$ and $\varepsilon\leq d/4$. Also $L=(N-|V_0|)/k\geq N/(2M)$. Thus a surviving <triangle in a graph> implies at least $d^3N^3/(64M^3)$ original <triangles in a graph>. Set $\rho=d^3/(128M^3)$ and take $N_0$ large enough for the <Szemerédi regularity lemma>. Fewer than $\rho N^3$ original <triangles in a graph> force the cleaned <graph> to be <triangle-free>, proving the <triangle removal lemma>.
Now suppose $0<\delta\leq1$ and $A\subseteq[n]^2$. Use the <tripartite graph encoding of a grid> to construct a <tripartite graph> with disjoint labelled classes
$$
X=[n],\qquad Y=[n],\qquad Z=[2n].
$$
For each $(a,b)\in A$, put in the three <edges> joining $a\in X$, $b\in Y$, and $a+b\in Z$. These yield $|A|$ canonical <triangles in a graph>. They are pairwise <edge-disjoint triangles>: an $XY$ <edge> determines $(a,b)$ directly, an $XZ$ <edge> determines $b=z-a$, and a $YZ$ <edge> determines $a=z-b$. Any deletion making the <graph> <triangle-free> must therefore remove at least $|A|$ <edges>.
On the other hand, an arbitrary <triangle in a graph> with labels $(x,y,z)$ gives three points of $A$:
$$
(x,y),\qquad(x,z-x),\qquad(z-y,y).
$$
Writing $d=z-x-y$, these are $(x,y),(x,y+d),(x+d,y)$. If $d\ne0$, they form the required <corner in an integer grid>. If there is no such <corner in an integer grid>, every <triangle in a graph> is canonical, and the total number is precisely $|A|\leq n^2$.
Apply the <triangle removal lemma> with $\eta=\delta/32$. The constructed <graph> has $N=4n$ <vertices>. For sufficiently large $n$, $N\geq N_0$ and
$$
n^2<\rho(4n)^3.
$$
In the absence of a <corner in an integer grid>, the <triangle removal lemma> would destroy all <triangles in a graph> by deleting at most
$$
\eta(4n)^2=\frac\delta2n^2<\delta n^2\leq|A|
$$
<edges>, contradicting the pairwise <edge-disjoint triangles>. \b[Every sufficiently large grid therefore has the asserted <corner in an integer grid> in every subset of positive fixed <density of a finite subset>.] For $\delta>1$ there is no eligible subset, so the assertion is vacuous. This proves the <corners theorem>, including the stipulated nonzero displacement; no positivity of $d$ was required.
Back to article page
