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.

16more comments