A small maximal Sidon set

Imre Z. Ruzsa*

Mathematical Institute of the Hungarian Academy of Sciences, Budapest, Pf. 127, H–1364 Hungary. e-mail: ruzsa@math-inst.hu

To the memory of Paul Erdős, my master and mentor.

Abstract. We construct a Sidon set A ⊂ [1, N] which has ≪ (N log N)^{1/3} elements and which is maximal in the sense that the inclusion of any other integer from [1, N] destroys the Sidon property.

MSC 1991 classification:primary 11B75, secondary 05B10, 11B13, 11B34.

Keywords: Sidon set

* Supported by Hungarian National Foundation for Scientific Research, Grant No. T 017433

A set A of integers is a Sidon set, if all the sums a + a′, a, a′ ∈ A are distinct. We say that a finite Sidon set A ⊂ [1, N] is maximal (for this N) if there is no Sidon set A′ such that

A ⊂ A′ ⊂ [1, N], A′ ≠ A.

An easy counting argument shows that for a maximal Sidon set we have always |A| ≫ N^{1/3}. Erdős, Sárközy and T. Sós [2] asked whether this can be improved. We show that this is not far from optimal.

Theorem.

There is a maximal Sidon set in [1, N] such that

|A| ≪ (N log N)^{1/3}.

Proof. Select a prime p (it will be around (N log N)^{1/3}) and put q = 1 + p + p^{2}. There is a Sidon set of size p + 1 modulo q, that is, there is a set

B = {b_{0}, b_{1}, ..., b_{p}}, B ⊂ [1, q]

such that the sums b_{i} + b_{j} all have distinct residues modulo q. (See, for instance, Halberstam-Roth [3].)

If we take such a set B, then for arbitrary integers d_{0}, ..., d_{p} the numbers in

A_{0} = {a_{i}}, a_{i} = b_{i} + d_{i}q

form a Sidon set. This set satisfies A_{0} ⊂ [1, N] if

0 ≤ d_{i} ≤ M − 1, M = [\frac{N}{q} ] .

Any such set can be extended to a maximal Sidon set A. We can include a number m to A_{0} and still have a Sidon set if and only if none of the equations

m = a_{u} + a_{v} − a_{w},  (1)
2m = a_{u} + a_{v}

has a solution. We will achieve that (1) is solvable for most integers 1 ≤ m ≤ N and this will keep the size of A down.

(1) can certainly hold only if

m ≡ b_{u} + b_{v} − b_{w} (mod q).  (2)

Lemma.

Suppose that m ≢ b_{i} (mod q) for all i. Then there is a sequence (u_{i}, v_{i}, w_{i}) of triplets of integers, 1 ≤ i ≤ I, such that each u = u_{i}, v = v_{i}, w = w_{i} is a solution of congruence (2), for i ≠ j the sets {u_{i}, v_{i}, w_{i}} and {u_{j}, v_{j}, w_{j}} are disjoint and I ≥ p/8.

Proof. Since the numbers b_{i} − b_{j}, i ≠ j are all incongruent modulo q and their number is q − 1, they represent each nonzero residue exactly once. Thus for each u there is exactly one pair (v, w) such that (2) holds. This shows that there are altogether p solutions. Similarly, for a fixed v there is exactly one (u, w), and for a given w there are at most two pairs (u, v).

Now let (u_{i}, v_{i}, w_{i}), 1 ≤ i ≤ I be a maximal selection of pairwise disjoint triplets of solutions. Each triplet (u, v, w) excludes the following triplets: itself; (v, u, w); at most two with u in the third position; at most two with v in the third position; one with w in the first position and one with w in the second. These are 8 excluded triplets altogether (with the selected triplets included), thus 8I ≥ p.

Now we construct A_{0}. For each i we select d_{i} randomly from the numbers 0, ..., M − 1, so that all M^{p+1} possibilities are equally probable.

We estimate the probability that (1) holds for a number m such that m ≢ b_{i} (mod q). (1) is equivalent to (2) and

d_{u} + d_{v} − d_{w} = \frac{m − (b_{u} + b_{v} − b_{w})}{q} = m′.  (3)

Since 2−2q ≤ m−(b_{u} +b_{v} −b_{w}) ≤ N +q −2, the integer m′ satisfies −1 ≤ m′ ≤ M +1.

In (2) and (3), w must be different from u and v, but u and v may coincide. If they are all distinct, then the probability that (3) holds is

P(d_{u} + d_{v} − d_{w} = m′) = S/M^{3},

where S denotes the number of triplets (x, y, z) such that x + y − z = m′, 0 ≤ x, y, z ≤ M − 1. If u = v, then this probability is S′/M^{2}, where S′ is the number of pairs (x, z) such that 2x − z = m′, 0 ≤ x, z ≤ M − 1.

Routine calculations show that (for M > M_{0}) uniformly in the range −1 ≤ m′ ≤ M + 1 we have S ≥ cM^{2} and S′ ≥ cM with a positive absolute constant c, thus

P(d_{u} + d_{v} − d_{w} = m′) ≥ c/M.

If we apply this for the selected disjoint triplets (u_{i}, v_{i}, w_{i}), then we have a collection of independent events and we obtain

P(d_{u_{i}} + d_{v_{i}} − d_{w_{i}} ≠ m′ for all 1 ≤ i ≤ I) ≤ (1 − \frac{c}{M} )^{I} ≤ e^{−cI/M}.

We have

e^{−cI/M} ≤ exp −\frac{cp}{8M} ≤ exp −\frac{cpq}{8N} ≤ exp −\frac{cp^{3}}{8N} .

Thus if we take p so that p > (CN log N)^{1/3} with C = 8/c, then this probability will be < 1/N. By Chebyshev’s theorem, we can achieve this with p ≪ (N log N)^{1/3}. Consequently for any m such that m ≢ b_{u} (mod q) we have

P((1) is not solvable ) < 1/N

and hence

P((1) is solvable for all m ≢ b_{u} (mod q)) > 0.

The set A_{0} corresponding to such a choice will be a Sidon set; it may not be maximal, but it has the following property. Any Sidon set

A ⊃ A_{0}, A ⊂ [1, N]

is of the form A = A_{0} ∪ A_{1}, where each element a ∈ A_{1} satisfies a ≡ b_{u} (mod q) for some u.

Now extend this A_{0} to a maximal Sidon set A. We estimate the size of A_{1}. For each a ∈ A_{1}, consider the unique u such that a ≡ b_{u} (mod q). For this u, the number a − a_{u} = a − b_{u} − qd_{u} is a multiple of q. These numbers are all distinct by the Sidon property of A, and they are in the interval (1 − N, N − 1). Their number is |A_{1}|, thus we have

|A_{1}| ≤ 1 + 2N/q ≪ N^{1/3},

thus

|A| = |A_{0}| + |A_{1}| ≪ (N log N)^{1/3}

as claimed.

Remark. Let g(N) denote the minimal cardinality of a maximal Sidon set in [1, N]. Thus we know that

N^{1/3} ≪ g(N) ≪ (N log N)^{1/3}.  (4)

If the right side gave the correct order of magnitude, this would immediately yield the celebrated theorem of Ajtai, Komlós and Szemerédi [1] on the existence of an infinite Sidon set which has always ≫ (N log N)^{1/3} elements up to N. At present I do not even have a heuristic argument that would indicate which side of (4) gives the truth.

References

[1] Ajtai, M.; Komlós, J.; Szemerédi, E., A dense infinite Sidon sequence, European J. Comb. 2(1981), 1–11.

[2] P. Erdős, A. Sárközy, Vera T. Sós, On sum sets of Sidon sets I., J. Number Theory 47(1994), 329–347.

[3] Halberstam, H.; Roth, K. F, Sequences, Clarendon, London; 1966 (2nd ed. Springer– Verlag, New York–Berlin, 1983). Printed 1999.2.28.