Convexity and sumsets

György Elekes, Melvyn B. Nathanson, Imre Z. Ruzsa

Abstract. We find a lower bound for the cardinality of a sumset A+B of two finite sets on the plane, one of which lies on a convex curve. If both sets have n elements, this estimate is cn^{2}, best possible in this generality. This yields a common treatment of the Erdős-Szemerédi problem of estimating max(|A + A|, |AA|), another problem of them about the number of distinct values of a_{i} + 1/a_{j}, and a result of Hegyvári about the sums b_{i} + b_{j} where b_{i+1} − b_{i} is monotonic.

1. Introduction

Erdős and Szemerédi [3] proved that for any set A of n real numbers either the set of sums

A + A = {a_{1} + a_{2} : a_{1}, a_{2} ∈ A}

or the set of products

AA = {a_{1}a_{2} : a_{1}, a_{2} ∈ A}

has at least cn^{α} elements, with positive constants c and α > 1. They did not specify the value of α. Nathanson [6] gave the value α = 32/31, and Elekes [2] improved it to 5/4.

Hegyvári [4] proved, confirming a conjecture of Erdős, that any set B = {b_{1}, ..., b_{n}} of n integers such that b_{i} < b_{i+1} and b_{i} − b_{i−1} < b_{i+1} − b_{i} for all i satisfies

|B − B| ≥ cn\frac{log n}{log log n}.

The third author (unpublished) improved this estimate to cn^{4/3}, and as a common generalization of these problems formulated the following conjecture. Let A ⊂ ℝ be a finite set, |A| = n, and let f be a strictly convex (or concave) function, defined on an interval containing A. Write

f(A) = {f(a) : a ∈ A}.

Then we have

max{|A + A|, |f(A) + f(A)|} ≥ cn^{α}

with constants c > 0 and α > 1.

The result of Erdős and Szemerédi would follow by considering f(x) = log x, that of Hegyvári by placing the points (i, b_{i}) on a suitable convex curve. (Details will be given in Section 3.)

In this note we establish a general result which involves these as special cases and has further applications, among others to a problem of Erdős and Szemerédi from [3] about the number of the sums

a_{1} + 1/a_{2}, a_{1}, a_{2} ∈ A.

(See Corollaries 3.7 and 3.8.) The method is an extension of the one used by the first author [4].

2. The main result

Let A ⊂ ℝ be a finite set, |A| = n, and let f be a strictly convex or concave function, defined on an interval containing A. Write

f(A) = {f(a) : a ∈ A},  (2.1)
S = {(a, f(a)) : a ∈ A} ⊂ ℝ^{2}.  (2.2)

Theorem 1.

For every finite set T ⊂ ℝ^{2} we have

|S + T | ≥ c min(n|T |, n^{3/2}|T |^{1/2})  (2.3)

with a certain absolute constant 0 < c < 1.

For the proof we need some preparation.

Definition 2.1. A system Γ of continuous plane curves (homeomorphic images of an interval) is a pseudo–line system if any two members of Γ share at most one point in common.

Lemma 2.2.

Let n and N be positive integers. Let, moreover, P be a set of N distinct points in the plane and e_{1}, e_{2}, …, e_{m} some (also distinct) pseudo lines. If each of the e_{i} contains n or more points of P , then

N ≥ c min(n^{3/2}, nm)  (2.4)

with a positive absolute constant c.

This is an immediate consequence of a result of Clarkson et al. [1] (see also [7]), which asserts that the number of incidences, which is in our case at least mn, is bounded from above by a constant multiple of N+m+(Nm)^{3/2}. For straight lines it was proved by Szemerédi and Trotter [10]. (See also Pach and Sharir [8] for generalizations.) Recently, a simple proof was found by Székely [9].

Proof of Theorem 1.

Let I ⊃ A be an interval on which f is defined. We have

