Sumsets : optimality of two basic inequalities

Question

One can prove that for $A$ and $B$ subsets of $\mathbb{Z}$ one has $$ |A|+|B|-1 \leq |A+B| \leq |A|\times |B| $$ where $A+B = \left\{ a+b,a\in A \text{ and } b \in B \right\}$ and, for $X$ a finite set, $|X|$ denotes its cardinal. I'm not interested on a proof of the two previous inequalities but the optimality of these inequalities in the sense on the following exercise.

I've just found here the following exercise (that proves that the previous bound are tight in general) : for $m,n,s$ integers such that $m\geq 1$, $n\geq 1$ and $m+n-1 \leq s \leq m\times n$, we can find $A$ and $B$ subsets of $\mathbb{Z}$ such that $|A|=m$, $B=n$ and $|A+B|=s$.

Do you have any hint for this exercise ?

Answer 1

Let $m>0$, $n>0$, $m+n-1\leq s\leq mn$, and $m\leq n$.

Let $s=nq+r$ where $0\leq r<n$, $1\leq q\leq m$ and if $r>0$, then $q<m$.

Let us define $$ B=\{1,\ldots,n\},\ A'=\{0,n,\ldots,n(q-1),-r\}. $$ It is clear that $|B|=n$ and if $r\neq0$, then $|A'|=q+1$ otherwise $|A'|=q$.

It is also clear that if $r=0$, then $$ A'+B=\{1,\ldots,nq\},\ |A'+B|=nq=s; $$ if $r>0$, then $$ A'+B=\{-r+1,\ldots,0,1,\ldots,nq\},\ |A'+B|=nq+r=s. $$

Next, in order to find the set $A$, consider several cases.

I. $r=0$.

I(a) If $m=q$, then $A=A'$.

I(b) If $q<m$, then $q>1$ and $$ A=A'\cup\{1,\ldots,m-q\}. $$ It is required to check that $|A|=m$ and $A+B=A'+B$. I leave all checks to the author of the question.

II. $r>0$.

II(a) If $m=q+1$, then $A=A'$.

II(b) If $q<m-1$, then $m>2$.

II(b1) If $q=1$, then $1<m\leq r+1$, $A'=\{0,-r\}$, and $$ A=A'\cup\{-1,\ldots,-m+2\}. $$ Again we need to check that $|A|=m$ and $A+B=A'+B$.

II(b2) Let $q>1$. In this case let us define $A$ as in case I(b). $$ A=A'\cup\{1,\ldots,m-q\}. $$ Once again we need to check that $|A|=m$ and $A+B=A'+B$.

Answer 2

Note: I encourage thinking of this problem as a set of points that is translated multiple times.

Idea: Consider the extreme ends of the inequality. How we can slowly transition from one to the other.
The LHS is when the terms are in an AP with the same difference, so the translated points are guaranteed to overlap each other.
The RHS is when the points are very far spread out, hence there is little chance of an overlap.

Goal: We can move from LHS to RHS by spreading out the points.
If we move slowly enough so that we reduce the overlap by 1 each time, that will guarantee we hit all numbers in the range.

Further Hints: If you can't visualize it, induction works.

Prove the statement for $m = 2$, $n \in \mathbb{N}$.
Even if you used induction, please try to visualize this thereafter.

Induct with the previous (as both the base case and used in the induction hypothesis) to prove that the statement works for $m, n \in \mathbb{N}$.