- Abstract. We present an elementary proof that if $A$ is a finite set of numbers, and the sumset $A{+}_{G}A$ is small, $\left|A{+}_{G}A\right|\le c\left|A\right|$ , along a dense graph $G$ , then $A$ contains $k$ -term arithmetic progressions.

1 Introduction

A well known theorem of Szemerédi [15] states that every dense subset of integers contains long arithmetic progressions. A different, but somehow related result of Freiman [7] says that if the sumset of a finite set of numbers
$A$
is small, i.e.

$|A+A|\le C\left|A\right|,$
then
$A$
is the subset of a (not very large) generalized arithmetic progression. Balog and Szemerédi proved in [1] that a similar structural statement holds under weaker assumptions. (For correct statements and details, see [9] ). As a corollary of their result, Freiman's theorem, and Szemerédi's theorem about
$k$
-term arithmetic progressions, Balog and Szemerédi proved Theorem 1 below. The goal of this paper is to present a simple, purely combinatorial proof of this assertion.

Let
$A$
be a set of numbers and
$G$
be a graph such that the vertex set of
$G$
is
$A.$
The sumset of
$A$
along
$G$
is
$$A{+}_{G}A=\{a+b:a,b\in A\text{and}(a,b)\in E(G\left)\right\}.$$

Theorem 1.
For every
$c,K,k>0$
there is a threshold
${n}_{0}={n}_{0}(c,K,k)$
such that if
$\left|A\right|=n\ge {n}_{0}$
,
$\left|A{+}_{G}A\right|\le K\left|A\right|$
, and
$\left|E\right(G\left)\right|\ge c{n}^{2}$
, then
$A$
contains a
$k$
-term arithmetic progression.

2 Lines and hyperplanes

There are arrangements of
$n$
lines on the Euclidean plane such that the maximum number of points incident with at least three lines is
$\frac{{n}^{2}}{6}.$
Not much is known about the structure of arrangements where the number of such points is close to the maximum, say
$c{n}^{2}$
, where
$c$
is a positive constant. Nevertheless, the following is true.

Lemma 1.
For every
$c>0$
there is a threshold
${n}_{0}={n}_{0}\left(c\right)$
and a positive
$\delta =\delta \left(c\right)$
such that, for any set of
$n\ge {n}_{0}$
lines
$L$
and any set of
$m\ge c{n}^{2}$
points
$P$
, if every point is incident to three lines, then there are at least
$\delta {n}^{3}$
triangles in the arrangement. (A triangle is a set of three distinct points from
$P$
such that any two are incident to a line from
$L.$
)

Proof. This lemma follows from the following theorem of Ruzsa and Szemerédi [13] .
Theorem 2.
[13] Let
$G$
be a graph on
$n$
vertices. If
$G$
is the union of
$c{n}^{2}$
edge-disjoint triangles, then
$G$
contains at least
$\delta {n}^{3}$
triangles, where
$\delta $
depends on
$c$
only.
To prove Lemma 1, let us construct a graph where
$L$
is the vertex set, and two vertices are adjacent if and only if the corresponding lines cross at a point of
$P$
.

This graph is the union of
$c{n}^{2}$
disjoint triangles, every point of
$P$
defines a unique triangle, so we can apply Theorem 2.
$\square $
The result above suffices to prove Theorem 1 for 3-term arithmetic progressions.

But for larger values of
$k$
, we need a generalization of Lemma 1.

Lemma 2.
For every
$c>0$
and
$d\ge 2$
, there is a threshold
${n}_{0}={n}_{0}(c,d)$
and a positive
$\delta =\delta (c,d)$
such that, for any set of
$n\ge {n}_{0}$
hyperplanes
$L$
and any set of
$m\ge c{n}^{d}$
points
$P$
, if every point is incident to
$d+1$
hyperplanes, then there are at least
$\delta {n}^{d+1}$
simplices in the arrangement.

(A simplex is a set of
$d+1$
distinct points from
$P$
such that any
$d$
are incident to a hyperplane from
$L.$
)

Lemma 2 follows from the Frankl-Rödl conjecture [6] , the generalization of Theorem 2. The
$d=3$
case was proved in [6] and the conjecture has been proved recently by Gowers [8] and independently by Nagle, Rödl, Schacht, and Skokan [2] ,[3] . For details, how Lemma 2 follows from the Frankl-Rödl conjecture, see [14] .
3 The $k=3$ case

