A generalization of primitive sets and a conjecture of Erdős
Tsz Ho Chan Jared Duker Lichtman Carl Pomerance
math.NT math.CO 11B75 (Primary), 11A05, 05C70 (Secondary)


[classification=text]









 




THC]Tsz Ho Chan
JDL]Jared Duker Lichtman
CP]Carl Pomerance



A set of integers greater than 1 is primitive if no element divides another. Erdős proved in 1935 that the sum of 1/(n log n) for n running over a primitive set A is universally bounded over all choices for A. In 1988 he asked if this universal bound is attained by the set of prime numbers. 

We answer the Erdős question in the affirmative for 2-primitive sets. Here a set is 2-primitive if no element divides the product of 2 other elements. 






§ INTRODUCTION AND STATEMENT OF RESULTS




A set of integers greater than 1 is called primitive if no element divides any other. Erdős <cit.> showed that there is a constant K such that for any primitive set A,

    f(A):=∑_n ∈ A1/n log n≤ K.

Further, in 1988 he asked if f(A) is maximized by the primes A = ℙ.  This is now referred to as the Erdős conjecture for primitive sets:

    For A primitive, we have  f(A)≤ f(ℙ)=  ∑_p ∈ℙ1/p log p =: C = 1.636616⋯,

where ℙ is the set of prime numbers. By a simple argument, the Erdős conjecture is equivalent to the assertion that f(A) ≤ f(𝒫(A)) for any primitive set A, where 𝒫(A) denotes the set of primes dividing some member of A.

Recently, the second and third authors <cit.> proved that
 
For any primitive set A,

    f(A) < e^γ = 1.781072⋯

where γ = 0.5772⋯ is the Euler-Mascheroni constant.
Further, if A does not contain a multiple of 8,  then

    f(A) ≤ f(𝒫(A)) + 2.37 × 10^-7.



One can strengthen the notion of primitivity as follows. We say that a set A of integers greater than 1 with |A|≥ k+1
is k-primitive if no element divides the product of k distinct other elements. Note that k-primitive implies j-primitive for all k≥ j≥ 1.

In 1938, Erdős <cit.> first studied the maximal cardinality of 2-primitive sets in an interval. 
The first author together with Győri and Sárközy <cit.> extended it to all k and it was subsequently improved in <cit.> and <cit.>. While the full conjecture remains out of reach, we prove the Erdős conjecture for 2-primitive sets (and hence k-primitive for all k≥2).
 
For any 2-primitive set A,

    f(A) ≤ f(𝒫(A)).


An immediate consequence is the following

If A is a primitive set with f(A) > f(𝒫(A)), then there exist three elements a,b,c∈ A with a |  bc.


On the other hand, the primes are not optimal among primitive sets with respect to logarithmic density. Indeed, Erdős, Sárközy, and Szemerédi <cit.> obtained the best possible upper bound

    ∑_n ∈ A_n ≤ x1/n≤( 1/√(2 π) + o(1) ) log x/√(loglog x)

for any primitive set A, while Erdős <cit.> showed that

    ∑_n ∈ A'_n ≤ x1/n≥( 1/√(2 π) + o(1) ) log x/√(loglog x)

where A' is the set of positive integers a ≤ x with Ω(a) = [loglog x]. (Here,
Ω(a) is the number of prime factors of a, counted with multiplicity.)
By contrast, the primes satisfy

    ∑_p ≤ x1/p = loglog x + O(1).


Nevertheless, one may wonder if the primes still maximize the logarithmic density among 2-primitive sets. Indeed, we prove this to be the case.
 
For all x≥2 and any 2-primitive set A,

    ∑_n ∈ A_n ≤ x1/n≤∑_p ∈𝒫(A)_p≤ x1/p


We use this to deduce Theorem <ref>.



By Proposition <ref>, we have F(x)≥0 for all x≥2, where

    F(x) := ∑_p ∈𝒫(A)_p ≤ x1/p - ∑_n ∈ A_n ≤ x1/n

Then by partial summation,

    ∑_p ∈𝒫(A)_p ≤ x1/p log p - ∑_n ∈ A_n ≤ x1/n log n = 
    F(x)/log x + ∫_2^-^xF(u)/u log^2 u du ≥ 0.

Hence taking x→∞ gives f(𝒫(A)) ≥ f(A) as desired.





In light of Proposition <ref>, it is natural to ask if there exists an exponent λ<1 for which 

    ∑_n ∈ A
    n≤ x1/n^λ≤∑_p ∈𝒫(A)
    p≤ x1/p^λ

holds for all 2-primitive A, x≥2. Banks and Martin <cit.> settled the question in the setting of 1-primitive sets, proving (<ref>) holds for all primitive A if and only if

    λ≥τ_1:=1.1403659⋯,

where t=τ_1 is the unique real solution to the equation

    ∑_ℙ p^-t = 1+(1-∑_ℙ p^-2t)^1/2.

The fact that τ_1 is markedly larger than 1 gives some indication as to why the full Erdős conjecture remains open.


In the setting of 2-primitive sets, we extend the range of valid exponents λ.
 
For any λ≥ 0.7983, x≥2, and any 2-primitive set A,

    ∑_n ∈ A
    n≤ x1/n^λ≤∑_p ∈𝒫(A)
    p≤ x1/p^λ


We remark it suffices to verify Theorem <ref> with λ=0.7983.  Indeed, suppose that  F_λ(x)≥0 for all x≥2, where 

    F_t(x) = ∑_p∈𝒫(A)
     p≤ xp^-t - ∑_n∈ A
     n≤ x n^-t.

Then, by partial summation, for any t>λ,

    F_t(x) = x^λ - tF_λ(x) + (t-λ)∫_2^x u^λ-t-1 F_λ(u)  du ≥ 0.

Hence we may define the critical exponent τ_2 for 2-primitive sets, as the infimum over all λ for which (<ref>) holds.
Thus, Theorem <ref> implies that τ_2≤0.7983.


We also note that Theorem <ref> with λ=1 gives us Proposition <ref>.
However, Theorem <ref> does not hold for every positive value of λ.  Indeed, 
in <cit.>, Erdős showed that there is a 2-primitive set A in [1,x] of cardinality π(x) - π(x^1/3) + c x^2/3 / (log x)^2. It consists of primes in (x^1/3, x] and a subset of { p_1 p_2 p_3 : p_i  are  primes ≤ x^1/3} where the triples {p_1, p_2, p_3} form a Steiner triple system. Thus, by the prime number theorem,

    ∑_n ∈ A1/n^λ≥∑_x^1/3 < p ≤ x1/p^λ + c x^2/3/(log x)^21/x^λ > ∑_p ≤ x1/p^λ

when λ < 0.5 and x is sufficiently large. Hence the above argument and Theorem <ref> together imply that the critical exponent lies in the interval

    0.5 ≤τ_2 ≤ 0.7983.


 

In a sequel paper, we shall address the question of critical exponents for k-primitive sets, with k≥3.





§ COMBINATORIAL LEMMAS


Before proving Theorem <ref>, we need lemmas in counting the maximal number of elements in a k-primitive set.

We first recall the following famous result due to Erdős and Szekeres <cit.>,
whose proof we provide for completeness.

A sequence of (r-1)(s-1)+1 real numbers has either a monotonic nondecreasing subsequence of length r
or a monotonic nonincreasing subsequence of length s.


Say the sequence is a_1,a_2,…,a_n, where n=(r-1)(s-1)+1.
For each a_i consider the ordered pair (b_i,c_i), where b_i is the length of the
longest nondecreasing subsequence ending at a_i and c_i is the length of the longest nonincreasing
subsequence ending at a_i.  Then no two pairs (b_i,c_i) and (b_j,c_j) can be equal, 
so for at least one choice of i we have b_i≥ r or c_i≥ s.


