The TME-EMT project

Navigation

Back to top

Some upper bounds

Combinatorial sieve estimates

Integers free of small primes

---

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.
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}). $$

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 . 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). $$

---