This research was supported by NSERC and OTKA grants.
<ph f="cmbx">On distinct consecutive differences</ph>

### József Solymosi

Department of Mathematics, University of British Columbia, Vancouver E-mail address : solymosi@math.ubc.ca
• Abstract. We show that if $A=\left\{{a}_{1},{a}_{2},\dots ,{a}_{k}\right\}$  is a monotone increasing set of numbers, and the differences of the consecutive elements are all distinct, then $|A+B|\ge c|A{|}^{1/2}|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=\left\{a+b:a,b\in A\text{and}b\in B\right\}$  Let $A=\left\{{a}_{1},{a}_{2},\dots ,{a}_{k}\right\}$  be a finite set of real numbers with the property that
 $\begin{array}{c}{a}_{i}-{a}_{i-1}<{a}_{i+1}-{a}_{i}\end{array}$ (1)
for any $1  Sets with this property are said to be convex sets. Answering a question of Erdős, Hegyvári [5proved 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 $|B|=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.$
Theorem 1. Let $A$  and $B$  be finite sets of real numbers with $|A|=k$  and $|B|=\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 $|B|$  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 $|A||B|$  , 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 $|A|=|B|=|C|=n,$  then $max\left\{|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=\left\{{a}_{1},{a}_{2},\dots ,{a}_{n}\right\}$  is a monotone increasing set of numbers. If the difference set of the consecutive elements, $D=\left\{{a}_{i+1}-{a}_{i}:1\le i\le n-1\right\}$  , is large, $|D|\ge \delta |A|$  , then $|A+B|\ge c|A{|}^{1/2}|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\left(k,\ell \right),$  the result is immediate for $min\left(k,\ell \right)\le 3,$  so we can assume that $k\ge 3$  and $\ell \ge 3.$  Let $A=\left\{{a}_{1},{a}_{2},\dots ,{a}_{k}\right\}$  and $B=\left\{{b}_{1},{b}_{2},\dots ,{b}_{\ell }\right\}$  , where ${a}_{1}<{a}_{2}<\cdots <{a}_{k}$  and ${b}_{1}<{b}_{2}<\cdots <{b}_{\ell }$  . Let $A+B=C=\left\{{c}_{1},{c}_{2},\dots ,{c}_{m}\right\},$  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
 $\begin{array}{c}\left\{{a}_{i}+{b}_{j},{a}_{i+1}+{b}_{j}\right\}.\end{array}$ (2)
Suppose that $\left\{c,{c}^{\prime }\right\}$  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 $\left\{{a}_{i}+{b}_{j},{a}_{i+1}+{b}_{j}\right\}=\left\{{a}_{{i}^{\prime }}+{b}_{{j}^{\prime }},{a}_{i+1}+{b}_{{j}^{\prime }}\right\},$  then $i={i}^{\prime }$  and $j={j}^{\prime }$  , and so the sumset $C$  contains exactly $\left(k-1\right)\ell$  pairs.
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}=\left\{{c}_{1},\dots ,{c}_{{s}_{1}}\right\},$  ${C}_{2}=\left\{{c}_{{s}_{1}+1},\dots ,{c}_{{s}_{2}}\right\},$  and, in general, for $u=1,\dots ,t,$  ${C}_{u}=\left\{{c}_{{s}_{u-1}+1},\dots ,{c}_{{s}_{u}}\right\}.$  Then $|{C}_{u}|={s}_{u}-{s}_{u-1}\text{for}u=1,\dots ,t\text{}.$  Fix an integer $j\in \left\{1,2,\dots ,\ell \right\}$  , 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{}{}{0}{}{u=1}{{k}_{j,u}\ge 1}}^{t}\left({k}_{j,u}-1\right)=k-{\sum }_{\genfrac{}{}{0}{}{u=1}{{k}_{j,u}\ge 1}}^{t}1\ge k-t.$  Since the set $C$  contains exactly $\left(k-1\right)\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{}{}{0}{}{u=1}{{k}_{j,u}\ge 1}}^{t}\left({k}_{j,u}-1\right)\ge \ell \left(k-t\right).$  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{}{}{0}{}{|{C}_{u}|}{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{}{}{0}{}{|{C}_{u}|}{2}\right).$  Therefore, ${\sum }_{u=1}^{t}\left(\genfrac{}{}{0}{}{|{C}_{u}|}{2}\right)\ge \ell \left(k-t\right).$  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 $|{C}_{u}|=q+1\text{for}u=1,\dots ,r\text{}$  and $|{C}_{u}|=q\text{for}u=r+1,\dots ,t\text{}.$  Then ${\sum }_{u=1}^{t}\left(\genfrac{}{}{0}{}{|{C}_{u}|}{2}\right)\le t\left(\genfrac{}{}{0}{}{q+1}{2}\right)\le \frac{k}{2}\left(\genfrac{}{}{0}{}{\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}\left(\sqrt{2\ell }-1\right).$  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=\left\{{a}_{1},{a}_{2},\dots ,{a}_{k}\right\}$  and ${A}^{\prime }=\left\{{a}_{1}^{\prime },{a}_{2}^{\prime },\dots ,{a}_{k}^{\prime }\right\}$  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 :\left\{1,2,\dots ,k-1\right\}\to \left\{1,2,\dots ,k-1\right\}$  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=|A|=|{A}^{\prime }|$  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 $|B|=\ell$  , and $|{B}^{\prime }|={\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=\left\{{a}_{1},{a}_{2},\dots ,{a}_{k}\right\}$  and ${A}^{\prime }=\left\{{a}_{1}^{\prime },{a}_{2}^{\prime },\dots ,{a}_{k}^{\prime }\right\}$  , 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 :\left\{1,2,\dots ,k-1\right\}\to \left\{1,2,\dots ,k-1\right\}$  be a one-to-one map such that the $k-1$  ordered pairs $\left({d}_{i},{d}_{\sigma \left(i\right)}^{\prime }\right)$  are distinct. Let $B=\left\{{b}_{1},{b}_{2},\dots ,{b}_{\ell }\right\}$  and ${B}^{\prime }=\left\{{b}_{1},{b}_{2},\dots ,{b}_{{\ell }^{\prime }}\right\}$  , 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
 $\begin{array}{c}\left({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 }\right).\end{array}$ (3)
Suppose that $1\le u\le k-1$  , $1\le v\le \ell ,$  and $1\le {v}^{\prime }\le {\ell }^{\prime },$  and that $\left({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 }\right)=\left({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 }\right).$  Then ${d}_{i}=\left({a}_{i+1}+{b}_{j}\right)-\left({a}_{i}+{b}_{j}\right)=\left({a}_{u+1}+{b}_{v}\right)-\left({a}_{u}+{b}_{v}\right)={d}_{u}$  and ${d}_{\sigma \left(i\right)}^{\prime }=\left({a}_{\sigma \left(i\right)+1}^{\prime }+{b}_{{j}^{\prime }}^{\prime }\right)-\left({a}_{\sigma \left(i\right)}^{\prime }+{b}_{{j}^{\prime }}^{\prime }\right)=\left({a}_{\sigma \left(u\right)+1}^{\prime }+{b}_{{v}^{\prime }}^{\prime }\right)-\left({a}_{\sigma \left(u\right)}^{\prime }+{b}_{{v}^{\prime }}^{\prime }\right)={d}_{\sigma \left(u\right)}^{\prime }.$  Therefore, $\left({d}_{i},{d}_{\sigma \left(i\right)}^{\prime }\right)=\left({d}_{u},{d}_{\sigma \left(u\right)}^{\prime }\right).$  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$  .
Similarly, ${j}^{\prime }={v}^{\prime }.$  This implies that there are $\left(k-1\right)\ell {\ell }^{\prime }$  distinct quadruples of the form ( 3 ).
Consider the sumsets $A+B$  and ${A}^{\prime }+{B}^{\prime }$  . $A+B=C=\left\{{c}_{1},\dots ,{c}_{m}\right\},$  where $|C|=m$  and ${c}_{1}<\cdots <{c}_{m}.$  Let ${A}^{\prime }+{B}^{\prime }={C}^{\prime }=\left\{{c}_{1}^{\prime },\dots ,{c}_{{m}^{\prime }}^{\prime }\right\},$  where $|{C}^{\prime }|={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}=\left\{{c}_{1},\dots ,{c}_{{s}_{1}}\right\},$  ${C}_{2}=\left\{{c}_{{s}_{1}+1},\dots ,{c}_{{s}_{2}}\right\},$  and, in general, for $u=1,\dots ,t,$  ${C}_{u}=\left\{{c}_{{s}_{u-1}+1},\dots ,{c}_{{s}_{u}}\right\}.$  Then $|{C}_{u}|={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 }=\left\{{c}_{{s}_{{u}^{\prime }-1}+1}^{\prime },\dots ,{c}_{{s}_{{u}^{\prime }}}^{\prime }\right\}$  for ${u}^{\prime }=1,\dots ,{t}^{\prime }.$  Fix an integer $j\in \left\{1,2,\dots ,\ell \right\}$  , 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
 $\begin{array}{c}\left\{{a}_{i}+{b}_{j},{a}_{i+1}+{b}_{j}\right\},\end{array}$ (4)
and so the number of pairs with fixed $j$  contained in the sets ${C}_{1},\dots ,{C}_{t}$  is ${\sum }_{\genfrac{}{}{0}{}{u=1}{{k}_{j,u}\ge 1}}^{t}\left({k}_{j,u}-1\right)=k-{\sum }_{\genfrac{}{}{0}{}{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 $\left(t-1\right){\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 $\left(t-1\right)\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 $\left({t}^{\prime }-1\right)\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 $\left(t+{t}^{\prime }-2\right)\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 $\left(k-1\right)\ell {\ell }^{\prime }-\left(t+{t}^{\prime }-2\right)\ell {\ell }^{\prime }=\left(k-t-{t}^{\prime }+1\right)\ell {\ell }^{\prime }.$  On the other hand, for each $u=1,\dots ,t$  and ${u}^{\prime }=1,\dots ,{t}^{\prime },$  the number of quadruples $\left(x,y,z,w\right)$  such that $x\ne y$  and $\left\{x,y\right\}\subseteq {C}_{u}$  for $u=1,\dots ,t$  , and also $z\ne w$  and $\left\{z,w\right\}\subseteq {C}_{{u}^{\prime }}^{\prime }$  is exactly $\left(\genfrac{}{}{0}{}{|{C}_{u}|}{2}\right)\left(\genfrac{}{}{0}{}{|{C}_{{u}^{\prime }}^{\prime }|}{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{}{}{0}{}{|{C}_{u}|}{2}\right)\left(\genfrac{}{}{0}{}{|{C}_{{u}^{\prime }}^{\prime }|}{2}\right)\le \frac{1}{4}{\sum }_{u=1}^{t}{\sum }_{{u}^{\prime }=1}^{{t}^{\prime }}|{C}_{u}{|}^{2}|{C}_{{u}^{\prime }}^{\prime }{|}^{2}.$  Therefore,
 $\begin{array}{c}\left(k-t-{t}^{\prime }+1\right)\ell {\ell }^{\prime }\le \frac{1}{4}{\sum }_{u=1}^{t}{\sum }_{{u}^{\prime }=1}^{{t}^{\prime }}|{C}_{u}{|}^{2}|{C}_{{u}^{\prime }}^{\prime }{|}^{2}.\end{array}$ (5)
If we let $t={t}^{\prime }=k/4$  and $|{C}_{u}|=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\left(m{m}^{\prime }{\right)}^{2}}{{k}^{2}},$  and so $\left(m{m}^{\prime }{\right)}^{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}.$

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 $|A|=|B|=|C|=n,$  then $max\left\{|A+B|,|F\left(A\right)+C|\ge c{n}^{5/4}.$  In particular, $|A+F\left(A\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 [4shows 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{}{}{0}{}{|S|}{2}\right),$  and $|S|$  is odd. Then there is a list $L$  of the elements of $S$  with repetitions, consists of $k=\left(\genfrac{}{}{0}{}{|S|}{2}\right)$  elements, such that the consecutive elements have distinct differences. ( $L=\left({s}_{1},{s}_{2},\dots ,{s}_{k}\right)$  where ${s}_{i+1}-{s}_{i}={s}_{j+1}-{s}_{j}$  implies that $i=j.$  ) Now we are ready to define $A.$  $A=\left\{i+{s}_{i}:1\le i\le k\right\}$  The set $A$  has the property that the consecutive differences are distinct, and it is not difficult to see that $|A+\left[k\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

1. Gy. Elekes, On the number of sums and products. Acta Arith. 81 (1997), no. 4, 365–367.
2. 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), .
3. Elekes, M. Nathanson, and I, Ruzsa, Convexity and sumsets. J. Number Theory 83 (2000), no. 2, 194–201.
4. I. Ruzsa, personal communication (2003)
5. N. Hegyvári, On consecutive sums in sequences. Acta Math. Hungar. 48 (1986), no. 1-2, 193–200.

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