INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A28

AN IMPROVED UPPER BOUND ON THE MAXIMUM SIZE OF k-PRIMITIVE SETS

Peter Hegarty

Chalmers University of Technology, 41296 Göteborg, Sweden

                          hegarty@math.chalmers.se

Received: 3/7/06, Revised: 9/11/06, Accepted: 9/21/06, Published: 10/13/06

Abstract

For k ≥ 3 and sufficiently large n depending on k, Sujith Vijay recently provided non-trivial lower and upper bounds for the size of the largest subset of {1, 2, …, n} such that no element divides k others. The gap between his lower and upper bounds is, however, substantial, and here we provide a better upper bound which significantly reduces this gap for large k.

1. Introduction

Let n be a positive integer. A subset S of {1, …, n} is said to be primitive if no member of S divides any other. It is a well-known application of the pigeonhole principle, or if one prefers, of Dilworth’s theorem, that |S| ≤ ⌈n/2⌉; the divisibility poset on {1, …, n} can be decomposed into ⌈n/2⌉ disjoint chains C_{x}, one for each odd number x ∈ {1, …, n}, where C_{x} = {1, …, n} ∩ {2^{k}x : k ≥ 0}. On the other hand, the set S_{0,n} = {x : n/2 < x ≤ n} is primitive, so ⌈n/2⌉ is the maximum size of a primitive subset of {1, …, n}.

Now let k ≥ 2 be an integer. A subset S of {1, …, n} is said to be k-primitive if no member of S divides k or more others. Following [5], we denote by f_{k}(n) the maximum size of a k-primitive subset of {1, …, n}. No simple formula for f_{k}(n), for any fixed k ≥ 2, is known (see [2], Problem B24). A trivial lower bound is found by generalizing the set S_{0,n} above: the set {x : n/(k+1) < x ≤ n} is k-primitive. Larger k-primitive sets are constructed explicitly in [5], and it is deduced that, for all sufficiently large n, depending on k,

\frac{f_{k}(n)}{n} ≥ \frac{k}{k + 1} + O (\frac{1}{k^{4}} ) .

In the special case k = 2, Lebensold [3] had earlier provided an even better construction. He also used the decomposition of the divisibility poset referred to above to provide an upper bound in this special case. He obtains the result that, for sufficiently large n,

0.6725 . . . .. ≤ \frac{f_{2}(n)}{n} ≤ 0.6736 ….

and remarks that the gap between these can be improved simply by resort to more computation, rather than to any new ideas. Now as k grows, it is easy to see that the type of argument used in [3] to obtain an upper bound on f_{k}(n)/n becomes less and less effective. A non-trivial upper bound is provided in [5] for all k but, as we shall see when we quote the result below, it leaves a substantial ‘gap’ between the lower and upper bounds in a ‘noncomputational’ sense. In this note we will modify the argument in [5] which produces a new upper bound that closes this gap significantly for large k.

For convenience we set g_{k}(n) := 1− \frac{f_{k}(n)}{n} (this reverses the role of upper and lower bounds: we hope no confusion arises in what follows). The following results are proven in [5] :

Theorem A (i) For each k ≥ 3 and sufficiently large n,

\frac{1}{8k ln k} < g_{k}(n) < \frac{1}{k + 1} − \frac{1}{8k^{4}} .  (1)

(ii) For each ϵ > 0 there exists k_{0}(ϵ) such that, for each k ≥ k_{0}(ϵ) and all n ≥ n_{0}(k),

\frac{1}{(2e^{γ} + ϵ)k ln k} < g_{k}(n) < \frac{1}{k + 1} − \frac{1 − ϵ}{k^{4}},  (2)

where γ is Euler’s constant.

The point is that the lower and upper bounds in (1) and (2) have different orders of magnitude as functions of k. We will prove better lower bounds which eliminate this gap. Our result is the following

Theorem B (i) There exists an absolute constant C > 0 such that, for all k ≥ 3, and all n sufficiently large, depending on k,

\frac{1}{Ck} < g_{k}(n).  (3)

In fact, one can take C to be the unique solution in [2, ∞) of the equation

\frac{1}{t} = \frac{5}{9} [ln (\frac{2t}{t + 2}) − \frac{11(t − 2)}{20t}] ,  (4)

namely C ≈ 18.1439 … (ii) Let ϵ > 0. Then there exists k_{0}(ϵ) such that, for each k ≥ k_{0}(ϵ) and all n ≥ n_{0}(k),

\frac{1 − ϵ}{k} < g_{k}(n).  (5)

2. Proof of Theorem B

Although inequality (5) is a stronger result than (3), except for the explicit value of the constant C, we shall first prove (3) separately. A somewhat technical modification of the argument will then provide (5).

Proof of part (i). For given k and n, let S be a k-primitive subset of {1, …, n} and denote its complement inside {1, …, n} by S′. Let c > 2 be a real number and suppose that |S′| < n/ck. We will show that, for sufficiently large n, depending on k, it must hold that

\frac{1}{c} ≥ \frac{k}{2(k − 1)} [ln (\frac{2c}{c + 2}) − \frac{c − 2}{2c} (1 + \frac{1}{k})] .  (6)

This says that c ≤ c_{k} for some c_{k} ∈ [2, ∞), where c_{10} is the solution C to (4). For k ≥ 10 this means that c ≤ c_{k} ≤ c_{10} = C. This, together with (1) and the fact that 8 ln k < c_{10} for all k < 10, gives the desired result.

Let I := Z ∩ (\frac{n}{2k}, \frac{n}{k}]. For each x ∈ I we let C_{x} := \{jx : 1 ≤ j and jx ≤ n\}. Clearly,

k ≤ |C_{x}| = ⌊\frac{n}{x}⌋ ≤ 2k − 1.

Since |I| = n/2k + O(1), it follows by our assumptions that |I ∩ S| > \frac{n}{k} (\frac{c−2}{2c}) − O(1). For each x ∈ I ∩ S let D_{x} := C_{x} ∩ S′. Since S is k-primitive we have |D_{x}| ≥ |C_{x}| − k = ⌊\frac{n}{x}⌋ − k. Thus

∑_{x∈I∩S} |D_{x}| ≥ ∑_{x=⌊ \frac{n}{k} ⌋−|I∩S|+1}^{⌊ \frac{n}{k} ⌋} ⌊\frac{n}{x}⌋ − k

≥ ∑_{x= \frac{n}{k}(\frac{c+2}{2c})+O(1)}^{\frac{n}{k} +O(1)}⌊\frac{n}{x}⌋ − k

≥ n · [∫\frac{n}{k}(\frac{c+2}{2c})^{\frac{n}{k}} \frac{dx}{x} + O (\frac{k}{n})] − (k + 1) · [\frac{n}{k} (\frac{c − 2}{2c}) + O(1)]

= n · [ln (\frac{2c}{c + 2}) − \frac{c − 2}{2c} (1 + \frac{1}{k})] + O(k).

Now, by definition, ⋃_{x∈I∩S} D_{x} ⊆ S′. Let y be a member of this union. Set A_{y} := {x ∈ I ∩S : y ∈ D_{x}} and a_{y} := |A_{y}|. We have an injection A_{y} ↪ {2, …, 2k − 1} given by y ↦ y/x, hence a_{y} ≤ 2(k − 1) for every y. It follows that

| ⋃_{x∈I∩S} D_{x}| ≥ \frac{1}{2(k − 1)} ∑_{x∈I∩S} |D_{x}|

and hence that

\frac{n}{ck} > |S′| ≥ \frac{n}{2(k − 1)} [ln (\frac{2c}{c + 2}) − \frac{c − 2}{2c} (1 + \frac{1}{k})] + O(1).

Thus we’ll obtain a contradiction for sufficiently large n unless (6) is satisfied, so we’re done.

Proof of part (ii). Let ϵ ∈ (0, 1) be given. We consider a fixed, sufficiently large k and in turn a sufficiently large n (how large will be determined in due course) and let S be a k-primitve subset of \{1, …, n\} with complement S′. We suppose that |S′| < (1 − ϵ)\frac{n}{k} and aim to derive a contradiction.

Let I := Z ∩ (\frac{ϵ}{2} · \frac{n}{k}, \frac{n}{k}]. It follows from our assumptions that |I ∩ S| > \frac{ϵ}{2} · \frac{n}{k} − O(1). For each x ∈ I ∩ S define the chain C_{x} and its subset D_{x} as before. Arguing as before we have that

∑_{x∈I∩S} |D_{x}| ≥ n · [∫\frac{n}{k}(1− \frac{ϵ}{2})^{\frac{n}{k}} \frac{dx}{x} + O (\frac{k}{ϵn})] − (k + 1) · [\frac{ϵ}{2} · \frac{n}{k} + O(1)]

= n · [ln (\frac{2}{2 − ϵ}) − \frac{ϵ}{2} (1 + \frac{1}{k})] + O (\frac{k}{ϵ} ) .

Hence for any fixed k ≥ Θ (\frac{1}{ϵ}) we have, for all sufficiently large n,

