101
$\begingroup$

Let $A$ be a finite set of real numbers. Is it always the case that $|AA+A| \geq |A+A|$?

My first instinct is that this is obviously true, and there is a one-line proof which I am foolishly overlooking. Can anyone provide one? Of course, any proof would be welcome! Any partial results would also be of interest.

$\endgroup$
  • 16
    $\begingroup$ Federico Poloni, $AA$ denotes the product set of $A$, and so $AA:=\{ab:a,b \in A\}$. The notation is standard in the field of sum-product estimates, but I can certainly see the ambiguity. The set you mention in your comment is sometimes denoted as $A^{(2)}$. $\endgroup$ – Oliver Roche-Newton Apr 27 '15 at 11:25
  • 7
    $\begingroup$ Is there even a case where $|aA+A|<|A+A|$ for $a\ne 0$? $\endgroup$ – Yaakov Baruch Apr 27 '15 at 13:10
  • 14
    $\begingroup$ The claim for subsets of the integers holds, and follows from this MO question: mathoverflow.net/questions/168844/… $\endgroup$ – Lucia Apr 27 '15 at 14:04
  • 6
    $\begingroup$ @YaakovBaruch the idea is good but at least for $a=-1$ there are examples. In fact this question, that is the question of sets with less differences than sums, got study in recent years. $\endgroup$ – user9072 Apr 27 '15 at 14:21
  • 6
    $\begingroup$ Antal Balog conjectured for $A \subset \mathbb{R}^+$, one has $|A+A \cdot A| \geq |A|^2$ in "A note on sum-product estimates" $\endgroup$ – George Shakan Apr 30 '15 at 12:25
52
$\begingroup$

If $p$ is an odd prime (EDIT: other than 5) for which $-1$ is a quadratic residue mod $p$, and $A$ is the set of non-zero quadratic non-residues mod $p$, then $A+A$ is all of ${\bf Z}/p{\bf Z}$, whilst $A+AA$ is ${\bf Z}/p{\bf Z} \backslash \{0\}$. So counterexamples exist in finite fields, which rules out some methods of proof (e.g. "Ruzsa calculus" by itself will be insufficient). Unfortunately, this example does not appear to be adaptable to the reals (for which $-1$ is certainly not a square, and for which there are no large multiplicative subgroups). Actually it looks difficult to build an example in the complex numbers (or any other characteristic zero field); I don't even see a way to construct an (EDIT: arbitrarily large) finite set $A$ obeying the weaker inequality $|A+AA| < \frac{|A| (|A|+1)}{2}$. One may indeed conjecture (in the spirit of the Erdos-Szemeredi sum-product conjecture) that one always has $|A+AA| \geq \frac{|A| (|A|+1)}{2}$ (EDIT: for sufficiently large $A$), but this is well beyond our current technology to prove. (EDIT: as noted in comments, there are small counterexamples obeying the weaker inequality, although they do not give counterexamples to the original inequality.)

$\endgroup$
  • $\begingroup$ A very interesting example. So, this tells us that any proof must take advantage of some property which holds for the reals but not for all finite fields. I wonder if the weaker conjecture that $|AA+A| \geq c|A+A|$, for some positive constant $c$, still holds in the finite field setting. $\endgroup$ – Oliver Roche-Newton Apr 28 '15 at 9:12
  • $\begingroup$ Interesting indeed. Ruzsa calculus can be improved slightly for torsion-free groups, e.g. Corollary 2.9 in Glasscock's thesis (people.math.osu.edu/glasscock.4/MSThesis.pdf) implies that a counterexample in such a group must have $|AA|<\frac{\sqrt{5}-1+o(1)}{2}|A+A|$. $\endgroup$ – GH from MO Apr 28 '15 at 10:31
  • $\begingroup$ It seems you need to exclude the case $p = 5$. $\endgroup$ – Stefan Kohl Apr 28 '15 at 10:52
  • $\begingroup$ If I'm not mistaken, a counterexample to your weaker inequality is $A = \{-1,0,1\}$. -- Maybe you rather meant to write $|A + AA| < \frac{|A|(|A|-1)}{2}$? $\endgroup$ – Stefan Kohl Apr 28 '15 at 10:59
  • $\begingroup$ Fair enough; I was implicitly thinking asymptotically in my answer, and have now edited it to clarify. But perhaps $\{-1,0,1\}$ is the only counterexample (this is about as close as one can get to being both closed under multiplication and addition, for a finite subset of the reals). $\endgroup$ – Terry Tao Apr 28 '15 at 16:53
