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.
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.)
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.
– Oliver Roche-Newton Apr 28 '15 at 09:12Here 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|.$$
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.
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|$.
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'.
– Yakk
Apr 27 '15 at 19:22
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".
– Oliver Roche-Newton Apr 28 '15 at 13:51The 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.
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.
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.
