, ,

Given two sets of numbers,

A

and

B

, the sumset of

A

and

B

, denoted by

A + B,

A + B = {a + b : a, b \in A and b \in B}

Let

A = {a_{1}, a_{2}, \dots, a_{k}}

be a finite set of real numbers with the property that

\begin{matrix} a_{i} - a_{i - 1} < a_{i + 1} - a_{i} \end{matrix}

(1)

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 | \geq c k log k / log log k .

Hegyvári's result was later improved by Elekes, Nathanson, and Ruzsa [3] . They proved that if

A

is convex, then

| A + B | \geq 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 \leq i, j \leq 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 | = ℓ .

A

has distinct consecutive differences, then

| A + B | \geq \frac{k \sqrt{ℓ}}{3} .

In particular, if

k = ℓ,

then

| A + B | \geq \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 {| A + B |, | F (A) + C | \geq 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 \leq i \leq n - 1}

, is large,

| D | \geq δ | A |

, then

| A + B | \geq c | A |^{1 / 2} | B |

for any finite set of numbers

B

, where

c

depends on

δ

only.

2 Distinct consecutive differences

of Theorem 1. Since

| A + B | \geq min (k, ℓ),

the result is immediate for

min (k, ℓ) \leq 3,

so we can assume that

k \geq 3

and

ℓ \geq 3 .

Let

A = {a_{1}, a_{2}, \dots, a_{k}}

and

B = {b_{1}, b_{2}, \dots, b_{ℓ}}

, where

a_{1} < a_{2} < \dots < a_{k}

and

b_{1} < b_{2} < \dots < b_{ℓ}

. Let

A + B = C = {c_{1}, c_{2}, \dots, c_{m}},

where

c_{1} < c_{2} < \dots < c_{m}

and

m = | A + B | .

Let

1 \leq i \leq k - 1

and

1 \leq j \leq ℓ .

A pair is a two-element subset of

C

of the form

\begin{matrix} {a_{i} + b_{j}, a_{i + 1} + b_{j}} . \end{matrix}

(2)

Suppose that

{c, c^{'}}

is a pair and

c < c^{'}

. Since the set

A

has distinct consecutive differences, there is a unique integer

i

such that

c^{'} - c = a_{i + 1} - a_{i} .

It follows that there is a unique integer

j

such that

c - a_{i} = c^{'} - a_{i + 1} = b_{j} .

Therefore, if

{a_{i} + b_{j}, a_{i + 1} + b_{j}} = {a_{i^{'}} + b_{j^{'}}, a_{i + 1} + b_{j^{'}}},

then

i = i^{'}

and

j = j^{'}

, and so the sumset

C

contains exactly

(k - 1) ℓ

pairs.

Let

s_{0}, s_{1}, \dots, s_{t}

be integers such that

0 = s_{0} < s_{1} < s_{2} < \dots < 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

| C_{u} | = s_{u} - s_{u - 1} for u = 1, \dots, t .

Fix an integer

j \in {1, 2, \dots, ℓ}

, and consider the increasing sequence

a_{1} + b_{j} < a_{2} + b_{j} < \dots < 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 .

k_{j, u} \geq 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}

\sum_{\binom{u = 1}{k_{j, u} \geq 1}}^{t} (k_{j, u} - 1) = k - \sum_{\binom{u = 1}{k_{j, u} \geq 1}}^{t} 1 \geq k - t .

Since the set

C

contains exactly

(k - 1) ℓ

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}^{ℓ} \sum_{\binom{u = 1}{k_{j, u} \geq 1}}^{t} (k_{j, u} - 1) \geq ℓ (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

(\binom{| C_{u} |}{2})

pairs, and so the number of pairs contained in the sets

C_{1}, \dots, C_{t}

is at most

\sum_{u = 1}^{t} (\binom{| C_{u} |}{2}) .

Therefore,

\sum_{u = 1}^{t} (\binom{| C_{u} |}{2}) \geq ℓ (k - t) .

We specialize this inequality as follows: Let

t = [\frac{k}{2}]

and

m = q t + r,

where

0 \leq r \leq t - 1 .

Then

q \leq \frac{m}{t} \leq \frac{2 m}{k - 1} .

Choose the integers

s_{1}, \dots, s_{t - 1}

such that

| C_{u} | = q + 1 for u = 1, \dots, r

and

| C_{u} | = q for u = r + 1, \dots, t .

Then

\sum_{u = 1}^{t} (\binom{| C_{u} |}{2}) \leq t (\binom{q + 1}{2}) \leq \frac{k}{2} (\binom{\frac{2 m}{k - 1} + 1}{2}) < \frac{k}{4} {(\frac{2 m}{k - 1} + 1)}^{2}

and so

\frac{k}{4} {(\frac{2 m}{k - 1} + 1)}^{2} > \frac{ℓ k}{2} .

This implies that

m > \frac{k - 1}{2} (\sqrt{2 ℓ} - 1) .

k \geq 3

and

ℓ \geq 3,

then

m > \frac{k \sqrt{ℓ}}{3} .

This completes the proof.

3 Distinct pairs of consecutive differences

Let

A = {a_{1}, a_{2}, \dots, a_{k}}

and

A^{'} = {a_{1}^{'}, a_{2}^{'}, \dots, a_{k}^{'}}

be nonempty sets of real numbers, where

a_{1} < a_{2} < \dots < a_{k}

and

a_{1}^{'} < a_{2}^{'} < \dots < a_{k}^{'}

. Let

d_{i} = a_{i + 1} - a_{i}

for

i = 1, \dots, k - 1

and

d_{i}^{'} = a_{i + 1}^{'} - a_{i}^{'}

for

i = 1, \dots, k - 1 .

The sets

A

and

A^{'}

have distinct pairs of consecutive differences if there exists a one-to-one map

σ : {1, 2, \dots, k - 1} \to {1, 2, \dots, k - 1}

such that the

k - 1

ordered pairs

(d_{i}, d_{σ (i)}^{'})

are distinct.

Theorem 3. Let

A

and

A^{'}

be nonempty finite sets of real numbers such that

k = | A | = | A^{'} |

and the sets

A

and

A^{'}

have distinct pairs of consecutive differences. Let

B

, and

B^{'}

be nonempty finite sets of real numbers with

| B | = ℓ

, and

| B^{'} | = ℓ^{'}

Then

| A + B | \cdot | A^{'} + B^{'} | ≫ {(k^{3} ℓ ℓ^{'})}^{1 / 2} .

ℓ = ℓ^{'} = k,

then

| A + B | \cdot | A^{'} + B^{'} | ≫ k^{5 / 2} .

Let

A = {a_{1}, a_{2}, \dots, a_{k}}

and

A^{'} = {a_{1}^{'}, a_{2}^{'}, \dots, a_{k}^{'}}

, where

a_{1} < a_{2} < \dots < a_{k}

and

a_{1}^{'} < a_{2}^{'} < \dots < a_{k}^{'}

. Let

d_{i} = a_{i + 1} - a_{i}

for

i = 1, \dots, k - 1

and

d_{i}^{'} = a_{i + 1}^{'} - a_{i}^{'}

for

i = 1, \dots, k - 1

. Let

σ : {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_{σ (i)}^{'})

are distinct. Let

B = {b_{1}, b_{2}, \dots, b_{ℓ}}

and

B^{'} = {b_{1}, b_{2}, \dots, b_{ℓ^{'}}}

, where

b_{1} < b_{2} < \dots < b_{ℓ}

and

b_{1}^{'} < b_{2}^{'} < \dots < b_{ℓ^{'}}^{'}

Let

1 \leq i \leq k - 1

1 \leq j \leq ℓ,

and

1 \leq j^{'} \leq ℓ^{'} .

We consider quadruples of the form

\begin{matrix} (a_{i} + b_{j}, a_{i + 1} + b_{j}, a_{σ (i)}^{'} + b_{j^{'}}^{'}, a_{σ (i) + 1}^{'} + b_{j^{'}}^{'}) . \end{matrix}

(3)

Suppose that

1 \leq u \leq k - 1

1 \leq v \leq ℓ,

and

1 \leq v^{'} \leq ℓ^{'},

and that

(a_{i} + b_{j}, a_{i + 1} + b_{j}, a_{σ (i)}^{'} + b_{j^{'}}^{'}, a_{σ (i) + 1}^{'} + b_{j^{'}}^{'}) = (a_{u} + b_{v}, a_{u + 1} + b_{v}, a_{σ (u)}^{'} + b_{v^{'}}^{'}, a_{σ (u) + 1}^{'} + b_{v^{'}}^{'}) .

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_{σ (i)}^{'} = (a_{σ (i) + 1}^{'} + b_{j^{'}}^{'}) - (a_{σ (i)}^{'} + b_{j^{'}}^{'}) = (a_{σ (u) + 1}^{'} + b_{v^{'}}^{'}) - (a_{σ (u)}^{'} + b_{v^{'}}^{'}) = d_{σ (u)}^{'} .

Therefore,

(d_{i}, d_{σ (i)}^{'}) = (d_{u}, d_{σ (u)}^{'}) .

The sets

A

and

A^{'}

have matching consecutive differences with permutation

σ

, 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^{'} = v^{'} .

This implies that there are

(k - 1) ℓ ℓ^{'}

distinct quadruples of the form ( 3 ).

Consider the sumsets

A + B

and

A^{'} + B^{'}

A + B = C = {c_{1}, \dots, c_{m}},

where

| C | = m

and

c_{1} < \dots < c_{m} .

Let

A^{'} + B^{'} = C^{'} = {c_{1}^{'}, \dots, c_{m^{'}}^{'}},

where

| C^{'} | = m^{'}

and

c_{1}^{'} < \dots < c_{m^{'}}^{'} .

Let

s_{0}, s_{1}, \dots, s_{t}

be integers such that

0 = s_{0} < s_{1} < s_{2} < \dots < 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

| C_{u} | = s_{u} - s_{u - 1} for u = 1, \dots, t .

Similarly, let

s_{0}^{'}, s_{1}^{'}, \dots, s_{t^{'}}^{'}

be integers such that

0 = s_{0}^{'} < s_{1}^{'} < s_{2}^{'} < \dots < s_{t - 1}^{'} < s_{t}^{'} = m^{'},

and partition the set

C^{'}

into

t^{'}

pairwise disjoint sets

C_{1}^{'}, \dots, C_{t^{'}}^{'}

as follows:

C_{u^{'}}^{'} = {c_{s_{u^{'} - 1} + 1}^{'}, \dots, c_{s_{u^{'}}}^{'}}

for

u^{'} = 1, \dots, t^{'} .

Fix an integer

j \in {1, 2, \dots, ℓ}

, and consider the increasing sequence

a_{1} + b_{j} < a_{2} + b_{j} < \dots < 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 .

k_{j, u} \geq 1,

then the set

C_{u}

contains exactly

k_{j, u} - 1

subsets of the form

\begin{matrix} {a_{i} + b_{j}, a_{i + 1} + b_{j}}, \end{matrix}

(4)

and so the number of pairs with fixed

j

contained in the sets

C_{1}, \dots, C_{t}

\sum_{\binom{u = 1}{k_{j, u} \geq 1}}^{t} (k_{j, u} - 1) = k - \sum_{\binom{u = 1}{k_{j, u} \geq 1}}^{t} 1 \geq 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, ℓ,

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) ℓ^{'} .

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) ℓ ℓ^{'} .

Similarly, the number of quadruples of the form ( 3 ) whose third and fourth coordinates do not belong to one of the sets

C_{1}^{'}, \dots, C_{t^{'}}^{'}

is at most

(t^{'} - 1) ℓ ℓ^{'} .

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^{'}}^{'}

is at most

(t + t^{'} - 2) ℓ ℓ^{'} .

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^{'}}^{'}

is bounded below by

(k - 1) ℓ ℓ^{'} - (t + t^{'} - 2) ℓ ℓ^{'} = (k - t - t^{'} + 1) ℓ ℓ^{'} .

On the other hand, for each

u = 1, \dots, t

and

u^{'} = 1, \dots, t^{'},

the number of quadruples

(x, y, z, w)

such that

x \neq y

and

{x, y} \subseteq C_{u}

for

u = 1, \dots, t

, and also

z \neq w

and

{z, w} \subseteq C_{u^{'}}^{'}

is exactly

(\binom{| C_{u} |}{2}) (\binom{| C_{u^{'}}^{'} |}{2})

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^{'}}^{'}

\sum_{u = 1}^{t} \sum_{u^{'} = 1}^{t^{'}} (\binom{| C_{u} |}{2}) (\binom{| C_{u^{'}}^{'} |}{2}) \leq \frac{1}{4} \sum_{u = 1}^{t} \sum_{u^{'} = 1}^{t^{'}} | C_{u} |^{2} | C_{u^{'}}^{'} |^{2} .

Therefore,

\begin{matrix} (k - t - t^{'} + 1) ℓ ℓ^{'} \leq \frac{1}{4} \sum_{u = 1}^{t} \sum_{u^{'} = 1}^{t^{'}} | C_{u} |^{2} | C_{u^{'}}^{'} |^{2} . \end{matrix}

(5)

If we let

t = t^{'} = k / 4

and

| C_{u} | = m / t = 4 m / k

and

C_{u^{'}}^{'} | = 4 m^{'} / k,

then

\frac{k ℓ ℓ^{'}}{2} \leq \frac{1}{4} \frac{k^{2}}{16} \frac{16 m^{2}}{k^{2}} \frac{16 {m^{'}}^{2}}{k^{2}} = \frac{4 (m m^{'})^{2}}{k^{2}},

and so

(m m^{'})^{2} \geq \frac{k^{3} ℓ ℓ^{'}}{8} .

ℓ = ℓ^{'} = k,

then

| A + B | \cdot | A^{'} + B^{'} | = m m^{'} ≫ 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 {| A + B |, | F (A) + C | \geq c n^{5 / 4} .

In particular,

| A + F (A) | \geq c n^{5 / 4} .

The two sets

A

and

F (A)

have distinct pairs of consecutive differences with

σ = I,

the identity map. For the second inequality set

B = F (A)

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 | = (\binom{| S |}{2}),

and

| S |

is odd. Then there is a list

L

of the elements of

S

with repetitions, consists of

k = (\binom{| S |}{2})

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 \leq i \leq k}

The set

A

has the property that the consecutive differences are distinct, and it is not difficult to see that

| A + [k] | \leq | S |^{3} \leq c k^{3 / 2},

where

[k]

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

A

is a convex set of integers?

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

References

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.

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

József Solymosi