February 17, 2004
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\'edi [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\"unnecke 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.
Similar papers 1
February 19, 2015
In this note it is established that, for any finite set $A$ of real numbers, there exist two elements $a,b \in A$ such that $$|(a+A)(b+A)| \gg \frac{|A|^2}{\log |A|}.$$ In particular, it follows that $|(A+A)(A+A)| \gg \frac{|A|^2}{\log |A|}$. The latter inequality had in fact already been established in an earlier work of the author and Rudnev (arXiv:1203.6237), which built upon the recent developments of Guth and Katz (arXiv:1011.4105) in their work on the Erd\H{o}s dist...
It was asked by E. Szemer\'edi if, for a finite set $A\subset\mathbb{Z}$, one can improve estimates for $\max\{|A+A|,|A\cdot A|\}$, under the constraint that all integers involved have a bounded number of prime factors -- that is, each $a\in A$ satisfies $\omega(a)\leq k$. In this paper, answer Szemer\'edi's question in the affirmative by showing that this maximum is of order $|A|^{\frac{5}{3}-o(1)}$ provided $k\leq (\log|A|)^{1-\epsilon}$ for some $\epsilon>0$. In fact, this...
June 5, 2018
The main result of this paper is the following: for all $b \in \mathbb Z$ there exists $k=k(b)$ such that \[ \max \{ |A^{(k)}|, |(A+u)^{(k)}| \} \geq |A|^b, \] for any finite $A \subset \mathbb Q$ and any non-zero $u \in \mathbb Q$. Here, $|A^{(k)}|$ denotes the $k$-fold product set $\{a_1\cdots a_k : a_1, \dots, a_k \in A \}$. Furthermore, our method of proof also gives the following $l_{\infty}$ sum-product estimate. For all $\gamma >0$ there exists a constant $C=C(\gamma...
March 19, 2015
We improve a result of Solymosi on sum-products in R, namely, we prove that max{|A+A|,|AA|}\gg |A|^{4/3+c}, where c>0 is an absolute constant. New lower bounds for sums of sets with small product set are found. Previous results are improved effectively for sets A from R with |AA| \le |A|^{4/3}.
January 1, 2022
We prove that the size of the product set of any finite arithmetic progression $\mathcal{A}\subset \mathbb{Z}$ satisfies \[|\mathcal A \cdot \mathcal A| \ge \frac{|\mathcal A|^2}{(\log |\mathcal A|)^{2\theta +o(1)} } ,\] where $2\theta=1-(1+\log\log 2)/(\log 2)$ is the constant appearing in the celebrated Erd\H{o}s multiplication table problem. This confirms a conjecture of Elekes and Ruzsa from about two decades ago. If instead $\mathcal{A}$ is relaxed to be a subset of ...
September 3, 2003
We prove the following theorem: for all positive integers $b$ there exists a positive integer $k$, such that for every finite set $A$ of integers with cardinality $|A| > 1$, we have either $$ |A + ... + A| \geq |A|^b$$ or $$ |A \cdot ... \cdot A| \geq |A|^b$$ where $A + ... + A$ and $A \cdot ... \cdot A$ are the collections of $k$-fold sums and products of elements of $A$ respectively. This is progress towards a conjecture of Erd\"os and Szemer\'edi on sum and product sets.
May 1, 2009
In their seminal paper from 1983, Erd\H{o}s and Szemer\'edi showed that any $n$ distinct integers induce either $n^{1+\epsilon}$ distinct sums of pairs or that many distinct products, and conjectured a lower bound of $n^{2-o(1)}$. They further proposed a generalization of this problem, in which the sums and products are taken along the edges of a given graph $G$ on $n$ labeled vertices. They conjectured a version of the sum-product theorem for general graphs that have at leas...
December 1, 2017
We prove new results on additive properties of finite sets $A$ with small multiplicative doubling $|AA|\leq M|A|$ in the category of real/complex sets as well as multiplicative subgroups in the prime residue field. The improvements are based on new combinatorial lemmata, which may be of independent interest. Our main results are the inequality $$ |A-A|^3|AA|^5 \gtrsim |A|^{10}, $$ over the reals, "redistributing" the exponents in the textbook Elekes sum-product inequality a...
March 28, 2017
This is a sequel to the paper arXiv:1312.6438 by the same authors. In this sequel, we quantitatively improve several of the main results of arXiv:1312.6438, and build on the methods therein. The main new results is that, for any finite set $A \subset \mathbb R$, there exists $a \in A$ such that $|A(A+a)| \gtrsim |A|^{\frac{3}{2}+\frac{1}{186}}$. We give improved bounds for the cardinalities of $A(A+A)$ and $A(A-A)$. Also, we prove that $|\{(a_1+a_2+a_3+a_4)^2+\log a_5 : a_i...
February 10, 2016
We improve a previous sum--products estimates in R, namely, we obtain that max{|A+A|,|AA|} \gg |A|^{4/3+c}, where c any number less than 5/9813. New lower bounds for sums of sets with small the product set are found. Also we prove some pure energy sum--products results, improving a result of Balog and Wooley, in particular.