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

ON THE LARGEST k-PRIMITIVE SUBSET OF [1,n]

Sujith Vijay

Department of Mathematics, Rutgers University, New Brunswick, NJ 08854, USA.

                          sujith@math.rutgers.edu

Received: 6/28/04, Revised: 1/24/06, Accepted: 1/27/06, Published: 2/1/06

Abstract

We derive bounds on the size of the largest subset of {1, 2, ..., n} such that no element divides k others, for k ≥ 3 and sufficiently large n.

1. Introduction

Let S ⊆ IN be a finite set of positive integers. We say that S is k-primitive if no member of S divides k other elements in S.

Let f_{k}(n) denote the size of the largest k-primitive subset of [1, n]. It is well-known that f_{1}(n) = ⌈\frac{n}{2}⌉. Lebensold [2] showed that, if n is sufficiently large,

(0.672...) < \frac{f_{2}(n)}{n} < (0.673...).

In this article, we show that, for k ≥ 3 and sufficiently large n,

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

Moreover, given ϵ > 0, there exists k_{0}(ϵ) such that for k ≥ k_{0}(ϵ) and n ≥ n_{0}(k),

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

2. The Lower Bound

For α ∈ IR and S ⊆ IN, we shall write αS to denote the set {αx : x ∈ S}. We begin by deriving a lower bound on f_{k}(n).

Define S_{0} = \{x : (k + 1)x > n\}, with |S_{0}| = \frac{nk}{k+1} + O(1). Clearly, S_{0} is k-primitive. Let S_{1} = \{x : \frac{n}{k+3} < x < \frac{nk}{(k+1)^{2}} , k(k + 1)| x\}. Observe that any element in S_{1} has exactly k + 1 other multiples in [1, n]. Let S_{2} = (k + 1)S_{1}, S_{3} = (k + 2)S_{1} and S′ = (S_{0} ∪ S_{1}) \ (S_{2} ∪ S_{3}). Note that S′ is k-primitive.

Let S_{4} = (k + 1)^{−1}S_{3} and and S_{5} = k^{−1}S_{2}. Any element in S_{4} ∪ S_{5} has at most k other multiples in [1, n]. By construction, at least one of these will not occur in S′. Furthermore, no multiple of an element in S_{4}, except possibly itself, occurs in S_{5} and vice versa. It follows that S ≐ S′ ∪ S_{4} ∪ S_{5} is k-primitive.

Note that

|S_{i}| = \frac{n(k − 1)}{k(k + 1)^{3}(k + 3)} + O(1), for 1 ≤ i ≤ 5.

Furthermore,

S_{i} ∩ S_{j} = ∅ for 1 ≤ i < j ≤ 5 except when i = 4 and j = 5.

Finally,

|S_{4} ∩ S_{5}| = \frac{n(k^{3} − 4k − 1)}{k^{2}(k + 1)^{5}(k + 2)(k + 3)} + O(1).

Thus we have,

|S| = |S_{0}| + |S_{1}| − |S_{4} ∩ S_{5}| > n (\frac{k}{k + 1} + \frac{1}{8k^{4}} ) .

Note that for sufficiently large k,

|S| > n (\frac{k}{k + 1} + \frac{1 − ϵ}{k^{4}}) .

3. The Upper Bound

Let S be a k-primitive subset of [1, n]. For a positive integer x ≤ n/(k + 1), let C_{x} ≐ {x, 2x, …, (k + 1)x} be the chain containing x. Observe that C_{x} ⊆ [1, n] and |S ∩ C_{x}| ≤ k.

Thus if C_{x_{1}}, C_{x_{2}}, …, C_{x_{m}} are pairwise disjoint, |S| ≤ n − m.

Let X = \{x : \frac{n}{2(k+1)} < x < \frac{n}{k+1}, x has no prime factor in [2, k]\}. Thus if r ≤ k and x ∈ X, we have (r, x) = 1.

We claim that {C_{x_{m}}}, x_{m} ∈ X is a pairwise disjoint collection.

Suppose not. Let rx_{i} = sx_{j}, x_{i} ≠ x_{j}, 1 ≤ r < s ≤ k + 1. Since r ≤ k and x_{j} ∈ X, we have (r, x_{j}) = 1. Thus x_{j}| x_{i}, i.e., x_{i} ≥ 2x_{j} > \frac{n}{k+1}, which is impossible. This proves our claim.

Let P_{k} denote the product of the prime numbers not exceeding k. The easy estimate P_{k} < 3^{k}, together with an application of the Chinese Remainder Theorem, yields

|X| = \frac{n}{2(k + 1)} ∏_{p≤k} (1 − \frac{1}{p}) + O(3^{k}).

By Mertens’s theorem,

∏_{p≤x} (1 − \frac{1}{p}) ≥ \frac{1}{e^{γ+δ} ln x} where |δ| < \frac{4}{ln(x + 1)} + \frac{1}{2x} + \frac{2}{x ln x}.

Computations for a bounded initial segment (suffices to consider x < 12000) establish that

∏_{p≤x} (1 − \frac{1}{p}) ≥ \frac{ln 3}{3 ln x} for x ≥ 3.

Therefore, we obtain, for k ≥ 3,

|X| > \frac{n}{8k ln k}

and, for sufficiently large k,

|X| > \frac{n}{(2e^{γ} + ϵ)k ln k} .

References

[1] R. K. Guy, Unsolved Problems in Number Theory, Second Edition. Springer-Verlag, 1994.

[2] K. Lebensold, A divisibility problem, Studies in Applied Mathematics 56, 1977.

[3] F. Mertens, Ein Beitrag zur analytyischen Zahlentheorie, Journal für die Reine und Angewandte Mathematik 78, 1874.