Abstract

A subset of the integers larger than 1 is primitive if no member divides another. Erdős proved in 1935 that the sum of $1/(a\log a)$ for $a$ running over a primitive set $A$ is universally bounded over all choices for $A$. In 1988 he asked if this universal bound is attained for the set of prime numbers. In this paper we make some progress on several fronts and show a connection to certain prime number “races” such as the race between $\pi (x)$ and $\mathrm{li}(x)$.

1. Introduction

A set of positive integers $>1$ is called primitive if no element divides any other (for convenience, we exclude the singleton set $\{1\}$). There are a number of interesting and sometimes unexpected theorems about primitive sets. After Besicovitch 4, we know that the upper asymptotic density of a primitive set can be arbitrarily close to $1/2$, whereas the lower asymptotic density is always $0$. Using the fact that if a primitive set has a finite reciprocal sum, then the set of multiples of members of the set has an asymptotic density, Erdős gave an elementary proof that the set of nondeficient numbers (i.e., $\sigma (n)/n\ge 2$, where $\sigma$ is the sum-of-divisors function) has an asymptotic density. Though the reciprocal sum of a primitive set can possibly diverge, Erdős 9 showed that for a primitive set $A$,

$$\begin{equation*} \sum _{a\in A}\frac{1}{a\log a}<\infty . \end{equation*}$$

In fact, the proof shows that these sums are uniformly bounded as $A$ varies over primitive sets.

Some years later in a 1988 seminar in Limoges, Erdős suggested that in fact we always have

$$\begin{equation} f(A):=\sum _{a\in A}\frac{1}{a\log a}\le \sum _{p\in \mathcal{P}}\frac{1}{p\log p}, \tag{1.1}{} \end{equation}$$

where $\mathcal{P}$ is the set of prime numbers. The assertion 1.1 is now known as the Erdős conjecture for primitive sets.

In 1991, Zhang 19 proved the Erdős conjecture for primitive sets $A$ with no member having more than 4 prime factors (counted with multiplicity).

After Cohen 6, we have

$$\begin{equation} C: = \sum _{p\in \mathcal{P}}\frac{1}{p\log p} = 1.63661632336\ldots \,, \tag{1.2}{} \end{equation}$$

the sum over primes in 1.1. Using the original Erdős argument in 9, Erdős and Zhang showed that $f(A)<2.89$ for a primitive set $A$, which was later improved by Robin to $2.77$. These unpublished estimates are reported in 11 by Erdős–Zhang, who used another method to show that $f(A)<1.84$. Shortly after, Clark 5 claimed that $f(A)\le e^\gamma =1.781072\dots$ . However, his brief argument appears to be incomplete.

Our principal results are the following.

Theorem 1.1.

For any primitive set $A$ we have $f(A) < e^\gamma$.

Theorem 1.2.

For any primitive set $A$ with no element divisible by $8$, we have $f(A)<C+2.37\times 10^{-7}$.

Say a prime $p$ is Erdős strong if for any primitive set $A$ with the property that each element of $A$ has the same least prime factor $p$, we have $f(A)\le 1/(p\log p)$. We conjecture that every prime is Erdős strong. Note that the Erdős conjecture 1.1 would immediately follow, though it is not clear that the Erdős conjecture implies our conjecture. Just proving our conjecture for the case of $p=2$ would give the inequality in Theorem 1.2 for all primitive sets $A$. Currently the best we can do for a primitive set $A$ of even numbers is that $f(A)<e^\gamma /2$; see Proposition 2.1 below.

For part of the next result, we assume the Riemann Hypothesis (RH) and the Linear Independence Hypothesis (LI), which asserts that the sequence of numbers $\gamma _n>0$ such that $\zeta (\tfrac{1}{2}+i\gamma _n)=0$ is linearly independent over $\mathbb{Q}$.

Theorem 1.3.

Unconditionally, all of the odd primes among the first $10^8$ primes are Erdős strong. Assuming RH and LI, the Erdős strong primes have relative lower logarithmic density $>0.995$.

The proof depends strongly on a recent result of Lamzouri 13, who was interested in the “Mertens race” between $\prod _{p\le x}(1-1/p)$ and $1/(e^\gamma \log x)$.

For a primitive set $A$, let $\mathcal{P}(A)$ denote the support of $A$, i.e., the set of prime numbers that divide some member of $A$. It is clear that the Erdős conjecture 1.1 is equivalent to the same assertion where the prime sum is over $\mathcal{P}(A)$.

Theorem 1.4.

If $A$ is a primitive set with $\mathcal{P}(A)\subset [3,\exp (10^6)]$, then

