Arithmetic progressions in sumsets (Q5917477): Difference between revisions

Let \(C, D \subset [1,N]\) be sets of integers, \(|C|=\gamma N\), \(|D|=\delta N\). \textit{J. Bourgain} [A tribute to Paul Erdős, Cambridge Univ. Press, 105-109 (1990; Zbl 0715.11006)] proved that \(C+D\) contains an arithmetic progression of length \( \exp c ( \log N)^{1/3}\) with a positive constant \(c\) depending on \(\gamma \) and \(\delta \). The reviewer [Acta Arith. 60, 191-202 (1991; Zbl 0728.11009)] showed that the \(1/3\) in the exponent cannot be replaced by any number \(> 2/3\). Here the exponent in Bourgain's bound is improved to \(1/2\); the reviewer conjectures that this is the correct exponent. \textit{G. A. Freiman}, \textit{H. Halberstam} and the reviewer [J. Lond. Math. Soc. (2) 46, 193-201 (1992; Zbl 0768.11005)] gave a lower estimate for the length of an a.p. in a triple sum \(A+A+A\), which is also improved here. Finally, the methods of the paper are applied to derive a bound for the van der Waerden number \(W(2;3,k)\). This bound is essentially the same as what one can get from Bourgain's estimate for the density of sets without a three-term a.p.; it is of theoretical interest that such an estimate can be given without giving a bound in the density problem. The underlying result, from which the above ones are deduced, is a Ramsey-type result of the following strange kind. Let \(A\subset Z_N\). Either \(A\) contains a subset \(S\) such that all Fourier coefficients of \(S\) (except the constant term) are small, or the complement of \(A\) contains a long arithmetic progression.