Sieve bounds
============

.. if-builder:: html

   .. toctree::
      :maxdepth: 2 
 


 
1. Some upper bounds
--------------------


Theorem 2 of :cite:`Montgomery-Vaughan73` contains the
following explicit version of the Brun-Tichmarsh Theorem.

 
.. admonition:: Theorem (1973)
   :class: thm-tme-emt

   Let :math:`x` and :math:`y` be positive real numbers, and let :math:`k` and :math:`\ell` be relatively
   prime positive integers. Then 
   :math:`\pi(x+y;k,\ell)-\pi(x;k,\ell) \le  \frac{2y}{\phi(k)\log (y/k)}`
   provided only that :math:`y > k`.


Here as usual, we have used the notation


:math:`\displaystyle  \pi(z;k,\ell)=\sum_{\substack{p\le z,\\ p\equiv \ell [k]}}1,` 
i.e. the number of primes up to :math:`z` that are coprime to :math:`\ell` modulo :math:`k`.
See
:cite:`Buethe14`
for a generic weighted version of this inequality.

Lemma 14 of
:cite:`Ramare13a`,
the following extension of the above is proved.

 
.. admonition:: Theorem (2021)
   :class: thm-tme-emt

   Let :math:`x\ge y>k\ge 1` be positive real numbers, :math:`k` being an integer. Then 
   :math:`\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.

 
.. admonition:: Theorem (2021)
   :class: thm-tme-emt

   Let :math:`x\ge \max(121,k^3)`. Then 
   :math:`\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
:cite:`Siebert76`.

 
.. admonition:: Theorem (1976)
   :class: thm-tme-emt

   Let :math:`a` and :math:`b` be coprime integers with :math:`2|ab`. Then we have, for :math:`x>1`,
   :math:`\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
:cite:`Riesel-Vaughan83`.

 
.. admonition:: Theorem (1983)
   :class: thm-tme-emt

   Let :math:`a` and :math:`b` be coprime integers with
   :math:`2|ab`. Then we have, for :math:`x \ge e^L`,
   :math:`\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
   
   
   
   
   :math:`L`:
   24
   25
   26
   27
   28
   29
   31
   34
   42
   60
   690
   
   
   :math:`A`:
   0
   1
   2
   3
   4
   5
   6
   7
   8
   8.3
   8.45
   
   
   
   





2. Density estimates 
---------------------


In Theorem 1, page 52 of
:cite:`Greaves01`,
we find the next widely applicable estimate.

 
.. admonition:: Theorem (2022)
   :class: thm-tme-emt

   Let :math:`\kappa` be a non-negative function on the primes such that
   :math:`\kappa(p) < p`. Assume there is a constant :math:`B` such that
   :math:`\displaystyle   \sum_{p < z} \frac{\kappa(p)\log p}{p}\le B\log z` 
   for some :math:`z\ge 2`. Then, when :math:`s\ge 2B`, we have 

   :math:`\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 here\footnote{\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
:cite:`Nathanson96-2`.


4. Integers free of small prime factors
---------------------------------------


In
:cite:`Fan22`, 
the following neat estimate is proved.

 
.. admonition:: Theorem (2022)
   :class: thm-tme-emt

   Let :math:`\Phi(x,z)` be the number of integers :math:`\le x` that do not have any
   prime factors :math:`\le z`. We have
   :math:`\displaystyle  \Phi(x,z)\le \frac{x}{\log z},\quad(1 < z\le x).`