, ,

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 | \leq C | A |,

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

A .

The sumset of

A

along

G

A +_{G} A = {a + b : a, b \in A and (a, b) \in E (G)} .

Theorem 1. For every

c, K, k > 0

there is a threshold

n_{0} = n_{0} (c, K, k)

such that if

| A | = n \geq n_{0}

| A +_{G} A | \leq K | A |

, and

| E (G) | \geq 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} (c)

and a positive

δ = δ (c)

such that, for any set of

n \geq n_{0}

lines

L

and any set of

m \geq c n^{2}

points

P

, if every point is incident to three lines, then there are at least

δ 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

δ n^{3}

triangles, where

δ

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.

□

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 \geq 2

, there is a threshold

n_{0} = n_{0} (c, d)

and a positive

δ = δ (c, d)

such that, for any set of

n \geq n_{0}

hyperplanes

L

and any set of

m \geq c n^{d}

points

P

, if every point is incident to

d + 1

hyperplanes, then there are at least

δ 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

A .

We define the difference-set of

A

along

G

A -_{G} A = {a - b : a, b \in A and (a, b) \in E (G)} .

Lemma 3. For every

ε, c, K > 0

there is a number

D = D (ε, c, K)

such that if

| A +_{G} A | \leq K | A |

and

| E (G) | \geq c | A |^{2}

, then there is a graph

G^{'} \subset G

such that

| E (G^{'}) | \geq (1 - ε) | E (G) |

and

| A -_{G^{'}} A | \leq D | A |

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 (G) .

By Lemma 1, the number of triangles in this arrangement is

δ 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

α n

triangles. Selecting

α = \frac{δ (ε c)}{ε c}

, where

δ (\cdot)

is the function from Lemma 1, all but at most

ε c n^{2}

points of

P

are popular.

t \in A - A

is popular if

| {(a, b) : a - b = t; a, b \in A} | \geq α n .

The number of popular

t

s is at most

D n

, where

D

depends on

α

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

α n

triangles.

Therefore

p

is incident to a line

x - y = t

, where

t

is popular, because this line contains at least

α n

“fourth” vertices of squares with

p

□

Proof of Theorem 1, case

k = 3 .

Let us apply Lemma 1 to the pointset

P^{'}

defined by

(a, b) \in P^{'}

iff

(a, b) \in E (G^{'})

and the lines are

y = a

for every

a \in A

x - y = t

for every

t \in A -_{G^{'}} A

, and

x + y = s

for every

s \in A +_{G} A .

By Theorem 2, if

| A |

is large enough, then there are triangles in the arrangement. The vertices of such triangles are vertices from

P^{'} \subset A \times A .

The vertical lines through the vertices form a 3-term arithmetic progression and therefore

A

contains

δ n^{2}

3-term arithmetic progressions, where

δ > 0

depends on

c

only.

□

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

| A | \geq 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 \dots \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¹ images of the simplex

S_{d}

whose vertices are listed below:

\begin{matrix} (0, 0, 0, 0, \dots, 0, 0) \end{matrix}

\begin{matrix} (1, 1, 0, 0, \dots, 0, 0) \end{matrix}

\begin{matrix} (2, 0, 1, 0, \dots, 0, 0) \end{matrix}

\begin{matrix} (3, 0, 0, 1, \dots, 0, 0) \end{matrix}

\begin{matrix} . . . \end{matrix}

\begin{matrix} (d - 1, 0, \dots, 1, 0) \end{matrix}

\begin{matrix} (d, 0, 0, 0, \dots, 0, 0) . \end{matrix}

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

\begin{matrix} {(0, 0, 0), (1, 1, 0), (2, 0, 1)} \end{matrix}

\begin{matrix} {(0, 0, 0), (1, 1, 0), (3, 0, 0)} \end{matrix}

\begin{matrix} {(0, 0, 0), (2, 0, 1), (3, 0, 0)} \end{matrix}

\begin{matrix} {(1, 1, 0), (2, 0, 1), (3, 0, 0)}, \end{matrix}

and the corresponding parallel planes in

{0, 1, 2} \times {- 1, 0, 1} \times {0, 1}

are the planes incident to the triples

\begin{matrix} {(0, 0, 0), (1, 1, 0), (2, 0, 1)} \end{matrix}

\begin{matrix} {(0, 0, 0), (1, 1, 0), (2, 0, 0)} \end{matrix}

\begin{matrix} {(0, 0, 0), (2, 0, 1), (2, 0, 0)} \end{matrix}

\begin{matrix} {(0, 0, 0), (1, - 1, 1), (2, - 1, 0)} . \end{matrix}

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

\begin{matrix} (1, 1, 0, 0, \dots, 0, 0) \end{matrix}

\begin{matrix} (2, 0, 1, 0, \dots, 0, 0) \end{matrix}

\begin{matrix} (3, 0, 0, 1, \dots, 0, 0) \end{matrix}

\begin{matrix} . . . \end{matrix}

\begin{matrix} (d - 1, 0, \dots, 1, 0) \end{matrix}

\begin{matrix} (d, 0, 0, 0, \dots, 0, 0), \end{matrix}

is parallel to the hyperplane through the vertices of

f - (1, 1, 0, 0, \dots, 0, 0),

\begin{matrix} (0, 0, 0, 0, \dots, 0, 0) \end{matrix}

\begin{matrix} (1, - 1, 1, 0, \dots, 0, 0) \end{matrix}

\begin{matrix} (2, - 1, 0, 1, \dots, 0, 0) \end{matrix}

\begin{matrix} . . . \end{matrix}

\begin{matrix} (d - 2, - 1, \dots, 1, 0) \end{matrix}

\begin{matrix} (d - 1, - 1, 0, 0, \dots, 0, 0) . \end{matrix}

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.

As the induction hypothesis, let us suppose that Theorem 3 is true for a

k \geq 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}

A_{d} = {\underset{︸}{A \times \dots \times A}}_{d}

is at least

c^{'} | A |^{d + 1}

(

c^{'}

depends on

c

only). Let us say that a point

p \in A_{d}

is popular if

p

is the holder of at least

α | A |

grids. If

p

is popular, then for any facet of

S_{d}

f

, the point

p

is the element of at least

α | A |

d

-tuples, similar and parallel to

f .

α

is small enough, then at least

γ | A |^{d}

points of

A_{d}

are popular, where

γ

depends on

c

and

α

only.

A hyperplane

H

β

-rich if it is incident to many points,

| H \cap A_{d} | \geq β | A |^{d - 1} .

For every facet of

S_{d}

f

, let us denote the set of

β

-rich hyperplanes which are parallel to

f

ℋ_{f} .

Lemma 4. For some choice of

β

, at least half of the popular points are incident to

d + 1

β

-rich hyperplanes, parallel to the facets of

S_{d} .

Suppose to the contrary that for a facet

f

, more than

\frac{γ}{2 d} | A |^{d}

popular points are not incident to hyperplanes of

ℋ_{f} .

Then more than

\begin{matrix} α | A | \frac{γ}{2 d} | A |^{d} = \frac{γ α}{2 d} | A |^{d + 1} \end{matrix}

(1)

d

-tuples, similar and parallel to

f

, are not covered by

ℋ_{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

ℒ_{1}, ℒ_{2}, \dots, ℒ_{m} .

A simple result of Elekes and Erdős [5] ,[4] implies that hyperplanes with few points cannot cover many

d

-tuples.

Theorem 4. [5] The number of homothetic copies of

f

L_{i}

is at most

c_{d} ℒ_{i}^{1 + 1 / (d - 1)}

, where

c_{d}

depends on

d

only.

The inequalities

\sum_{i = 1}^{m} ℒ_{i} \leq | A |^{d}, and ℒ_{i} \leq β | 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} ℒ_{i}^{1 + 1 / (d - 1)} \leq c_{d} \frac{| A |^{d}}{β | A |^{d - 1}} (β | A |^{d - 1})^{1 + 1 / (d - 1)} = c_{d} β^{1 / (d - 1)} | A |^{d + 1} .

If we compare this bound to (1), and choose

β

such that

\frac{γ α}{2 d} = c_{d} β^{1 / (d - 1)}

, then at least half of the popular points are covered by

d + 1

β

-rich hyperplanes parallel to the facets of

S_{d} .

□

Finally we can apply Lemma 2 with the pointset

P

of “well-covered” popular points of

A_{d}

and with the sets of hyperplanes

L = \cup_{f \subset S_{d}} ℋ_{f} .

The number of points is at least

\frac{γ α}{2} | A |^{d}

. For a given

f,

| ℋ_{f} | \leq \frac{| A |^{d}}{β | A |^{d - 1}} = | A | / β .

The number of hyperplanes in

L

is at most

(d + 1) | A | / β .

By Lemma 2, we have at least

δ^{'} | A |^{d + 1}

homothetic copies of

S_{d}

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

δ^{'} | A |^{2}

(k + 1)

-term arithmetic progressions in

A .

□

¹ 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

| A | = n

and

| A + B | \leq δ n

. Let

k \geq 1

and

l \geq 1 .

Then

| k B - l B | \leq δ^{k + l} n .

It follows from the inequality, that for any dimension

d

and

d

-dimensional integer vector

\vec{v} = (x_{1}, \dots, x_{d}), x_{i} \in Z

, there is a

c > 0

depending on

d, δ

and

\vec{v}

such that the following holds: If

| A + A | \leq δ | A |

, then

A_{d}

can be covered by

c | A |

hyperplanes with the same normal vector

\vec{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

A_{d}

, and the pointset of the arrangement is

A_{d} .

Then we do not have to deal with rich planes and popular points, and we can apply Lemma 2 directly.

References

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.

Department of Mathematics, University of British Columbia, Vancouver E-mail address : solymosi@math.ubc.ca

József Solymosi