GAPS IN DENSE SIDON SETS

Javier Cilleruelo

Departamento de Matemáticas, Universidad Autónoma de Madrid, Madrid, Spain 28049

                       franciscojavier.cilleruelo@uam.es

Received: 3/23/00, Accepted: 8/22/00, Published: 8/24/00

Abstract

We prove that if A ⊂ [1, N] is a Sidon set with N^{1/2}−L elements, then any interval I ⊂ [1, N] of length cN contains c|A| + E_{I} elements of A, with |E_{I}| ≤ 52N^{1/4}(1 + c^{1/2}N^{1/8})(1 + L_{+}^{1/2}N^{−1/8}), L_{+} = max{0, L}. In particular, if |A| = N^{1/2} + O(N^{1/4}), and g(A) is the maximum gap in A, we deduce that g(A) ≪ N^{3/4}. Also we prove that, under this condition, the exponent 3/4 is sharp.

1. Introduction

We say that A is a Sidon set if all the sums a + a′, a ≤ a′, are different. Erdős and Turan [5] proved that if A ⊂ [1, N] is a Sidon set then |A| ≤ N^{1/2} + O(N^{1/4}). On the other hand, Bose and Chowla [1] proved that if N = p^{2} + p + 1, then there exists a Sidon set A ⊂ [1, N] with p elements; i.e, the upper bound (1.1) is sharp except for the error term.

Sidon sets of large size have notable properties of regularity. In [7], M. Koluntzakis proved that the elements of a Sidon set of large size, |A| ∼ N^{1/2}, are well distribuited in the classes of residues of small modulo. See [5] for an elementary proof of this result.

Erdős and Freud [4] proved that if |A| ∼ N^{1/2} then the elements of A are well distributed in the interval [1, N].

Theorem A (Erdős-Freud). Let c > 0 and A ⊂ [1, N] a Sidon set with |A| ∼ N^{1/2} elements. Then, any interval of length cN contains ∼ cN^{1/2} elements.

S.W. Graham [6] has proved a more precise result.

Theorem B (S. Graham). Let A ⊂ [1, N] be a Sidon set with N^{1/2} + O(N^{1/4}) elements. Then, any interval of length cN contains cN^{1/2} + O(N^{3/8}) elements.

Typeset by AMS-TEX

2 INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 0 (2000), #A11

If we denote by g(A) = max_{a_{k−1},a_{k}∈A}{a_{k} − a_{k−1}} the maximum gap in A, from the Theorem B it is easy to deduce that if A is a Sidon set A ⊂ [1, N] with N^{1/2}+O(N^{1/4}), then g(A) ≪ N^{7/8}.

In this paper we shall use an identity (Lemma 2.1), which was introduced in [2] and [3], to obtain a better result.

Theorem 1.1. Let A ⊂ [1, N] a Sidon set with N^{1/2} − L elements. Then, any interval of length cN contains c|A| + E_{I} elements of A, with

|E_{I}| ≤ 52N^{1/4}(1 + c^{1/2}N^{1/8})(1 + L_{+}^{1/2}N^{−1/8}), L_{+} = max{0, L}.

In particular we deduce from this theorem the following corollary for gaps.

Corollary 1.1. If A ⊂ [1, N] is a Sidon set and |A| = N^{1/2} + O(N^{1/4}), then g(A) ≪ N^{3/4}.

It is easy to see that the exponent 3/4 is the best possible if A ⊂ [1, N] is a Sidon set with |A| = N^{1/2} +O(N^{1/4}). Consider N = p^{2} +p+1, and a Sidon set A, A ⊂ [1, N] with p ≥ \sqrt{N} −1 elements. If we split the interval [1, N] in intervals of length [N^{3/4}], then, one of them contains less than 2N^{1/4} elements. If we remove these elements from A we have a Sidon set A′ with |A′| = N^{1/2} + O(N^{1/4}) elements and g(A′) ≫ N^{3/4}.

We don’t know how to derive a better estimate for g(A) when the error term is less than N^{1/4}. It is related with the difficulty of improving the error term in the upper bound for finite Sidon sets. It would be interesting to know a good upper bound for g(A) when A is a Sidon set of maximal size. Maybe, it is possible an upper bound like g(A) ≪ N^{1/2+ϵ}.

It should be noted that the classical construction of Erdős and Turan [5] of Sidon sets, A_{p} = {2kp + (k^{2})_{p} : k = 0, 1, …, p − 1}, gives g(A) ≪ N^{1/2} for these sets. It seems not to be the case for the Ruzsa’s construction [8] of finite Sidon sets. Numerical and heuristic arguments suggest that g(A)/N^{1/2} → ∞ in this case. In particular, it would imply that the Erdős’s Conjecture, F (N) ≤ N^{1/2} + O(1), is not true.

2. Proofs

The proof of the following lemma can be found in [2] or [3].

Lemma 2.1. Let A ⊂ [1, N] be a sequence of integers. Then, for any integer H ≥ 1 we have

