The size of set of simple sums and products of k distinct integers exceeds k^d

Number theory 1 Minute

You need to know: The size |S| of set S (that is, the number of elements in it), sum \sum_{i=1}^k and product \prod_{i=1}^k notations.

Background: Let A=\{a_1, a_2, \dots, a_k\} be a set of k distinct integers, and let S(A) = \left\{\sum_{i=1}^k \epsilon_i a_i \,|\,\epsilon_i = 0 \text{ or } 1\right\} and \Pi(A) = \left\{\prod_{i=1}^k a_i^{\epsilon_i} \,|\,\epsilon_i = 0 \text{ or } 1\right\} be the set of all possible simple sums and products of elements of A, respectively. Let g(k) = \min\limits_{A:|A|=k}(|S(A)|+|\Pi(A)|).

The Theorem: On 27th November 2001, Mei-Chu Chang submitted to the Annals of Mathematics a paper in which she proved that for any \epsilon>0 there is a k_0=k_0(\epsilon) such that g(k) > k^{(1/2-\epsilon)\frac{\log k}{\log (\log k)}} for all k\geq k_0.

Short context: In 1983, Erdős and Szemerédi conjectured that the set of sums S(A) and set of products \Pi(A) cannot both be small. Specifically, they conjectured that g(k) grows faster than any polynomial in k, that is, for any d, there exists a constant k_0=k_0(d) such that g(k) > k^d for any k \geq k_0(d). The Theorem implies this conjecture and in fact provides a stronger lower bound on g(k). Because it is known that g(k) < k^{c\frac{\log k}{\log (\log k)}} for some constant c, the bound in the Theorem is the best possible up to the constant factor in the exponent.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 3.5 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment