MAXIMAL SETS OF INTEGERS WITH DISTINCT DIVISORS

R. Balasubramanian and K. Soundararajan

Institute for Mathematical Sciences, Tharamani P. O., Madras 600 113, India. Department of Mathematics, Princeton University, Princeton, N. J. 08544, U.S.A.

Submitted: May 23, 1995; Accepted October 22, 1995

Abstract. A set of positive integers is said to have the distinct divisor property if there is an injective map that sends every integer in the set to one of its proper divisors. In 1983, P. Erdős and C. Pomerance showed that for every c > 1, a largest subset of [N, cN] with the distinct divisor property has cardinality ∼ δ(c)N, for some constant δ(c) > 0. They conjectured that δ(c) ∼ c/2 as c → ∞. We prove their conjecture. In fact we show that there exist positive absolute constants D_{1}, D_{2} such that D_{1} ≤ c^{β}(c/2 − δ(c)) ≤ D_{2} where β = log 2/ log(3/2).

1. Introduction

Let S denote a set of positive integers and τ : S → ℕ be defined so that τ(s) is a proper divisor of s (that is, τ(s) divides s and τ(s) < s). The ensemble (S, τ) is said to have the ‘distinct divisor property’ if τ is injective, that is, if the τ(s) are different for different values of s. We will also say that S has the distinct divisor property if there exists a τ, as above, such that (S, τ) has the distinct divisor property.

Let c > 1 denote a real number and N a large natural number. Let S be a subset of [N, cN] with the distinct divisor property such that, of all subsets of [N, cN] having distinct divisors, S has maximal cardinality. If c is fixed and N tends to infinity then P. Erdős and C. Pomerance, [1], have shown that

|S| = (δ(c) + o(1))N

where δ(c) is a continuous increasing function of c. As c tends to 1 they established that

δ(c) = c − 1 + o(1).

In this note we are concerned with the behaviour of δ(c) as c tends to infinity. Division by 2 clearly invests the set of even integers in [N, cN] with the distinct divisor property; hence δ(c) ≥ (c − 1)/2. Also, since a proper divisor of an integer less than cN is less than cN/2 clearly δ(c) ≤ c/2. Erdős and Pomerance conjectured that this latter upper bound is actually the truth for large c. In other words they conjectured that as c tends to infinity

δ(c) = \frac{c}{2} + o(1).

Typeset by AMS-TEX

1991 Mathematics Subject Classification. Primary 11A05.

We prove this and more by finding the exact order of magnitude for c/2 − δ(c) as c → ∞.

Theorem 1. There exist positive absolute constants D_{1} and D_{2} such that

\frac{D_{1}}{c^{β}} ≤ \frac{c}{2} − δ(c) ≤ \frac{D_{2}}{c^{β}} ,

where β = log 2/ log(3/2) = 1.7095 . . ..

We realise Theorem 1 as the sum of the following two Propositions, which are proved by two very different arguments.

Proposition 2. Let k denote the greatest integer not exceeding log c/ log(3/2). Suppose S is a subset of the integers in [N, cN] and that (S, τ) satisfies the distinct divisor property. Then

\frac{cN}{2} − |S| ≥ \frac{N}{2^{k+2}} + O(k).

Proposition 3. Suppose c > 2. There exists a subset, S, of integers in [N, cN] and a map τ such that (S, τ) obeys the distinct divisor property and with

\frac{cN}{2} − |S| ≪ \frac{N}{c^{β}} .

All implied constants are absolute; that is they are independent of c and N. The restriction to c > 2 in Proposition 3 is obviously harmless. The presence of the constant β is best explained by noting that it is the minimum value of the function log p_{i}/ log(p_{i+1}/p_{i}) (where p_{i} denotes the ith smallest prime).

We thank Professor A. Granville to whom our present exposition is largely due. An earlier version of this note proved the weaker result δ(c) = c/2 + o(1). We are grateful to the referee, Professor C. Pomerance, who, by simplifying our earlier proof, helped clarify the situation and motivated us to strengthen our result.

2. Proof of Proposition 2

