The Erdős-Szemerédi problem on sum set and product set
| dc.creator | Chang, Mei-Chu | |
| dc.date | 2004-02-17 | |
| dc.date.accessioned | 2026-07-07T05:05:32Z | |
| dc.date.available | 2026-07-07T05:05:32Z | |
| dc.description | The basic theme of this paper is the fact that if $A$ is a finite set of integers, then the sum and product sets cannot both be small. A precise formulation of this fact is Conjecture 1 below due to Erd\H os-Szemerédi [E-S]. (see also [El], [T], and [K-T] for related aspects.) Only much weaker results or very special cases of this conjecture are presently known. One approach consists of assuming the sum set $A + A$ small and then deriving that the product set $AA$ is large (using Freiman's structure theorem). (cf [N-T], [Na3].) We follow the reverse route and prove that if $|AA| < c|A|$, then $|A+A| > c^\prime |A|^2$ (see Theorem 1). A quantitative version of this phenomenon combined with Plünnecke type of inequality (due to Ruzsa) permit us to settle completely a related conjecture in [E-S] on the growth in $k$. If $$ g(k) \equiv \text{min}\{|A[1]| + |A\{1\}|\} $$ over all sets $A\subset \Bbb Z$ of cardinality $|A| = k$ and where $A[1]$ (respectively, $A\{1\}$) refers to the simple sum (resp., product) of elements of $A$. (See (0.6), (0.7).) It was conjectured in [E-S] that $g(k)$ grows faster than any power of $k$ for $k\to\infty$. We will prove here that $\ell n g(k)\sim\frac{(\ell n k)^2}{\ell n \ell n k}$ (see Theorem 2) which is the main result of this paper. | |
| dc.description | 19 pages published version | |
| dc.identifier | https://arxiv.org/abs/math/0402285 | |
| dc.identifier | http://arxiv.org/abs/math/0402285 | |
| dc.identifier | Ann. of Math. (2), Vol. 157 (2003), no. 3, 939--957 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/70197 | |
| dc.subject | Combinatorics | |
| dc.title | The Erdős-Szemerédi problem on sum set and product set | |
| dc.type | text |