arXiv:0704.0555v1  [math.NT]  4 Apr 2007
THE GRAHAM CONJECTURE IMPLIES THE ERDÖS-TURÁN
CONJECTURE
LIANGPAN LI
Abstract. Erdös and Turán once conjectured that any set A ⊂ N with
1/a = ∞ should contain infinitely many progressions of arbitrary length
k ≥ 3. For the two-dimensional case Graham conjectured that if B ⊂ N × N
satisfies
(x,y)∈B
x2 + y2
then for any s ≥ 2, B contains an s × s axes-parallel grid. In this paper
it is shown that if the Graham conjecture is true for some s ≥ 2, then the
Erdös-Turán conjecture is true for k = 2s− 1.
1. Introduction
One famous conjecture of Erdös and Turán [2] asserts that any set A ⊂ N with∑
a∈A 1/a = ∞ should contain infinitely many progressions of arbitrary length
k ≥ 3. There are two important progresses towards this direction due to Szemerédi
[7] and Green and Tao [5] respectively, which assert that if A has positive upper
density or A is the set of the prime numbers, then A contains infinitely many
progressions of arbitrary length.
If one considers the similar question in the two-dimensional plane, Graham [4]
conjectured that if B ⊂ N× N satisfies
(x,y)∈B
x2 + y2
then B contains the four vertices of an axes-parallel square. More generally, for
any s ≥ 2 it should be true that B contains an s× s axes-parallel grid. Furstenberg
and Katznelson [3] proved the two-dimensional Szemerédi theorem, that is, any set
B ⊂ N × N with positive upper density contains an s × s axes-parallel grid. In
another words, such a set B contains any finite pattern.
The purpose of this paper is to show that if the Graham conjecture is true, then
the Erdös-Turán conjecture is also true.
2. The Graham conjecture implies the Erdös-Turán conjecture
Suppose that the Erdös-Turán conjecture is false for k = 3. Then there exists a
A = {a1 < a2 < a3 < · · · } ⊂ N
Date: April 4, 2007.
2000 Mathematics Subject Classification. 11B25.
http://arxiv.org/abs/0704.0555v1
2 LIANGPAN LI
n∈N 1/an = ∞ such that A contains no arithmetic progression of length 3.
Define a set B ⊂ N× N by
(an +m,m) : n ∈ N,m ∈ N
(x,y)∈B
x2 + y2
(an +m)2 +m2
(an +m)2 +m2
(an + an)2 + a2n
In the sequel we indicate that B contains no square and argue it by contradiction.
This would mean that the Graham conjecture is false for s = 2. Suppose that for
some n,m, l ∈ N, B contains a square of the following form:
(an +m,m+ l), (an +m+ l,m+ l),
(an +m,m), (an +m+ l,m).
It follows easily from the construction of B that an − l, an, an + l ∈ A, which yields
a contradiction since A contains no arithmetic progression of length 3 according to
the initial assumption.
Similarly, if the Graham conjecture is true for some s ≥ 2, then the Erdös-Turán
conjecture is true for k = 2s− 1. The interested reader can easily provide a proof.
3. Concluding Remarks
Let r(k,N) be the maximal cardinality of a subset A of {1, 2, . . . , N} which is
free of k-term arithmetic progressions. Behrend [1] and Rankin [6] had shown that
r(k,N) ≥ N · exp(−c(logN)1/(k−1)).
Similarly, let r̃(s,N) be the maximal cardinality of a subset B of {1, 2, . . . , N}2
which is free of s× s axes-parallel grids. For any set A ⊂ {1, 2, . . . , N}, define
Θ(A) = {(a+m,m) : a ∈ A,m = 1, 2, . . . , N} ⊂ {1, 2, . . . , 2N}2.
Following the discussion in Section 2, one can easily deduce that if A is free of 2s−1
term of arithmetic progression, then Θ(A) is free of s× s axes-parallel grid. Hence
r̃(s, 2N) ≥ r(2s− 1, N) ·N
≥ N2 exp(−c(logN)1/(2s−2)).
We end this paper with a question. Does the Erdös-Turán conjecture imply the
Graham conjecture?
THE GRAHAM CONJECTURE IMPLIES THE ERDÖS-TURÁN CONJECTURE 3
References
[1] F.A. Behrend, On sets of integers which contain no three terms in arithmetic progression,
Proc. Nat. Aca. Sci. 32 (1946), 331–332.
[2] P. Erdös and P.Turán, On some sequences of integers, J. London Math. Soc. 11 (1936),
261–264.
[3] H. Furstenberg and Y. Katznelson, An ergodic Szemeredi theorem for commuting transfor-
mation, J. d’Analyse Math. 34 (1979), 275–291.
[4] R. Graham, Conjecture 8.4.6 in Discrete and Computational Geometry (J.E. Goodman and
J. O’Rourke, eds), CRC Press, Boca Raton, NY, p.11.
[5] B. Green and T. Tao, The primes contain arbitrarily long arithmetic progressions, to appear
in Ann. of Math.
[6] R.A. Rankin, Sets of integers containing not more than a given number of terms in arithmetic
progression, Proc. Roy. Soc. Edinburgh Sect A. 65 (1960/61), 332–344.
[7] E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta
Arith. 27 (1975), 299–345.
Department of Mathematics, Shanghai Jiaotong University, Shanghai 200240, Peo-
ple’s Republic of China
E-mail address: liliangpan@sjtu.edu.cn

  Erd\"{o}s and Tur\'{a}n once conjectured that any set $A\subset\mathbb{N}$
