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 Reference 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 Reference 9 showed that for a primitive set $A$,
where $\mathcal{P}$ is the set of prime numbers. The assertion Equation 1.1 is now known as the Erdős conjecture for primitive sets.
In 1991, Zhang Reference 19 proved the Erdős conjecture for primitive sets $A$ with no member having more than 4 prime factors (counted with multiplicity).
the sum over primes in Equation 1.1. Using the original Erdős argument in Reference 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 Reference 11 by Erdős–Zhang, who used another method to show that $f(A)<1.84$. Shortly after, Clark Reference 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.
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 Equation 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}$.
The proof depends strongly on a recent result of Lamzouri Reference 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 Equation 1.1 is equivalent to the same assertion where the prime sum is over $\mathcal{P}(A)$.
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 Reference 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 Reference 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 Reference 3. We prove the following result.
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 Reference 11, for a primitive set $A$ let
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 Reference 20 states that $f((\mathbb{N}_k)'_p)\le f(p)$ for all primes $p$,$k\ge 1$. We also let
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.
Now, one would hope that the Mertens inequality Equation 3.1 holds for all primes $q$. However, Equation 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.
To complete the proof, we use a result of Lamzouri Reference 13 relating the Mertens inequality to the race between $\pi (x)$ and $\mathrm{li}(x)$, studied by Rubinstein and Sarnak Reference 18. Under the assumption of RH and LI, he proved that the set $\mathcal{N}$ of real numbers $x$ satisfying
We note that if a prime $p=p_n\in \mathcal{N}$, then for $p'=p_{n+1}$ we have $[p,p')\subset \mathcal{N}$ because the prime product on the left-hand side is constant on $[p,p')$, while $1/\log x$ is decreasing for $x\in [p,p')$.
The set of primes $\mathcal{Q}$ in $\mathcal{N}$ is precisely the set of non-Mertens primes, so $\mathcal{Q}=\mathcal{P}\setminus \mathcal{P}^{\text{Mert}}$. From the above observation, we may leverage knowledge of the continuous logarithmic density $\delta (\mathcal{N})$ to obtain an upper bound on the relative (upper) logarithmic density of non-Mertens primes
since $\sum \log (p'/p) = \sum d_p/p + O(1)$. The average gap is roughly $\log p$, so we may consider the primes for which $d_p < \epsilon \log p$ for a small positive constant $\epsilon$ to be determined.
where $c_2$ is for the twin-prime constant $2\prod _{p>2}p(p-2)/(p-1)^2=1.3203\ldots$ . Denote the prime product by $F(d) = \prod _{p\mid d\atop p>2}\frac{p-1}{p-2}$, and consider the multiplicative function $H(d) = \sum _{u\mid d}\mu (u)F(d/u)$. We have $H(2^k)=0$ for all $k\ge 1$, and for $p>2$ we have $H(p)=F(p)-1$ and $H(p^k)=0$ if $k\ge 2$. Thus,
We claim that every pair of primes $p,q$ with $2<p\le q<e^{10^6}$ is a Mertens pair. Assume this and let $A$ be a primitive set supported on the odd primes up to $e^{10^6}$. By Equation 2.1, if $p\notin A$, we have
By Equation 2.2, this last product exceeds $e^{-\gamma }/\log (2q)>e^{-\gamma }/\log (pq)$, and using this in the above display shows that $p,q$ is indeed a Mertens pair. Since all of the odd primes up to $p_{10^8}$ are Mertens, to complete the proof of our assertion, it suffices to consider the case when $p>p_{10^8}$. Define $E_p$ via the equation
It remains to note that $4.999(\log p_{10^8})^4 >1{,}055{,}356$.
It seems interesting to record the principle that we used in the proof.
4. Odd primitive sets
We say a primitive set is odd if every member of the set is an odd number. In this section we prove Theorem 1.2 and establish a curious result on parity for primitive sets.
Since a cube-free number cannot be divisible by 8, Equation 4.2 holds for all primitive sets $A$ of cube-free numbers. Also, the proof of Corollary 4.4 can be adapted to show that Equation 4.2 holds for all primitive sets $A$ containing no number that is 4 (mod 8).
We close out this section with a curious result about those primitive sets $A$ where Equation 4.2 does not hold. Namely, the Erdős conjecture must then hold for the set of odd members of $A$. Put another way, Equation 4.2 holds for any primitive set $A$ for which the Erdős conjecture for the odd members of $A$fails.
Let $\mathcal{P}^{\text{Zh}}$ denote the set of Zhang primes. We are interested in Zhang primes because of the following result.
From this one might hope that all primes are Zhang. However, the prime 2 is not Zhang since $C> 1/\log 2$, and the prime 3 is not Zhang since $C-1/(2\log 2)>1/\log 3$. Nevertheless, as with Mertens primes, it is true that the remaining primes up to $p_{10^8}$ are Zhang. Indeed, starting from Equation 1.2, we computed that
The computation stopped at $10^8$ for convenience, and one could likely extend this further with some patience. It seems likely that there is also a “race” between $\sum _{p\ge q}1/(p\log p)$ and $1/\log q$, as with Mertens primes, and that a large logarithmic density of primes $q$ are Zhang, with a small logarithmic density of primes failing to be Zhang.
A related conjecture due to Banks and Martin Reference 2 is the chain of inequalities
succinctly written as $f(\mathbb{N}_k) > f(\mathbb{N}_{k+1})$ for all $k\ge 1$, where $\mathbb{N}_k = \{n: \Omega (n) = k\}$. As mentioned in the introduction, we know only that $f(\mathbb{N}_1)> f(\mathbb{N}_k)$ for all $k\ge 2$ and $f(\mathbb{N}_2)>f(\mathbb{N}_3)$. More generally, for a subset $Q$ of primes, let $\mathbb{N}_k(Q)$ denote the subset of $\mathbb{N}_k$ supported on $Q$. A result of Zhang Reference 20 implies that $f(\mathbb{N}_1(Q)) > f(\mathbb{N}_{k}(Q))$ for all $k>1$, while Banks and Martin showed that $f(\mathbb{N}_k(Q)) > f(\mathbb{N}_{k+1}(Q))$ if $\sum _{p\in Q}1/p$ is not too large. We prove a similar result in the case where $Q$ is a subset of the Zhang primes and we replace $f(\mathbb{N}_k(Q))$ with $h(\mathbb{N}_k(Q))$. Recall that $h(A) = \sum _{a\in A}1/(a\log P(a))$.
It is interesting that if we do not in some way restrict the primes used, the analog of the Banks–Martin conjecture for the function $h$ fails. In particular, we have
We have already shown in Equation 2.1 that $g(A'_q)\le g(q)$ for any primitive set $A$ and prime $q$, so the analog for $g$ of the strong Erdős conjecture holds.
Let $N_k(x)$ denote the number of members of $\mathbb{N}_k$ in $[1,x]$. We use the Sathe–Selberg theorem (see Reference 15, Theorem 7.19), from which we have that uniformly for $B({k})< x\le B({k+m})$, as $k\to \infty$,
the last estimate following from Stirling’s formula. This proves Equation 5.2 and so the theorem.
The sets $\mathbb{N}_k$ and Theorem 1.5 give us the following result.
Acknowledgments
We thank Greg Martin for his thoughts in connection with Remark 3.3 and Kevin Ford for the content of Remark 3.5. We thank Paul Kinlaw, Zhenxiang Zhang, and the referee for some helpful comments.
C. Axler, New estimates for the $n$-th prime number, arXiv:1706.03651v1 [math.NT], 2017.
Reference [2]
William D. Banks and Greg Martin, Optimal primitive sets with restricted primes, Integers 13 (2013), Paper No. A69, 10. MR3118387, Show rawAMSref\bib{bm}{article}{
author={Banks, William D.},
author={Martin, Greg},
title={Optimal primitive sets with restricted primes},
journal={Integers},
volume={13},
date={2013},
pages={Paper No. A69, 10},
issn={1553-1732},
review={\MR {3118387}},
}
Reference [3]
J. Bayless, P. Kinlaw, and D. Klyve, Sums over primitive sets with a fixed number of prime factors, Math. Comp., electronically published on March 5, 2019, DOI:10.1090/mcom/3416 (to appear in print).
Reference [4]
A. S. Besicovitch, On the density of certain sequences of integers, Math. Ann. 110 (1935), no. 1, 336–341, DOI 10.1007/BF01448032. MR1512943, Show rawAMSref\bib{besicovitch}{article}{
author={Besicovitch, A. S.},
title={On the density of certain sequences of integers},
journal={Math. Ann.},
volume={110},
date={1935},
number={1},
pages={336--341},
issn={0025-5831},
review={\MR {1512943}},
doi={10.1007/BF01448032},
}
Reference [5]
David A. Clark, An upper bound of $\sum 1/(a_i\log a_i)$ for primitive sequences, Proc. Amer. Math. Soc. 123 (1995), no. 2, 363–365, DOI 10.2307/2160889. MR1243164, Show rawAMSref\bib{clark}{article}{
author={Clark, David A.},
title={An upper bound of $\sum 1/(a_i\log a_i)$ for primitive sequences},
journal={Proc. Amer. Math. Soc.},
volume={123},
date={1995},
number={2},
pages={363--365},
issn={0002-9939},
review={\MR {1243164}},
doi={10.2307/2160889},
}
Reference [6]
H. Cohen, High precision computation of Hardy-Littlewood constants, preprint, https://www.math.u-bordeaux.fr/$\sim$hecohen/ .
Reference [7]
Harold G. Diamond and Kevin Ford, Generalized Euler constants, Math. Proc. Cambridge Philos. Soc. 145 (2008), no. 1, 27–41, DOI 10.1017/S0305004108001187. MR2431637, Show rawAMSref\bib{DF}{article}{
author={Diamond, Harold G.},
author={Ford, Kevin},
title={Generalized Euler constants},
journal={Math. Proc. Cambridge Philos. Soc.},
volume={145},
date={2008},
number={1},
pages={27--41},
issn={0305-0041},
review={\MR {2431637}},
doi={10.1017/S0305004108001187},
}
Reference [8]
Pierre Dusart, Explicit estimates of some functions over primes, Ramanujan J. 45 (2018), no. 1, 227–251, DOI 10.1007/s11139-016-9839-4. MR3745073, Show rawAMSref\bib{dusart}{article}{
author={Dusart, Pierre},
title={Explicit estimates of some functions over primes},
journal={Ramanujan J.},
volume={45},
date={2018},
number={1},
pages={227--251},
issn={1382-4090},
review={\MR {3745073}},
doi={10.1007/s11139-016-9839-4},
}
Reference [9]
Paul Erdös, Note on sequences of integers no one of which is divisible by any other, J. London Math. Soc. 10 (1935), no. 2, 126–128, DOI 10.1112/jlms/s1-10.1.126. MR1574239, Show rawAMSref\bib{erdos35}{article}{
author={Erd\"{o}s, Paul},
title={Note on sequences of integers no one of which is divisible by any other},
journal={J.~London Math. Soc.},
volume={10},
date={1935},
number={2},
pages={126--128},
review={\MR {1574239}},
doi={10.1112/jlms/s1-10.1.126},
}
Reference [10]
P. Erdös, On the integers having exactly $K$ prime factors, Ann. of Math. (2) 49 (1948), 53–66, DOI 10.2307/1969113. MR0023279, Show rawAMSref\bib{erdos48}{article}{
author={Erd\"{o}s, P.},
title={On the integers having exactly $K$ prime factors},
journal={Ann. of Math. (2)},
volume={49},
date={1948},
pages={53--66},
issn={0003-486X},
review={\MR {0023279}},
doi={10.2307/1969113},
}
Reference [11]
Paul Erdős and Zhen Xiang Zhang, Upper bound of $\sum 1/(a_i\log a_i)$ for primitive sequences, Proc. Amer. Math. Soc. 117 (1993), no. 4, 891–895, DOI 10.2307/2159512. MR1116257, Show rawAMSref\bib{ez}{article}{
author={Erd\H {o}s, Paul},
author={Zhang, Zhen Xiang},
title={Upper bound of $\sum 1/(a_i\log a_i)$ for primitive sequences},
journal={Proc. Amer. Math. Soc.},
volume={117},
date={1993},
number={4},
pages={891--895},
issn={0002-9939},
review={\MR {1116257}},
doi={10.2307/2159512},
}
Reference [12]
Mitsuo Kobayashi, On the density of abundant numbers, ProQuest LLC, Ann Arbor, MI. Thesis (Ph.D.)–Dartmouth College, 2010. MR2996025, Show rawAMSref\bib{mits1}{book}{
author={Kobayashi, Mitsuo},
title={On the density of abundant numbers},
note={Thesis (Ph.D.)--Dartmouth College, 2010},
publisher={ProQuest LLC, Ann Arbor, MI},
pages={239},
isbn={978-1267-15782-9},
review={\MR {2996025}},
}
Reference [13]
Youness Lamzouri, A bias in Mertens’ product formula, Int. J. Number Theory 12 (2016), no. 1, 97–109, DOI 10.1142/S1793042116500068. MR3455269, Show rawAMSref\bib{lamz}{article}{
author={Lamzouri, Youness},
title={A bias in Mertens' product formula},
journal={Int. J. Number Theory},
volume={12},
date={2016},
number={1},
pages={97--109},
issn={1793-0421},
review={\MR {3455269}},
doi={10.1142/S1793042116500068},
}
Reference [14]
Jared Duker Lichtman, The reciprocal sum of primitive nondeficient numbers, J. Number Theory 191 (2018), 104–118, DOI 10.1016/j.jnt.2018.03.021. MR3825463, Show rawAMSref\bib{JDLpnd}{article}{
author={Lichtman, Jared Duker},
title={The reciprocal sum of primitive nondeficient numbers},
journal={J. Number Theory},
volume={191},
date={2018},
pages={104--118},
issn={0022-314X},
review={\MR {3825463}},
doi={10.1016/j.jnt.2018.03.021},
}
Reference [15]
Hugh L. Montgomery and Robert C. Vaughan, Multiplicative number theory. I. Classical theory, Cambridge Studies in Advanced Mathematics, vol. 97, Cambridge University Press, Cambridge, 2007. MR2378655, Show rawAMSref\bib{MV}{book}{
author={Montgomery, Hugh L.},
author={Vaughan, Robert C.},
title={Multiplicative number theory. I. Classical theory},
series={Cambridge Studies in Advanced Mathematics},
volume={97},
publisher={Cambridge University Press, Cambridge},
date={2007},
pages={xviii+552},
isbn={978-0-521-84903-6},
isbn={0-521-84903-9},
review={\MR {2378655}},
}
Reference [16]
H. Riesel and R. C. Vaughan, On sums of primes, Ark. Mat. 21 (1983), no. 1, 46–74, DOI 10.1007/BF02384300. MR706639, Show rawAMSref\bib{RV}{article}{
author={Riesel, H.},
author={Vaughan, R. C.},
title={On sums of primes},
journal={Ark. Mat.},
volume={21},
date={1983},
number={1},
pages={46--74},
issn={0004-2080},
review={\MR {706639}},
doi={10.1007/BF02384300},
}
Reference [17]
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR0137689, Show rawAMSref\bib{RS1}{article}{
author={Rosser, J. Barkley},
author={Schoenfeld, Lowell},
title={Approximate formulas for some functions of prime numbers},
journal={Illinois J. Math.},
volume={6},
date={1962},
pages={64--94},
issn={0019-2082},
review={\MR {0137689}},
}
Reference [18]
Michael Rubinstein and Peter Sarnak, Chebyshev’s bias, Experiment. Math. 3 (1994), no. 3, 173–197. MR1329368, Show rawAMSref\bib{RubSarn}{article}{
author={Rubinstein, Michael},
author={Sarnak, Peter},
title={Chebyshev's bias},
journal={Experiment. Math.},
volume={3},
date={1994},
number={3},
pages={173--197},
issn={1058-6458},
review={\MR {1329368}},
}
Reference [19]
Zhen Xiang Zhang, On a conjecture of Erdős on the sum $\sum _{p\leq n}1/(p\log p)$, J. Number Theory 39 (1991), no. 1, 14–17, DOI 10.1016/0022-314X(91)90030-F. MR1123165, Show rawAMSref\bib{zhang1}{article}{
author={Zhang, Zhen Xiang},
title={On a conjecture of Erd\H {o}s on the sum $\sum _{p\leq n}1/(p\log p)$},
journal={J. Number Theory},
volume={39},
date={1991},
number={1},
pages={14--17},
issn={0022-314X},
review={\MR {1123165}},
doi={10.1016/0022-314X(91)90030-F},
}
Reference [20]
Zhen Xiang Zhang, On a problem of Erdős concerning primitive sequences, Math. Comp. 60 (1993), no. 202, 827–834, DOI 10.2307/2153122. MR1181335, Show rawAMSref\bib{zhang2}{article}{
author={Zhang, Zhen Xiang},
title={On a problem of Erd\H {o}s concerning primitive sequences},
journal={Math. Comp.},
volume={60},
date={1993},
number={202},
pages={827--834},
issn={0025-5718},
review={\MR {1181335}},
doi={10.2307/2153122},
}
Show rawAMSref\bib{3937344}{article}{
author={Lichtman, Jared},
author={Pomerance, Carl},
title={The Erd\H os conjecture for primitive sets},
journal={Proc. Amer. Math. Soc. Ser. B},
volume={6},
number={1},
date={2019},
pages={1-14},
issn={2330-1511},
review={3937344},
doi={10.1090/bproc/40},
}
Settings
Change font size
Resize article panel
Enable equation enrichment
(Not available in this browser)
Note. To explore an equation, focus it (e.g., by clicking on it) and use the arrow keys to navigate its structure. Screenreader users should be advised that enabling speech synthesis will lead to duplicate aural rendering.