We next bound the size of a k-primitive set based on the number of prime factors used to generate its elements.

 
For k≥2, suppose A is a k-primitive set and T⊂ A with |𝒫(T)| = n. If n≤ k, then |T|≤ n. If n=k+1, then |T|≤ n+1. 
Further, for k=2,  n=4 we have |T|≤ 19.

 
We may assume that |T|≥ n.
Let 𝒫(T) = {q_1,…,q_n} and write each t=∏_i q_i^e_i∈ T as an exponent vector v⃗ = (e_1,…,e_n). Define the notation v⃗≥0 if e_i≥0 for all i, and define v⃗≤w⃗ if
 w⃗-v⃗≥0.
Take v⃗_1 with maximal entry e_1 among T.  Then take
v⃗_2 with maximal e_2 among the remaining vectors, and similarly define
 v⃗_3,…,v⃗_n.  Thus, the chosen vectors are distinct.

Case n≤ k: If |T|≥ n+1 then T has some vector v⃗≠v⃗_i for all i. But then v⃗≤v⃗_1+⋯+v⃗_n.  This implies that T, and hence A, is not n-primitive, and since n≤ k, it
implies that A is not k-primitive, a contradiction.  Hence we cannot have |T|≥ n+1 when n≤ k.

Case n=k+1: If |T|≥ n+2 then T has vectors w⃗_1w⃗_2
with w⃗_j∉{v⃗_1,…v⃗_n} for j=1,2. Write w⃗_j = (f_1^(j),…,f_n^(j)). By the pigeonhole principle, we may assume

    f_i^(1)≤ f_i^(2)

for at least n/2 values of i, say i=1,…, ⌈ n/2⌉. Thus, we deduce

    w⃗_1 ≤w⃗_2 + v⃗_⌈ n/2⌉+1+⋯+v⃗_n

 contradicting T as k-primitive, since 1 + ⌊ n/2 ⌋=1+⌊(k+1)/2⌋≤ k.
 
Now say k=2, n = 4.
Suppose there are 20 members in T with corresponding vectors

    w⃗_i := (e_i,1, e_i,2, e_i,3, e_i_4)  for  1 ≤ i ≤ 20.

Since A is 2-primitive, so is T.
Without loss of generality, say w⃗_18 has maximal first coordinate, w⃗_19w⃗_18
has maximal second coordinate among the remaining 19 vectors, and 
w⃗_20 has maximal third coordinate among the remaining 18 vectors with
w⃗_20w⃗_18,w⃗_19.
Arrange the remaining 17 vectors in ascending order of their first coordinate (i.e.,  e_1,1≤ e_2,1≤ ... ≤ e_17,1). By Lemma <ref>, there is a monotonic sequence of length 5 among the e_i,2's. Without loss of generality, say e_1,2, e_2,2, e_3,2, e_4,2, e_5,2 form such a sequence.

Case 1: e_1,2≤ e_2,2≤ e_3,2≤ e_4,2≤ e_5,2. Consider the numbers e_i,3 for i=1,…,5.
By Lemma <ref>, there is a monotonic sequence 
of length 3 among the e_i,3's, without loss of generality, say it is e_1,3,e_2,3,e_3,3.
If e_1,3≤ e_2,3≤ e_3,3, this forces e_2,4 > e_1,4 + e_3,4 for otherwise w⃗_2≤w⃗_1+w⃗_3, contradicting T being 2-primitive.
 But this implies that w⃗_1 ≤w⃗_2  which contradicts T being primitive. Hence, we must have e_1,3≥ e_2,3≥ e_3,3. Again, this forces e_2,4 > e_1,4 + e_3,4, which in turn implies that
 w⃗_1≤w⃗_2+w⃗_20, again a contradiction.
 
Case 2: e_1,2≥ e_2,2≥ e_3,2≥ e_4,2≥ e_5,2. By Lemma <ref>, there is a monotonic sequence of length 3 among the e_i,3's, without loss of generality, say it is e_1,3,e_2,3,e_3,3.  If 
e_1,3≤ e_2,3≤ e_3,3, then again this forces e_2,4>e_1,4+e_3,4.
But then w⃗_1≤w⃗_2+w⃗_19.
 Hence, we must have e_1,3≥ e_2,3≥ e_3,3. This forces e_2,4 > e_1,4 + e_3,4. But then 
 w⃗_3≤w⃗_2+w⃗_18, again a contradiction.

Therefore, there can be at most 19 members in T.



It is not clear if the number “19" in Lemma <ref> is optimal.
We will not need it here, but by similar methods one can prove that if
T is a 2-primitive set of positive integers with |𝒫(T)| = n≥3,
then |T|≤ 9^2^n-3.





§ PROOF OF THEOREM <REF>

Let A⊂(1,x] be a 2-primitive set. 
Let 0.79 ≤λ < 1 be a parameter to be defined later. First, we partition A into primes S and composites T. Note S and 𝒫(T) are disjoint since A is primitive. For a prime p, define

    T_p := { t ∈ T : p |  t }.

If some prime p ∈𝒫(T) satisfies

    ∑_t ∈ T_p1/t^λ≤1/p^λ,

then we replace the members of T_p with the prime p (i.e., redefine A=(T\ T_p)∪{ p }). This would make ∑_T_p t^-λ at least as big while keeping A 2-primitive. Repeat the process with each prime p ∈𝒫(T) until no such prime satisfies (<ref>). If T = ∅ after doing this, then A=S consists of primes so Proposition <ref> follows. Otherwise T ≠∅, so we may assume

    ∑_t ∈ T_p1/t^λ > 1/p^λ     for all   p ∈𝒫(T).

Consider the set

    D := {t / p : t ∈ T ,  p |  t }


We record some useful properties of T and D.

Let T be a 2-primitive set for which (<ref>) holds and let D be as in (<ref>).


  (i) For each p∈𝒫(T),  T_p has at least 3 elements.

  (ii) The map sending ordered pairs (t, p) with t∈ T and p| t to t/p∈ D is injective.

  (iii) Each t∈ T has at least 3 prime factors (counted with multiplicity).

  (iv) D is a primitive set of composite numbers.



(i) 
For p∈𝒫(T), (<ref>) implies that 

    ∑_t∈ T_p1/(t/p)^λ>1>2^-0.79+3^-0.79,

Thus (i) follows, since t/p∈ℤ_>1 for all t∈ T_p.

(ii)  If not, then t_1 / p_1 = t_2 / p_2 for some t_1, t_2, p_1 | t_1, and p_2 |  t_2.  If t_1 ≠ t_2, by (i) there exists some p_1 k ∈ T_p_1 other than t_1,t_2. But then t_1 = (t_1 / p_1) p_1 = (t_2 / p_2) p_1 | t_2 (p_1 k), which contradicts T as 2-primitive. Hence t_1 = t_2, which forces p_1 = p_2.

(iii) If not, say t = p q. Since T_p,T_q each have at least 3 elements, there are some p m and q n other than t∈ T. But then, t = p q |  (p m)(q n) which contradicts T as 2-primitive.  (This argument holds whether or not p q.)

(iv) If not, then (t / p) |  (t_1 / p_1) for some t, t_1 ∈ T, p |  t, p_1 |  t_1,
and t/p t_1/p_1. If p_1 = p, then t |  t_1 which contradicts T as primitive. And if p_1 ≠ p, then there is some p l ∈ T_p other than t and t_1. This implies t |  t_1· p l, and since
t t_1 (otherwise p=p_1), we have a contradiction to T being 2-primitive. Thus D is primitive, and also composite by (iii).


For Theorem <ref>, we must show

    ∑_t ∈ T1/t^λ - ∑_p ∈𝒫(T)1/p^λ < 0.

Suppose 𝒫(T) consists of primes q_1 < q_2 < ⋯ < q_r. Let 2 = p_1 < p_2 < ⋯ < p_r be the first r primes in ℙ. We are going to modify the set T by the following process. First, if each q_i=p_i,
we let T stand as it is.  Otherwise, let i be the smallest index such that q_i > p_i.  Then q_j=p_j
for all j<i and we have p_i∤ t for all t∈ T.  Then replace each t∈ T_q_i with p_i/q_i· t.
This keeps T as 2-primitive, and by (<ref>),

    0  <  ∑_t∈ T_q_i1/t^λ -1/q_i^λ <  q_i^λ/p_i^λ(∑_t∈ T_q_i1/t^λ-1/q_i^λ)
    =∑_t∈ T_q_i1/(p_i/q_i· t)^λ-1/p_i^λ.

So replacing each t∈ T_q_i with p_i/q_i· t preserves (<ref>).  We repeat this
process for each i with q_i>p_i and in the end we have 𝒫(T)={p_1,p_2,…,p_r}.
By showing (<ref>) for this T it would follow that (<ref>) fails for some p_i,
and this contradiction would prove the theorem.

We have reduced Theorem <ref> to the following.


Suppose λ≥ 0.7983 and
T is a 2-primitive set of composite numbers satisfying (<ref>)
with 𝒫(T)=ℙ∩(1,Y] for some Y.
Then 

    ∑_t ∈ T1/t^λ - ∑_p ≤ Y1/p^λ < 0.



Our goal now is to prove Theorem <ref>.
For a parameter 0 < θ < 1 to be chosen later, we define λ as

    λ = τ(1 - θ),  where τ = 1.140366.


First consider those t ∈ T with greatest prime factor P(t) ≥ t^θ. Then t^1- θ≥ t / P(t) and so t^-λ≤ (t/P(t))^-λ / (1 - θ) = (t/P(t))^-τ. Hence

    ∑_t ∈ T_P(t) ≥ t^θ t^-λ≤∑_t ∈ T_P(t) ≥ t^θ(t/P(t))^-τ≤∑_p ≤ Y p^-τ

by (<ref>), since { t/P(t):t∈ T }⊂ D is primitive by part (iii) of Lemma <ref>.



For a positive integer t, we consider the following unique factorization

    t = m(t) M(t)

into positive integers m(t) ≤ M(t) with ratio M(t) / m(t) minimal. 
Let

    ℳ(T)={m(t):t∈ T}∪{M(t):t∈ T}.

We need two lemmas.

 
For any 2-primitive set T, consider the graph on the integers with edges {t,m(t)} and {t,M(t)}
for t∈ T, where if m(t)=M(t), there is just one edge containing t. 
This graph contains a matching from T into ℳ(T).


Let t∈ T.    
If m(t)∉{m(t'),M(t')} for all other t'∈ T, then we can match t with m(t).
So assume m(t)∈{m(t'),M(t')} for some other t'∈ T.  
Then M(t)∉{m(t”),M(t”)}
for all t”∈ T with t” t,t', since otherwise  t| t't”,
contradicting T being 2-primitive.  

If m(t)<M(t), then 2-primitive implies M(t)∉{m(t'),M(t')} so we can match t with M(t). 

Otherwise m(t)=M(t), which means t=m(t)^2. Then t'≠ t forces m(t')<M(t'), so we make define m' = t'/m(t) (that is m' is the singleton in {m(t'),M(t')}∖{m(t)}).
We would like to match t' with m' instead of m(t), freeing up m(t) to
be matched with t. So suppose this is blocked by some
t” different from t' (and necessarily different from t) with m'∈{m(t”),M(t”)}.  
But then t'| tt”, a violation of 2-primitivity.  Thus, the matching can be completed.


 
Suppose 0<θ<1/3 and that T is 2-primitive with P(t) < t^θ for each t ∈ T. Let N(z)=|T∩[2,z]|. Then, with q running over primes in the interval
I:=[z^(1+θ)/4,z^(1+θ)/2), we have

    N(z) < z^(1 + θ)/2-∑_q∈ I⌊z^(1+θ)/2/q⌋




By Lemma <ref>, it suffices to bound |ℳ(T∩[2,z])|.
  We first 
show that ℳ(T∩[2,z])⊂[1,z^(1+θ)/2).
Let t∈ T with t≤ z.  Say t = q_1 q_2 ... q_r where the primes q_i are written in nondecreasing order.  Let d = q_1 q_2 ... q_i be maximal with d ≤ t^(1 - θ)/2.  Then
d' = d q_i+1 satisfies t^(1 - θ)/2 < d' < t^(1 + θ)/2.
Also, d” = t/d' satisfies the same double inequality.  Thus, 

    t^(1 - θ)/2 < m(t) ≤ M(t) < t^(1 + θ)/2≤ z^(1+θ)/2.

We further note that the members m of ℳ(T∩[2,z]) satisfy P(m)<z^θ, since m divides
some member of T∩[2,z] and every t in that set has P(t)<z^θ.  In particular, m is not divisible
by any prime q≥ z^θ.  Note that if θ<1/3, then θ <(1+θ)/4. So, m is not divisible
by any prime in the interval I.  Since no integer below z^(1+θ)/2
is divisible by 2 primes from I, the lemma follows.

Set

    T^p={t∈ T:P(t)=p},

so that T^p⊂ T_p.  We have the following variant of Lemma <ref>.

For any 2-primitive set T and prime p, let N_p(z) denote the number of members t of T^p with
t≤ z.  With q running over the primes in I_p:=(max{p,z^1/4},z^1/2), we have

    N_p(z)≤ z^1/2-∑_q∈ I_p⌊z^1/2/q⌋.



Note that if T is 2-primitive, so too is T^p/p={t/p:t∈ T^p}.  Thus, we may apply Lemma <ref>
to obtain a matching from T^p/p into ℳ(T^p/p).  The prime factors of each element t/p∈ T^p/p
are at most p, so following the proof of Lemma <ref>, we have m(t/p),M(t/p)∈[t^1/2/p,t^1/2).
The lemma then follows in the same way as Lemma <ref>.


For x≥2 we have

    ∑_x^1/2<q<x
    q  prime⌊x/q⌋≥(log 2-1.25/log x-2.5/(log x)^2)x.



First suppose that x≥286^2.  We have the sum is at least

    ∑_x^1/2<q<xx/q-π(x).

 From <cit.>, we have that π(x)<1.25x/log x and from <cit.> that

    ∑_q<x1/q >loglog x +B-1/2(log x)^2,

where B is the Mertens constant.  Further, from <cit.>,

    ∑_q≤ x^1/21/q<loglog x^1/2+B+1/2(log x^1/2)^2=loglog x-log 2+B+2/(log x)^2.

This proves the lemma in the range x≥286^2 and direct calculation shows that
it holds in the wider range x≥2.

We shall find it useful to use the following asymptotically weaker estimates
in small cases.  The proof follows by checking values of x≤ 3213 after which
Lemma <ref> is stronger.

For x≥185, we have ∑_q∈(x^1/2,x]⌊ x/q⌋ >0.5x.
For x≥ 67, we have ∑_q∈(x^1/2,x]⌊ x/q⌋ >0.45x.


Let

    θ=0.3,  λ=0.7982562,  ν=1/θ=10/3.

  For each prime p, let

    S_p=∑_t∈ T
    P(t)=p<t^θ1/t^λ.

With (<ref>) it will suffice to prove Theorem <ref> if we
show under its hypotheses that for each Y≥2,

    ∑_p≤ YS_p≤∑_p≤ Y(1/p^λ-1/p^τ).




 §.§ Small primes, Y≤ 37

We are going to estimate S_p for various small primes p.
Take t∈ T with P(t)<t^θ. If t≤ q^ν for a prime q, then 
P(t)<(q^ν)^θ=q.
If q=3, we see there can be at most one such t; that is, T can contain
at most one power of 2.  The values of t≤ 5^ν are supported on {2,3},
so by Lemma <ref> with k=n=2 we see that there are at most 2 such
members of T.  Similarly, Lemma <ref> with k=2, n=3 shows that
T has at most 4 members below 7^ν, and with k=2, n=4, T has at
most 19 members below 11^ν.
Since members t of T with P(t)<t^θ have at least ⌈ν⌉=4 prime factors (counted with multiplicity), we have

    S_2   ≤1/2^4λ<0.1093463,
    
    S_2+S_3   <0.1093463+2-1/3^νλ<0.1631052,
    
    S_2+S_3+S_5   <0.1631052+4-2/5^νλ<0.1907220,
    
    S_2+S_3+S_5+S_7   <0.1907220+19-4/7^νλ<0.2753295.



Computing ∑_p≤ Y(1/p^λ-1/p^τ) directly for Y=2,3,5,7 gives lower bounds

    0.121399, 0.251741, 0.368904, 0.471733,

respectively.  
Thus we observe ∑_p≤ Y S_p < ∑_p≤ Y(1/p^λ-1/p^τ), so by 
(<ref>), Theorem <ref> holds 
when Y=2,3,5,7, respectively.  

Now consider 11≤ p≤ 37. By partial summation, we have the equality

    S_p=∫_p^ν^∞λ/z^1+λN_p(z) dz ,

noting that the integral converges, since N_p(z)≤ z^(1+θ)/2 by Lemma <ref>.

We use Lemmas <ref> and <ref> to get the upper estimates for N_p(z):

    N_p(z)   ≤⌊√(z)⌋-∑_max(p,z^1/4)<q≤√(z)⌊√(z)/q⌋,
    
    N_p(z)   ≤√(z)(1-log2+2.5/log z+10/(log z)^2), when p≤ z^1/4.

We split the integral in (<ref>) at p^4.
In the first range when z< p^4, we bound the contribution to (<ref>) by splitting up into intervals [m^2,(m+1)^2] and using (<ref>), which gives

    S_p':=∫_p^ν^p^4λ/z^1+λN_p(z) dz    ≤ ∑_m_0<m<p^2∫_m^2^(m+1)^2λ/z^1+λN_p(z) dz  + ∫_p^ν^(m_0+1)^2λ/z^1+λN_p(z) dz 
       ≤ ∑_m_0<m<p^2(1/m^2λ-1/(m+1)^2λ)(m-∑_p<q≤ m⌊m/q⌋) 
            +  (1/p^νλ-1/(m_0+1)^2λ)(m_0-∑_p<q≤ p^ν/2⌊m_0/q⌋)

where m_0 = ⌊ p^ν/2⌋.

For the second range when z≥ p^4, we use (<ref>) when z≥3213^2 and for smaller values of z we use Corollary <ref>. That is,

    S_p” :=  ∫_p^4^∞λ/z^1+λN_p(z) dz     ≤∫_3213^2^∞λ/z^λ+1/2(1-log2+2.5/log z+10/(log z)^2) dz
            +  0.5∫_max(p^4, 185^2)^3213^2λ/z^1/2+λ dz
      +  0.55∫_p^4^max(p^4, 185^2)λ/z^1/2+λ dz.

Denote the integrals

    f(y)     := ∫_y^∞λ/z^λ+1/2 dz 
    
    g(y)     := ∫_y^∞λ/z^λ+1/2(1-log2+2.5/log z+10/(log z)^2) dz.

So we obtain

    S_p”   ≤ (1-log 2)f(3213^2) + g(3213^2) 
          +  0.5[f(max(p^4,185^2))-f(3213^2)]  +  0.55[f(p^4)-f(max(p^4,185^2))] 
        =  (0.5-log 2)f(3213^2) + g(3213^2)  -  0.05f(max(p^4,185^2))  +  0.55f(p^4).


Using the estimates in (<ref>), (<ref>), we bound S_p = S_p' + S_p” by the following. 





    
    p   S_p≤    ∑_q≤ pS_q≤    ∑_q≤ p(q^-λ-q^-τ)≥

    11   0.13259   0.40792   0.55427

    13   0.11241   0.52033   0.62966

    17   0.08382   0.60415   0.69432

    19   0.07601   0.68016   0.75484

    23   0.06194   0.74210   0.80868

    29   0.04757   0.78967   0.85521

    31   0.04501   0.83468   0.89978

    37   0.03680   0.87148   0.93950

    


