On the additive completion of primes

Imre Z. Ruzsa*

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

1. Introduction

We shall investigate sets B of positive integers with the property that, in various senses, most positive integers are contained in the sumset

S = {p + b : b ∈ B, p prime}.  (1.1)

We are interested in how thin this set can be in terms of the counting function

B(x) = |B ∩ [1, x]|.

Erdős [2] (see also in [5]) proved the existence of a set B such that S contains all but finitely many natural numbers and

B(x) = O((log x)^{2}).

Improving a result of Wolke [7], Kolountzakis [6] proved the existence of a set B such that d(S) = 1, where d denotes asymptotic density, and

B(x) = O(log x log log x).

(It should be noted here that Wolke’s completion, while slightly denser, has the interesting additional property of consisting exclusively of primes and neighbours of primes.)

We improve Kolountzakis’ result as follows.

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

(a) For every ε > 0 there is a set B such that

B(x) = O(log x)

and the set S defined in (1.1) satisfies \underline{d}(S) > 1−ε, where \underline{d} denotes lower asymptotic density.

(b) For every function ω(x) → ∞ there exists a set B such that

B(x) = O(ω(x) log x)

and the set S defined in (1.1) satisfies d(S) = 1.

As far as I know, no lower estimate has been published for B(x) in either context. An obvious counting argument yields that if d(S) = 1, then

lim inf B(x)/ log x ≥ 1.

I think that Theorem 1 above is best possible in the following sense.

Conjecture 1. If d(S) = 1, then necessarily

B(x)/ log x → ∞.

I am unable to prove even the following weaker conjectures. Conjecture 2. If S contains all but finitely many natural numbers, then neces-

sarily

B(x)/ log x → ∞.

Conjecture 3. If d(S) = 1, then necessarily

lim sup B(x)/ log x > 1.

In this direction we obtain the following result.

Theorem 2.

If S satisfies

x − S(x) ≤ x^{1−log log log x/ log log x}

for large x (hence a fortiori if S contains all but finitely many natural numbers), then

lim inf B(x)/ log x ≥ e^{γ},

where γ denotes the Euler-Mascheroni constant.

2. Proof of Theorem 1

We use P to denote the set of primes, and the traditional π(x) (rather than P (x)) for its counting function.

Let 0 < c_{0} < 1 be a constant with the following property:

π(x + y) − π(x) ∼ \frac{y}{log x}  (2.1)

holds uniformly in the range x^{c_{0}} ≤ y ≤ x as x → ∞ (2/3 is known to be such a number), and fix another constant c_{1} with c_{0} < c_{1} < 1.

Both parts of the theorem will follow from the following finite version.

Lemma 2.1.

For every ε > 0 there is a K = K(ε) and an N_{0} = N_{0}(ε) such that for N > N_{0} we can always find a set

B ⊂ [N^{c_{0}}, 2N^{c_{0}}]

of integers such that

|B| ≤ K log N  (2.2)

and the set S = P + B satisfies

S(x) ≥ (1 − ε)x for all N^{c_{1}} ≤ x ≤ N.  (2.3)

Proof. We show the existence of such a set by a probabilistic argument.

Write

I = [N^{c_{0}}, 2N^{c_{0}}] ∩ ℕ, L = |I| = N^{c_{0}} + O(1).

Let B be a random subset of I such that each n ∈ I is included into B independently with a common probability

ϱ = \frac{K log N}{2L}

so that the expected number of elements is

E(|B|) = ϱL = \frac{K}{2} log N.

We will show that with a proper choice of K we have

P((2.3) holds) > 1/N,  (2.4)

while

P(|B| > K log N) < 1/N,  (2.5)

so that there will be a set that satisfies both (2.3) and |B| ≤ K log N.

Note that we will not establish that most sets B with about K log N elements have property (2.3). We are able to do this with a more complicated argument than the one in the sequel, which also exploits further properties of the primes outside (2.1).

We show that (2.3) follows from the following related property of a set B:

for each x_{j} = N/2^{j} satisfying N^{c_{1}} ≤ x_{j} ≤ N we have

S(x_{j}) > (1 − ε/2)x_{j}.  (2.6)

To see how (2.6) implies (2.3), observe that the function T (x) = x − S(x) is increasing. Hence for a general x, with, say, x_{j} ≥ x > x_{j+1} = x_{j}/2, we find

T (x) ≤ T (x_{j}) ≤ \frac{ε}{2}x_{j} < εx

as wanted.

Now we estimate the probability that (2.6) holds for a fixed value of j.