with $\sum_{a\in A}{1}/{a}=\infty$ should contain infinitely many progressions
of arbitrary length $k\geq3$. For the two-dimensional case Graham conjectured
that if $B\subset \mathbb{N}\times\mathbb{N}$ satisfies $$\sum\limits_{(x,y)\in
B}\frac{1}{x^2+y^2}=\infty,$$ then for any $s\geq2$, $B$ contains an $s\times
s$ axes-parallel grid. In this paper it is shown that if the Graham conjecture
is true for some $s\geq2$, then the Erd\"{o}s-Tur\'{a}n conjecture is true for
$k=2s-1$.

Introduction
One famous conjecture of Erdös and Turán [2] asserts that any set A ⊂ N with∑
a∈A 1/a = ∞ should contain infinitely many progressions of arbitrary length
k ≥ 3. There are two important progresses towards this direction due to Szemerédi
[7] and Green and Tao [5] respectively, which assert that if A has positive upper
density or A is the set of the prime numbers, then A contains infinitely many
progressions of arbitrary length.
If one considers the similar question in the two-dimensional plane, Graham [4]
conjectured that if B ⊂ N× N satisfies
(x,y)∈B
x2 + y2
then B contains the four vertices of an axes-parallel square. More generally, for
any s ≥ 2 it should be true that B contains an s× s axes-parallel grid. Furstenberg
and Katznelson [3] proved the two-dimensional Szemerédi theorem, that is, any set
B ⊂ N × N with positive upper density contains an s × s axes-parallel grid. In
another words, such a set B contains any finite pattern.
The purpose of this paper is to show that if the Graham conjecture is true, then
the Erdös-Turán conjecture is also true.
2. The Graham conjecture implies the Erdös-Turán conjecture
Suppose that the Erdös-Turán conjecture is false for k = 3. Then there exists a
A = {a1 < a2 < a3 < · · · } ⊂ N
Date: April 4, 2007.
2000 Mathematics Subject Classification. 11B25.
http://arxiv.org/abs/0704.0555v1
2 LIANGPAN LI
n∈N 1/an = ∞ such that A contains no arithmetic progression of length 3.
Define a set B ⊂ N× N by
(an +m,m) : n ∈ N,m ∈ N
(x,y)∈B
x2 + y2
(an +m)2 +m2
(an +m)2 +m2
(an + an)2 + a2n
In the sequel we indicate that B contains no square and argue it by contradiction.
This would mean that the Graham conjecture is false for s = 2. Suppose that for
some n,m, l ∈ N, B contains a square of the following form:
(an +m,m+ l), (an +m+ l,m+ l),
(an +m,m), (an +m+ l,m).
It follows easily from the construction of B that an − l, an, an + l ∈ A, which yields
a contradiction since A contains no arithmetic progression of length 3 according to
the initial assumption.
Similarly, if the Graham conjecture is true for some s ≥ 2, then the Erdös-Turán
conjecture is true for k = 2s− 1. The interested reader can easily provide a proof.
3. Concluding Remarks
Let r(k,N) be the maximal cardinality of a subset A of {1, 2, . . . , N} which is
free of k-term arithmetic progressions. Behrend [1] and Rankin [6] had shown that
r(k,N) ≥ N · exp(−c(logN)1/(k−1)).
Similarly, let r̃(s,N) be the maximal cardinality of a subset B of {1, 2, . . . , N}2
which is free of s× s axes-parallel grids. For any set A ⊂ {1, 2, . . . , N}, define
Θ(A) = {(a+m,m) : a ∈ A,m = 1, 2, . . . , N} ⊂ {1, 2, . . . , 2N}2.
Following the discussion in Section 2, one can easily deduce that if A is free of 2s−1
term of arithmetic progression, then Θ(A) is free of s× s axes-parallel grid. Hence
r̃(s, 2N) ≥ r(2s− 1, N) ·N
≥ N2 exp(−c(logN)1/(2s−2)).
We end this paper with a question. Does the Erdös-Turán conjecture imply the
Graham conjecture?
THE GRAHAM CONJECTURE IMPLIES THE ERDÖS-TURÁN CONJECTURE 3
References
[1] F.A. Behrend, On sets of integers which contain no three terms in arithmetic progression,
Proc. Nat. Aca. Sci. 32 (1946), 331–332.
[2] P. Erdös and P.Turán, On some sequences of integers, J. London Math. Soc. 11 (1936),
261–264.
[3] H. Furstenberg and Y. Katznelson, An ergodic Szemeredi theorem for commuting transfor-
mation, J. d’Analyse Math. 34 (1979), 275–291.
[4] R. Graham, Conjecture 8.4.6 in Discrete and Computational Geometry (J.E. Goodman and
J. O’Rourke, eds), CRC Press, Boca Raton, NY, p.11.
[5] B. Green and T. Tao, The primes contain arbitrarily long arithmetic progressions, to appear
in Ann. of Math.
[6] R.A. Rankin, Sets of integers containing not more than a given number of terms in arithmetic
progression, Proc. Roy. Soc. Edinburgh Sect A. 65 (1960/61), 332–344.
[7] E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta
Arith. 27 (1975), 299–345.
Department of Mathematics, Shanghai Jiaotong University, Shanghai 200240, Peo-
ple’s Republic of China
E-mail address: liliangpan@sjtu.edu.cn
