15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think your displayed equation is wrong... $\endgroup$ – Nick Gill Jun 2 '14 at 16:21
  • 1
    $\begingroup$ 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. $\endgroup$ – Brendan Murphy Jun 2 '14 at 16:58
  • 3
    $\begingroup$ 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. $\endgroup$ – Brendan Murphy Jun 2 '14 at 17:02
7
$\begingroup$

(This is not really an answer, but I am new here so cannot comment).

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.

By the way, a small correction; in the proof, you are right to say that the sets are distinct, but it seems to me that the crucial property that you are really using is that the sets are disjoint.

$\endgroup$
  • $\begingroup$ I agree it would be quite nice if this (or a similar) argument could work on a different sum-product estimate, especially one that is dilation invariant. Also, thanks for the correction! $\endgroup$ – George Shakan Jun 5 '14 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.