A given number n ∈ [2N^{c_{0}}, N] will be in S if at least one number n − p, p prime, is in B. This is possible if n − p ∈ I, or p ∈ n − I. The number of such primes is

z_{n} = π(n − N^{c_{0}}) − π(n − 2N^{c_{0}}) ∼ \frac{L}{log n}

by property (2.1). We have n ∉ S only if none of these z_{n} integers is in B; the probability of this event is

P(n ∉ S) = (1 − ϱ)^{z_{n}} ≤ exp(−ϱz_{n}).

We have

ϱz_{n} ∼ \frac{K log N}{2L} \frac{L}{log n} = \frac{K log N}{2 log n} ≥ K/2,

thus ϱz_{n} > K/3 for large N uniformly in the above range of n. Hence

P(n ∉ S) < e^{−K/3}.  (2.7)

Consequently the expectation of T (x_{j}) satisfies

E(T (x_{j})) < e^{−K/3}x_{j} + 2N^{c_{0}},  (2.8)

where the last term comes from the fact that (2.7) need not hold for n < 2N^{c_{0}}. Since our numbers satisfy x_{j} ≥ N^{c_{1}}, the second summand of (2.8) is of a smaller order of magnitude than the first and we have

E(T (x_{j})) < 2e^{−K/3}x_{j}

for large N. From Markov’s inequality we can now infer

P(T (x_{j}) ≥ (ε/2)x_{j}) ≤ 4e^{−K/3}/ε ≤ 1/2,

or in other words

P(S(x_{j}) > (1 − ε/2)x_{j}) ≥ 1/2,  (2.9)

provided

e^{−K/3} ≤ ε/8.  (2.10)

The property that (2.6) holds for a fixed value of j defines a monotonically increasing family of sets B (if a set B has this property, then so does every set containing B). Such increasing families are always positively correlated, that is, the probability that a random set is in the intersection of several such families is at least as high as the product of the corresponding probabilities. This is stated in this form in Alon and Spencer [1, Theorem 3.2] and is a corollary to either Fortuin, Kasteleyn and Ginibre’s inequality [3] (the usual approach), or to an earlier inequality of Esary, Proschan and Walkup [2]. In our case this means that

P(S(x_{j}) > (1 − ε/2)x_{j} for all j) ≥ ∏_{j} P(S(x_{j}) > (1 − ε/2)x_{j}) ≥ 2^{−J},

where J is the number of the values x_{j} considered. Since these are defined by x_{j} = N/2^{j} > N^{c_{1}}, we have

2^{J} ≤ 2N^{1−c_{1}} < N,

which concludes the proof that (2.6), and hence (2.3) as well, holds at least with probability 1/N.

To show (2.5) note that

Ee^{|B|} = (1 − ϱ + ϱe)^{L} ≤ exp(ϱ(e − 1)L) = exp (\frac{e − 1}{2}K log N) .

Thus from Markov’s inequality we get

P(|B| > K log N) = P(e^{|B|} > e^{K log N})

≤ exp (\frac{e − 1}{2}K log N − K log N) = N^{K(e−3)/2},

which is smaller than 1/N provided

K > 2/(3 − e).  (2.11)

(Alternatively, we could refer to various forms of Bernstein’s or Chernoff’s inequality.)

We have established (2.4) and (2.5), thus the proof of Lemma 2.1 is complete. For K we obtain the value

K = 3 log(8/ε),  (2.12)

which satisfies (2.11) if ε < 3/4.

Proof of Theorem 1, part (a).

We define a sequence N_{i} starting from the N_{0} of the lemma by the recursion

N_{i+1} = [N_{i}^{1/c_{1}}] .

We apply the lemma to each N = N_{i} to get a set

B_{i} ⊂ [N_{i}^{c_{0}}, 2N_{i}^{c_{0}}] ,

satisfying

|B_{i}| ≤ K log N_{i}

and (2.3) for the set S_{i} = P + B_{i} in the range N_{i}^{c_{1}} ≤ x ≤ N_{i}. We put B = ⋃ B_{i}. For the set S = P + B we have evidently

S(x) ≥ S_{i}(x) ≥ (1 − ε)x

in the above range, and since N_{i} is selected to make these overlap, we have this everywhere. To estimate B(x) define k as the smallest subscript with N_{k}^{c_{0}} > x. This means that N_{k−1} ≤ x^{1/c_{0}}, thus

N_{k} ≤ N_{k−1}^{1/c_{1}} ≤ x^{1/c_{0}c_{1}}.

Observe that log N_{i} grows exponentially, hence

B(x) ≤ ∑_{i≤k} |B_{i}| = O(|B_{k}|) = O(log N_{k}) = O(log x)

