Arithmetical progressions and the number of sums (Q1203463)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Arithmetical progressions and the number of sums
scientific article

    Statements

    Arithmetical progressions and the number of sums (English)
    0 references
    0 references
    0 references
    8 February 1993
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    addition of sets
    0 references
    Freiman's theory
    0 references
    arithmetical progression
    0 references
    0 references