HIGH ORDER COMPLEMENTARY BASES OF PRIMES

V. H. Vu ^{1}

Department of Mathematics, University of California at San Diego La Jolla, CA 92093, USA

                             vanvu@ucsd.edu

Received: 3/24/02, Accepted: 10/22/02, Published: 10/23/02

Abstract

We show that there is a set X ⊂ N with density O(log n) such that every sufficiently large natural number can be represented as sum of two elements from X and a prime. The density is a log^{1/2} n factor off being best possible.

1. Introduction

A central notion in additive number theory is that of bases. A subset X of N is a basis of order k if every sufficiently large number n ∈ N can be represented as a sum of k elements of X. Here and later N denotes the set of natural numbers.

In this note, we are working with a related notion of complementary bases. Given a set A ⊂ N, a set X ⊂ N is a complementary basis of order k of A if every sufficiently large natural number can be written as a sum of an element in A and k elements in X. All asymptotic notations are used under the assumption that n → ∞. The logarithms have natural base.

Consider the set P of primes. Since P has density n/ log n, it is clear by the pigeon hole principle that a complementary basis of order k of P should have density Ω(log^{1/k} n). As far as we know, it is still an open question to determine, even for the case k = 1, that whether there is a complementary basis of P with density O(log^{1/k} n). In [1], Erdős shown that for k = 1, there is a complementary base of density O(log^{2} n). In a recent paper, Ruzsa [5], improving a result of Kolountzakis [4], showed that there exists a set X of density ω(n) log n, where ω(n) is a function tending to infinity arbitrarily slow in n, such that the set X + P has density one (i.e., almost all natural numbers can be represented as a sum of an element from X and a prime).

1Research supported in part by grant RB091G-VU from UCSD, by NSF grant DMS-0200357, and by a Sloan fellowship.

AMS Subject Classificiation Numbers: 05, 11.

Key words: Complementary bases, the probabilistic method, primes.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 2 (2002), #A12 2

In this note, we focus on the case k = 2. Our main theorem is

Theorem 1.1 P has a complementary basis of order 2 and density O(log n).

Corollary 1.2 For all k ≥ 2, P has a complementary basis of order k and density O(log n).

We conjecture that

Conjecture. For any fixed k, P has a complementary basis of order k and density O(log^{1+o(1))/k} n).

The probabilistic method is the only effective approach so far to this type of problems. It seems that to prove even the density O(log^{2/k} n) for k ≥ 3 requires a new tool from probability theory. Such a tool should surely be of independent interest. The first step towards the conjecture might be to prove a bound with the exponent decreasing in k.

2. Proof of Theorem 1.1

We construct the claimed complementary basis X by the random method. For each x ∈ N, choose x to be in X with probability p_{x} = c/x, where c is a positive constant to be determined. Let t_{x} be the binary random variable representing the choice of x (thus t_{x} = 1 with probability p_{x} and 0 with probability 1−p_{x}). We skip the fairly easy proof of the fact that almost surely, X(m) = O(log m) for every m, i.e, X has the right density; the interested readers might want to consider this as a warm-up exercise. Now let us consider the number representations of n as sum of a prime and two elements from X. This number is a random variable depending on the t_{j}’s, j < n and can be expressed as follows

Y_{n} = ∑_{p<n} ∑_{i+j=n−p} t_{i}t_{j},

where in the second sum we do not count permutations. Here and later in a sum over p we understand that p is a prime. We next show that there is a constant n_{0} such that with probability at least 1/2, Y_{n} ≥ 1 for all n ≥ n_{0}. To achieve this goal, it suffices to prove that for all sufficiently large n, P r(Y_{n} = 0) ≤ n^{−2} (notice that the sum ∑_{n=n_{0}}^{∞} n^{−2} goes to 0 as n_{0} tends to infinity). It has turned out that it is much more convenient to work with the following truncation of Y_{n}

Y′_{n} = ∑_{p≤n−2n^{2/3}} ∑_{i+j=n−p; i,j≥n^{2/3}} t_{i}t_{j}.

In the following, we shall prove

P r(Y′ = 0) ≤ n^{−2}.  (1)

Central to the proof of (1) is the following

Lemma 2.3 For all sufficient large n

∑_{p≤n−n^{2/3}} \frac{1}{n − p} = Θ(1),

and

∑_{p≤n−2n^{2/3}} \frac{1}{n − p} = Θ(1).

