An infinite Sidon sequence

Imre Z. Ruzsa*

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

Abstract. We show the existence of an infinite Sidon sequence such that the number of elements in [1, N] is N^{\sqrt{2}−1+o(1)} for all large N.

1. Introduction

A set B of numbers is called a Sidon set if all the sums a + b, a, b ∈ B are distinct. It is well known that the maximal cardinality of a Sidon set selected from the first N integers is ∼ \sqrt{N} (Bose, Chowla, Erdős-Turán). The behaviour of infinite Sidon sets of integers is not so well understood. We use B(N) to denote the number of elements of B in [1, N]. The estimate lim sup B(N)/\sqrt{N} ≤ 1 follows from the results on the finite case. Erdős proved that the limsup can be ≥ 1/2 here, which was improved to 1/\sqrt{2} by Krückeberg. On the other hand, Erdős showed that an infinite Sidon set cannot be so dense for all N, even

lim inf \frac{B(N)\sqrt{log N}}{\sqrt{N}} ≤ 1.  (1.1)

Chowla and Mian observed that the greedy algorithm yields an infinite Sidon set such that

B(N) ≫ N^{1/3}.  (1.2)

Erdős and Rényi showed for every ε > 0 the existence of an infinite sequence A such that

A(N) ≫ N^{1/2−ε}

which has the following weaker property: the number of solutions of n = a + b, a, b ∈ A is bounded. (For proofs and further references on the above classical results see Halberstam-Roth [2].)

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

So far the only improvement over (1.2) is due to Ajtai, Komlós and Szemerédi [1]. They constructed an infinite Sidon set satisfying

B(N) ≫ (N log N)^{1/3}.  (1.3)

Our aim is to improve this result.

Theorem.

There exists an infinite Sidon set B satisfying

B(N) = N^{γ+o(1)}, γ = \sqrt{2} − 1 = 0.41421356....  (1.4)

2. The construction

Our starting point is the observation that the numbers log p, for p prime, form a Sidon set of reals. Our plan is to take the binary development of these numbers and rearrange the digits to form a Sidon set of integers. If the developments were finite (and not too long), this could be done easily. Since the developments are infinite, we have to round them off. We will show that the resulting sequence still almost has the Sidon property, which will enable us to extract a large Sidon subset from it.

Our construction will also be random, in a slightly unusual way. Rather than select individual elements randomly, we choose a random parameter α in the interval [1, 2] at the start which determines a set, and we show that for almost all choices of α in this interval the set obtained will have the required properties.

From now on we fix β and γ to denote the numbers

β = \sqrt{2} + 1, γ = 1/β = \sqrt{2} − 1.

(We shall obtain this β as the solution of a quadratic equation (2.19).) As told above, the construction will depend on a real number α ∈ [1, 2].

For prime p ≥ 3 develop the number α log p in the binary system:

α log p = ∑_{i=0}^{k} ε_{ip}2^{i} + ∑_{i=1}^{∞} δ_{ip}2^{−i},

where

k = k_{p} = [log_{2}(α log p)].

Here and throughout log_{2} means logarithm to base 2. (We shall sometimes suppress the second subscript p.) We shall cut this development into blocks at places corresponding to squares, and rearrange these blocks to form an integer of size about p^{β}. We define

K = K_{p} = min{i > 2 : 2^{(i−1)^{2}} > p^{β}},

that is,

K_{p} = 2 + [\sqrt{β log_{2} p}] .

It is easy to check that K_{p} > k_{p} for all p. Now we put

P_{K} = {p : K_{p} = K},

λ_{p} = ∑_{i=0}^{k} ε_{ip}2^{i} + ∑_{i=1}^{K^{2}} δ_{ip}2^{−i}.

The definition of K shows that

|λ_{p} − α log p| ≤ 2^{−K^{2}} < 2^{−(K−1)^{2}} < p^{−β}.  (2.1)

We shall combine the digits at places (i − 1)^{2} + 1, ..., i^{2} into a single number Δ_{ip}, that is, we put

Δ_{ip} = ∑_{j=(i−1)^{2}+1}^{i^{2}} δ_{j}2^{i^{2}−j} (i = 1, ..., K).

Hence

Δ_{ip} < 2^{i^{2}−(i−1)^{2}} = 2^{2i−1}.