We partition the interval (N, cN] into the sets B_{1} ∪ B_{2} ∪ ⋯ ∪ B_{k+1} where B_{j} = ((2/3)^{j}cN, (2/3)^{j−1}cN] for j = 1, 2, …, k, and B_{k+1} = (N, (2/3)^{k}cN]. Similarly we partition [1, cN/2], where the potential divisors lie, into intervals A_{1} ∪ A_{2} ∪ ⋯ ∪ A_{k+2}, where A_{i} = ((2/3)^{i}cN/2, (2/3)^{i−1}cN/2] for i = 1, 2, …, k, with A_{k+1} = (N/2, (2/3)^{k}cN/2] and A_{k+2} = (1, N/2]. Note that if s ∈ B_{j} then any proper divisor of s must lie in some interval A_{i} with i ≥ j; moreover, if that divisor lies in A_{j}, then it must be s/2, since any other proper divisor is ≤ s/3 ≤ (2/3)^{j−1}cN/3 = (2/3)^{j}cN/2 and thus belongs to A_{i} for some i > j.

Now [cN/2] − |S| = [cN/2] − |τ(S)| counts the number of integers in [1, cN/2] that do not belong to τ(S). We obtain a lower bound for this quantity by only counting, for each i, those integers n ∈ A_{i} which do not belong to τ(S), and which are divisible by 2^{i−1}. Thus

[cN/2] − |S| ≥ ∑_{i=1}^{k+2} (#{n ∈ A_{i} : 2^{i−1}|n} − #{s ∈ S : τ(s) ∈ A_{i}, 2^{i−1}|τ(s)}) .

As we saw above, if τ(s) ∈ A_{i} then s ∈ B_{j} for some j ≤ i. Suppose that 2^{i−1} divides τ(s). We claim that 2^{j} divides s, which follows if j = i since 2^{j−1} divides τ(s) = s/2; and which follows if j < i since then 2^{j} divides 2^{i−1}, which divides τ(s), which divides s. Therefore

∑_{i=1}^{k+2} #{s ∈ S : τ(s) ∈ A_{i}, 2^{i−1}|τ(s)} ≤ ∑_{j=1}^{k+1} #{s ∈ B_{j} : 2^{j}|s}

(noting that, since τ is injective, no value of s gets counted twice in the argument above). Now #{n ∈ A_{i} : 2^{i−1}|n} = #{n ∈ B_{i} : 2^{i}|n} + O(1), so substituting this into the two displays above, we get

[cN/2] − |S| ≥ #{n ∈ A_{k+2} : 2^{k+1}|n} + O(k) = N/2^{k+2} + O(k).

3. Proof of Proposition 3

We wish to construct a ‘big’ set S of integers s in [N, cN] with the distinct divisors τ(s); since τ is injective, this is equivalent to constructing a ‘big’ set R = τ(S) ⊂ [1, cN/2], such that for each n ∈ R, there exists some distinct proper multiple τ^{−1}(n), of n, in [N, cN]. In fact we shall select τ^{−1}(n) = np(n) for some prime p(n), which we choose as follows: For n = [cN/2] let p([cN/2]) = 2. For n = [cN/2] − 1, [cN/2] − 2, …, 1 we define p(n) to be the largest prime p for which

i) N < np ≤ cN, and

ii) np ≠ n′p(n′) for any n′ > n, with n′ ≤ [cN/2], provided such a prime p exists, otherwise we let p(n) = 0 (and then n ∉ R). We note that |S| = |R| is exactly the number of integers n ≤ cN/2 for which p(n) ≠ 0; and thus

[cN/2] − |S| = #{n ≤ cN/2 : p(n) = 0}.  (1)

For each prime p_{k}, we define the set of integers

I_{k} = {p_{1}^{α_{1}}p_{2}^{α_{2}} … p_{k}^{α_{k}} : α_{k} ≥ 1, ∏_{j=1}^{k}(p_{j+1}/p_{j})^{α_{j}} > c/2}.

Lemma. If p(n) = 0 for some integer n ≤ cN/2, then there exists k such that n ≤ N/p_{k}, and I_{k} contains a divisor d of n.

We now complete the proof of Proposition 3, postponing the proof of the Lemma:

Proof of Proposition 3. Using the Lemma we have

#\{n ≤ cN/2 : p(n) = 0\} ≤ ∑_{k≥1} ∑_{d∈I_{k}} #\{n ≤ N/p_{k} : d|n\} ≤ ∑_{k≥1} \frac{N}{p_{k}} ∑_{d∈I_{k}} \frac{1}{d}. (2)

By definition, we have that

∑_{d∈I_{k}} \frac{1}{d} ≤ ∑_{α_{k}≥1} \frac{1}{p_{k}^{α_{k}}} ∑_{α_{k−1}≥0} \frac{1}{p_{k−1}^{α_{k−1}}} … ∑_{α_{2}≥0} \frac{1}{p_{2}^{α_{2}}} ∑_{α_{1}≥A_{1}} \frac{1}{2^{α_{1}}} ,  (3)

where (3/2)^{A_{1}} > (c/2)/ ∏_{j=2}^{k}(p_{j+1}/p_{j})^{α_{j}} ≥ (c/2)/(5/3)^{(α_{2}+α_{3}+···+α_{k})}, from the definition of the set I_{k}, since p_{j+1}/p_{j} ≤ 5/3 when j ≥ 2. Therefore, setting γ = 2^{log(5/3)/ log(3/2)} ≈ 2.39471, we get

∑_{α_{1}≥A_{1}} \frac{1}{2^{α_{1}}} ≪ \frac{1}{2^{A_{1}}} ≪ c^{−β}γ^{α_{2}+α_{3}+···+α_{k}}.

Substituting this into (3) gives

∑_{d∈I_{k}} \frac{1}{d} ≪ c^{−β} ∑_{α_{k}≥1} (\frac{γ}{p_{k}} )^{α_{k}} ∑_{α_{k−1}≥0} (\frac{γ}{p_{k−1}} )^{α_{k−1}} … ∑_{α_{2}≥0} (\frac{γ}{p_{2}} )^{α_{2}}

= c^{−β} \frac{γ}{p_{k}} ∏_{i=2}^{k} (1 − \frac{γ}{p_{i}} )^{−1} ≪ c^{−β} \frac{1}{p_{k}} ∏_{3≤p≤p_{k}} (1 − \frac{1}{p})^{−γ} ≪ c^{−β} \frac{(log p_{k})^{γ}}{p_{k}} ,

using Mertens’ theorem that ∏_{p≤x}(1 − 1/p) ≍ 1/ log x (see [2] for example). Substituting this estimate into (2), and that estimate back into (1), gives

cN/2 − |S| = #\{n ≤ N/2 : p(n) = 0\} ≪ c^{−β}N ∑_{k≥1} \frac{(log p_{k})^{γ}}{p_{k}^{2}} ≪ N/c^{β}.

Finally we return to the

Proof of the Lemma. We must have n ≤ N/2 for, if cN/2 ≥ n > N/2 then p = 2 satisfies i) N < 2n ≤ cN, and ii) 2n ≠ n′p(n′) for any n′ > n, since n′p(n′) ≥ 2n′ > 2n, so that p(n) ≥ 2.

Let p_{k_{0}} be the least prime exceeding N/n; by Bertrand’s postulate p_{k_{0}} ≤ 2N/n < cN/n (since c > 2), and so N < np_{k_{0}} ≤ cN. However p(n) = 0, which means that np_{k_{0}} cannot satisfy (ii) above; in other words, there must exist an integer n_{1} > n such that np_{k_{0}} = n_{1}p_{k_{1}} (where we define k_{1} so that p_{k_{1}} = p(n_{1})). We note that p_{k_{0}} > p_{k_{1}} (since n_{1} > n and np_{k_{0}} = n_{1}p_{k_{1}}), so that p_{k_{1}} ≤ N/n and thus n ≤ N/p_{k_{1}}.

We now construct a useful sequence of integers n_{1}, n_{2}, n_{3}, …, n_{m} ∈ R (for some m); we show how to determine n_{j+1} from n_{j}:

