Arithmetical progressions and the number of sums. (English) Zbl 0761.11005

Ruzsa, I. Z.

Period. Math. Hung. 25, No. 1, 105-111 (1992).

Let \(r_ k(n)\) denote the maximal number of integers that can be selected from the interval \([1,n]\) without including a \(k\) term arithmetical progression and write \(\omega_ k(n)=n/r_ k(n)\). Let \(A\) be a finite set of integers, \(| A|=n\) and assume that \(A\) does not contain any \(k\)-term arithmetical progression. It is proved that \[ | A+B|\geq\textstyle{{1\over 2}}\omega_ k(n)^{1/4} n^{1/4}| B|^{3/4} \] for every set \(B\), in particular \(| A+A|\geq{1\over 2}\omega_ k(n)^{1/4}n\), \(| A- A|\geq{1\over 2}\omega_ k(n)^{1/4}n\).
It is known that \(\omega_ 3(n)\gg(\log n)^ c\) with a positive constant \(c\) (Heath-Brown, Szemerédi). Applying this estimate we obtain that \[ | A+A|\geq n(\log n)^ c, \qquad | A-A|\geq n(\log n)^ c \] for \(n>n_ 0\), whenever \(A\) does not contain any 3-term arithmetical progression with a positive absolute constant \(c\). This is an effective version of a result of G. A. Freiman [Foundations of a structural theory of set addition (Kazan 1966; Zbl 0203.353); English transl. (1973)]. The proof is completely different from Freiman’s but uses his fundamental concept of isomorphism.

Reviewer: I.Z.Ruzsa (Budapest)

MSC:

11B25	Arithmetic progressions
11B50	Sequences (mod \(m\))
11B75	Other combinatorial number theory

Keywords:

addition of sets; Freiman’s theory; arithmetical progression

Citations:

Zbl 0203.353; Zbl 0271.10044

References:

[1]	G. A. Freiman, (1966),Foundations of a Structural Theory of Set Addition (in Russian), Kazan Gos. Ped. Inst., Kazan.
[2]	G. A. Freiman, (1973),Foundations of a Structural Theory of Set Addition, Translation of Mathematical Monographs Vol. 37, Amer. Math. Soc., Providence, R. I., USA. · Zbl 0271.10044
[3]	D. R. Heath-Brown, (1987), Integer sets containing no arithmetic progressions,J. London Math. Soc. 35, 385–394. · Zbl 0589.10062 · doi:10.1112/jlms/s2-35.3.385
[4]	H. Plünnecke, (1970), Eine zahlentheoretische Anwendung der Graphtheorie,J. Reine Angew. Math. 243, 171–183. · Zbl 0199.36701 · doi:10.1515/crll.1970.243.171
[5]	H. Plünnecke, (1970), Eine zahlentheoretische Anwendung der Graphtheorie,J. Reine Angew. Math. 243, 171–183. · Zbl 0199.36701 · doi:10.1515/crll.1970.243.171
[6]	I. Z. Ruzsa, (1978), On the cardinality of A+A and A, in:Coll. Math. Soc. J. Bolyai 18, Combinatorics, Keszthely 1976, North-Holland-Bolyai Társulat, Budapest (1978), 933–938.
[7]	I. Z. Ruzsa (1989), An application of graph theory to additive number theory,Scientia, Ser A 3 97–109. · Zbl 0743.05052
[8]	E. Szemerédi, (1975), On sets of integers containing nok-elements in arithmetic progression,Acta Arithmetica 27, 299–345.
[9]	E. Szemerédi, (1990), Integer sets containing no arithmetic progressions,Acta Math. Acad. Sci. Hungar. 56, 155–158. · Zbl 0721.11007