∑_{x∈I∩S} |D_{x}| ≥ Θ(ϵ^{2}n).  (7)

On the other hand,

| ⋃_{x∈I∩S} D_{x}| ≤ |S′| < \frac{ϵn}{k}.  (8)

For each y ∈ ⋃_{x∈I∩S} D_{x} we define the set A_{y} as before. The map y ↦ y/x gives an injection of A_{y} into \{2, 3, …, ⌊\frac{2k}{ϵ}⌋\}, hence a_{y} < 2k/ϵ for each y. On the other hand, (7) and (8) imply that, on average, a_{y} ≥ Θ(ϵk). At the very least, we can thus deduce the following :

‘There are at least Θ (\frac{ϵ^{3}}{k} n) numbers in \{1, …, n\}, each with at least Θ(ϵk) divisors in \{1, …, ⌊\frac{2k}{ϵ}⌋\}’.

But now we have the desired contradiction, as the above statement cannot possibly be true, for any fixed ϵ ∈ (0, 1], any fixed k sufficiently large depending on ϵ, and all sufficiently large n depending on k. This follows immediately from the following lemma :

Lemma Let δ ∈ (0, 1). For each pair l, n of positive integers, set

A(n, l) := {x ∈ {1, …, n} : x has at least δ · l divisors in {1, …, l}}.

Then for each l >>_{δ} 0,

lim_{n→∞} \frac{|A(n, l)|}{n} = 0.  (9)

Proof. The result follows from a number of standard estimates in analytic number theory, but for the sake of completeness we present the argument in detail. First recall some standard notation : for each pair (x, y) of positive real numbers with 1 ≤ y ≤ x, we denote by Ψ(x, y) the number of integers in [1, x] all of whose prime divisors lie in [1, y]. It was first proven by Dickman [1] that, if ρ : [0, ∞) → (0, 1] is the unique continuous function satisfying

ρ(u) = 1, for 0 ≤ u ≤ 1,

ρ(u − 1) + u\frac{dρ}{du} = 0, for 1 < u < ∞,

then, for each u ∈ (1, ∞), lim_{x→∞} \frac{Ψ(x, x^{1/u})}{x} = ρ(u). From this and the prime number theorem it follows easily that, for any δ′ ∈ (0, 1/ρ^{−1}(δ)) and all sufficently large l (depending on δ, δ′), if A is a subset of {1, …, l} of size at least δ · l, then the numbers in A contain in total at least l^{δ′} distinct prime factors. Now consider a fixed large l and suppose (9) were false. Then for all large n there would be a positive proportion of the integers in {1, …, n} each divisible by at least l^{δ′} distinct primes in {1, …, l}. A positive proportion of these will in turn each have at least Θ_{l} [(ln n)^{l^{δ′}−1}] distinct divisors. But for all sufficiently large n this will contradict the result of Dirichlet (see any standard number theory text, for example [4], Theorem 8.28) that \frac{1}{n} ∑_{i=1}^{n} d(i) ∼ ln n, where d(i) denotes the number of divisors of i. This completes the proof of the lemma, and with it that of Theorem B.

3. Concluding Remarks

The trivial lower bound g_{k}(n) ≤ \frac{1}{k+1} gives a lower bound on the function k_{0}(ϵ) in part (ii) of Theorem B of the form

k_{0}(ϵ) ≳ \frac{1}{ϵ}.  (10)

The lower bound obtained by the above proof is, however, much worse. This is because, in the proof of the Lemma, we require at the very least that l^{\frac{1}{ρ^{−1}(δ)}} = Ω(1). This in turn implies a lower bound of the form

k_{0}(ϵ) = Ω [ϵ · exp {ρ^{−1}(cϵ^{2})}] ,  (11)

for some absolute constant c. The gap between (10) and (11) remains a challenging problem.

References

[1] K. Dickman, On the frequency of numbers containing prime factors of a certain relative magnitude, Ark. Mat. Astron. Fys. 22A, no.10, (1930), 1-14.

[2] R.K. Guy, Unsolved Problems in Number Theory (second edition). Springer Verlag, 1994.

[3] K. Lebensold, A divisibility problem, Studies in Appl. Math. 56 (1976/77), no.3, 291-294.

[4] I. Niven, H. Zuckerman and H. Montgomery, Introduction to the Theory of Numbers (fifth edition). Wiley, 1991.

[5] S. Vijay, On the largest k-primitive subset of [1, n], Integers : Electronic Journal of Combinatorial Number Theory 6 (2006), Paper A1.