INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A13

A NOTE ON P-SETS

Stephan Baier

Center of Mathematics, Department of Pure Mathematics and Mathematical Statistics, University of

Cambridge, Wilberforce Road, Cambridge CB3 0WB, United Kingdom

                         S.Baier@dpmms.cam.ac.uk

Received: 10/3/03, Accepted: 9/26/04, Published: 10/8/04

Abstract

A P-set is a set S of positive integers such that no element of S divides the sum of any two (not necessarily being different) larger elements. Erdös and Sárközy [2] conjectured that there exists a constant c > 0 such that for every P-set S we have |{s ∈ S : s ≤ N}| < N^{1−c} for infinitely many integers N. For P-sets S consisting of pairwise coprime integers this conjecture has been proved by T. Schoen [6] who showed that in this case we have |{s ∈ S : s ≤ N}| < 2N^{2/3} for infinitely many integers N. In the present note we prove that the term 2N^{2/3} in Schoen′s estimate can be replaced by (3+ε)N^{2/3}/ log N. Our method uses the arithmetic form of the large sieve as well as mean value estimates for multiplicative functions. (Mathematics Subject Classification (2000): 11B05, 10H25)

1. Introduction

Notation: Whenever S is a discrete set of positive real numbers, we define the corresponding counting function A_{S} : ℝ^{+} → ℕ ∪ {0} by

A_{S}(N) := |{s ∈ S : s ≤ N}|.

A P-set is a set S of positive integers such that no element of S divides the sum of any two (not necessarily being different) larger elements. In [2] Erdös and Sárközy studied the behaviour of the corresponding counting function A_{S}(N). They showed that A_{S}(N) = o(N) as N → ∞ and pointed out that this estimate is in a certain sense optimal. Furthermore, they conjectured that there exists a constant c > 0 such that A_{S}(N) < N^{1−c} for infinitely many integers N. For P-sets S consisting of pairwise coprime integers this conjecture has been proved by T. Schoen [6] who showed that in this case we have A_{S}(N) < 2N^{2/3} for infinitely many integers N. His method depends on the analytic form of the large sieve. Moreover, by giving a counterexample, Schoen pointed out that c cannot be choosen greater than 1/2.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY x (200x), #Axx 2

In the present note we improve Schoen′s first-mentioned result. Throughout the following, we suppose that S is a given P-set consisting of pairwise coprime integers.

Theorem: Let any ε > 0 be given. Then we have

A_{S}(N) < (3 + ε)N^{2/3}(log N)^{−1}

for infinitely many integers N.

2. General estimation of A_{S}(N)

Without loss of generality, we suppose that 1 ∉ S (otherwise, S could not contain any integer greater than 1).

Our starting point for estimating A_{S}(N) is the following simple observation: If q, r ∈ S and q < r, then we have s ≢ −r mod q for all s ∈ S with s > q (this follows directly from the definition of S to be a P-set). From this, we conclude that for every q ∈ S there exist at least 1 + [q/2] residue classes R_{1}(q),R_{2}(q),...,R_{ω(q)}(q) mod q which do not contain any element of S greater than q (particularly, the residue class 0 mod q will be one of them and, if q is even, q/2 mod q will be another of them).

This leads us to defining the following sieve for given real z, N with 1 ≤ z ≤ N (however, here we use a set of pairwise coprime integers instead of a set of primes):

𝔄 := {n ∈ ℕ : z < n ≤ N},
𝔓 := {q ∈ S : q ≤ z},
Ω(q) := ⋃_{i=1}^{ω(q)} R_{i}(q) (q ∈ 𝔓),
𝔐 := {m ∈ 𝔄 : m ∉ Ω(q) for all q ∈ 𝔓}.

Then, by our above observations, we have

A_{S} (N) ≤ |𝔐| + z.  (1)

To obtain an upper bound for |𝔐|, we use the arithmetic form of the large sieve established by H.L. Montgomery (see [1], [5]).

Lemma 1: On the above sieve hypotheses, we have

