## The Erdős-Szemerédi problem on sum set and product set.(English)Zbl 1055.11017

For a set of $$k$$ integers we form the $$2^k$$ formal subset sums and the $$2^k$$ formal subset product. Let $$g(k)$$ denote the minimum of the cardinality of the union of these two sets taken over all $$k$$-element sets of integers. The main result of the paper asserts that $$g(k)\gg \exp c( \log k)^2 / \log \log k$$, confirming a conjecture of P. Erdős and E. Szemerédi [On sums and products of integers, Studies in pure mathematics, Mem. of P. Turán, 213–218 (1983; Zbl 0526.10011)]. For the constant $$c$$ the author gives the value $$1/8-\varepsilon$$, and a method is outlined that leads to an improvement to $$1/2-\varepsilon$$. An example is quoted from the above Erdős-Szemerédi paper which shows that $$c$$ cannot exceed 1, thus the logarithmic order of magnitude of this quantity is known.
The most important new idea is contained in Proposition 9. Let $$A$$ be a finite set of positive integers, and let $$m$$ denote its multiplicative dimension (the affine dimension of the set $$\{ \log a: a\in A\}$$ over the field of rationals). For every trigonometric function $$f(x) = \sum _{a\in A} d_a e^{2\pi iax}$$ with coefficients $$d_a\geq 0$$ and for every positive integer $$h$$ we have $$\| f \| _{2h} \leq (2h^2-h)^{m/2} \| f\| _2$$. Another interesting consequence is is the following. If $$A$$ is a set of positive integers and the set of products of pairs satisfies $$| A^2| <\alpha | A$$, then the set of $$h$$-fold sums satisfies $$| hA| <c_h(\alpha )| A| ^h$$.

### MSC:

 11B75 Other combinatorial number theory

### Keywords:

sumset; product set

Zbl 0526.10011
Full Text: