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

Chang, Mei-Chu

Ann. Math. (2) 157, No. 3, 939-957 (2003).

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\).

Reviewer: Imre Z. Ruzsa (Budapest)

MSC:

11B75

Other combinatorial number theory

Keywords:

sumset; product set

Citations:

Zbl 0526.10011