|𝔐| ≤ (N + Q^{2}) (∑_{k≤Q} g(k))^{−1}

for every Q ≥ 1, where g(k) is defined by

g(k) := \{ \begin{matrix}1 & if k = 1, \\ ∏_{i=1}^{r} \frac{ω(q_{i})}{q_{i}−ω(q_{i})} & if there are distinct q_{1}, ..., q_{r} ∈ 𝔓 such that k = q_{1} ⋯ q_{r}, \\ 0 & otherwise. \end{matrix}

We note that g is well-defined since the set 𝔓 consists of pairwise coprime integers.

The original version of Montgomery′s sieve employs, as usual in context of sieve theory, a set of prime numbers 𝔓 instead of, more generally, a set of pairwise coprime integers, but our more general version of this sieve can be proved in exactly the same manner as the original one.

As already pointed out, in our application we have ω(q) ≥ 1 + [q/2] if q ∈ 𝔓. This implies g(k) ≥ 1 whenever g(k) > 0. Hence, choosing z := Q and N := Q^{2}, we obtain the following result from (1) and Lemma 1.

Lemma 2: For every real Q ≥ 1 we have

A_{S} (Q^{2}) ≤ \frac{2Q^{2}}{|A_{K}(Q)|} + Q,

where the set K is defined to be the union of {1} and the set of all products of distinct elements of S, i.e.

K := {1} ∪ {q_{1} ⋯ q_{r} : r ∈ ℕ, q_{1}, ..., q_{r} are distinct elements of S} ,

and A_{K}(Q) denotes the counting function corresponding to K.

3. Proof of Theorem.

The key ingredient for our improvement of Schoen′s result is the following

Lemma 3: Let α, β and N_{0} be real numbers with α > 0, 1/2 < β < 1 and N_{0} ≥ 2. Suppose that

A_{S}(N) ≥ αN^{β}(log N)^{−1}  (2)

holds for every integer N ≥ N_{0}. Define the set K as in Lemma 2. Then for every ε_{0} > 0 there exist real numbers x_{0}(ε_{0}) ≥ 2 and C(ε_{0}) > 0 such that

A_{K}(x) ≥ C(ε_{0})x^{β}(log x)^{αβ−1−ε_{0}}

for every real x ≥ x_{0}(ε_{0}).

Proof. The condition (2) implies that there is a subset T of S such that

A_{T} (x) ∼ αx^{β}(log x)^{−1}  (3)

as x → ∞. Let L be the union of {1} and the set of all elements of K which can be represented as a product of elements of T , i.e.

L := {1} ∪ {q_{1} ⋯ q_{r} : r ∈ ℕ, q_{1}, ..., q_{r} are distinct elements of T } .

We employ the following result in [4], page 202 to obtain a lower bound for A_{L}(x):

Let f be a non-negative multiplicative function defined on the usual set of positive integers. Suppose that

∑_{p≤x} f(p) ∼ α · \frac{x^{β}}{log x} (α > 0, β > 0)

as x → ∞, where the sum on the left side runs over the prime numbers p ≤ x. Suppose further that for a certain δ > 0 we have

∑_{p, k≥2} \frac{f(p^{k})}{p^{kβ(1−δ)}} < ∞.

Then,

∑_{n≤x} f(n) ∼ (∑_{p≤x} f(p)) · \frac{e^{−αβγ}}{Γ(1 + αβ)} · ∏_{p≤x} (1 + \frac{f(p)}{p^{β}} + \frac{f(p^{2})}{p^{2β}} + ...)

as x → ∞, where γ denotes the Euler constant.

We note that this result keeps its validity if the set of prime numbers is replaced by a set 𝔔 of pairwise coprime integers and the function f is, more generally, defined to be a multiplicative function on the arithmetical semigroup 𝔊 generated by the set 𝔔 (see [3]; the arithmetical semigroup 𝔊 may be understood as “generalized integers”, the set 𝔔 as “generalized prime numbers”).

In our case, we set 𝔔 := T . Hence, the arithmetical semigroup 𝔊 is the union of {1} and the set of all products of (not necessarily being different) elements of T . For f we take the characteristic function of the set L (this set L may be understood as the set of “squarefree” elements of our arithmetical semigroup 𝔊, and the function f corresponds to the function μ^{2} on the set of usual positive integers, where μ is the Möbius function), i.e. we set

f(n) := \{ \begin{matrix}1 & if n ∈ L, \\ 0 & if n ∈ 𝔊 \ L. \end{matrix}

Now, from (3) and our generalized version of the above-mentioned result on multiplicative functions in [4, page 202], we derive

A_{L}(x) ∼ A_{T} (x) · \frac{e^{−αβγ}}{Γ(1 + αβ)} · ∏_{\begin{matrix}q ≤ x, \\ q ∈ T \end{matrix}} (1 + q^{−β})  (4)

as x → ∞. Using the Taylor series expansion of the logarithm in the neighbourhood of 1, the asymptotic estimate (3) and the condition 1/2 < β in Lemma 3, we deduce that

log ∏_{\begin{matrix}q ≤ x, \\ q ∈ T \end{matrix}} (1 + q^{−β}) = ∑_{\begin{matrix}q ≤ x, \\ q ∈ T \end{matrix}} (q^{−β} + O(q^{−2β})) = ∑_{\begin{matrix}q ≤ x, \\ q ∈ T \end{matrix}} q^{−β} + O(1).  (5)

Using partial summation, we get

∑_{\begin{matrix}q ≤ x, \\ q ∈ T \end{matrix}} q^{−β} = x^{−β}A_{T} (x) + β ∫_{2}^{x} y^{−(β+1)}A_{T} (y) dy + O(1).  (6)

¿From (3), we obtain

∫_{2}^{x} y^{−(β+1)}A_{T} (y) dy ∼ α log log x  (7)

as x → ∞. Let ε_{0} > 0 be given. Then, combining (3), (4), (5), (6) and (7), we get

A_{L}(x) ≥ Cx^{β}(log x)^{αβ−1−ε_{0}}

for every sufficiently large real x, where C is a suitable positive constant depending on ε_{0}. This implies the result of Lemma 3 since L is a subset of K. □

We now turn to the final

Proof of Theorem. We assume that there exists a N_{0} ≥ 2 such that

A_{S}(N) ≥ (3 + ε)N^{2/3}(log N)^{−1}  (8)

holds for all integers N ≥ N_{0}. ¿From this assumption and Lemmas 2 and 3 (choose α := 3 + ε, β := 2/3 and ε_{0} := ε/3) it follows that there exist real numbers Q_{0} ≥ 2 and D > 0 such that

A_{S} (Q^{2}) ≤ DQ^{4/3} (log Q)^{−1−ε/3} + Q  (9)

for every real Q ≥ Q_{0}. But (9) contradicts (8) if N = Q^{2} and Q is sufficiently large. Therewith, the proof of Theorem is completed. □

Acknowledgement

This paper was written when the author held a Postdoctoral Fellowship at the Harish-Chandra Research Institute at Allahabad (India). He wishes to thank this institute for financial support and for providing very good working conditions. Furthermore, the author would like to thank Prof. Lutz Lucht (University of Clausthal, Germany) for some valuable comments on multiplicative functions.

References

[1] Büdern, J., Einführung in die analytische Zahlentheorie, Springer-Verlag, Berlin 1995.

[2] Erdös, P., Sárközy, A., On the divisibility of sequences of integers, Proc. London Math. Soc. (3) 21 (1970), 97-101.

[3] Knopfmacher, J., Abstract Analytic Number Theory (2nd. ed. Dover), New York 1990.

[4] Lucht, L., Asymptotische Eigenschaften multiplikativer Funktionen, J. Reine Angew. Math. 266 (1974), 200–220.

[5] Montgomery, H.L., Topics in multiplicative number theory, Springer-Verlag, Berlin 1971.

[6] Schoen, T., On a problem of Erdös and Sarközy, J. Comb. Theory Ser. A 94 (2001), no. 1, 191-195.