Arithmetic progressions in sumsets

Volume 60 / 1991

Imre Ruzsa Acta Arithmetica 60 (1991), 191-202 DOI: 10.4064/aa-60-2-191-202


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.


  • Imre Ruzsa

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image