17
$\begingroup$

Here is a small observation, generalizing Lucia's comment.

Proposition. If $A$ is a set of real numbers with minimal distance at least $1$, then $$|A+AA| \geq \frac{|A|(|A|-1)}{2}\geq |A+A|-|A|.$$

Proof. Let $r_m>\dots>r_1>0$ be the positive elements of $A$. Then the subsets $r_i+r_m A$ of $A+AA$ are pairwise disjoint, because $r_i+r_ma=r_j+r_ma'$ $(i\neq j)$ would imply $$ r_m\leq |r_m(a-a')|=|r_i-r_j|<r_m.$$ Hence $|A+AA| \geq m|A|$. Similarly, let $s_n<\dots<s_1<0$ be the negative elements of $A$. Then the subsets $s_i+s_n A$ of $A+AA$ are pairwise disjoint, because $s_i+s_na=s_j+s_na'$ $(i\neq j)$ would imply $$ |s_n|\leq |s_n(a-a')|=|s_i-s_j|<|s_n|.$$ Hence $|A+AA| \geq n|A|$. It follows that $$ |A+AA| \geq\max(m,n)|A|\geq\frac{m+n}{2}|A|\geq\frac{|A|-1}{2}|A|\geq |A+A|-|A|.$$

Remark. If $m\neq n$ and $0\not\in A$, then the last display improves to $$|A+AA| \geq\max(m,n)|A|\geq\frac{m+n+1}{2}|A|=\frac{|A|+1}{2}|A|\geq |A+A|.$$

$\endgroup$
  • 3
    $\begingroup$ This is also noted in the comments to the post Lucia mentioned. $\endgroup$ – Brendan Murphy Apr 27 '15 at 21:25
  • 5
    $\begingroup$ @BrendanMurphy: I see now your comment there, but my post gives more detail (e.g. the separation of positive and negative elements is not entirely trivial), so I leave it. On the other hand, I don't claim any originality here, and I thank for your comment! $\endgroup$ – GH from MO Apr 27 '15 at 21:27
  • 3
    $\begingroup$ @Suvrit you cannot scale easily as $AA$ and $A$ scales differently yet then you add them (so if you scale by $c$ you get $c^2 AA + cA$ so $c AA + A$ not $AA +A$). If one could scale one could just assume WLOG $1 \in A$ and thus $A \subset AA $. Done. $\endgroup$ – user9072 Apr 28 '15 at 13:16
  • 1
    $\begingroup$ @quid: excellent; thanks! I somehow ignored the $c^2$ on $AA$ --- and this highlights the crux... $\endgroup$ – Suvrit Apr 28 '15 at 14:30
  • 1
    $\begingroup$ @TheMaskedAvenger: Thanks for catching this, I updated my post accordingly. $\endgroup$ – GH from MO Apr 28 '15 at 19:50
14
$\begingroup$

I believe there is an "energy" version of the conjectural inequality $|A+AA| \geq |A+A|$ which may explain why it was intuitive that there should be an "easy" proof of that inequality. Namely:

Proposition Let $A$ be a finite collection of nonzero elements of a field $F$. Let $a_1,a_2,a_3,a'_1,a'_2,a'_3$ be chosen uniformly and independently from $A$. Then $$ {\mathbf P}( a_1 + a_2 a_3 = a'_1 + a'_2 a'_3 ) \leq {\mathbf P}( a_1 + a_2 = a'_1 + a'_2 ).$$

Informally, this asserts that $A+AA$ is "flatter" than $A+A$ in an $L^2$ sense, which leans toward $A+AA$ being larger in size than $A+A$, but does not imply it (as my counterexample in my other response shows).

The proof is basically Cauchy-Schwarz. If one defines $E(A,B;C,D)$ to be the number of quadruples $a \in A, b \in B, c \in C, d \in D$ with $a+b=c+d$, then two applications of Cauchy-Schwarz give $$ E(A,B;C,D) \leq E(A,A;A,A)^{1/4} E(B,B;B,B)^{1/4} E(C,C;C,C)^{1/4} E(D,D;D,D)^{1/4}$$ which imply in particular that $$ {\mathbf P}( a_1 + a_2 b = a'_1 + a'_2 c ) \leq {\mathbf P}( a_1 + a_2 = a'_1 + a'_2 )$$ for any non-zero deterministic $b,c$. Replacing $b,c$ by $a_3, a'_3$ and then taking expectations we obtain the claim.