2 ∑_{1≤h≤H} d(h)(H − h) = \frac{H^{2}|A|^{2}}{N + H − 1} − H|A| + D_{H},

where

D_{H} = ∑_{1≤n≤N+H−1} (A(n) − A(n − H) − \frac{H|A|}{N + H − 1})^{2} ,

A(n) is the counting function of A and d(h) = #{h = a − a′; a, a′ ∈ A}. □

A(n) − A(n − H) is the number of elements of A lying in the interval (n − H, n] and the quantity \frac{H|A|}{N+H−1} is the expected value of A(n) − A(n − H). Then, D_{H} is a measure of the distribution of the elements of A in the interval [1, N + H − 1].

The argument of the proof of the Theorem 1.1 is the following: If |A| is close to N^{1/2}, (L small), then D_{H} is “small” and consequently, the number of elements of A lying in intervals of length H is “close”, at least in average, to the expected number. From that we can deduce a “good” distribution in any interval I = (αN, βN]. Upper and lower bounds for the error E_{I} = |A ∩ I| − (β − α)|A| are obtained in two different steps (Lemma 2.3 and Lemma 2.4).

Lemma 2.2. If A ⊂ [1, N] is a Sidon set with |A| = N^{1/2} − L then, for any integer H we have

D_{H} ≤ \frac{3H^{2}L_{+}}{N^{1/2}} + \frac{H^{3}}{N} + 2HN^{1/2}

where L_{+} = max{0, L}.

Proof. We apply Lemma 2.1 to the sequence A. Since A is a Sidon set, hence d(h) ≤ 1 for any integer h ≥ 1 and 2 ∑_{1≤h≤H−1} d(h)(H − h) ≤ H^{2}. Also we use the trivial estimate for the size of a Sidon set, |A| ≤ 2N^{1/2}.

D_{H} ≤ H^{2} − \frac{H^{2}|A|^{2}}{N + H − 1} + H|A| = \frac{H^{2}N + H^{3} − H^{2} − H^{2}|A|^{2}}{N + H − 1} + H|A|

≤ \frac{H^{2}(N−|A|^{2})}{N} + \frac{H^{3}}{N} + 2HN^{1/2}.

If L ≤ 0 , then D_{H} ≤ \frac{H^{3}}{N} + 2HN^{1/2}.

If L > 0, then D_{H} ≤ \frac{H^{2}}{N} (N^{1/2} + |A|)L_{+} + \frac{H^{3}}{N} + 2HN^{1/2} ≤ \frac{3H^{2}L_{+}}{N^{1/2}} + \frac{H^{3}}{N} + 2HN^{1/2}. □

Let I = (αN, βN], c = β − α and we write |A ∩ I| = c|A| + E_{I}. We will choose H = [N^{3/4}] in all the proofs.

4 INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 0 (2000), #A11

Lemma 2.3. E_{I} ≤ 10N^{1/4}(c^{1/2}N^{1/8} + 1)(L_{+}^{1/2}N^{−1/8} + 1). Proof. We write I_{H} = (αN, βN + H], then cN + H − 1 ≤ |I_{H}| ≤ cN + H + 1. We have

∑_{n∈I_{H}} A(n) − A(n − H) ≥ H|A ∩ I|,

since each a ∈ A ∩ I is counted H times in the sum. Then,

∑_{n∈I_{H}} (A(n) − A(n − H) − \frac{H|A|}{N + H − 1}) ≥ H|A ∩ I| − \frac{|I_{H}|H|A|}{N + H − 1}

= E_{I}H + H|A| (c − \frac{|I_{H}|}{N + H − 1}) ≥ E_{I}H − H|A|\frac{(1 − c)(H + 1)}{N + H − 1} ≥ E_{I}H − \frac{H^{2}|A|}{N}.

Then

E_{I} ≤ H^{−1} ∑_{n∈I_{H}} (A(n) − A(n − H) − \frac{H|A|}{N + H − 1}) + \frac{H|A|}{N}.

Now we apply Cauchy’s inequality, Lemma 2.1 and the trivial estimates |A| ≤ 2N^{1/2}, N^{3/4}/2 ≤ H ≤ N^{3/4} to get

E_{I} ≤ H^{−1}|I_{H}|^{1/2}D_{H}^{1/2} + \frac{H|A|}{N}

≤ H^{−1} ((cN)^{1/2} + (H + 1)^{1/2}) (\frac{\sqrt{3}HL_{+}^{1/2}}{N^{1/4}} + \frac{H^{3/2}}{N^{1/2}} + \sqrt{2}H^{1/2}N^{1/4}) + \frac{H|A|}{N}

≤ 2N^{−3/4} (c^{1/2}N^{1/2} + \sqrt{2}N^{3/8}) (\sqrt{3}N^{1/2}L_{+}^{1/2} + N^{5/8} + \sqrt{2}N^{5/8}) + 2N^{1/4}

≤ 10N^{1/4} (c^{1/2}N^{1/8} + 1) (L_{+}^{1/2}N^{−1/8} + 1) . □

