Sieve bounds

1. Some upper bounds

Theorem 2 of [Montgomery and Vaughan, 1973] 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) \le \frac{2y}{\phi(k)\log (y/k)}\) provided only that \(y > k\).

Here as usual, we have used the notation

\(\displaystyle \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 [Büthe, 2014] for a generic weighted version of this inequality.

Lemma 14 of [Ramaré and Viswanadham, 2021], 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 [Siebert, 1976].

Theorem (1976)

Let \(a\) and \(b\) be coprime integers with \(2|ab\). Then we have, for \(x>1\), \(\displaystyle \sum_{\substack{p\le x,\\ ap+b\text{ 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 [Riesel and Vaughan, 1983].

Theorem (1983)

Let \(a\) and \(b\) be coprime integers with \(2|ab\). Then we have, for \(x \ge e^L\), \(\displaystyle \sum_{\substack{p\le x,\\ ap+b\text{ 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

2. Density estimates

In Theorem 1, page 52 of [Greaves, 2001], 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 \(\displaystyle \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

\(\displaystyle \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 herefootnote{url{Articles/Art10.html#asy}}.

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 [Nathanson, 1996].

4. Integers free of small prime factors

In [Fan, 2022], 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 \(\displaystyle \Phi(x,z)\le \frac{x}{\log z},\quad(1 < z\le x).\)