$\endgroup$
  • $\begingroup$ Nice! Or, saying the same thing in a slightly different language, this proves that $|\{(a,b,c,d,e,f) \in A^6 : a+cb=d+ef\}| \leq |A|^2E^+(A)$, where $E^+(A)$ is the additive energy of $A$. $\endgroup$ – Oliver Roche-Newton Apr 30 '15 at 8:47
11
$\begingroup$

The corresponding thing in measure fails.

Let $A = [0,1/2]$. Then $A+A = [0,1]$ has measure $1$. And $AA = [0,1/4]$, so $AA+A = [0,3/4]$ has measure $3/4$.

But I did not manage to convert this to a finite counterexample.

$\endgroup$
  • 21
    $\begingroup$ With measures you can make sets "smaller" by multiplying its element with a number $<1$. $AA$ becomes scaled smaller twice. This doesn't happen in the discrete case. $\endgroup$ – j.p. Apr 27 '15 at 13:57
  • 2
    $\begingroup$ @j.p.: we are using real numbers, so $1/2$ can be an element of $A$. But you are right we would want $AA$ not merely to be half the size, but rather to have half the number of elements. $\endgroup$ – Gerald Edgar Apr 27 '15 at 14:01
  • 2
    $\begingroup$ Yes, I was referring with "size" (implicitly) to the number of elements in the discrete case. $\endgroup$ – j.p. Apr 27 '15 at 14:04
10
$\begingroup$

One interesting case is to take $A=\{(1+a)a^i:0\leq i< n\}$ for some $a>0$ and some $n$. Then $|AA|=2n-1$ (which I think is the minimum possible) and for generic $a$ we have $|A+A|=n(n+1)/2\sim n^2/2$ (which is maximal). Experimental calculations show that $|AA+A|\sim 2n^2$. This is much smaller than the naive guess of approximately $n^3$, but still bigger than $|A+A|$.

$\endgroup$
  • 2
    $\begingroup$ I'm not sure whether $|AA|=2n-1$ is minimum possible. For instance, if $A = \{ -1,0,1 \}$, then $AA = A$. Perhaps if you replace your set $A$ by $A \cup -A$ you also get interesting examples; I haven't verified this. $\endgroup$ – Tom De Medts Apr 27 '15 at 15:53
  • 1
    $\begingroup$ @TomDeMedts adding 0 adds 1 to element to both A and AA. Adding all negations doubles the number of elements of A and AA if A was strictly positive. First add negations, then add 0, for n elements in A', and 2n-3 elements in AA'. $\endgroup$ – Yakk Apr 27 '15 at 19:22
  • 5
    $\begingroup$ Another more obvious example for which $|AA+A| \ll |A|^2$ is the set $A=\{1,2,\dots,N\}$. Then $AA+A \subset \{1,N^2+N\}$. I think part of the difficulty in showing that $AA+A$ is always "large" comes from the fact that there are very different sets (i.e. both arithmetic and geometric progressions) for which $A+AA$ is relatively "small". $\endgroup$ – Oliver Roche-Newton Apr 28 '15 at 13:51
8
$\begingroup$

Here is another lower bound for $|A+a_nA|$, which is close to $|A|^2$ if the gaps between elements of $A$ are bounded independent of $|A|$. (This is getting somewhat off topic, although it seems that $|A+AA|\geq |A+A|$ might be true by coincidence in cases where $1\not\in A$.)

Let $A=\{a_1,\ldots,a_n\}$ with $0<a_1<\cdots<a_n$, and let $\delta=\min_{i\not=j}|a_i-a_j|$; WLOG $\delta<1$. Then I

Claim: that $$ |A+a_nA|\geq\frac{\delta}3 |A|^2. $$

Proof: Let $d=\lceil 1/\delta\rceil$ and let $g=a_n-a_1$. Fix $\lambda$ in $A$ and let $S_{\lambda}$ denote the number of solutions to $$ y_i=b-\lambda x_i $$ with $(x_i,y_i)\in A\times A$, labelling the $x_i$'s so that $x_1<\cdots<x_{S_{\lambda}}$.

