Arithmetic progressions in sumsets

Imre Z. Ruzsa

Acta Arithmetica (1991)

  • Volume: 60, Issue: 2, page 191-202
  • ISSN: 0065-1036

Abstract

top
1. Introduction. Let A,B ⊂ [1,N] be sets of integers, |A|=|B|=cN. Bourgain [2] proved that A+B always contains an arithmetic progression of length e x p ( l o g N ) 1 / 3 - ε . Our aim is to show that this is not very far from the best possible. Theorem 1. Let ε be a positive number. For every prime p > p₀(ε) there is a symmetric set A of residues mod p such that |A| > (1/2-ε)p and A + A contains no arithmetic progression of length (1.1) e x p ( l o g p ) 2 / 3 + ε . A set of residues can be used to get a set of integers in an obvious way. Observe that the 1/2 in the theorem is optimal: if |A|>p/2, then A+A contains every residue. Acknowledgement. I profited much from discussions with E. Szemerédi; he directed my attention to this problem and to Bourgain’s paper.

How to cite

top

Imre Z. Ruzsa. "Arithmetic progressions in sumsets." Acta Arithmetica 60.2 (1991): 191-202. <http://eudml.org/doc/206433>.

@article{ImreZ1991,
abstract = {1. Introduction. Let A,B ⊂ [1,N] be sets of integers, |A|=|B|=cN. Bourgain [2] proved that A+B always contains an arithmetic progression of length $exp(logN)^\{1/3-ε\}$. Our aim is to show that this is not very far from the best possible. Theorem 1. Let ε be a positive number. For every prime p > p₀(ε) there is a symmetric set A of residues mod p such that |A| > (1/2-ε)p and A + A contains no arithmetic progression of length (1.1)$exp(logp)^\{2/3+ε\}$. A set of residues can be used to get a set of integers in an obvious way. Observe that the 1/2 in the theorem is optimal: if |A|>p/2, then A+A contains every residue. Acknowledgement. I profited much from discussions with E. Szemerédi; he directed my attention to this problem and to Bourgain’s paper. },
author = {Imre Z. Ruzsa},
journal = {Acta Arithmetica},
keywords = {addition of sets; exponential sums; arithmetic progression; upper bound},
language = {eng},
number = {2},
pages = {191-202},
title = {Arithmetic progressions in sumsets},
url = {http://eudml.org/doc/206433},
volume = {60},
year = {1991},
}

TY - JOUR
AU - Imre Z. Ruzsa
TI - Arithmetic progressions in sumsets
JO - Acta Arithmetica
PY - 1991
VL - 60
IS - 2
SP - 191
EP - 202
AB - 1. Introduction. Let A,B ⊂ [1,N] be sets of integers, |A|=|B|=cN. Bourgain [2] proved that A+B always contains an arithmetic progression of length $exp(logN)^{1/3-ε}$. Our aim is to show that this is not very far from the best possible. Theorem 1. Let ε be a positive number. For every prime p > p₀(ε) there is a symmetric set A of residues mod p such that |A| > (1/2-ε)p and A + A contains no arithmetic progression of length (1.1)$exp(logp)^{2/3+ε}$. A set of residues can be used to get a set of integers in an obvious way. Observe that the 1/2 in the theorem is optimal: if |A|>p/2, then A+A contains every residue. Acknowledgement. I profited much from discussions with E. Szemerédi; he directed my attention to this problem and to Bourgain’s paper.
LA - eng
KW - addition of sets; exponential sums; arithmetic progression; upper bound
UR - http://eudml.org/doc/206433
ER -

References

top
  1. [1] A. C. Berry, The accuracy of the Gaussian approximation to the sum of independent variables, Trans. Amer. Math. Soc. 49 (1941), 122-136. Zbl0025.34603
  2. [2] J. Bourgain, On arithmetic progressions in sums of sets of integers, in: A Tribute to Paul Erdős (A. Baker, B. Bollobás, A. Hajnal, eds.), Cambridge Univ. Press, Cambridge 1990, 105-109. Zbl0715.11006
  3. [3] C. G. Esseen, Fourier analysis of distribution functions. A mathematical study of the Laplace-Gaussian law, Acta Math. 77 (1945), 1-125. 
  4. [4] I. Z. Ruzsa, Essential components, Proc. London Math. Soc. 54 (1987), 38-56. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.