With this notation we can express λ_{p} as follows:

λ_{p} = ∑_{i=0}^{k} ε_{ip}2^{i} + ∑_{i=1}^{K} Δ_{ip}2^{−i^{2}}.  (2.2)

Now we build for each prime p a natural number b_{p}. Our Sidon set will be a subset of the set of these integers.

Informally the construction of b_{p} goes as follows. We write down the blocks Δ_{1}, ..., Δ_{K}, leaving 5 spaces between each consecutive pair. The 1st, 3rd, and 5th places will always contain a zero. To the 2nd places we insert the digits ε_{ip}. The 4th places will also contain zeros except one, the K’th (after Δ_{K}). This will determine the order of magnitude of b_{p} and it will mark which block P_{K} the prime p came from.

More formally we put (k = k_{p}, K = K_{p})

b_{p} = ∑_{i=1}^{K} Δ_{ip}2^{(i−1)^{2}+5i} + ∑_{i=0}^{k} ε_{ip}2^{i^{2}+5i+2} + 2^{K^{2}+5K+4}.

Since k < K, we have

2^{K^{2}+5K+4} < b_{p} < 2^{K^{2}+5K+5}.

This shows

b_{p} = p^{β+o(1)}.

We introduce the following notation for the last term:

t_{p} = 2^{K^{2}+5K+4}.

Further we put Δ_{ip} = 0 for i > K and ε_{ip} = 0 for i > k.

Now we will find upper bounds for the number of solutions for the equation x+y = u + v in our set. We can write this equation as

b_{p} + b_{s} = b_{q} + b_{r}.  (2.3)

Without restricting generality we may assume that of the four numbers b_{p} is the largest, and further that b_{r} ≤ b_{q}, which can be achieved by renaming the variables if necessary. Thus we have

b_{p} > b_{q} ≥ b_{r} > b_{s}.  (2.4)

Lemma 2.1.

Let x, y, u, v be positive integers such that x + y = u + v. Suppose that 1 ≤ m < n are integers and that the m’th and n’th digits of x, y, u, v are all 0. Let x′, y′, u′, v′ be the integers whose m + 1’th, ..., n − 1’th digits are identical to those of x, y, u, v, respectively, and the rest are 0. Then we have x′ + y′ = u′ + v′.

Proof.: obvious.

On applying this lemma to the equation (2.3) with various choices of m and n we obtain the following.

Lemma 2.2.

Equation (2.3) holds if and only if we have t_{p} + t_{s} = t_{q} + t_{r}, and for all i we have ε_{ip} + ε_{is} = ε_{iq} + ε_{ir} and Δ_{ip} + Δ_{is} = Δ_{iq} + Δ_{ir} .

Lemma 2.3.

If equation (2.3) and the condition (2.4) hold, then there are integers K ≥ L such that p, q ∈ P_{K}, r, s ∈ P_{L} , and we have

λ_{p} + λ_{s} = λ_{q} + λ_{r}.  (2.5)

Proof. (2.5) follows from (2.2) and the corresponding equalities for the ε’s and Δ’s. Since the t_{p} are powers of 2, t_{p} + t_{s} = t_{q} + t_{r} can hold only if either t_{p} = t_{q} and t_{s} = t_{r}, or t_{p} = t_{r} and t_{s} = t_{q}. Inequality (2.4) excludes the second possibility (except when all four are equal, when the first also holds), thus we have the first possibility which is equivalent to saying p, q ∈ P_{K}, r, s ∈ P_{L}, and K ≥ L again by (2.4).

Lemma 2.4.

If (2.3) and (2.4) hold, then we have (with K and L given by the previous lemma)

|ps − qr| < 8qr2^{−L^{2}},  (2.6)
qr > 2^{L^{2}−2}  (2.7)

and

(K − 1)^{2} > βL^{2} − 2β − (L − 1)^{2} = (β − 1)(L − 1)^{2} + β(2L − 3).  (2.8)

Proof. By (2.5) and (2.1) we have

α| log p + log s − log q − log r| = α |log \frac{ps}{qr}| < 4 · 2^{−L^{2}}.  (2.9)

Since |1 − e^{z}| ≤ 2z for |z| ≤ 1 and α ≥ 1, we have

|1 − \frac{ps}{qr}| < 8 · 2^{−L^{2}}.

Multiplying by qr we get (2.6).