S ⊂ J = {(x, f(x) : x ∈ I}.

Our system Γ of pseudo-lines will consist of the translated copies J +t of this curve. The fact that each two intersect in at most one point is a direct consequence of convexity (or concavity, resp.). The number of curves is m = |T |. On these curves we consider the points

(a, f(a)) + t, a ∈ A, t ∈ T.

On each curve the number of points is n = |A|, consistent with the notations in both the Theorem and the Lemma. The total number of points is N = |S + T |. We apply (2.4) to get

N = |S + T | ≥ c min(n^{3/2}m^{1/2}, nm)

as claimed.

Remark 2.3. For |T | ≤ n the bound is cn|T |, and n|T | is obviously an upper bound, thus we have the exact order of magnitude. The lower bound can also easily be obtained directly, by observing that the |T | sets of the form S + t, t ∈ T each have n elements and the intersection of any two has at most one element.

For n ≤ |T | ≤ n^{3} the bound is cn^{3/2}|T |^{1/2}, and in this generality this is also best possible. Namely, let A = {1, 2, ..., n} and f(x) = x^{2}. Now consider the set

T = {(i, j) : 1 ≤ i ≤ k, 1 ≤ j ≤ nk}.  (2.5)

We have |T | = nk^{2}, and an easy calculation yields (we assume k ≤ n) that |S+T | ≪ kn^{2}.

For |T | > n^{3} the bound becomes worse than |T |. In this range nothing essentially better than |T | can be claimed. This is shown by the previous example for k > n.

3. Applications

The most interesting applications arise by substituting direct products into T. Put T = C × D, and for simplicity assume that |T | = |C||D| ≥ n. Since S ⊂ A × B, we have

S + T ⊂ (A + C) × (f(A) + D).  (3.1)

Thus from Theorem 1 we obtain the following.

Corollary 3.1. Assume that C, D ⊂ ℝ, and |C||D| ≥ n. We have

|A + C||f(A) + D| ≥ cn^{3/2}(|C||D|)^{1/2}.  (3.2)

The case C = A, D = f(A) of (3.2) gives the following. Corollary 3.2. We have

|A + A||f(A) + f(A)| ≥ cn^{5/2}.  (3.3)

In particular, either A + A or f(A) + f(A) has at least cn^{5/4} elements.

We can use this to improve Hegyvári’s result mentioned in the Introduction. Corollary 3.3. Let B = {b_{1}, ..., b_{n}} be a set of n real numbers such that b_{i} < b_{i+1} and b_{i} − b_{i−1} <

b_{i+1} − b_{i} for all i. We have

|B + D| ≥ c_{1}n^{3/2}.

for every set D with |D| = n, in particular

|B + B| ≥ c_{1}n^{3/2}.

and

|B − B| ≥ c_{1}n^{3/2}.

Proof. This condition implies that we can find a convex function f such that f(i) = b_{i} for i = 1, ..., n. We apply (3.2) to this function and the sets A = C = {1, 2, ..., n}, where we have f(A) = B. Since |A + A| = 2n − 1, we get |B + D| ≥ (c/2)n^{3/2}.

The case C = f(A), D = A of (3.2) gives the following.

Corollary 3.4. For every set A and convex function f we have

|A + f(A)| ≥ cn^{5/4}.  (3.4)

We introduce the multiplicative analog of our notations

AB = {ab : a ∈ A, b ∈ B}.

By considering f(x) = log x, after obvious transformations from Corollary 3.3 we obtain the following.

Corollary 3.5. Let A, C, D be sets of positive reals. We have

|A + C||AD| ≥ n^{3/2}(|C||D|)^{1/2}.  (3.5)

With C = D = A this reduces to the following result from [2].

Corollary 3.6. Let A be a set of n positive real numbers. We have

|A + A||AA| ≥ cn^{5/2};  (3.6)

in particular, either A + A or AA has at least n^{5/4} elements.

By considering f(x) = 1/x, with the notation

1/A = {1/a : a ∈ A}  (3.7)

corollaries 3.2 and 3.4 yield the following results.

Corollary 3.7. Let A be a set of n positive real numbers. We have

|A + A||1/A + 1/A| ≥ cn^{5/2};  (3.8)

in particular, either A + A or 1/A + 1/A has at least n^{5/4} elements.

Corollary 3.8. We have always

|A + 1/A| ≥ n^{5/4}.  (3.9)

We conjecture that the exponents in (3.6) and (3.8) should have the value 3 − ε. We think that the proper exponent in (3.9) is 2 − ε. We have an example of a set where

|A + 1/A| ≪ n^{2−c/ log log n},

and for every δ > 0 an example where

|A + A| ≪ n^{1+δ}, |AA| ≪ n^{2−c(δ)/ log log n}.

4. More than two summands

We write Sk = S + S + ... + S, for a repeated addition of k identical sets.

Theorem 2.

Let S, T be as in Theorem 1. We have for every integer k ≥ 1

|Sk + T | ≥ c′n^{3(1−2^{−k})}|T |^{2^{−k}}  (4.1)

if |T | ≥ n, and

|Sk + T | ≥ c′n^{3−2^{−(k−2)}}|T |^{2^{−k−1}}  (4.2)

if |T | < n, with a certain absolute constant 0 < c′ < 1.

Proof. This follows by a repeated application of Theorem 1 to the sets T, S + T, ..., S(k − 1) + T. For the constant we obtain the value

c^{2−2^{1−k}};  (4.3)

since the exponent does not exceed 2, we may put c′ = c^{2}.

Remark 4.1. Unlike Theorem 1, Theorem 2 is probably not best possible for k ≥ 2.

By putting T = S into Theorem 2 we obtain the following.

Corollary 4.2.

For every integer k ≥ 1 we have

|Sk| ≥ cn^{3−2^{−(k−2)}}.  (4.4)

Remark 4.3. For the set S = {(i, i^{2}) : 1 ≤ i ≤ n} we have

|S3| ≍ \frac{n^{3}}{\sqrt{log n}}, |S4| ≍ n^{3}.  (4.5)

We conjecture that this example is nearly extremal, that is, we have

|S3| ≫ n^{3−ε}, |S4| ≫ n^{3}  (4.6)

for every set S. This would also improve Theorem 2 for k ≥ 3.

Here the second claim follows from Cauchy’s lemma (see e. g. Nathanson [7, p. 31]). This yields that (x, y) ∈ S4 if x, y are odd, 1 ≤ x ≤ n and x^{2}/4 ≤ y ≤ x^{2}/3.

To get the first claim, consider the numbers

a = i + j + k, b = i^{2} + j^{2} + k^{2}.

These satisfy

d = 12b − 4a^{2} = (2i − j − k)^{2} + 3(j − k)^{2}.

This shows that d can contain only primes ≡ 1 (mod 6) with an odd exponent. The number of admissible values of d up to x is ∼ c(x/\sqrt{log x} and we obtain the upper estimate by grouping the pairs (a, b) according to the value of d. Conversely, let d is a number, divisible by 4 and free of primes ≡ −1 (mod 6). Tt has a representation in the form s^{2} + 3t^{2}, and we must have s ≡ t (mod 2). For an arbitrary value of k the integers

j = t + k, i = \frac{t + s}{2} + k

yield a pair (a, b) with this value of d, and we have

a = i + j + k = \frac{3t + s}{2} + 3k.

The last equation shows that different values of k yield different values of a. Obviously if we start with d < (n/2)^{2}, take nonnegative values of s, t and 0 < k < n/2, then i, j, k < n and we find a point in our set S3.

Put T = C × D, and assume that |T | = |C||D| ≥ n. Since S ⊂ A × B, we have

Sk + T ⊂ (Ak + C) × (f(A)k + D).  (4.7)

Thus from Theorem 2 we obtain the following.

Corollary 4.4. Assume that C, D ⊂ ℝ, and |C||D| ≥ n. For every integer k ≥ 1 we have

|Ak + C||f(A)k + D| ≥ c′n^{3(1−2^{−k})}(|C||D|)^{2^{−k}}.  (4.8)

The case C = A, D = f(A) of (4.8) gives the following.

Corollary 4.5. For every integer k ≥ 2 we have

|Ak||f(A)k| ≥ cn^{3−2^{1−k}}.  (4.9)

We introduce the multiplicative analog of our notation

A^{k} = AA...A, k factors.

By considering f(x) = log x, from Corollary 4.5 we obtain the following.

Corollary 4.6. For every integer k ≥ 2 we have

|Ak||A^{k}| ≥ cn^{3−2^{1−k}}.  (4.10)

We conjecture that the exponent should go to infinity here rather than to 3. However, to obtain such a result we would need to find a more specific approach, since, as the previous examples indicate, the corresponding result with general convex function cannot yield exponents exceeding 3.

It would be interesting to find analogous result for different summands. We can iterate Theorem 1 with different sets, but because of its alternative nature a branching can occur at each place and the results are complicatted and not satisfactory.

References

[1] Clarkson, K.; Edelsbrunner, H.; Guibas, L.; Sharir, M.; Welzl, E., Combinatorial complexity bounds for arrangements of curves and surfaces, Discrete Comp. Geom. 5(1990), 99–106.

[2] Elekes, Gy., On the number of sums and products, Acta Arithmetica 81(1997), 365–367.

[3] Erdős, P.; Szemerédi, E., On sums and products of integers, in: Studies in Pure Math. to the memory of P. Turán, Akadémiai Kiadó, Budapest (1983), 213–218.

[4] Hegyvári, N., On consecutive sums in sequences, Acta Math. Acad. Sci. Hungar. 48(1986), 193-200.

[5] Nathanson, M. B., Additive number theory: The classical bases, Springer–Verlag, New York–Berlin, Graduate Texts in Mathematics 164 1996.

[6] Nathanson, M. B., On sums and products of integers, Proc. Amer. Math. Soc. 125(1997), 9–16.

[7] Pach, J.; Agarwal, P. K., Combinatorial geometry, Wiley & Sons, New York – Chichester 1995.

[8] Pach, J.; Sharir, M., Repeated angles in the plane and related problems, J. Comb. Th., ser. A 59(1990), 12-22.

[9] Székely, L. A., Crossing numbers and hard Erdős problems in discrete geometry, Comb. Prob. Comp. 11(1993), 1–10.

[10] Szemerédi, E.; Trotter, W. T. Jr., Extremal problems in discrete geometry, Combinatorica 3(1983), 381–392. Printed 1999.2.28.