- Abstract. We show that if $A=\{{a}_{1},{a}_{2},\dots ,{a}_{k}\}$ is a monotone increasing set of numbers, and the differences of the consecutive elements are all distinct, then $|A+B|\ge c\left|A{|}^{1/2}\right|B|$ for any finite set of numbers $B$ . The bound is tight up to the constant multiplier.

1 introduction

Given two sets of numbers,
$A$
and
$B$
, the sumset of
$A$
and
$B$
, denoted by
$A+B,$
is
$$A+B=\{a+b:a,b\in A\text{and}b\in B\}$$
Let
$A=\{{a}_{1},{a}_{2},\dots ,{a}_{k}\}$
be a finite set of real numbers with the property that

for any
$1<i<k.$
Sets with this property are said to be convex sets. Answering a question of Erdős, Hegyvári [5] proved that if
$A$
is convex then
$|A+A|\ge cklogk/loglogk.$
Hegyvári's result was later improved by Elekes, Nathanson, and Ruzsa [3] . They proved that if
$A$
is convex, then
$|A+B|\ge c{k}^{3/2}$
for any set
$B$
with
$\left|B\right|=k.$
In this paper we extend this result for sets with distinct consecutive differences. Set
$A$
has distinct consecutive differences if for any
$1\le i,j\le k,$
${a}_{i+1}-{a}_{i}={a}_{j+1}-{a}_{j}$
implies
$i=j.$

$$\begin{array}{c}{a}_{i}-{a}_{i-1}<{a}_{i+1}-{a}_{i}\end{array}$$ | (1) |

Theorem 1.
Let
$A$
and
$B$
be finite sets of real numbers with
$\left|A\right|=k$
and
$\left|B\right|=\ell .$
If
$A$
has distinct consecutive differences, then
$$|A+B|\ge \frac{k\sqrt{\ell}}{3}.$$
In particular, if
$k=\ell ,$
then
$$|A+B|\ge \frac{{k}^{3/2}}{3}.$$