Let
$A$
be a set of numbers and
$G$
be a graph such that the vertex set of
$G$
is
$A.$
We define the difference-set of
$A$
along
$G$
as
$$A{-}_{G}A=\{a-b:a,b\in A\text{and}(a,b)\in E(G\left)\right\}.$$

Lemma 3.
For every
$\epsilon ,c,K>0$
there is a number
$D=D(\epsilon ,c,K)$
such that if
$\left|A{+}_{G}A\right|\le K\left|A\right|$
and
$\left|E\right(G\left)\right|\ge c|A{|}^{2}$
, then there is a graph
${G}^{\prime}\subset G$
such that
$\left|E\right({G}^{\prime}\left)\right|\ge (1-\epsilon )\left|E\right(G\left)\right|$
and
$\left|A{-}_{{G}^{\prime}}A\right|\le D\left|A\right|$
.
Proof. Let us consider the arrangement of points given by a subset of the Cartesian product
$A\times A$
and the lines
$y=a$
,
$x=a$
for every
$a\in A$
, and
$x+y=t$
for every
$t\in A{+}_{G}A.$
The pointset
$P$
is defined by
$(a,b)\in P$
iff
$(a,b)\in E\left(G\right).$
By Lemma 1, the number of triangles in this arrangement is
$\delta {n}^{3}.$
The triangles here are right isosceles triangles. We say that a point in
$P$
is popular if the point is the right-angle vertex of at least
$\alpha n$
triangles. Selecting
$\alpha =\frac{\delta \left(\epsilon c\right)}{\epsilon c}$
, where
$\delta (\cdot )$
is the function from Lemma 1, all but at most
$\epsilon c{n}^{2}$
points of
$P$
are popular.

A
$t\in A-A$
is popular if
$\left|\right\{(a,b):a-b=t;a,b\in A\left\}\right|\ge \alpha n.$
The number of popular
$t$
s is at most
$Dn$
, where
$D$
depends on
$\alpha $
only.
$A\times A$
is a Cartesian product, therefore every triangle can be extended to a square adding one extra point from
$A\times A$
. Every popular point
$p$
is the right-angle vertex of at least
$\alpha n$
triangles.

Therefore
$p$
is incident to a line
$x-y=t$
, where
$t$
is popular, because this line contains at least
$\alpha n$
“fourth” vertices of squares with
$p$
.
$\square $
Proof of Theorem 1, case
$k=3.$
Let us apply Lemma 1 to the pointset
${P}^{\prime}$
defined by
$(a,b)\in {P}^{\prime}$
iff
$(a,b)\in E\left({G}^{\prime}\right)$
and the lines are
$y=a$
for every
$a\in A$
,
$x-y=t$
for every
$t\in A{-}_{{G}^{\prime}}A$
, and
$x+y=s$
for every
$s\in A{+}_{G}A.$
By Theorem 2, if
$\left|A\right|$
is large enough, then there are triangles in the arrangement. The vertices of such triangles are vertices from
${P}^{\prime}\subset A\times A.$
The vertical lines through the vertices form a 3-term arithmetic progression and therefore
$A$
contains
$\delta {n}^{2}$
3-term arithmetic progressions, where
$\delta >0$
depends on
$c$
only.
$\square $

4 The general, $k>3$ , case

Following the steps of the proof for
$k=3$
, we prove the general case by induction on
$k.$
We prove the following theorem, which was conjectured by Erdős and proved by Balog and Szemerédi in [1] . Theorem 3, together with the
$k=3$
case, gives a proof of Theorem 1.

Theorem 3.
For every
$c>0$
and
$k>3$
there is an
${n}_{0}$
such that, if
$A$
contains at least
$c|A{|}^{2}$
3-term arithmetic progressions and
$\left|A\right|\ge {n}_{0}$
, then
$A$
contains a
$k$
-term arithmetic progression.
Instead of triangles, we must consider simplices. Set
$k=d$
. In the
$d$
-dimensional space we show that
$A\times \cdots \times A$
, the
$d$
-fold Cartesian product of
$A$
, contains a simplex in which the vertices' first coordinates form a
$(d+1)$
-term arithmetic progression.

The simplices we are looking for are homothetic^{1 }
images of the simplex
${S}_{d}$
whose vertices are listed below:

An important property of
${S}_{d}$
is that its facets can be pushed into a “shorter” grid. The facets of
${S}_{d}$
are parallel to hyperplanes, defined by the origin
$(0,0,0,0,\dots ,0,0)$
, and some
$(d-1)$
-tuples of the grid
$$\{0,1,2,\dots ,d-1\}\times \{-1,0,1\}\times \{0,1{\}}^{d-2}.$$
For example, if
$d=3$
, then the facets are

and the corresponding parallel planes in
$$\{0,1,2\}\times \{-1,0,1\}\times \{0,1\}$$
are the planes incident to the triples

In general, if a facet of
${S}_{d}$
contains the origin and the “last point”
$(d,0,0,0,\dots ,0,0),$
then if we replace the later one by
$(d-1,0,0,0,\dots ,0,0)$
, the new
$d$
-tuples define the same hyperplane. The remaining facet
$f$
, given by

is parallel to the hyperplane through the vertices of
$f-(1,1,0,0,\dots ,0,0),$

In a homothetic copy of the grid
$${T}_{d}=\{0,1,2,\dots ,d-1\}\times \{-1,0,1\}\times \{0,1{\}}^{d-2},$$
the image of the origin is called the holder of the grid.

$$\begin{array}{c}(0,0,0,0,\dots ,0,0)\end{array}$$ |

$$\begin{array}{c}(1,1,0,0,\dots ,0,0)\end{array}$$ |

$$\begin{array}{c}(2,0,1,0,\dots ,0,0)\end{array}$$ |

$$\begin{array}{c}(3,0,0,1,\dots ,0,0)\end{array}$$ |

$$\begin{array}{c}...\end{array}$$ |

$$\begin{array}{c}(d-1,0,\dots ,1,0)\end{array}$$ |

$$\begin{array}{c}(d,0,0,0,\dots ,0,0).\end{array}$$ |

$$\begin{array}{c}\left\{\right(0,0,0),(1,1,0),(2,0,1\left)\right\}\end{array}$$ |

$$\begin{array}{c}\left\{\right(0,0,0),(1,1,0),(3,0,0\left)\right\}\end{array}$$ |

$$\begin{array}{c}\left\{\right(0,0,0),(2,0,1),(3,0,0\left)\right\}\end{array}$$ |

$$\begin{array}{c}\left\{\right(1,1,0),(2,0,1),(3,0,0\left)\right\},\end{array}$$ |

$$\begin{array}{c}\left\{\right(0,0,0),(1,1,0),(2,0,1\left)\right\}\end{array}$$ |

$$\begin{array}{c}\left\{\right(0,0,0),(1,1,0),(2,0,0\left)\right\}\end{array}$$ |

$$\begin{array}{c}\left\{\right(0,0,0),(2,0,1),(2,0,0\left)\right\}\end{array}$$ |

$$\begin{array}{c}\left\{\right(0,0,0),(1,-1,1),(2,-1,0\left)\right\}.\end{array}$$ |

$$\begin{array}{c}(1,1,0,0,\dots ,0,0)\end{array}$$ |

$$\begin{array}{c}(2,0,1,0,\dots ,0,0)\end{array}$$ |

$$\begin{array}{c}(3,0,0,1,\dots ,0,0)\end{array}$$ |

$$\begin{array}{c}...\end{array}$$ |

$$\begin{array}{c}(d-1,0,\dots ,1,0)\end{array}$$ |

$$\begin{array}{c}(d,0,0,0,\dots ,0,0),\end{array}$$ |

$$\begin{array}{c}(0,0,0,0,\dots ,0,0)\end{array}$$ |

$$\begin{array}{c}(1,-1,1,0,\dots ,0,0)\end{array}$$ |

$$\begin{array}{c}(2,-1,0,1,\dots ,0,0)\end{array}$$ |

$$\begin{array}{c}...\end{array}$$ |

$$\begin{array}{c}(d-2,-1,\dots ,1,0)\end{array}$$ |

$$\begin{array}{c}(d-1,-1,0,0,\dots ,0,0).\end{array}$$ |