as claimed.

Proof of Theorem 1, part (b). In the proof of part (a) we replace the constant ε by a decreasing sequence ε_{i} tending to 0 sufficiently slowly.

3. Proof of Theorem 2

We prove Theorem 2 in the following form. Suppose that α < e^{γ} and B ⊂ [1, x] satisfies

k = |B| ≤ α log x.

Then for some c < 1 and x > x_{0}(α) there are at least

x^{1−c log log log x/ log log x}

numbers up to x not of the form p + b, b ∈ B, p prime.

Let p_{i} denote the i’th prime. Put

r = [\frac{log x}{(log log x)^{3}} ]

and m = p_{1}...p_{r}. By an averaging argument we find a residue class a (mod m) such that

l = #\{b ∈ B : (a − b, m) = 1\} ≤ \frac{ϕ(m)}{m}k.

Let b_{1}, ..., b_{l} be the elements of B such that (b − a, m) = 1. Let π be any permutation of the set {1, 2, ..., l}. We shall consider the integers n satisfying

\begin{matrix}n ≡ a (mod m), \\ n ≡ b_{j} (mod p_{r+π(j})), j = 1, ..., l. \end{matrix}  (3.1)

These integers occupy a residue class modulo M, where

M = m ∏_{j=1}^{l} p_{r+j} = ∏_{i=1}^{r+l} p_{i}.

We show that the majority of these numbers lies outside P + B. Indeed, suppose that n = p + b, or p = n − b. If b is one of b_{1}, ..., b_{l}, say b_{j}, then n − b is divisible by p_{r+π(j)}. If b is none of these, then

(n − b, m) = (a − b, m) > 1,

thus n − b is divisible by one of p_{1}, ..., p_{r}. Consequently the prime p can be only one of p_{1}, ..., p_{r+l}, and the total number of such integers n (for all permutations together) is at most k(r + l).

To estimate the number of integers n satisfying (3.1) we firs find a bound for M. By Mertens’s theorem we have

\frac{ϕ(m)}{m} = ∏_{j=1}^{r}(1 − \frac{1}{p_{j}} ) ∼ e^{−γ}(log r)^{−1} ∼ e^{−γ}(log log x)^{−1}.

Consequently

l ≤ \frac{ϕ(m)}{m}k ≤ (1 + o(1))αe^{−γ} \frac{log x}{log log x}.

Write L = l + r. By the above estimate and the definition of r we have

L ≤ α_{1} \frac{log x}{log log x}

for large x with any α_{1} > αe^{−γ}. Since α < e^{γ}, we can achieve this with α_{1} < 1. Using the prime number theorem in the form p_{i} ∼ i log i we obtain

M = ∏_{i=1}^{L} p_{i} < L!(log L)^{L}e^{o(L)}.

By (3.2) this yields M = o(x), in particular, M < x for large x.

Each congruence (3.1) defines a residue class modulo M, thus at least [x/M] ≥ x/(2M) integers up to x. Since there are l! possible choices for the permutation π, this means altogether at least

\frac{1}{2} \frac{l!}{M} x

numbers. As said above, of these numbers at most Lk can be in P +B, thus the number elements outside P + B is at least

\frac{1}{2} \frac{l!}{M} x − Lk.  (3.2)

To estimate this number from below observe that

\frac{M}{l!} ≤ \frac{L!}{l!}(log L)^{L}e^{o(L)} < L^{r}(log L)^{L}e^{o(L)} < exp ((α_{1} + o(1))\frac{log x log log log x}{log log x}) .

Hence the first term of (3.2) is larger than

x^{1−c log log log x/ log log x}

with any c > α_{1} for large x. Since Lk = o((log x)^{2}), the second term is of smaller order of magnitude than the first, and our claim is established for arbitrary α_{1} < c < 1.

References

[1] Alon, N.; Spencer, J. H., The probabilistic method, Wiley, New York 1992.

[2] Erdős, P., Some results on additive number theory, Proc. Amer. Math. Soc. 5(1954), 847–853.

[3] Esary, J.D.; Proschan, F.; Walkup, D. W., Association of random variables, with applications, Ann. Math. Statist. 38(1967), 1366–1374.

[4] Fortuin, C. M; Kasteleyn, P. W., Correlation inequalities on some partially ordered sets, Comm. Math. Phys. 22(1971), 89–103.

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

[6] Kolountzakis, M. N., On the additive complements of the primes and sets of similar growth, Acta Arithmetica 77(1996), 1–8.

[7] Wolke, D., On a problem of Erdős in additive number theory, J. Number Theory 59(1996), 209–213. Printed 1999.2.28.