×

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

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.

MSC:

11B25 Arithmetic progressions
11B50 Sequences (mod \(m\))
11B75 Other combinatorial number theory
PDF BibTeX XML Cite
Full Text: DOI

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
[4] H. Plünnecke, (1970), Eine zahlentheoretische Anwendung der Graphtheorie,J. Reine Angew. Math. 243, 171–183. · Zbl 0199.36701
[5] H. Plünnecke, (1970), Eine zahlentheoretische Anwendung der Graphtheorie,J. Reine Angew. Math. 243, 171–183. · Zbl 0199.36701
[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.