Proof of Lemma 2.3. To verify the first equality, let us set n_{1} = n − n^{2/3} and n_{l} = n_{l−1} − n_{l−1}^{2/3} for all l = 2, 3, 4, …, s where s is the first place where n_{s} ≤ n/2. It is a routine to show by induction that

n − \frac{ln^{2/3}}{2} ≥ n_{l} ≥ n − ln^{2/3}.  (2)

Let P_{l} denote the set of primes in the interval [n_{l}, n_{l−1}). It is clear, by (2), that for all p ∈ P_{l},

\frac{2}{ln^{2/3}} ≥ \frac{1}{n − p} ≥ \frac{1}{ln^{2/3}} .  (3)

On the other hand, it is a well-known fact in number theory that the number of primes in the interval [m − m^{2/3}, m) is Θ(m^{2/3}/ log m) for every sufficiently large m (see, for instance, [2]). Thus

|P_{l}| = Θ(n_{l−1}^{2/3}/ log n_{l−1}) = Θ(n^{2/3}/ log n)

for all l. This and (3) yield

∑_{l=2}^{s} ∑_{p∈P_{l}} \frac{1}{n − p} = Θ(log^{−1} n ∑_{l=2}^{s} 1/l) = Θ(log^{−1} n × log s) = Θ(1).  (4)

To complete the proof of the first equality, notice that ∑_{p≥n/2} 1/(n−p) ≤ ∑_{j=n/2}^{n} 1/j = O(\frac{n}{log n} \frac{1}{n}) = o(1). The second equality follows easily. Q.E.D

The second main ingredient of our proof is a large deviation bound, due to Janson [3]. Let z_{1}, …, z_{m} be independent indicator random variables and consider a random variable Y = ∑_{α} I_{α} where each I_{α} is the product of few z_{j}’s. We write α ∼ β if there is some z_{j} which occurs in both I_{α} and I_{β}. Furthermore, set Δ = ∑_{α∼β} E(I_{α}I_{β}). To this end, E(A) denotes the expectation of the random variable A.

Theorem 2.4 (Janson) For any Y as above and any positive number ε

P r(Y ≤ (1 − ε)E(Y)) ≤ e^{− \frac{(εE(Y ))^{2}}{2(E(Y )+Δ)}} .

From Theorem 2.4, one can routinely derive the following lemma. For a pair 1 ≤ i, j ≤ m, we write i ∼ j if there is some α such that I_{α} contains both z_{i} and z_{j}.

Lemma 2.5 There is a positive constant r such that the following holds. If each term I_{α} in Y is the product of exactly 2 random variables and for all m ≥ i ≥ 1, E(Y) ≥ r log n(E(∑_{j∼i} t_{j}) + 1), then

P r(Y = 0) ≤ n^{−2}.

We now apply Lemma 2.5 to Y′_{n}. Let us notice that in our setting, i ∼ j if and only if there is a prime number p such that i + j + p = n. Therefore,

E(∑_{j∼i} t_{j}) = ∑_{p≤n−i−n^{2/3}} \frac{c}{n − i − p} ≤ ∑_{p≤m−m^{2/3}} \frac{c}{m − p},

where m = n − i. By Lemma 2.3, there is a constant a such that E(∑_{j∼i} t_{j}) ≤ ac. Moreover, a simple calculation yields that

E( ∑_{i+j=n−p,i,j≥n^{2/3}} t_{i}t_{j}) = Ω(c^{2} \frac{log(n − p)}{n − p}).

This and Lemma 2.3 together imply

E(Y′) = Ω( ∑_{p≤n−2n^{2/3}} \frac{log(n − p)}{n − p}) = Ω(c^{2} log n ∑_{p≤n−2n^{2/3}} \frac{1}{n − p}) = Ω(c^{2} log n). (5)

(5) guarantees that there is a positive constant b such that E(Y′) ≥ bc^{2} log n. Thus, by increasing c, we can guarantee that the condition of Lemma 2.5 is met and this completes the proof. Q.E.D

Acknowledgement. The author would like to thank Andrew Granville for a correction concerning the result of Ruzsa quoted in the introduction.

References

[1] P. Erdős, Problems and results in additive number theory, Colloque sur la Théory de Nombre (CBRM) (Bruxelles, 1956), 127-137

[2] H. Halberstam and K. F. Roth, Sequences, Springer-Verlag, New York, 1983.

[3] S. Janson, Poisson approximation for large deviations, Random Structures and Algorithms, 1 (1990), 221-230.

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

[5] I. Ruzsa, On the additive completion of primes. Acta Arith. 86 (1998), no. 3, 269–