{% if Art01 %} <a href=”https://gitlab.com/{{ gitlab_user }}/{{ gitlab_repo }}/-/edit/{{ gitlab_version }}{{ conf_py_path }}{{ Art01 }}.rst”> ✏️ Modifier cette page </a> {% endif %}
Explicit bounds on primes¶
Collecting references: [Dusart, 1998], [Dusart, 2018]
1. Bounds on primes, in special ranges¶
The paper [Rosser and Schoenfeld, 1962], contains several bounds valid only when the variable is small enough. These are proved by direction verifications. Different direct computations can be used to get effect in limited range. Here is a typical result.
Theorem ([Büthe, 2016])
Assume the Riemann Hypothesis has been checked up to height \(H_0\). Then when \(x\) satisfies \(\sqrt{x/\log x}\le H_0/4.92\), we have
\(|\psi(x)-x|\le \frac{\sqrt{x}}{8\pi}\log^2x\) when \(x > 59\),
\(|\theta(x)-x|\le \frac{\sqrt{x}}{8\pi}\log^2x\) when \(x > 599\),
\(|\pi(x)-\text{li}(x)|\le \frac{\sqrt{x}}{8\pi}\log x\) when \(x > 2657\).
If we use the value \(H_0=3 \cdot 10^{12}\) obtained by Platt and Trudgian in [Platt and Trudgian, 2021] (which improves previous results in [Platt, 2017] ), these bounds are thus valid for \(x\le 2.16\cdot 10^{25}\). In [Büthe, 2018] the following bounds are also obtained.
Theorem (2018)
We have
\(|\psi(x)-x|\le 0.94\sqrt{x}\) when \(11 < x\le 10^{19}\),
\(0<\text{li}(x)-\pi(x)\le\frac{\sqrt{x}}{\log x}\Bigl(1.95+\frac{3.9}{\log x}+\frac{19.5}{\log^2x}\Bigr)\) when \(2\le x\le 10^{19}\).
2. Bounds on primes, without any congruence condition¶
The subject really started with the four papers [Rosser, 1941], [Rosser and Schoenfeld, 1962], [Rosser and Schoenfeld, 1975] and [Schoenfeld, 1976].
We recall the usual notation: \(\pi(x)\) is the number of primes up to \(x\) (so that \(\pi(3)=2\)), the function \(\psi(x)\) is the summatory function of the van Mangold function \(\Lambda\), i.e. \(\psi(x)=\sum_{n\le x}\Lambda(n)\), while we also define \(\vartheta(x)=\sum_{p\le x}\log p\). Here are some elegant bounds that one can find in those papers.
Theorem (1962)
For \(x > 0\), we have \(\psi(x)\le 1.03883 x\) and the maximum of \(\psi(x)/x\) is attained at \(x=113\).
When \(x\ge17\), we have \(\pi(x) > x/\log x\).
When \(x > 1\), we have \(\displaystyle \sum_{p\le x}1/p > \log\log x\).
When \(x > 1\), we have \(\displaystyle \sum_{p\le x}(\log p)/p < \log x\).
There are many other results in those papers. In [Dusart, 1999] , one can find among other things the inequality
and also
Theorem (1999)
When \(x\ge e^{22}\), we have \(\displaystyle\psi(x)=x+O^*\Bigl(0.006409\frac{x}{\log x}\Bigr)\).
When \(x\ge 10\,544\,111\), we have \(\displaystyle\vartheta(x)=x+O^*\Bigl(0.006788\frac{x}{\log x}\Bigr)\).
When \(x\ge 3\,594\,641\), we have \(\displaystyle\vartheta(x)=x+O^*\Bigl(0.2\frac{x}{\log^2 x}\Bigr)\).
When \(x > 1\), we have \(\displaystyle\vartheta(x)=x+O^*\Bigl(515\frac{x}{\log^3 x}\Bigr)\).
This is improved in [Dusart, 2018] , and in particular, it is shown that the 515 above can be replaced by 20.83 and also that
Bounds of the shape \(|\psi(x)-x|\le \epsilon x\) have started appearing in [Rosser and Schoenfeld, 1962] The latest paper is [Faber and Kadiri, 2015] with its corrigendum [Faber and Kadiri, 2018], where the explicit density estimate from [Kadiri, 2013] is put to contribution, even for moderate values of the variable. In particular, when \(x\ge 485\,165\,196\), we have
Sharper estimates of this type for larger \(x\) were obtained in [] and [Johnston and Yang, 2023]. In particular, we have [Johnston and Yang, 2023]
In [Platt and Trudgian, 2021] , one find the following estimate
Theorem (2021)
When \(x\ge e^{2000}\), we have \(\biggl|\frac{\psi(x)-x}{x}\biggr|\le 235\,(\log x)^{0.52}\exp-\sqrt{\frac{\log x}{5.573412}}\;.\)
The paper [Johnston and Yang, 2023] further proves in Theorem 1.1 the next estimate.
Theorem (2023)
When \(x\ge 2\), we have \(\biggl|\frac{\psi(x)-x}{x}\biggr|\le 9.39\,(\log x)^{1.51}\exp-0.8274\sqrt{\log x}\;.\)
When \(x\ge 23\), we have \(\biggl|\frac{\psi(x)-x}{x}\biggr|\le 0.026\,(\log x)^{1.801}\exp-0.1853\frac{(\log x)^{3/5}}{(\log\log x)^{1/5}}\;.\)
Several estimates are also provided for \(\psi(x)\), \(\pi(x)\) and \(\vartheta(x)\).
A lighly sharper estimate than that above was obtained at the same time in []
Theorem (2023)
When \(x\ge 2\), we have \(\biggl|\frac{\psi(x)-x}{x}\biggr|\le 9.22022\,(\log x)^{1.5}\exp-0.8476836\sqrt{\log x}\;.\)
Refined bounds for \(\pi(x)\) are to be found in [Panaitopol, 2000] and in [Axler, 2016]
By comparing in an efficient manner with \(\psi(x)-x\), [Ramaré, 2013], obtained the next two results. [There was an error in this paper which is corrected below].
Theorem (2013)
For \(x > 1\), we have \(\sum_{n\le x}\Lambda(n)/n=\log x-\gamma+O^*(1.833/\log^2x)\). When \(x\ge 1\,520\,000\), we can replace the error term by \(O^*(0.0067/\log x)\). When \(x\ge 468\,000\), we can replace the error term by \(O^*(0.01/\log x)\). Furthermore, when \(1\le x\le 10^{10}\), this error term can be replaced by \(O^*(1.31/\sqrt{x})\).
Theorem (2013)
For \(x\ge 8950\), we have \(\displaystyle \sum_{n\le x}\Lambda(n)/n=\log x-\gamma +\frac{\psi(x)-x}{x}+O^*\Bigl(\frac{1}{2\sqrt{x}}+1.75\cdot 10^{-12}\Bigl)\) .
[Mawia, 2017] developed the method to incorporate more functions (and corrected the initial work), extending results of [Rosser and Schoenfeld, 1962] . Here are some of his results.
Theorem (2017)
For \(x\ge 2\), we have \(\displaystyle \sum_{p\le x}\frac1p=\log\log x+B+O^*\Bigl(\frac{4}{\log^3x}\Bigr).\) When \(x\ge 1000\), one can replace the 4 in the error term by 2.3, and when \(x\ge24284\), by 1. The constant \(B \approx 0.261497\) is known as the Meissel-Mertens constant.
Theorem (2017)
For \(\log x\ge 4635\), we have \(\sum_{p\le x}\frac1p=\log\log x+B+O^*\Bigl(1.1\frac{\exp(-\sqrt{0.175\log x})}{(\log x)^{3/4}}\Bigr).\)
When truncating sums over primes, Lemma 3.2 of [Ramaré, 2016] is handy.
Theorem (2016)
Let \(f\) be a \(C^1\) non-negative, non-increasing function over \([P,\infty)\), where \(P\ge 3\,600\,000\) is a real number and such that \(\lim_{t\rightarrow\infty}tf(t)=0\). We have
\(\sum_{p\ge P} f(p)\log p\le (1+\epsilon) \int_P^\infty f(t) dt + \epsilon P f(P) + P f(P) / (5 \log^2 P)\)
with \(\epsilon=1/914\). When we can only ensure \(P\ge2\), then a similar inequality holds, simply replacing the last \(1/5\) by 4.
The above result relies on (5.1*) of [Schoenfeld, 1976] because it is easily accessible. However on using Proposition 5.1 of [Dusart, 2016], one has access to \(\epsilon=1/36260\).
Here is a result due to [Treviño, 2012].
Theorem (2012)
For \(x\) a positive real number. If \(x \geq x_0\) then there exist \(c_1\) and \(c_2\) depending on \(x_0\) such that \(\displaystyle \frac{x^2}{2\log{x}} +\frac{c_1 x^2}{\log^2{x}} \leq \sum_{p \leq x} p \leq\frac{x^2}{2\log{x}} + \frac{c_2 x^2}{\log^2{x}}.\) The constants \(c_1\) and \(c_2\) are given for various values of \(x_0\) in the next table.
\(\begin{array}{rrr} x_0 & c_1 & c_2 \\315437 & 0.205448 & 0.330479\\468577 & 0.211359 & 0.32593\\486377 & 0.212904 & 0.325537\\644123 & 0.21429 & 0.322609\\678407 & 0.214931 & 0.322326\\758231 & 0.215541 & 0.321504\\758711 & 0.215939 & 0.321489\\10544111 & 0.239818 & 0.29251\\\end{array}\)
Further estimates can be found in [Axler, 2019] (Proposition 2.7 and Corollary 2.8). In [Deléglise and Nicolas, 2019] (Proposition 2.7 and Corollary 2.8) and [Deléglise and Nicolas, 2019] (Proposition 2.5, Corollary 2.6, 2.7 and 2.8), we find among other results the next two.
Theorem (2019)
On setting \(\pi_r(x)=\sum_{p\le x}p^r\), we have
\(\displaystyle \frac{3x^2}{20(\log x)^4}\le \pi_1(x)-\biggl( \frac{x^2}{2\log x} +\frac{x^2}{4(\log x)^2} \frac{x^2}{4(\log x)^3}\biggr)\le \frac{107x^2}{160(\log x)^4}\)
where the upper estimate is valid when \(x\ge 110117910\) and the lower one when \(x\ge905238547\).
We have
\(\displaystyle \frac{-1069x^3}{648(\log x)^4} \le \pi_2(x)-\biggl( \frac{x^3}{3\log x} +\frac{x^3}{9(\log x)^2} \frac{x^3}{27(\log x)^3} \biggr)\le \frac{11181x^3}{648(\log x)^4}\)
where the upper estimate is valid when \(x\ge 60173\) and the lower one when \(x\ge 1091239\). In addition,
\(\displaystyle \pi_3(x)\le 0.271\frac{x^4}{\log x}\quad\text{for }x\ge 664,\)
\(\displaystyle \pi_4(x)\le 0.237\frac{x^5}{\log x}\quad\text{for }x\ge 200,\)
\(\displaystyle \pi_5(x)\le 0.226\frac{x^5}{\log x}\quad\text{for }x\ge 44,\)
For \(x\ge 1\) and \(r\ge5\), we have \(\displaystyle \pi_r(x)\le \frac{\log 3}{3}\bigl(1+(2/3)^r\bigr) \frac{x^{r+1}}{\log x}\) .
3. Bounds containing the \(n\)-th prime¶
Denote by \(p_n\) the \(n\)-th prime. Thus \(p_1=2,\;p_2=3,\; p_4=5,\cdots\).
The classical form of the prime number theorem yields easily \(p_n \sim n \log n.\) [Rosser, 1938] shows that this equivalence does not oscillate by proving that \(p_n\) is greater than \(n\log n\) for \(n\geq 2\).
The asymptotic formula for \(p_n\) can be developped as shown in [Cipolla, 1902]
This asymptotic expansion is the inverse of the logarithmic integral \(\mbox{Li}(x)\) obtained by series reversion.
[Rosser, 1938] obtained a finite version of the above: for every \(n> 1\):
He improves these results in [Rosser, 1941] : for every \(n\geq 55\),
This result was subsequently improved by Rosser and Schoenfeld [Rosser and Schoenfeld, 1962] in 1962 to
where the first and the second inequalities holds for \(n > 1\) and \(n > 19\), respectively. Those constants were subsequently reduced by [Robin, 1983] . In particular, the lower bound
is valid for \(n>1\) and the constant \(1.0072629\) can be replaced by 1 for \(p_k\leq 10^{11}\). Then [Massias and Robin, 1996] showed that the constant term equals to 1 in the lower bound was admissible for \(p_k < e^{598}\) and \(p_k > e^{1800}\). Finally, [Dusart, 1999] showed that
for all \(n>1\) and also that
for \(\displaystyle n > 39017\) i.e. \(p_n > 467473\).
In [Carneiro et al., 2019], the authors prove the next result.
Theorem (2019)
Under the Riemann Hypothesis, for all \(n \geq 3\),we have, \(p_{n+1}-p_n\le\frac{22}{25}\sqrt{p_n}\log p_n\).
In [Axler, 2019] we find (Theorem 1.6 and 1.7) the next result.
Theorem (2019)
We have \(\displaystyle \sum_{i\le k}p_i\ge \frac{k^2}4 +\frac{k^2}{4\log k} -\frac{k^2(\log\log k-2.9)}{4(\log k)^2}\quad(\text{for } k\ge 6309751),\)
as well as
\(\displaystyle \sum_{i\le k}p_i\le\frac{k^2}4 +\frac{k^2}{4\log k} -\frac{k^2(\log\log k-4.42)}{4(\log k)^2}\quad(\text{for }k\ge 256376).\)
In [De Koninck and Letendre, 2020] we find in passing (Lemma 4.8) the next result.
Theorem (2020)
We have \(\displaystyle \sum_{i\le k}\log p_i\le k\bigl(\log k+\log\log k -1/2\Bigr)\quad(\text{for }k\ge 5),\) as well as \(\displaystyle \sum_{i\le k}\log\log p_i\ge k\biggl(\log\log k+\frac{\log\log -3/2}{\log k}\biggr) \quad(\text{for }k\ge 6).\)
4. Bounds on primes in arithmetic progressions¶
Collecting references: [McCurley, 1984], [McCurley, 1984], [Ramaré and Rumely, 1996], [Dusart, 2002]
Lemma 10 of [Moree, 2004] , section 4 of [Moree and te Riele, 2004] .
A consequence of Theorem 1.1 and 1.2 of [Bennett et al., 2018] states that
Theorem (2018)
We have
\(\displaystyle \max_{3\le q\le 10^4}\max_{ x\ge 8\cdot 10^9}\max_{\substack{1\le a\le q,\\(a,q)=1}} \frac{\log x}{x}\Bigl|\sum_{\substack{n\le x,\\ n\equiv a[q]}}\Lambda(n) -\frac{x}{\varphi(q)}\Bigr|\le 1/840.\)
When \(q\in(10^4, 10^5]\), we may replace \(1/840\) by \(1/160\) and when \(q\ge 10^5\), we may replace \(1/840\) by \(\exp(0.03\sqrt{q}\log^3q)\).
Furthermore, we may replace \(\sum_{\substack{n\le x,\\ n\equiv a[q]}}\Lambda(n)\) by \(\sum_{\substack{p\le x,\\ p\equiv a[q]}}\log p\) with no changes in the constants.
Similarly, as a consequence of Theorem 1.3 of [Bennett et al., 2018] states that
Theorem (2018)
We have
\(\displaystyle \max_{3\le q\le 10^4}\max_{ x\ge 8\cdot 10^9}\max_{\substack{1\le a\le q,\\(a,q)=1}} \frac{\log^2 x}{x}\Bigl| \sum_{\substack{p\le x,\\ p\equiv a[q]}}1 -\frac{\textrm{Li}(x)}{\varphi(q)}\Bigr|\le 1/840.\)
When \(q\in(10^4, 10^5]\), we may replace \(1/840\) by \(1/160\) and when \(q\ge 10^5\), we may replace \(1/840\) by \(\exp(0.03\sqrt{q}\log^3q)\).
Concerning estimates with a logarithmic density, in [Ramaré, 2009] and in [Platt and Ramaré, 2017] estimates for the functions \(\displaystyle\sum_{\substack{n\le x,\\ n\equiv a[q]}}\Lambda(n)/n\) are considered. Extending computations from the former, the latter paper Theorem 8.1 reads as follows.
Theorem (2016)
We have \(\displaystyle \max_{q\le 1000}\max_{q\le x\le 10^5}\max_{\substack{1\le a\le q,\\ (a,q)=1}} \sqrt{x}\Bigl| \sum_{\substack{n\le x,\\ n\equiv a[q]}}\frac{\Lambda(n)}{n} -\frac{\log x}{\varphi(q)}-C(q,a)\Bigr|\in(0.8533,0.8534)\) and the maximum is attained with \(q=17\), \(x=606\) and \(a=2\).
The constant \(C(q,a)\) is the one expected, i.e. such that \(\sum_{\substack{n\le x,\\ n\equiv a[q]}}\frac{\Lambda(n)}{n}-\frac{\log x}{\varphi(q)}-C(q,a)\) goes to zero when \(x\) goes to infinity.
When \(q\) belongs to “Rumely’s list”, i.e. in one of the following set:
\(\{k\le 72\}\)
\(\{k\le 112, k\text{ non premier}\}\)
\(\begin{aligned}\{116, 117, &120, 121, 124, 125, 128, 132, 140, 143, 144, 156, 163, \\ &169, 180, 216, 243, 256, 360, 420, 432\}\end{aligned}\)
Theorem 2 of [Ramaré, 2009] gives the following.
Theorem (2002)
When \(q\) belongs to Rumely’s list and \(a\) is prime to \(q\), we have \(\displaystyle \sum_{\substack{n\le x,\\ n\equiv a[q]}}\frac{\Lambda(n)}{n} =\frac{\log x}{\varphi(q)}+C(q,a)+O^*(1)\) as soon as \(x\ge1\).
More precise bounds are given.
5. Least prime verifying a condition¶
In [Bach and Sorenson, 1996] , the authors estimate the magnitude of the first prime number in reduced residue classes.
Theorem (1996)
Let \(m\) and \(q\) be integers, with \(gcd(m;q)=1\). There is a prime \(p \equiv m (\mod q)\) satisfying \(p < 2(q\log q)^2\).
We also have the following result connected to prime gaps in residue classes [Kadiri, 2008].
Theorem (2008)
Let \(q\geq 3\) be a non-exceptional modulus and let \((a,q)=1\). For any \(\epsilon >0\), there exists a computable constant \(\alpha>0\) such that, if \(x \geq \alpha \log^2q\), then the interval \([e^x,e^{x+\epsilon}]\) contains a prime \(p \equiv a (\mod q)\).
The constant \(\alpha\) in the theorem above was computed for several \(\epsilon\) and \(q\geq q_0\) as in the following table