Since our numbers are odd primes, the left side of (2.6) is at least 2 and this shows (2.7).

On the other hand we have q^{β} < 2^{(K−1)^{2}} and r^{β} < 2^{(L−1)^{2}}. On raising (2.7) to power β and substituting these inequalities we obtain (2.8).

(2.8) shows that we have K > L, and for large values K is much larger than L. Now we estimate the number

J_{KL} = #{p, q, r, s : p, q ∈ P_{K}, r, s ∈ P_{L}, p ≠ q, r ≠ s, |ps − qr| < 8qr2^{−L^{2}}}.

Lemma 2.5. We have

J_{KL} ≪ 2^{2γ((K−1)^{2}+(L−1)^{2})−L^{2}}.  (2.10)

(Recall that γ = 1/β.) Proof. Write a = ps−qr. For fixed a, r, s we get the general solution of the equation

ps − qr = a in p, q by the formula

p = p_{0} + tr, q = q_{0} + ts,

where p_{0}, q_{0} denotes the smallest solution.

Since p < 2^{γ(K−1)^{2}}, we have t < 2^{γ(K−1)^{2}}/r. Thus for given a, r, s the number of solutions is ≤ 1 + 2^{γ(K−1)^{2}}/r = O(2^{γ(K−1)^{2}}/r).

(2.6) shows that |a| ≪ r2^{γ(K−1)^{2}−L^{2}}. Thus for given r, s the number of solutions is O(2^{2γ(K−1)^{2}−L^{2}}).

Finally we have r, s < 2^{γ(L−1)^{2}}. Thus the total number of solutions is

≪ 2^{2γ((K−1)^{2}+(L−1)^{2})−L^{2}}

as claimed.

(2.6) is only a necessary condition for p, q, r, s to form a solution of (2.3). Now we derive further conditions that will yield better estimates than J_{KL} for the number of solutions from prescribed blocks.

Lemma 2.6. Suppose that b_{p} + b_{s} = b_{q} + b_{r}. Then we have

[2^{K^{2}}α log p] ≡ [2^{K^{2}}α log q] (mod 2^{K^{2}−L^{2}}).  (2.11)

Proof. We have

α log p = ∑_{i=0}^{k} ε_{ip}2^{i} + ∑_{i=1}^{∞} δ_{ip}2^{−i},

[2^{K^{2}}α log p] = ∑_{i=0}^{k} ε_{ip}2^{K^{2}+i} + ∑_{i=1}^{K^{2}} δ_{ip}2^{K^{2}−i},

thus

[2^{K^{2}}α log p] ≡ ∑_{i=L^{2}+1}^{K^{2}} δ_{ip}2^{K^{2}−i} (mod 2^{K^{2}−L^{2}}).  (2.12)

On the other hand, we know that

Δ_{ip} + Δ_{is} = Δ_{iq} + Δ_{ir}

holds for all i. Now if L < i ≤ K, then Δ_{is} = Δ_{ir} = 0, so necessarily Δ_{ip} = Δ_{iq}. In other words we have δ_{jp} = δ_{jq} for L^{2} < j ≤ K^{2}, thus the right side of (2.12) remains unchanged if we replace p by q. This proves (2.11).

Congruence (2.11) depends on the parameter α. Now we estimate, for given p and q, the measure of those α’s for which (2.11) holds. We denote Lebesgue measure by μ.

Lemma 2.7.

Let K > L and p, q ∈ P_{K}, p ≠ q be given. Suppose that there is at least one pair r, s ∈ P_{L} and an α ∈ [0, 1] such that (2.3) holds. Then we have

μ(α : (2.12) holds) ≪ 2^{L^{2}−K^{2}}.  (2.13)

Proof. By substracting the sides of (2.12) and taking into account that [x] − [y] = [x − y] + 0 or 1, we obtain

[2^{K^{2}}α log(p/q)] ≡ 0 or − 1 (mod 2^{K^{2}−L^{2}}).  (2.14)
Write M = 2^{K^{2}−L^{2}} and T = |2^{K^{2}} log(p/q)|. The real numbers x satisfying
[x] ≡ 0 or − 1 (mod M)

occupy an interval of length 2 within any interval of length M. Hence the set of numbers α satisfying (2.14) is the union of certain intervals of length 2/T, one in each interval of length M/T. The number of such intervals that intersect [0, 1] is at most 1 + T/M, consequently we have