As the induction hypothesis, let us suppose that Theorem 3 is true for a
$k\ge 3$
in a stronger form, providing that the number of
$k$
-term arithmetic progressions in
$A$
is at least
$c|A{|}^{2}.$
Then the number of distinct homothetic copies of
${T}_{d}$
in
${\mathbb{A}}_{d}={\underbrace{A\times \dots \times A}}_{d}$
is at least
${c}^{\prime}|A{|}^{d+1}$
(
${c}^{\prime}$
depends on
$c$
only). Let us say that a point
$p\in {\mathbb{A}}_{d}$
is popular if
$p$
is the holder of at least
$\alpha \left|A\right|$
grids. If
$p$
is popular, then for any facet of
${S}_{d}$
,
$f$
, the point
$p$
is the element of at least
$\alpha \left|A\right|$
$d$
-tuples, similar and parallel to
$f.$
If
$\alpha $
is small enough, then at least
$\gamma |A{|}^{d}$
points of
${\mathbb{A}}_{d}$
are popular, where
$\gamma $
depends on
$c$
and
$\alpha $
only.

A hyperplane
$H$
is
$\beta $
-rich if it is incident to many points,
$|H\cap {\mathbb{A}}_{d}|\ge \beta |A{|}^{d-1}.$
For every facet of
${S}_{d}$
,
$f$
, let us denote the set of
$\beta $
-rich hyperplanes which are parallel to
$f$
by
${\mathcal{\mathscr{H}}}_{f}.$

$d$
-tuples, similar and parallel to
$f$
, are not covered by
${\mathcal{\mathscr{H}}}_{f}.$
Let us denote the hyperplanes incident to the “uncovered”
$d$
-tuples by
${L}_{1},{L}_{2},\dots ,{L}_{m}$
, and the number of points on the hyperplanes by
${\mathcal{\mathcal{L}}}_{1},{\mathcal{\mathcal{L}}}_{2},\dots ,{\mathcal{\mathcal{L}}}_{m}.$
A simple result of Elekes and Erdős [5] ,[4] implies that hyperplanes with few points cannot cover many
$d$
-tuples.

Lemma 4.
For some choice of
$\beta $
, at least half of the popular points are incident to
$d+1$
$\beta $
-rich hyperplanes, parallel to the facets of
${S}_{d}.$

Suppose to the contrary that for a facet
$f$
, more than
$\frac{\gamma}{2d}|A{|}^{d}$
popular points are not incident to hyperplanes of
${\mathcal{\mathscr{H}}}_{f}.$
Then more than
$$\begin{array}{c}\alpha \left|A\right|\frac{\gamma}{2d}|A{|}^{d}=\frac{\gamma \alpha}{2d}|A{|}^{d+1}\end{array}$$ | (1) |

Theorem 4.
[5] The number of homothetic copies of
$f$
in
${L}_{i}$
is at most
${c}_{d}{\mathcal{\mathcal{L}}}_{i}^{1+1/(d-1)}$
, where
${c}_{d}$
depends on
$d$
only.
The inequalities
$${\sum}_{i=1}^{m}{\mathcal{\mathcal{L}}}_{i}\le |A{|}^{d},\text{and}{\mathcal{\mathcal{L}}}_{i}\le \beta |A{|}^{d-1}.$$
lead us to the proof of Lemma 4.

The number of
$d$
-tuples covered by
${L}_{i}$
s is at most
$${c}_{d}{\sum}_{i=1}^{m}{\mathcal{\mathcal{L}}}_{i}^{1+1/(d-1)}\le {c}_{d}\frac{|A{|}^{d}}{\beta |A{|}^{d-1}}\left(\beta \right|A{|}^{d-1}{)}^{1+1/(d-1)}={c}_{d}{\beta}^{1/(d-1)}|A{|}^{d+1}.$$
If we compare this bound to (1), and choose
$\beta $
such that
$\frac{\gamma \alpha}{2d}={c}_{d}{\beta}^{1/(d-1)}$
, then at least half of the popular points are covered by
$d+1$
$\beta $
-rich hyperplanes parallel to the facets of
${S}_{d}.$
$\square $
Finally we can apply Lemma 2 with the pointset
$P$
of “well-covered” popular points of
${\mathbb{A}}_{d}$
and with the sets of hyperplanes
$L={\cup}_{f\subset {S}_{d}}{\mathcal{\mathscr{H}}}_{f}.$
The number of points is at least
$\frac{\gamma \alpha}{2}|A{|}^{d}$
. For a given
$f,$
$\left|{\mathcal{\mathscr{H}}}_{f}\right|\le \frac{|A{|}^{d}}{\beta |A{|}^{d-1}}=\left|A\right|/\beta .$
The number of hyperplanes in
$L$
is at most
$(d+1)\left|A\right|/\beta .$
By Lemma 2, we have at least
${\delta}^{\prime}|A{|}^{d+1}$
homothetic copies of
${S}_{d}$
in
${\mathbb{A}}_{d}.$
Let us project them onto
${x}_{1}$
, the first coordinate axis. Every image is a
$(k+1)$
-term arithmetic progression, and the multiplicity of one image is at most
$|A{|}^{d-1}.$
Therefore there are at least
${\delta}^{\prime}|A{|}^{2}$
$(k+1)$
-term arithmetic progressions in
$A.$
$\square $

