Arithmetical progressions and the number of sums (Q1203463): Difference between revisions

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 \textit{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.