# Sum and product estimate over integers, rationals, and reals

My question is the following: is finding a lower bound for $|A+A\cdot A|$ (as a function of $|A|$) where $A$ is any finite subset of the positive integers equivalent to finding the same lower bound when $A$ is allowed to be any finite subset of the positive rationals, or even if $A$ is allowed to be a subset of positive real numbers? I am doubtful, as in exercise 8.3.1 in Tao in Vu's book on additive combinatorics they say that it is open for the traditional sum-product conjecture of Erdős and Szemerédi whether or not the sum-product conjecture over the integers is equivalent to the same problem over the real numbers. I expect that this problem is at least as hard (interestingly, Erdős and Szemerédi only conjecture for the integers).

Note that if $A$ is a subset of the rationals and $q$ is the least common multiple of the elements of $A$, then letting $B = q \cdot A$, we have $|A+ A \cdot A| = |q \cdot B + B \cdot B|$, which does not yield a solution to the problem.

My question is motivated by the following (simple) observation.

Claim. Let $A = \{a_1 < \ldots < a_n\}$ be a finite subset of the positive integers. Then $$|A+A \cdot A| \geq |A|^2 + |A| - 1.$$

Proof. The sets $a_1 + a_n \cdot A , \ldots , a_n + a_n \cdot A$ are all disjoint, since they contain elements that are different modulo $a_n$. Also, we have not counted $a_1 + a_1 a_1 < \ldots < a_1 + a_{n-1} a_1$ which are also in $A + A \cdot A$.

This inequality is seen to be tight by considering $\{1, \ldots , n\}$. My first question is has anyone seen this before? I have not seen it in the literature. An application of incidence geometry (see Tao and Vu again, exercise 8.3.3 this time) gives that for $A$, $B$, and $C$ finite subsets of the positive real numbers one has $|A+B\cdot C| = \Theta(|A|^{1/2}|B|^{1/2}|C|^{1/2})$, which is the best result in this direction I know (up to a removal of the constant).

Update: After some discussion with Oliver, we found that a similar, slightly harder, proof gives $\sum_{a \in A} |A+ a \cdot A| = \Omega(|A|^3)$ when $A$ is a finite subset of the integers. The basic idea is to show $|A + a_j \cdot A| \geq (j+1)|A| - j$ which can be done by observing that $A$ must intersect at least $j$ residue classes modulo $a_j$ and a little more work from there.

• I think your displayed equation is wrong... – Nick Gill Jun 2 '14 at 16:21
• I haven't seen that exact equation before. I would say that the rational question is harder, since there is a (possible) obstruction to your argument: the first part of your argument follows from the fact that $a_n\not\in (A-A)/(A-A)$, which is true because the fractions in $(A-A)/(A-A)$ must have denominators of magnitude at least 1 and hence have smaller magnitude. On the other hand, if you believe the Erdos-Szemeredi conjecture then (at least for $1\in A$) you would expect $|A+A\cdot A|\gtrsim |A|^2$, so counterexamples might be hard to come by. – Brendan Murphy Jun 2 '14 at 16:58
• Also, I think your argument would work for any set of positive reals whose differences are always greater than 1 in magnitude, but then as you point out the problem isn't scale invariant so you get stuck. – Brendan Murphy Jun 2 '14 at 17:02

This is a nice argument. I was wondering about lower bounds for $|AA+A|$ in the case when $A\subset{\mathbb{R}}$, trying to get an improvement on the exponent $3/2$ that you mentioned above. I'm sure there are others who could make the same confession, but perhaps this simple argument had been overlooked because of the assumption that $A$ is a set of reals. At least I can say that I hadn't seen the argument before.
It's unusual to get such a big improvement for a sum-product type problem in $\mathbb{Z}$ (as opposed to $\mathbb{R}$). It would be interesting if the argument could be tweaked to get some different optimal sum-product type results for sets of integers (or indeed for sufficiently well-separated sets as Brendan suggested). Maybe the dual problem of lower bounds for $|A(A+A)|$ should be considered for this approach, although I don't think it works quite so nicely.