Lemma 2.4. −E_{I} ≤ 52N^{1/4}(c^{1/2}N^{1/8} + 1)(L_{+}^{1/2}N^{−1/8} + 1). Proof.

∑_{n∈I_{H}} A(n) − A(n − H) ≤ H (|A ∩ I| + |A ∩ (αN − H, αN]| + |A ∩ (βN, βN + H]|) .

We apply Lemma 2.3 to the intervals (αN − H, αN] and (βN, βN + H] to obtain an upper bound for the last two terms.

|A∩(αN −H, αN]|+|A∩(βN, βN +H]| ≤ 2\frac{H}{N} |A|+20N^{1/4} (\frac{H^{1/2}N^{1/8}}{N^{1/2}} + 1) (L_{+}^{1/2}N^{−1/8} + 1)

≤ 4N^{1/4} + 40N^{1/4}(L_{+}^{1/2}N^{−1/8} + 1) ≤ 44N^{1/4} + 40N^{1/8}L_{+}^{1/2}.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 0 (2000), #A11 5

Then,

∑_{n∈I_{H}} (A(n) − A(n − H) − \frac{H|A|}{N + H − 1}) ≤ H|A∩I|− \frac{|I_{H}|H|A|}{N + H − 1} +H (44N^{1/4} + 40N^{1/8}L_{+}^{1/2})

= E_{I}H + H|A| (c − \frac{|I_{H}|}{N + H − 1}) + H (44N^{1/4} + 40N^{1/8}L_{+}^{1/2})

≤ E_{I}H + H(44N^{1/4} + 40N^{1/8}L_{+}^{1/2}),

because |I_{H}| ≥ cN + H − 1.

Finally we apply Cauchy inequality and Lemma 2.2 to obtain

−E_{I} ≤ 44N^{1/4} + 40N^{1/8}L_{+}^{1/2} + H^{−1} ∑_{n∈I_{H}} |A(n) − A(n − H) − \frac{H|A|}{N + H − 1}|

≤ 44N^{1/4} + 40N^{1/8}L_{+}^{1/2} + 2N^{−3/4}|I_{H}|^{1/2}D_{H}^{1/2}

≤ 44N^{\frac{1}{4}} + 40N^{\frac{1}{8}} L+^{\frac{1}{2}} + 2N^{\frac{−3}{4}} ((cN)^{1/2} + (H + 1)^{1/2}) (\frac{\sqrt{3}HL_{+}^{1/2}}{N^{1/4}} + \frac{H^{3/2}}{N^{1/2}} + \sqrt{2}H^{1/2}N^{1/4})

≤ 44N^{1/4} + 40N^{1/8}L_{+}^{1/2} + 2N^{−3/4} (c^{1/2}N^{1/2} + \sqrt{2}N^{3/8}) (\sqrt{3}N^{1/2}L_{+}^{1/2} + N^{5/8} + \sqrt{2}N^{5/8}) ≤ 52N^{1/4}(1 + c^{1/2}N^{1/8})(1 + L_{+}^{1/2}N^{−1/8}). □

Lemma 2.3 and Lemma 2.4 imply Theorem 1.1. To prove Corollary 1.1, suppose that A = N^{1/2} − L, with L_{+} ≤ kN^{1/4}, and let I be any interval of length k′N^{3/4}. If we apply Lemma 2.4 we have

|A ∩ I| > \frac{k′}{N^{1/4}} |A| − 52N^{1/4}(1 + k′^{1/2})(1 + k^{1/2}) > k′N^{1/4} − kk′ − 52N^{1/4}(1 + k′^{1/2})(1 + k^{1/2}).

If we take k′ large enough, k′ > 10000k, then |A ∩ I| > 0 for any interval of length greater than k′N^{3/4}. References

1. R.C. Bose and S. Chowla, Theorems in the additive theory of numbers, Comment. Math. Helvet 37 (1962-3), 141-147.

2. J. Cilleruelo, New upper bounds for B_{h} sequences, (preprint).

3. J. Cilleruelo and G. Tenenbaum, An overlapping lemma and applications, (preprint).

4. P. Erdős and R. Freud, On Sums of a Sidon-Sequence, J. Number Theory 38 (1991), 196-205.

5. P. Erdős and P. Turan, On a problem of Sidon in additive number theory and on some related problems, J. London Math. Soc. 16 (1941), 212-215;P. Erdős, Addendum 19 (1944), 208.

6. S.W. Graham, B_{h} sequences, Proceedings of a Conference in Honor of Heini Halberstam (B.C.Berndt, H.G.Diamond, A.J.Hildebrand, eds.), Birkhauser, 1996, pp. 337-355.

7. M. Kolountzakis, On the uniform distribution in residue classes of dense sets of integers with distinct sums, J. Number Theory 76 (1999), 147-153.

8. I. Ruzsa, Solving a linear equation in a set of integers I, Acta Arithmetica LXV.3 (1993), 259-282.