Sub-claim: $S_{\lambda}\leq d\lceil g/\lambda\rceil+1$.

Proof: Since the minimum gap between consecutive $x_i$'s is $\delta$, we have $$ |x_{i+d}-x_i|\geq 1 $$ hence $$ |y_{i+d}-y_i| = \lambda|x_{i+d}-x_i|\geq \lambda. $$ If we let $k=d\lceil g/\lambda\rceil$, then $$ |y_{k+1}-y_1|\geq \lambda\lceil g/\lambda\rceil\geq g. $$ Since the maximum gap between any two elements of $A$ is $g$, it follows that $S_\lambda\leq k+1=d\lceil g/\lambda\rceil+1$.

End proof of sub-claim

Note that $S_{\lambda}$ is the number of ways to write $b=a+\lambda a'$ with $a,a'\in A$; this is typically denoted $r_{A+\lambda A}(b)$.

If we take $\lambda=a_n$, then we have $r_{A+\lambda A}(b)\leq d+1$. Since there are $|A|^2$ pairs $(a,a')$ and $|A+\lambda A|$ many targets $b$, we have $$ |A+\lambda A|\geq\frac{|A|^2}{d+1}\geq\frac{\delta}{2\delta+1}|A|^2. $$ QED

Note that if $\lambda<1$, it is better to reverse the roles of $x_i$ and $y_i$ in the sub-claim.

Assuming that $a_1>1$ for simplicity, we can prove a lower bound for $|A+AA|$, which could potentially be better than the lower bound for $|A+a_nA|$.

First, note that $$ |A|^3\leq |A+AA|\sup_{b\in A+AA}|\{(a,a',a'')\in A^3\colon a+a'a''=b\}|. $$ Now $$ |\{(a,a',a'')\in A^3\colon a+a'a''=b\}|=\sum_{i=1}^n r_{A+a_iA}(b). $$ Since $r_{A+a_iA}(b)\leq d\lceil g/a_i\rceil+1$ independent of $b$, it follows that $$ |A|^3\leq |A+AA|\sum_{i=1}^n \left(d\lceil g/a_i\rceil+1\right). $$

It might be possible to improve the bound by looking for large subsets of $A$ where $g$ is smaller or $\delta$ is larger; if $a_n$ is an outlier and you can make $g$ smaller, then the first first bound is improved. Unfortunately, if $A$ is too uniform, these bounds are useless. For example, a set of $n$ points in $(1,2)$ that are "generic" but roughly equally spaced (so $\delta\approx 1/n$) shows that these bounds can't prove $|A+AA|\geq |A+A|$ in general.

$\endgroup$
  • $\begingroup$ Very nice! I have only a petty quibble that you should change the notation so that $r$ has only one meaning. So, $|AA+A| \gg |A|^2$ for well-separated sets, and this argument broadens the definition of well-separated. $\endgroup$ – Oliver Roche-Newton Apr 29 '15 at 9:15
0
$\begingroup$

I think $\big\{-1, 0, \frac{1+\sqrt{5}}{2}\big\}$ is a counterexample. THIS IS WRONG, see comments, but I'll leave it up as a warning.

$\endgroup$
  • 3
    $\begingroup$ For your set, the left-hand side of the equation gets $8$, while the right-hand side gets $6$, if I'm not mistaken. So this doesn't look like a counterexample. $\endgroup$ – Stefan Kohl Apr 27 '15 at 11:50
  • $\begingroup$ $A+A$ clearly has 9 elements. $AA+A$ has 8, if I'm not mistaken. $\endgroup$ – Yaakov Baruch Apr 27 '15 at 11:51
  • 1
    $\begingroup$ How can $A+A$ have $9$ elements? We always have $|A+A| \leq |A|(|A|+1)/2$, so $|A+A| \leq 6$ in this case. $\endgroup$ – Tom De Medts Apr 27 '15 at 11:53
  • 5
    $\begingroup$ @YaakovBaruch, $A+A$ has at most six elements if $|A|=3$. Addition is commutative. $\endgroup$ – Joonas Ilmavirta Apr 27 '15 at 11:53
  • 5
    $\begingroup$ blunder! Yes, $A+A$ has 6. $\endgroup$ – Yaakov Baruch Apr 27 '15 at 11:54

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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