$$\begin{equation*} f(A)\le \sum _{p\in \mathcal{P}(A)}\frac{1}{p\log p}. \end{equation*}$$

If some primitive set $A$ of odd numbers exists with $f(A)>\sum _{p\in \mathcal{P}(A)}1/(p\log p)$, Theorem 1.4 suggests that it will be very difficult indeed to give a concrete example!

For a positive integer $n$, let $\Omega (n)$ denote the number of prime factors of $n$ counted with multiplicity. Let $\mathbb{N}_k$ denote the set of integers $n$ with $\Omega (n)=k$. Zhang 20 proved a result that implies $f(\mathbb{N}_k)< f(\mathbb{N}_1)$ for each $k\ge 2$, so that the Erdős conjecture holds for the primitive sets $\mathbb{N}_k$. More recently, Banks and Martin 2 conjectured that $f(\mathbb{N}_1)>f(\mathbb{N}_2)>f(\mathbb{N}_3)>\cdots$ . The inequality $f(\mathbb{N}_2)>f(\mathbb{N}_3)$ was just established by Bayless, Kinlaw, and Klyve 3. We prove the following result.

Theorem 1.5.

There is a positive constant $c$ such that $f(\mathbb{N}_k)\ge c$ for all $k$.

We let the letters $p,q,r$ represent primes. In addition, we let $p_n$ represent the $n$th prime. For an integer $a>1$, we let $P(a)$ and $p(a)$ denote the largest and smallest prime factors of $a$. Modifying the notation introduced in 11, for a primitive set $A$ let

$$\begin{align*} A_p & = \{a\in A: p(a)\ge p\},\\ A'_p & = \{a\in A: p(a) = p\},\\ A''_p & = \{a/p : a\in A'_p\}. \end{align*}$$

We let $f(a)=1/(a\log a)$, and so $f(A)=\sum _{a\in A}f(a)$. In this language, Zhang’s full result 20 states that $f((\mathbb{N}_k)'_p)\le f(p)$ for all primes $p$, $k\ge 1$. We also let

$$\begin{equation*} g(a)=\frac{1}{a}\prod _{p<P(a)}\left(1-\frac{1}{p}\right),\qquad h(a)=\frac{1}{a\log P(a)}, \end{equation*}$$

with $g(A)=\sum _{a\in A}g(a)$ and $h(A)=\sum _{a\in A}h(a)$.

2. The Erdős approach

In this section we will prove Theorem 1.1. We begin with an argument inspired by the original 1935 paper of Erdős 9.

Proposition 2.1.

For any primitive set $A$, if $q\notin A$, then

$$\begin{equation*} f(A'_q) < e^\gamma g(q) = \frac{e^\gamma }{q}\prod _{p<q}\bigg (1-\frac{1}{p}\bigg ). \end{equation*}$$

Proof.

For each $a\in A'_q$, let $S_a = \{ba : p(b) \ge P(a)\}$. Note that $S_a$ has asymptotic density $g(a)$. Since $A'_q$ is primitive, we see that the sets $S_a$ are pairwise disjoint. Further, the union of the sets $S_a$ is contained in the set of all natural numbers $m$ with $p(m) = q$, which has asymptotic density $g(q)$. Thus, the sum of densities for each $S_a$ is dominated by $g(q)$, that is,

$$\begin{align} g(A'_q)=\sum _{a\in A'_q}g(a) \le g(q). \tag{2.1}{} \end{align}$$

By Theorem 7 in 17, we have for $x\ge 285$,

$$\begin{equation} \prod _{p\le x}\left(1-\frac{1}{p}\right)>\frac{1}{e^\gamma \log (2x)}, \tag{2.2}{} \end{equation}$$

which may be extended to all $x\ge 1$ by a calculation. Thus, since each $a \in A'_q$ is composite,

$$\begin{equation*} g(a)=\frac{1}{a}\prod _{p<P(a)}\bigg (1-\frac{1}{p}\bigg ) > \frac{e^{-\gamma }}{ a\log \big (2P(a)\big )} \ge \frac{e^{-\gamma }}{ a\log a} = e^{-\gamma }f(a). \end{equation*}$$

Hence by 2.1,

$$\begin{equation*} f(A'_q)/e^\gamma < g(A'_q) \le g(q). \end{equation*}$$ ■

Remark 2.2.

Let $\sigma$ denote the sum-of-divisors function, and let $A$ be the set of $n$ with $\sigma (n)/n\ge 2$ and $\sigma (d)/d<2$ for all proper divisors $d$ of $n$, the set of primitive nondeficient numbers. Then an appropriate analog of $g(A)$ gives the density of nondeficient numbers recently shown in 12 to lie in the tight interval $(0.2476171,\,0.2476475)$. In 14, an analog of Proposition 2.1 is a key ingredient for sharp bounds on the reciprocal sum of the primitive nondeficient numbers.

Remark 2.3.

We have $g(\mathcal{P})=1$. Indeed, it is easy to see by induction over primes $r$ that

$$\begin{equation*} \sum _{p\le r}g(p)=\sum _{p\le r}\frac{1}{p}\prod _{q<p}\left(1-\frac{1}{q}\right)=1-\prod _{p\le r}\left(1-\frac{1}{p}\right). \end{equation*}$$

Letting $r\to \infty$ we get that $g(\mathcal{P})=1$. There is also a holistic way of seeing this. Since $g(p)$ is the density of the set of integers with least prime factor $p$, it would make sense that $g(\mathcal{P})$ is the density of the set of integers which have a least prime factor, and this density is 1. To make this rigorous, one notes that the density of the set of integers whose least prime factor is $>y$ tends to 0 as $y\to \infty$. As a consequence of $g(\mathcal{P})=1$, we have

$$\begin{equation} \sum _{p>2}g(p)=\frac{1}{2}, \tag{2.3}{} \end{equation}$$

an identity we will find to be useful.

For a primitive set $A$, let

$$\begin{equation*} A^k = \{a\in A: 2^k\| a\}, \qquad B^k = \{a/2^k: a\in A^k\}. \end{equation*}$$

The next result will help us prove Theorem 1.1.

Lemma 2.4.

For a primitive set $A$, let $k\ge 1$ be such that $2^k\notin A$. Then we have

$$\begin{equation*} f(A^{k}) < \frac{e^\gamma }{2^k}\sum _{p\notin A\atop p>2}g(p). \end{equation*}$$

Proof.

The hypothesis $2^k\notin A$ implies that $1\notin B^k$, so that $B^k$ is a primitive set. If $2^kp\notin A$ for a prime $p>2$, then $(B^k)'_p$ is a primitive set of odd composite numbers, so by Proposition 2.1, $f((B^k)'_p) < e^\gamma g(p)$.

Now if $2^kp\in A$ for some odd prime $p$, then $(B^{k})'_p=\{p\}$, and note that $p\notin A$ by primitivity. We have $f(2^kp) < 2^{-k}e^\gamma g(p)$ since

$$\begin{equation*} \frac{1}{2^kp\log (2^kp)}\le \frac{1}{2^kp\log (2p)}<\frac{e^\gamma }{2^k}g(p), \end{equation*}$$

which follows from 2.2. Since $(B^k)'_p\ne \emptyset$ implies $p\notin A$, we have

$$\begin{align*} f(A^k)=\sum _{p\notin A\atop p>2}f(2^k{\cdot }(B^k)'_p)& \le \sum _{p\in B^k,p\notin A\atop p>2}f(2^kp) + 2^{-k}\sum _{p\notin B^k,p\notin A\atop p>2}f((B^k)'_p)\\ & < \frac{e^\gamma }{2^k}\sum _{p\notin A\atop p>2}g(p). \end{align*}$$ ■

With Lemma 2.4 in hand, we prove $f(A)<e^\gamma$.

Proof of Theorem 1.1.

From Erdős–Zhang 11, we have that $f(A_3)<0.92$. If $2\in A$, then $A'_2=\{2\}$, so that $f(A)=f(A_3)+f(A'_2)<0.92+1/(2\log 2)<e^\gamma$. Hence we may assume that $2\notin A$. If $A$ contains every odd prime, then $A'_2$ consists of at most one power of 2, and the calculation just concluded shows we may assume this is not the case. Hence there is at least one odd prime $p_0\notin A$. By Proposition 2.1, we have