^{1 }
Here we say that two simplices are homothetic if the corresponding facets are parallel.

5 ${G}_{n}={K}_{n}$

When the full sumset
$A+A$
is small then it is easier to prove that
$A$
contains long arithmetic progressions. We can use the following Plünecke type inequality [10, 12, 9] .

Theorem 5.
Let
$A$
and
$B$
be finite subsets of an abelian group such that
$\left|A\right|=n$
and
$|A+B|\le \delta n$
. Let
$k\ge 1$
and
$l\ge 1.$
Then
$$|kB-lB|\le {\delta}^{k+l}n.$$

It follows from the inequality, that for any dimension
$d$
and
$d$
-dimensional integer vector
$\stackrel{\u20d7}{v}=({x}_{1},\dots ,{x}_{d}),{x}_{i}\in \mathbb{Z}$
, there is a
$c>0$
depending on
$d,\delta $
and
$\stackrel{\u20d7}{v}$
such that the following holds: If
$|A+A|\le \delta \left|A\right|$
, then
${\mathbb{A}}_{d}$
can be covered by
$c\left|A\right|$
hyperplanes with the same normal vector
$\stackrel{\u20d7}{v}$
. Using this, we can define our hyperplane-point arrangement, with the hyperplanes parallel to the facets of
${S}_{d}$
containing at least one point of
${\mathbb{A}}_{d}$
, and the pointset of the arrangement is
${\mathbb{A}}_{d}.$
Then we do not have to deal with rich planes and popular points, and we can apply Lemma 2 directly.
References
Department of Mathematics, University of British Columbia, Vancouver E-mail address : solymosi@math.ubc.ca

- A. Balog and E. Szemerédi, A statistical theorem of set addition, Combinatorica, 14 (1994), 263–268.
- B. Nagle, V. Rödl, and M. Schacht, The counting lemma for regular $k$ -uniform hypergraphs, manuscript.
- V. Rödl and J. Skokan, Regulariry lemma for $k$ -uniform hypergraphs, Random Structures Algorithms, (2004)
- Gy. Elekes, Sums versus products in number theory, algebra and Erdős geometry. in: Paul Erdős and his Mathematics. II, Budapest, Bolyai Society Mathematical Studies, 11. (2002), page 277.
- Gy. Elekes and P. Erdős, Similar configurations and pseudo grids, in Intuitive Geometry. Amsterdam: North-Holland, Coll. Math. Soc. János Bolyai, 63 (1994), 85–104.
- P. Frankl and V. Rödl, Extremal problems on set systems. Random Structures Algorithms 20 (2002), 131–164.
- G.A. Freiman, Foundations of Structural Theory of Set Addition, Translation of Mathematical Monographs vol. 37, Amer. Math. Soc., Providence, R.I., USA (1973).
- W.T. Gowers, Hypergraph Regularity and the multidimensional Szemerédi Theorem, manuscript
- M.B. Nathanson, Additive Number Theory. Inverse Problems and the Geometry of Sumsets. Graduate Texts in Mathematics 165 Springer 1996
- H. Plünecke, Eigenschaften und Abschätzungen von Wirkungsfunctionen, volume 22. Berichte der Gesellshaft für Mathematik und Datenverarbeitung, Bonn, 1969.
- K.F. Roth, On certain sets of integers, J.London Math. Soc. 28 (1953), 245–252.
- I.Z. Ruzsa, An application of graph theory to additive number theory. Scientica, ser. A, 3 (1989) 97–109.
- I.Z. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles. in: Colloquia Mathematica Societatis János Bolyai, 18. Combinatorics, Keszthely (Hungary), 1976, 939–945.
- J. Solymosi, A note on a question of Erdős and Graham, Combinatorics, Probability, and Computing 13 (2004)
- E. Szemerédi, On sets of integers containing no $k$ elements in arithmetic progression. Acta Arithmetica 27 (1975), 199–245.