μ(α : (2.12) holds) ≤ (2/T) (1 + \frac{T}{M} ) .  (2.15)

By (2.9) we have

log(p/q) = log(r/s) + O(2^{−L^{2}}).

On the other hand we have |1 − r/s| ≥ 1/s, thus | log(r/s)| ≥ 1/(2s) > 2^{−1−γL^{2}} and so | log(p/q)| ≫ 2^{−γL^{2}}. We conclude that

T ≫ 2^{K^{2}−γL^{2}} > M = 2^{K^{2}−L^{2}}.

Hence the right side of (2.15) is ≪ (1/T)(T/M) = 1/M as claimed.

Lemma 2.8. Let K > L, p, q ∈ P_{K}, p ≠ q and r, s ∈ P_{L} be given. We have

μ(α : b_{p} + b_{s} = b_{q} + b_{r}) \{ \begin{matrix}= 0, & if |ps − qr| ≥ 8qr2^{−L^{2}}, \\ ≪ 2^{L^{2}−K^{2}}, & if |ps − qr| < 8qr2^{−L^{2}}. \end{matrix}  (2.16)

Proof. This is the combination of the above lemma with Lemma 2.4.

Write

G_{KL}(α) = #{p, q, r, s : p, q ∈ P_{K}, r, s ∈ P_{L}, p ≠ q, b_{p} + b_{s} = b_{q} + b_{r}}.

Lemma 2.9. For K > L we have

∫_{1}^{2} G_{KL}(α) dα ≪ 2^{2γ((L−1)^{2}+(K−1)^{2})−K^{2}}.  (2.17)

Proof. By summing (2.16) for all possible values of p, q, r, s we obtain

∫_{1}^{2} G_{KL}(α) dα ≪ 2^{L^{2}−K^{2}}J_{KL}.

(2.17) follows by substituting the estimate of J_{KL} from Lemma 2.5.

Write

G_{K}(α) = #{p, q, r, s : p, q ∈ P_{K}, (2.3) and (2.4) hold.}

Lemma 2.10.

∫_{1}^{2} G_{K}(α) dα ≪ 2^{γ(K−1)^{2}−2K}.  (2.18)

Proof. By definition we have

G_{K}(α) = ∑_{L≤K} G_{KL}(α).

From (2.8) we infer that G_{KL}(α) ≠ 0 is possible (with a finite number of exceptions) only if (L − 1)^{2} < (K − 1)^{2}/(β − 1). On summing (2.17) for these values of L we obtain the estimate ≪ 2^{Z} with

Z = 2γ (1 + \frac{1}{β − 1}) (K − 1)^{2} − K^{2} = (\frac{2}{β − 1} − 1) (K − 1)^{2} − 2K + 1.

This reduces to (2.18), since our number β was selected to satisfy the equation

\frac{2}{β − 1} − 1 = \frac{1}{β} .  (2.19)

Proof of the Theorem.

By the Borel-Cantelli lemma we can find a value of α such that we have, with the exception of finitely many values of K,

G_{K}(α) < 2^{γ(K−1)^{2}−K}.

From now on fix α to be such a number.

The cardinality of P_{K} is

|P_{K}| = π(2^{γ(K−1)^{2}}) − π(2^{γ(K−2)^{2}}) ∼ \frac{2^{γ(K−1)^{2}}}{(γ log 2)K^{2}} .

Thus for K > K_{0} we have G_{K}(α) < |P_{K}|/2. Hence, if for each p, q, r, s satisfying (2.3) and (2.4) with p ∈ P_{K} we omit p from P_{K}, the set Q_{K} of remaining elements satisfies |Q_{K}| > |P_{K}|/2. Our Sidon set will be

B = ⋃_{K>K_{0}} Q_{K}.

To estimate the number of elements of B up to x observe that

b_{p} < 2^{K^{2}+5K+5} < 2^{(K+3)^{2}}.

Thus for K = [\sqrt{log_{2} x} − 3] the set Q_{K} consists of integers < x. Hence we have

B(x) ≫ (1/2 − ε)π(2^{γ(K−1)^{2}}) = x^{γ+o(1)}.

A similar calculation yields an upper estimate which concludes the proof of the theorem.

References

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

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