$$\begin{align} f(A) &= \sum _pf(A'_p)= \sum _{p\in A}f(p) + \sum _{p\notin A} f(A'_p) < \sum _{p\in A}f(p) + e^\gamma \sum _{p\notin A\atop p>2} g(p) + f(A'_2). \tag{2.4}{} \end{align}$$

First suppose $A$ contains no powers of $2$. Then by Lemma 2.4,

$$\begin{align*} f(A'_2) = \sum _{k\ge 1}f(A^{k}) < \sum _{k\ge 1}\frac{e^\gamma }{2^k}\sum _{p\notin A\atop p>2}g(p) = e^\gamma \sum _{p\notin A\atop p>2}g(p). \end{align*}$$

Substituting into 2.4, we conclude, using 2.3, that

$$\begin{align} f(A) & < \sum _{p\in A}f(p) + 2e^\gamma \sum _{p\notin A\atop p>2}g(p) \le 2e^\gamma \sum _{p>2}g(p) = e^\gamma . \tag{2.5}{} \end{align}$$

For the last inequality in 2.5 we used that for every prime $p$,

$$\begin{equation} \frac{f(p)}{e^\gamma g(p)}<1.082, \tag{2.6}{} \end{equation}$$

which follows after a short calculation using 17, Theorem 7.

Now if $2^K\in A$ for some positive integer $K$, then $K$ is unique and $K\ge 2$. Also $A^K=\{2^K\}$ and $A^k=\emptyset$ for all $k>K$, so again by Lemma 2.4,

$$\begin{align*} f(A'_2) = \sum _{k=1}^Kf(A^{k}) < f(2^K) + \sum _{k=1}^{K-1}\frac{e^\gamma }{2^k}\sum _{p\notin A\atop p>2}g(p) = f(2^K) + (1-2^{1-K})e^\gamma \sum _{p\notin A\atop p>2}g(p). \end{align*}$$

Substituting into 2.4 gives

$$\begin{align} f(A) \!<\! \sum _{p\in A}f(p) + f(2^K) + (2-2^{1-K})e^\gamma \sum _{p\notin A\atop p>2}g(p) & \le f(2^K) + (2-2^{1-K})e^\gamma \sum _{p>2}g(p)\\ & \le f(2^K) + (1-2^{-K})e^\gamma < e^\gamma , \tag{2.7}{} \end{align}$$

using identity 2.3, inequality 2.6, and $f(2^K)< 2^{-K} e^\gamma$. This completes the proof.

■

3. Mertens primes

In this section we will prove Theorems 1.3 and 1.4. Note that by Mertens’ theorem,

$$\begin{equation*} \prod _{p<x}\left(1-\frac{1}{p}\right)\sim \frac{1}{e^\gamma \log x},\quad x\to \infty , \end{equation*}$$

where $\gamma$ is Euler’s constant. We say a prime $q$ is Mertens if

$$\begin{equation} e^\gamma \prod _{p<q}\Big (1-\frac{1}{p}\Big ) \le \frac{1}{\log q} \tag{3.1}{} \end{equation}$$

and let $\mathcal{P}^{\text{Mert}}$ denote the set of Mertens primes. We are interested in Mertens primes because of the following consequence of Proposition 2.1, which shows that every Mertens prime is Erdős strong.

Corollary 3.1.

Let $A$ be a primitive set. If $q\in \mathcal{P}^{\mathrm{Mert}}$, then $f(A'_q)\le f(q)$. Hence if $A'_q \subset \{q\}$ for all $q\notin \mathcal{P}^{\mathrm{Mert}}$, then $A$ satisfies the Erdős conjecture.

Proof.

By Proposition 2.1 we have $f(A'_q)\le \max \{e^\gamma g(q),f(q)\}$. If $q\in \mathcal{P}^{\text{Mert}}$, then

$$\begin{equation*} e^\gamma g(q) = \frac{e^\gamma }{q}\prod _{p<q}\bigg (1-\frac{1}{p}\bigg )\le \frac{1}{q\log q} =f(q), \end{equation*}$$

so $f(A'_q)\le f(q)$.

■

Now, one would hope that the Mertens inequality 3.1 holds for all primes $q$. However, 3.1 fails for $q=2$ since $e^\gamma > 1/\log 2$. Nevertheless, we have computed that $q$ is indeed a Mertens prime for all $2<q\le p_{10^8} = 2{,}038{,}074{,}743$, thus proving the unconditional part of Theorem 1.3.

3.1. Proof of Theorem 1.3

To complete the proof, we use a result of Lamzouri 13 relating the Mertens inequality to the race between $\pi (x)$ and $\mathrm{li}(x)$, studied by Rubinstein and Sarnak 18. Under the assumption of RH and LI, he proved that the set $\mathcal{N}$ of real numbers $x$ satisfying

$$\begin{align*} e^\gamma \prod _{p\le x}\bigg (1-\frac{1}{p}\bigg ) > \frac{1}{\log x} \end{align*}$$

has logarithmic density $\delta (\mathcal{N})$ equal to the logarithmic density of numbers $x$ with $\pi (x)>\mathrm{li}(x)$, and in particular

$$\begin{align} \delta (\mathcal{N}) = \lim _{x\to \infty }\frac{1}{\log x}\int _{t\in \mathcal{N}\cap [2,x]}\frac{dt}{t} = 0.00000026\ldots \,. \tag{3.2} \end{align}$$

We note that if a prime $p=p_n\in \mathcal{N}$, then for