The basic idea behind the proof is the following. The sumset
$A+B$
consists of
$\left|B\right|$
translates of
$A$
. The translates of two consecutive elements of
$A$
are typically not ”far” from each other in the sumset
$A+B.$
Also, from a translate of two consecutive elements,
$b+{a}_{i}$
,
$b+{a}_{i+1}$
we can recover the value of
$b$
, since all of the consecutive differences are distinct. Then the number of ”close” pairs in
$A+B$
should be large, around
$\left|A\right|\left|B\right|$
, therefore
$A+B$
is also large.
In the second part of the paper we extend the result for two sets. As an application we show that for any convex function
$F$
, and finite sets of real numbers,
$A,B,$
and
$C$
, if
$\left|A\right|=\left|B\right|=\left|C\right|=n,$
then
$max\left\{\right|A+B|,|F\left(A\right)+C|\ge c{n}^{5/4}.$
Along the lines of the proof one can prove the ”statistical” version of Theorem 1 and Theorem 3. We state the analogue of Theorem 1 without working out the details of the proof.

Theorem 2.
Let
$A=\{{a}_{1},{a}_{2},\dots ,{a}_{n}\}$
is a monotone increasing set of numbers. If the difference set of the consecutive elements,
$D=\{{a}_{i+1}-{a}_{i}:1\le i\le n-1\}$
, is large,
$\left|D\right|\ge \delta \left|A\right|$
, then
$|A+B|\ge c\left|A{|}^{1/2}\right|B|$
for any finite set of numbers
$B$
, where
$c$
depends on
$\delta $
only.

2 Distinct consecutive differences

of Theorem 1. Since
$|A+B|\ge min(k,\ell ),$
the result is immediate for
$min(k,\ell )\le 3,$
so we can assume that
$k\ge 3$
and
$\ell \ge 3.$
Let
$A=\{{a}_{1},{a}_{2},\dots ,{a}_{k}\}$
and
$B=\{{b}_{1},{b}_{2},\dots ,{b}_{\ell}\}$
, where
${a}_{1}<{a}_{2}<\cdots <{a}_{k}$
and
${b}_{1}<{b}_{2}<\cdots <{b}_{\ell}$
. Let
$$A+B=C=\{{c}_{1},{c}_{2},\dots ,{c}_{m}\},$$
where
${c}_{1}<{c}_{2}<\cdots <{c}_{m}$
and
$m=|A+B|.$
Let
$1\le i\le k-1$
and
$1\le j\le \ell .$
A pair is a two-element subset of
$C$
of the form

Suppose that
$\{c,{c}^{\prime}\}$
is a pair and
$c<{c}^{\prime}$
. Since the set
$A$
has distinct consecutive differences, there is a unique integer
$i$
such that
$${c}^{\prime}-c={a}_{i+1}-{a}_{i}.$$
It follows that there is a unique integer
$j$
such that
$$c-{a}_{i}={c}^{\prime}-{a}_{i+1}={b}_{j}.$$
Therefore, if
$$\{{a}_{i}+{b}_{j},{a}_{i+1}+{b}_{j}\}=\{{a}_{{i}^{\prime}}+{b}_{{j}^{\prime}},{a}_{i+1}+{b}_{{j}^{\prime}}\},$$
then
$i={i}^{\prime}$
and
$j={j}^{\prime}$
, and so the sumset
$C$
contains exactly
$(k-1)\ell $
pairs.

$$\begin{array}{c}\{{a}_{i}+{b}_{j},{a}_{i+1}+{b}_{j}\}.\end{array}$$ | (2) |

Let
${s}_{0},{s}_{1},\dots ,{s}_{t}$
be integers such that
$$0={s}_{0}<{s}_{1}<{s}_{2}<\cdots <{s}_{t-1}<{s}_{t}=m.$$
We partition the set
$C$
into
$t$
pairwise disjoint sets
${C}_{1},\dots ,{C}_{t}$
as follows:
$${C}_{1}=\{{c}_{1},\dots ,{c}_{{s}_{1}}\},$$
$${C}_{2}=\{{c}_{{s}_{1}+1},\dots ,{c}_{{s}_{2}}\},$$
and, in general, for
$u=1,\dots ,t,$
$${C}_{u}=\{{c}_{{s}_{u-1}+1},\dots ,{c}_{{s}_{u}}\}.$$
Then
$\left|{C}_{u}\right|={s}_{u}-{s}_{u-1}\text{for}u=1,\dots ,t\text{}.$
Fix an integer
$j\in \{1,2,\dots ,\ell \}$
, and consider the increasing sequence
$${a}_{1}+{b}_{j}<{a}_{2}+{b}_{j}<\cdots <{a}_{k}+{b}_{j}.$$
Let
${k}_{j,u}$
denote the number of elements of this sequence that belong to the set
${C}_{u}.$
Then
$${\sum}_{u=1}^{t}{k}_{j,u}=k.$$
If
${k}_{j,u}\ge 1,$
then the set
${C}_{u}$
contains exactly
${k}_{j,u}-1$
pairs of the form ( 2 ), and so the number of pairs with fixed
$j$
contained in the sets
${C}_{1},\dots ,{C}_{t}$
is
$${\sum}_{\genfrac{}{}{0ex}{}{u=1}{{k}_{j,u}\ge 1}}^{t}({k}_{j,u}-1)=k-{\sum}_{\genfrac{}{}{0ex}{}{u=1}{{k}_{j,u}\ge 1}}^{t}1\ge k-t.$$
Since the set
$C$
contains exactly
$(k-1)\ell $
distinct pairs, it follows that the total number of pairs contained in the sets
${C}_{1},\dots ,{C}_{t}$
is at least
$${\sum}_{j=1}^{\ell}{\sum}_{\genfrac{}{}{0ex}{}{u=1}{{k}_{j,u}\ge 1}}^{t}({k}_{j,u}-1)\ge \ell (k-t).$$
We can obtain a simple upper bound for the total number of pairs contained in the sets
${C}_{1},\dots ,{C}_{t}$
as follows: For
$u=1,\dots ,t,$
the set
${C}_{u}$
contains at most
$\left(\genfrac{}{}{0ex}{}{\left|{C}_{u}\right|}{2}\right)$
pairs, and so the number of pairs contained in the sets
${C}_{1},\dots ,{C}_{t}$
is at most
$${\sum}_{u=1}^{t}\left(\genfrac{}{}{0ex}{}{\left|{C}_{u}\right|}{2}\right).$$
Therefore,
$${\sum}_{u=1}^{t}\left(\genfrac{}{}{0ex}{}{\left|{C}_{u}\right|}{2}\right)\ge \ell (k-t).$$
We specialize this inequality as follows: Let
$$t=\left[\frac{k}{2}\right]$$
and
$$m=qt+r,$$
where
$$0\le r\le t-1.$$
Then
$$q\le \frac{m}{t}\le \frac{2m}{k-1}.$$
Choose the integers
${s}_{1},\dots ,{s}_{t-1}$
such that
$\left|{C}_{u}\right|=q+1\text{for}u=1,\dots ,r\text{}$
and
$\left|{C}_{u}\right|=q\text{for}u=r+1,\dots ,t\text{}.$
Then
$${\sum}_{u=1}^{t}\left(\genfrac{}{}{0ex}{}{\left|{C}_{u}\right|}{2}\right)\le t\left(\genfrac{}{}{0ex}{}{q+1}{2}\right)\le \frac{k}{2}\left(\genfrac{}{}{0ex}{}{\frac{2m}{k-1}+1}{2}\right)<\frac{k}{4}{\left(\frac{2m}{k-1}+1\right)}^{2}$$
and so
$$\frac{k}{4}{\left(\frac{2m}{k-1}+1\right)}^{2}>\frac{\ell k}{2}.$$
This implies that
$$m>\frac{k-1}{2}(\sqrt{2\ell}-1).$$
If
$k\ge 3$
and
$\ell \ge 3,$
then
$$m>\frac{k\sqrt{\ell}}{3}.$$
This completes the proof.

3 Distinct pairs of consecutive differences

Let
$A=\{{a}_{1},{a}_{2},\dots ,{a}_{k}\}$
and
${A}^{\prime}=\{{a}_{1}^{\prime},{a}_{2}^{\prime},\dots ,{a}_{k}^{\prime}\}$
be nonempty sets of real numbers, where
${a}_{1}<{a}_{2}<\cdots <{a}_{k}$
and
${a}_{1}^{\prime}<{a}_{2}^{\prime}<\cdots <{a}_{k}^{\prime}$
. Let
${d}_{i}={a}_{i+1}-{a}_{i}$
for
$i=1,\dots ,k-1$
and
${d}_{i}^{\prime}={a}_{i+1}^{\prime}-{a}_{i}^{\prime}$
for
$i=1,\dots ,k-1.$
The sets
$A$
and
${A}^{\prime}$
have distinct pairs of consecutive differences if there exists a one-to-one map
$\sigma :\{1,2,\dots ,k-1\}\to \{1,2,\dots ,k-1\}$
such that the
$k-1$
ordered pairs
$\left({d}_{i},{d}_{\sigma \left(i\right)}^{\prime}\right)$
are distinct.

Theorem 3.
Let
$A$
and
${A}^{\prime}$
be nonempty finite sets of real numbers such that
$k=\left|A\right|=\left|{A}^{\prime}\right|$
and the sets
$A$
and
${A}^{\prime}$
have distinct pairs of consecutive differences. Let
$B$
, and
${B}^{\prime}$
be nonempty finite sets of real numbers with
$\left|B\right|=\ell $
, and
$\left|{B}^{\prime}\right|={\ell}^{\prime}$
Then
$$|A+B|\cdot |{A}^{\prime}+{B}^{\prime}|\gg {\left({k}^{3}\ell {\ell}^{\prime}\right)}^{1/2}.$$
If
$\ell ={\ell}^{\prime}=k,$
then
$$|A+B|\cdot |{A}^{\prime}+{B}^{\prime}|\gg {k}^{5/2}.$$

Let
$A=\{{a}_{1},{a}_{2},\dots ,{a}_{k}\}$
and
${A}^{\prime}=\{{a}_{1}^{\prime},{a}_{2}^{\prime},\dots ,{a}_{k}^{\prime}\}$
, where
${a}_{1}<{a}_{2}<\cdots <{a}_{k}$
and
${a}_{1}^{\prime}<{a}_{2}^{\prime}<\cdots <{a}_{k}^{\prime}$
. Let
${d}_{i}={a}_{i+1}-{a}_{i}$
for
$i=1,\dots ,k-1$
and
${d}_{i}^{\prime}={a}_{i+1}^{\prime}-{a}_{i}^{\prime}$
for
$i=1,\dots ,k-1$
. Let
$\sigma :\{1,2,\dots ,k-1\}\to \{1,2,\dots ,k-1\}$
be a one-to-one map such that the
$k-1$
ordered pairs
$({d}_{i},{d}_{\sigma \left(i\right)}^{\prime})$
are distinct. Let
$B=\{{b}_{1},{b}_{2},\dots ,{b}_{\ell}\}$
and
${B}^{\prime}=\{{b}_{1},{b}_{2},\dots ,{b}_{{\ell}^{\prime}}\}$
, where
${b}_{1}<{b}_{2}<\cdots <{b}_{\ell}$
and
${b}_{1}^{\prime}<{b}_{2}^{\prime}<\cdots <{b}_{{\ell}^{\prime}}^{\prime}$
.
Let
$1\le i\le k-1$
,
$1\le j\le \ell ,$
and
$1\le {j}^{\prime}\le {\ell}^{\prime}.$
We consider quadruples of the form

Suppose that
$1\le u\le k-1$
,
$1\le v\le \ell ,$
and
$1\le {v}^{\prime}\le {\ell}^{\prime},$
and that
$$({a}_{i}+{b}_{j},{a}_{i+1}+{b}_{j},{a}_{\sigma \left(i\right)}^{\prime}+{b}_{{j}^{\prime}}^{\prime},{a}_{\sigma \left(i\right)+1}^{\prime}+{b}_{{j}^{\prime}}^{\prime})=({a}_{u}+{b}_{v},{a}_{u+1}+{b}_{v},{a}_{\sigma \left(u\right)}^{\prime}+{b}_{{v}^{\prime}}^{\prime},{a}_{\sigma \left(u\right)+1}^{\prime}+{b}_{{v}^{\prime}}^{\prime}).$$
Then
$${d}_{i}=({a}_{i+1}+{b}_{j})-({a}_{i}+{b}_{j})=({a}_{u+1}+{b}_{v})-({a}_{u}+{b}_{v})={d}_{u}$$
and
$${d}_{\sigma \left(i\right)}^{\prime}=({a}_{\sigma \left(i\right)+1}^{\prime}+{b}_{{j}^{\prime}}^{\prime})-({a}_{\sigma \left(i\right)}^{\prime}+{b}_{{j}^{\prime}}^{\prime})=({a}_{\sigma \left(u\right)+1}^{\prime}+{b}_{{v}^{\prime}}^{\prime})-({a}_{\sigma \left(u\right)}^{\prime}+{b}_{{v}^{\prime}}^{\prime})={d}_{\sigma \left(u\right)}^{\prime}.$$
Therefore,
$$({d}_{i},{d}_{\sigma \left(i\right)}^{\prime})=({d}_{u},{d}_{\sigma \left(u\right)}^{\prime}).$$
The sets
$A$
and
${A}^{\prime}$
have matching consecutive differences with permutation
$\sigma $
, and so
$i=u.$
Since
${a}_{i}+{b}_{j}={a}_{u}+{b}_{v}={a}_{i}+{b}_{v},$
it follows that
${b}_{j}={b}_{v}$
and
$j=v$
.

$$\begin{array}{c}({a}_{i}+{b}_{j},{a}_{i+1}+{b}_{j},{a}_{\sigma \left(i\right)}^{\prime}+{b}_{{j}^{\prime}}^{\prime},{a}_{\sigma \left(i\right)+1}^{\prime}+{b}_{{j}^{\prime}}^{\prime}).\end{array}$$ | (3) |

Similarly,
${j}^{\prime}={v}^{\prime}.$
This implies that there are
$(k-1)\ell {\ell}^{\prime}$
distinct quadruples of the form ( 3 ).

Consider the sumsets
$A+B$
and
${A}^{\prime}+{B}^{\prime}$
.
$$A+B=C=\{{c}_{1},\dots ,{c}_{m}\},$$
where
$\left|C\right|=m$
and
${c}_{1}<\cdots <{c}_{m}.$
Let
$${A}^{\prime}+{B}^{\prime}={C}^{\prime}=\{{c}_{1}^{\prime},\dots ,{c}_{{m}^{\prime}}^{\prime}\},$$
where
$\left|{C}^{\prime}\right|={m}^{\prime}$
and
${c}_{1}^{\prime}<\cdots <{c}_{{m}^{\prime}}^{\prime}.$
Let
${s}_{0},{s}_{1},\dots ,{s}_{t}$
be integers such that
$$0={s}_{0}<{s}_{1}<{s}_{2}<\cdots <{s}_{t-1}<{s}_{t}=m.$$
We partition the set
$C$
into
$t$
pairwise disjoint sets
${C}_{1},\dots ,{C}_{t}$
as follows:
$${C}_{1}=\{{c}_{1},\dots ,{c}_{{s}_{1}}\},$$
$${C}_{2}=\{{c}_{{s}_{1}+1},\dots ,{c}_{{s}_{2}}\},$$
and, in general, for
$u=1,\dots ,t,$
$${C}_{u}=\{{c}_{{s}_{u-1}+1},\dots ,{c}_{{s}_{u}}\}.$$
Then
$\left|{C}_{u}\right|={s}_{u}-{s}_{u-1}\text{for}u=1,\dots ,t\text{}.$
Similarly, let
${s}_{0}^{\prime},{s}_{1}^{\prime},\dots ,{s}_{{t}^{\prime}}^{\prime}$
be integers such that
$$0={s}_{0}^{\prime}<{s}_{1}^{\prime}<{s}_{2}^{\prime}<\cdots <{s}_{t-1}^{\prime}<{s}_{t}^{\prime}={m}^{\prime},$$
and partition the set
${C}^{\prime}$
into
${t}^{\prime}$
pairwise disjoint sets
${C}_{1}^{\prime},\dots ,{C}_{{t}^{\prime}}^{\prime}$
as follows:
$${C}_{{u}^{\prime}}^{\prime}=\{{c}_{{s}_{{u}^{\prime}-1}+1}^{\prime},\dots ,{c}_{{s}_{{u}^{\prime}}}^{\prime}\}$$
for
${u}^{\prime}=1,\dots ,{t}^{\prime}.$
Fix an integer
$j\in \{1,2,\dots ,\ell \}$
, and consider the increasing sequence
$${a}_{1}+{b}_{j}<{a}_{2}+{b}_{j}<\cdots <{a}_{k}+{b}_{j}.$$
These
$k$
numbers belong to sumset
$C.$
Let
${k}_{j,u}$
denote the number of elements of this sequence that belong to the set
${C}_{u}.$
Then
$${\sum}_{u=1}^{t}{k}_{j,u}=k.$$
If
${k}_{j,u}\ge 1,$
then the set
${C}_{u}$
contains exactly
${k}_{j,u}-1$
subsets of the form

and so the number of pairs with fixed
$j$
contained in the sets
${C}_{1},\dots ,{C}_{t}$
is
$${\sum}_{\genfrac{}{}{0ex}{}{u=1}{{k}_{j,u}\ge 1}}^{t}({k}_{j,u}-1)=k-{\sum}_{\genfrac{}{}{0ex}{}{u=1}{{k}_{j,u}\ge 1}}^{t}1\ge k-t.$$
There are
$k-1$
pairs of the form ( 4 ), and so the number of such pairs that do not belong to one of the sets
${C}_{1},\dots ,{C}_{t}$
is at most
$t-1$
. Therefore, for each
$j=1,\dots ,\ell ,$
the number of quadruples of the form ( 3 ) whose first two coordinates do not belong to one of the sets
${C}_{1},\dots ,{C}_{t}$
is at most
$$(t-1){\ell}^{\prime}.$$
Summing over
$j$
, we conclude that the number of quadruples of the form ( 3 ) whose first two coordinates do not belong to one of the sets
${C}_{1},\dots ,{C}_{t}$
is at most
$$(t-1)\ell {\ell}^{\prime}.$$
Similarly, the number of quadruples of the form ( 3 ) whose third and fourth coordinates do not belong to one of the sets
${C}_{1}^{\prime},\dots ,{C}_{{t}^{\prime}}^{\prime}$
is at most
$$({t}^{\prime}-1)\ell {\ell}^{\prime}.$$
Therefore, the number of quadruples of the form ( 3 ) whose first pair of coordinates does not belong to a set
${C}_{u}$
or whose last pair of coordinates does not belong to a set
${C}_{{u}^{\prime}}^{\prime}$
is at most
$(t+{t}^{\prime}-2)\ell {\ell}^{\prime}.$
It follows that the number of quadruples of the form ( 3 ) whose first pair of coordinates belongs to one of sets
${C}_{u}$
and whose last pair of coordinates also belongs to one of the sets
${C}_{{u}^{\prime}}^{\prime}$
is bounded below by
$$(k-1)\ell {\ell}^{\prime}-(t+{t}^{\prime}-2)\ell {\ell}^{\prime}=(k-t-{t}^{\prime}+1)\ell {\ell}^{\prime}.$$
On the other hand, for each
$u=1,\dots ,t$
and
${u}^{\prime}=1,\dots ,{t}^{\prime},$
the number of quadruples
$(x,y,z,w)$
such that
$x\ne y$
and
$\{x,y\}\subseteq {C}_{u}$
for
$u=1,\dots ,t$
, and also
$z\ne w$
and
$\{z,w\}\subseteq {C}_{{u}^{\prime}}^{\prime}$
is exactly
$$\left(\genfrac{}{}{0ex}{}{\left|{C}_{u}\right|}{2}\right)\left(\genfrac{}{}{0ex}{}{\left|{C}_{{u}^{\prime}}^{\prime}\right|}{2}\right)$$
It follows that a simple upper bound for the number of quadruples of the form ( 3 ) whose first pair of coordinates belongs to one of sets
${C}_{u}$
and whose last pair of coordinates also belongs to one of the sets
${C}_{{u}^{\prime}}^{\prime}$
is
$${\sum}_{u=1}^{t}{\sum}_{{u}^{\prime}=1}^{{t}^{\prime}}\left(\genfrac{}{}{0ex}{}{\left|{C}_{u}\right|}{2}\right)\left(\genfrac{}{}{0ex}{}{\left|{C}_{{u}^{\prime}}^{\prime}\right|}{2}\right)\le \frac{1}{4}{\sum}_{u=1}^{t}{\sum}_{{u}^{\prime}=1}^{{t}^{\prime}}\left|{C}_{u}{|}^{2}\right|{C}_{{u}^{\prime}}^{\prime}{|}^{2}.$$
Therefore,

If we let
$t={t}^{\prime}=k/4$
and
$\left|{C}_{u}\right|=m/t=4m/k$
and
${C}_{{u}^{\prime}}^{\prime}|=4{m}^{\prime}/k,$
then
$$\frac{k\ell {\ell}^{\prime}}{2}\le \frac{1}{4}\frac{{k}^{2}}{16}\frac{16{m}^{2}}{{k}^{2}}\frac{16{{m}^{\prime}}^{2}}{{k}^{2}}=\frac{4(m{m}^{\prime}{)}^{2}}{{k}^{2}},$$
and so
$$(m{m}^{\prime}{)}^{2}\ge \frac{{k}^{3}\ell {\ell}^{\prime}}{8}.$$
If
$\ell ={\ell}^{\prime}=k,$
then
$$|A+B|\cdot |{A}^{\prime}+{B}^{\prime}|=m{m}^{\prime}\gg {k}^{5/2}.$$

$$\begin{array}{c}\{{a}_{i}+{b}_{j},{a}_{i+1}+{b}_{j}\},\end{array}$$ | (4) |

$$\begin{array}{c}(k-t-{t}^{\prime}+1)\ell {\ell}^{\prime}\le \frac{1}{4}{\sum}_{u=1}^{t}{\sum}_{{u}^{\prime}=1}^{{t}^{\prime}}\left|{C}_{u}{|}^{2}\right|{C}_{{u}^{\prime}}^{\prime}{|}^{2}.\end{array}$$ | (5) |

4 Remarks

A simple consequence of Theorem 3 is the following result, which was first proved by Elekes, Nathanson, and Ruzsa [3] .

Theorem 4.
For any strictly convex real function
$F$
, and finite sets of real numbers,
$A,B,$
and
$C$
, if
$\left|A\right|=\left|B\right|=\left|C\right|=n,$
then
$max\left\{\right|A+B|,|F\left(A\right)+C|\ge c{n}^{5/4}.$
In particular,
$|A+F(A\left)\right|\ge c{n}^{5/4}.$

The two sets
$A$
and
$F\left(A\right)$
have distinct pairs of consecutive differences with
$\sigma =I,$
the identity map. For the second inequality set
$B=F\left(A\right)$
and
$C=A.$
A construction of Ruzsa [4] shows that the bounds in Theorem 1 and 3 are tight.
However, as we will see, in his construction
$A$
and
$B$
have very different structures.

It is possible, that if
$A=B$
in Theorem 1, then
$|A+B|$
is much larger, maybe close to
$|A{|}^{2}.$
Here we sketch Ruzsa's construction. Let
$S$
be set such that all the differences in
$S$
are distinct,
$|S-S|=\left(\genfrac{}{}{0ex}{}{\left|S\right|}{2}\right),$
and
$\left|S\right|$
is odd. Then there is a list
$L$
of the elements of
$S$
with repetitions, consists of
$k=\left(\genfrac{}{}{0ex}{}{\left|S\right|}{2}\right)$
elements, such that the consecutive elements have distinct differences. (
$L=({s}_{1},{s}_{2},\dots ,{s}_{k})$
where
${s}_{i+1}-{s}_{i}={s}_{j+1}-{s}_{j}$
implies that
$i=j.$
) Now we are ready to define
$A.$
$$A=\{i+{s}_{i}:1\le i\le k\}$$
The set
$A$
has the property that the consecutive differences are distinct, and it is not difficult to see that
$|A+[k\left]\right|\le |S{|}^{3}\le c{k}^{3/2},$
where
$\left[k\right]$
denotes the first
$k$
natural numbers.

The example shows that Theorem 1 is sharp, however Erdős' original question is still wide open; What is the smallest possible size of
$A+A$
if
$A$
is a convex set of integers?

Acknowledgement: I thank Mel Nathanson for his help on writing up the paper.

References
Department of Mathematics, University of British Columbia, Vancouver E-mail address : solymosi@math.ubc.ca

- Gy. Elekes, On the number of sums and products. Acta Arith. 81 (1997), no. 4, 365–367.
- Gy. Elekes, Sums versus products in number theory, algebra and Erdős geometry. in: Paul Erdős and his Mathematics. II, Budapest, Bolyai Society Mathematical Studies, 11. (2002), .
- Elekes, M. Nathanson, and I, Ruzsa, Convexity and sumsets. J. Number Theory 83 (2000), no. 2, 194–201.
- I. Ruzsa, personal communication (2003)
- N. Hegyvári, On consecutive sums in sequences. Acta Math. Hungar. 48 (1986), no. 1-2, 193–200.