The TME-EMT project
Sieve bounds
Theorem 2 of contains the
following explicit version of the Brun-Tichmarsh Theorem.
Theorem (1973)
Let $x$ and $y$ be positive real numbers, and let $k$ and $\ell$ be relatively
prime positive integers. Then
$
\pi(x+y;k,\ell)-\pi(x;k,\ell)
< \frac{2y}{\phi(k)\log (y/k)}
$ provided only that $y>k$.
Here as usual, we have used the notation
$$
\pi(z;k,\ell)=\sum_{\substack{p\le z,\\ p\equiv \ell [k]}}1,
$$
i.e. the number of primes up to $z$ that are coprime to $\ell$ modulo $k$.
See
for a generic weighted version of this inequality.
Lemma 14 of
,
the following extension of the above is proved.
Theorem (2021)
Let $x\ge y>k\ge 1$ be positive real numbers, $k$ being an integer. Then
$
\displaystyle
\sum_{\substack{x < m \le x+y\\ m\equiv a[k]}}\frac{\Lambda(m)}{\log m}
< \frac{2y}{\phi(k)\log (y/k)}.
$
And in Lemma 15 of the same paper, we find the next estimate.
Theorem (2021)
Let $x\ge \max(121,k^3)$. Then
$
\displaystyle
\sum_{\substack{x < m \le 2x\\ m\equiv a[k]}}\Lambda(m)
< \frac{9}{2}\frac{x}{\phi(k)}.
$
Here is a bound concerning a sieve of dimension 2 proved by
.
Theorem (1976)
Let $a$ and $b$ be coprime integers with $2|ab$. Then we have, for $x>1$,
$$
\sum_{\substack{p\le x,\\ \text{$ap+b$ prime}}}1
\le 16 \omega\frac{x}{(\log x)^2}\prod_{\substack{p|ab,\\ p >
2}}\frac{p-1}{p-2}
\qquad \omega=\prod_{p > 2}(1-(p-1)^{-2}).
$$
This is improved for large values in Lemma 4 of
.
Theorem (1983)
Let $a$ and $b$ be coprime integers with $2|ab$. Then we have, for $x
\ge e^L$,
$$
\sum_{\substack{p\le x,\\ \text{$ap+b$ prime}}}1
\le \biggl(\frac{16 \omega\, x}{(\log x)(A+\log x)}-100\sqrt{x}\biggr)\prod_{\substack{p|ab,\\ p >
2}}\frac{p-1}{p-2}
\qquad \omega=\prod_{p > 2}(1-(p-1)^{-2})
$$
and where
|
|
| $L$: |
24 |
25 |
26 |
27 |
28 |
29 |
31 |
34 |
42 |
60 |
690 |
| $A$: |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
8.3 |
8.45 |
In Theorem 1, page 52 of
,
we find the next widely applicable estimate.
Theorem (2022)
Let $\kappa$ be a non-negative function on the primes such that
$\kappa(p) < p$. Assume there is a constant $B$ such that
$$
\sum_{p < z} \frac{\kappa(p)\log p}{p}
\le B\log z
$$
for some $z\ge 2$. Then, when $s\ge 2B$, we
have
$$
\sum_{d\le z^{s/2}}\mu^2(d)
\prod_{p|d}\frac{\kappa(p)}{p-\kappa(p)}
\ge
\Bigl(1-\exp-\bigl(\frac{s}{2}\log\frac{s}{2B}-\frac{s}{2}+B\bigr)\Bigr)
\prod_{p < z}\biggl(1-\frac{\kappa(p)}{p}\biggr)^{-1}.
$$
See also
here.
3. Combinatorial sieve estimates
The combinatorial sieve is known to be difficult from an explicit
viewpoint. For the linear sieve, the reader may look at Chapter 9,
Theorem 9.7 and 9.8 from
.
4. Integers free of small prime factors
In
,
the following neat estimate is proved.
Theorem (2022)
Let $\Phi(x,z)$ be the number of integers $\le x$ that do not have any
prime factors $\le z$. We have
$$
\Phi(x,z)\le \frac{x}{\log z},
\quad(1 < z\le x).
$$
Last updated on February 6th, 2024, by Olivier Ramaré