Let k_{j} be defined by the relation p_{k_{j}} = p(n_{j}).

• If n_{j}p_{k_{j}+1} > cN then let m = j, and the sequence is terminated.

• If n_{j}p_{k_{j}+1} ≤ cN then there must exist an integer n_{j+1} > n_{j} for which n_{j}p_{k_{j}+1} = n_{j+1}p(n_{j+1}) (else p(n_{j}) ≥ p_{k_{j}+1} by definition).

Since n_{j+1}p_{k_{j+1}+1} > n_{j+1}p_{k_{j+1}} = n_{j}p_{k_{j}+1}, we see that n_{1}p_{k_{1}+1} < n_{2}p_{k_{2}+1} < n_{3}p_{k_{3}+1} < … forms an increasing sequence of integers, and so we will eventually find an integer m for which n_{m}p_{k_{m}+1} > cN.

We have seen that n < n_{1} < n_{2} < ⋯ < n_{m}, and thus p_{k_{0}} > p_{k_{1}} ≥ p_{k_{2}} ≥ p_{k_{3}} ≥ ⋯ ≥ p_{k_{m}} (since n_{j+1} > n_{j} and n_{j}p_{k_{j}+1} = n_{j+1}p_{k_{j+1}} imply that p_{k_{j}+1} > p_{k_{j+1}}, and thus p_{k_{j}} ≥ p_{k_{j+1}}). Now n_{j+1} = (p_{k_{j}+1}/p_{k_{j+1}})n_{j}; iterating this gives

n_{j} = (\frac{p_{k_{j−1}+1}}{p_{k_{j}}} ) (\frac{p_{k_{j−2}+1}}{p_{k_{j−1}}} ) … (\frac{p_{k_{1}+1}}{p_{k_{2}}} ) (\frac{p_{k_{0}}}{p_{k_{1}}} ) n.  (4)

Define d = p_{1}^{α_{1}}p_{2}^{α_{2}} … p_{k}^{α_{k}} = p_{k_{m}}p_{k_{m−1}} … p_{k_{2}}p_{k_{1}} where k = k_{1}. We show that d divides n by proving that p_{i}^{α_{i}} divides n for each i: Let j be the largest integer for which k_{j} = i. Then p_{k_{j}}p_{k_{j−1}} … p_{k_{1}} = p_{i}^{α_{i}}p_{i+1}^{α_{i+1}} … p_{k}^{α_{k}}. Moreover i ≤ k_{j−1} < k_{j−1} + 1 ≤ k_{j−2} + 1 ≤ ⋯ ≤ k_{1} + 1 ≤ k_{0}, and so p_{i} is coprime with p_{k_{j−1}+1}p_{k_{j−2}+1} … p_{k_{1}+1}p_{k_{0}}. Now, p_{i}^{α_{i}} divides p_{k_{j}}p_{k_{j−1}} … p_{k_{1}}, which is a divisor of (p_{k_{j−1}+1}p_{k_{j−2}+1} … p_{k_{1}+1}p_{k_{0}})n by (4), since n_{j} is an integer; and so p_{i}^{α_{i}} divides n.

To complete the proof of the Lemma we need to show that d ∈ I_{k}, which we do by taking (4) with j = m, multiplying it by p_{k_{m+1}} and rearranging, to get

∏_{i=1}^{k} (\frac{p_{i+i}}{p_{i}} )^{α_{i}} = (\frac{p_{k_{m}+1}}{p_{k_{m}}} ) (\frac{p_{k_{m−1}+1}}{p_{k_{m−1}}} ) … (\frac{p_{k_{1}+1}}{p_{k_{1}}} ) = \frac{n_{m}p_{k_{m}+1}}{np_{k_{0}}} > \frac{cN}{2N} = \frac{c}{2},

using the fact that p_{k_{0}} ≤ 2N/n, by Bertrand’s postulate.

References

[1] P. Erdős and C. Pomerance, An analogue of Grimm’s problem of finding distinct prime factors of consecutive integers. Util. Math. 24 (1983), 45-65.

[2] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers. Fourth edition; New York; Oxford University Press, 1960.