Arithmetic progressions in sumsets

• Autorzy: Imre Z. Ruzsa
• Języki publikacji: EN

Abstrakty

EN

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.

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Acta Arithmetica
• Rocznik: 1991-1992
• Tom: 60
• Numer: 2
• Strony: 191-202

Daty

wydano

1991

otrzymano

1991-01-30

Twórcy

autor

Imre Z. Ruzsa

• Mathematical Institute, Hungarian Academy of Sciences, Budapest, Pf. 127, H-1364 Hungary

Bibliografia

• [1] A. C. Berry, The accuracy of the Gaussian approximation to the sum of independent variables, Trans. Amer. Math. Soc. 49 (1941), 122-136.
• [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.
• [3] C. G. Esseen, Fourier analysis of distribution functions. A mathematical study of the Laplace-Gaussian law, Acta Math. 77 (1945), 1-125.
• [4] I. Z. Ruzsa, Essential components, Proc. London Math. Soc. 54 (1987), 38-56.