Arithmetic progressions in sumsets

Imre Ruzsa¹

¹

Acta Arithmetica, Tome 60 (1991) no. 2, pp. 191-202

Résumé

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.

Détail

DOI : 10.4064/aa-60-2-191-202