Show that $|A+A|\geq (2n-1)$

Question

Consider a set $A$ consisting of $n$ natural numbers $\{a_i\}_{i=1}^n$ such that $a_1<a_2 < \cdots <a_{n-1} < a_n$. Define the set $A+A$ such that it contains $a_i + a_j \ ; \ i \leq j$ as its elements.

Prove That $|A+A| \geq (2n-1)$. When does the equality hold?

I tried to list out the elements for general $n$, but it became too tedious.

Any help will be appreciated.
Thanks.

Answer 1

We assume that $A$ and $B$ are finite nonempty subsets of an integral domain $D$ of characteristic $0$, whose field of fractions is $F$. We claim that $|A+B|\geq |A|+|B|-1$, and that the equality holds iff $A$ and $B$ are arithmetic progressions with the same common difference. (If $A$ and $B$ are arithmetic progressions with the same common difference, then it is easily seen that the equality occurs.)

First, note that $\mathbb{Q}$ is a subfield of $F$, and the smallest subfield $K$ of $F$ containing $A$ and $B$ is a field extension of $\mathbb{Q}$ with finite transcendental degree. Hence, $K$ can be embedded into $\mathbb{C}$. Therefore, it suffices to prove the claim when $D=F=\mathbb{C}$.

Now, we equip $\mathbb{C}$ with the total ordering $<$ by demanding that, for $x,x',y,y'\in\mathbb{R}$, $x+\text{i}y<x'+\text{i}y'$ iff (1) $x<x'$ or (2) $x=x'$ and $y<y'$. This ordering is compatible with addition, namely, for $z_1,z_2,z\in\mathbb{C}$, $z_1<z_2$ implies $z_1+z<z_2+z$.

Write $A=\left\{a_1,a_2,\ldots,a_m\right\}$ and $B=\left\{b_1,b_2,\ldots,b_n\right\}$ such that $a_1<a_2<\ldots<a_m$ and $b_1<b_2<\ldots<b_n$ (making $m=|A|$ and $n=|B|$). Without loss of generality, assume that $m\leq n$. Then, $$a_1+b_1<a_1+b_2<\ldots<a_1+b_n<a_2+b_n<\ldots<a_m+b_n\,.\tag{*}$$ This proves that $A+B$ has at least $m+n-1=|A|+|B|-1$ elements.

Suppose that the equality $|A+B|=|A|+|B|-1$ holds. Note that $$a_1+b_1<a_2+b_1<\ldots<a_m+b_1<a_m+b_2<\ldots<a_m+b_n\tag{**}$$ also contains $m+n-1$ elements of $A+B$. We conclude that $a_1+b_i=a_i+b_1$ for all $i=1,2,\ldots,m$. Thus, $b_i=a_i+t$, where $t:=b_1-a_1$ for $i=1,2,\ldots,m$. Since $$a_1+b_1<a_1+b_2<a_2+b_2<a_3+b_2<\ldots<a_m+b_2<a_m+b_3<\ldots<a_m+b_n$$ also contains $2+(m-1)+(n-2)=m+n-1$ elements of $A+B$, we have that $a_2+b_2=a_1+b_3$, $a_3+b_2=a_1+b_4$, $\ldots$, $a_{m-1}+b_2=a_1+b_m$. Thus, $$a_2-a_1=b_3-b_2=(a_3+t)-(a_2+t)=a_3-a_2\,,$$ $$a_3-a_1=b_4-b_2=(a_4+t)-(a_2+t)=a_4-a_2\,,$$ $$\ldots\,,$$ $$a_{m-1}-a_1=b_m-b_2=(a_m+t)-(a_2+t)=a_m-a_2\,.$$ This proves that $a_2-a_1=a_3-a_2=\ldots=a_m-a_{m-1}=:d$. That is, $A$ is an arithmetic progression with common difference $d$.

From the relationship between $a_i$ and $b_i$ with $i=1,2,\ldots,m$, we conclude that $\left\{b_1,b_2,\ldots,b_m\right\}$ is a subset of $B$ which is an arithmetic progression with common difference $d$. Now, from (*) and (**), $a_1+b_{m+1}=a_m+b_2$, $a_1+b_{m+2}=a_m+b_3$, $\ldots$, $a_1+b_n=a_m+b_{n+1-m}$. This implies that $$b_{m+1}=b_2+(a_m-a_1)=b_m+d\,,$$ $$b_{m+2}=b_3+(a_m-a_1)=b_{m+1}+d\,,$$ $$\ldots\,,$$ $$b_n=b_{n+1-m}-(a_m-a_1)=b_{n-1}+d\,.$$ Thus, $B$ is an arithmetic progression with common difference $d$ as well.

Note that, if $D$ is the field $\mathbb{F}_p$ for a prime natural number $p$, then we have a similar inequality, known as the Cauchy-Davenport Inequality: $|A+B|\geq \min\big\{p,|A|+|B|-1\big\}$. This last inequality is also true in general for an integral domain $D$ of characteristic $p$.

Answer 2

Hint: Why are $$ a_n+a_n,a_n+a_{n+1},\cdots,a_n+a_2,a_n+a_1,a_{n-1}+a_1,\cdots,a_2+a_1,a_1+a_1 $$ all distinct?

To see that this is the minimum, suppose that $A$ is an arithmetic sequence: $$ A=\{a_1,a_1+r,a_1+2r,\cdots,a_1+(n-1)r\}. $$ Then the list above is $\{2a_1,2a_1+r,\cdots,2a_1+2(n-1)r\}$. Can you prove that every $a_i+a_j$ is in this list?

Answer 3

if $A=\{ 1,...,n\}$, then $A+A=\{2,...,2n\}$. A simple computation gives that $|A|=n$ and $|A+A|=2n-1$.

Following the hint of Michael Burr, $a_n+A\cap a_1+A=\{ a_1+a_n \}$. Therefore, using the classical formula $card(A\cup B)=card(A)+card(B)-card(A\cap B)$, we have that $card(A+A)\geqslant card(\{ a_1,a_n\} + A)=card(a_1+A\cup a_n+A) = 2n-1$.