Note that the first entry in the third column is found by adding S_11 to the
estimate in (<ref>).    Since the entries in the fourth column
exceed the entries in the third column, (<ref>) implies
Theorem <ref> for Y≤ 37.



 §.§ Large primes, Y≥ 41

Now assume that Y≥41.  We have via partial summation that

    ∑_t∈ T
    P(t)<t^θ1/t^λ=∑_p≤7S_p
    +∑_11≤ p≤ 23∫_p^ν^29^νλ/z^1+λN_p(z) dz
    +∫_29^ν^∞λ/z^1+λN(z) dz.

(As before, the last integral converges.)
 From (<ref>) the S_p terms contribute at most 0.27533. Using Lemmas <ref>, <ref>, and <ref>, and Corollary <ref>,
we similarly obtain
 
    ∑_t∈ T
    P(t)<t^θ   1/t^λ
       <0.27533+0.08455+0.06576
     +0.03756+0.02953+0.01487+0.45614=0.96374,

 where the second to the sixth terms correspond to the five finite integrals,
 and the last term is our estimate for the tail integral.  We also note that
 
    ∑_p≤ Y(1/p^λ-1/p^τ)≥∑_p≤41(1/p^λ-1/p^τ)>0.97661.

Since this estimate exceeds the prior one, this gives Theorem <ref>
with λ=0.7982562.  
 

 






§ ACKNOWLEDGMENTS
 
The authors would like to acknowledge the University of Memphis for hosting the 2019 Erdős Lecture Series, during which the initial ideas for this paper were conceived.  The second author was supported by a Clarendon Scholarship at
the University of Oxford.
The third author is grateful for the
hospitality of Santa Clara University and was funded by their Paul R. and Virginia P.
Halmos Endowed Professorship in Mathematics and Computer Science.
The authors thank the referee for a careful reading.




amsplain
9

BM W.D. Banks and G. Martin, Optimal primitive sets with restricted primes, Integers 13 (2013), #A69, 10 pp.
    
C11 T.H. Chan, On sets of integers, none of which divides the product of k others, European J. Comb. 32 (2011), 443–447.
    
CGS T.H. Chan, E. Győri and A. Sárközy, On a problem of Erdős on integers, none of which divides the product of k others, European J. Comb. 31 (2010), 260–269.

E35 P. Erdős, Note on sequences of integers no one of which is divisible by any other, J. London Math. Soc. 10 (1935), 126–128.

ES P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935),
463–470.

E38 P. Erdős, On sequences of integers no one of which divides the product of two others and on some related problems, Tomsk. Gos. Univ. Ucen. Zap. 2 (1938), 74–82.

E48 P. Erdős, On the integers having exactly k prime factors, Annals of Math. 49 (1948), 53–66.

ESS P. Erdős, A. Sárközy and E. Szemerédi, On an extremal problem concerning primitive sequences, J. London Math. Soc. 42 (1967), 484-488.

LP J.D. Lichtman and C. Pomerance, The Erdős conjecture for primitive sets, Proc. Amer. Math. Soc., Series B 6 (2019), 1–14.

PS P.P. Pach and Cs. Sándor, Multiplicative bases and an Erdős problem, Combinatorica 38 (2018), 1175–1203.

RS  J.B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94.












[THC]
  Tsz Ho Chan

  Kennesaw State University

  Kennesaw, GA 30144

  thchan6174gmailcom 

  <https://www.memphis.edu/msci/people/tchan.php>

[JDL]
  Jared Duker Lichtman

  University of Oxford

  Oxford, OX2 6GG, UK

  jareddlichtmangmailcom 

  <https://www.maths.ox.ac.uk/people/jared.lichtman>

[CP]
  Carl Pomerance

  Dartmouth College

  Hanover, NH 03755

  carlpomerancedartmouthedu

  <https://math.dartmouth.edu/ carlp/>



