Namespaces
Variants
Actions

Difference between revisions of "Buchstab identity"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX done)
Line 1: Line 1:
A form of the Sylvester [[Inclusion-and-exclusion principle|inclusion-and-exclusion principle]] specialized to sieve theory (cf. also [[Sieve method|Sieve method]]). Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111030/b1110301.png" /> be a finite integer sequence and, for any integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111030/b1110302.png" />, denote by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111030/b1110303.png" /> the subsequence of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111030/b1110304.png" /> that are multiples of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111030/b1110305.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111030/b1110306.png" /> be a set of prime numbers (cf. also [[Prime number|Prime number]]), and, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111030/b1110307.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111030/b1110308.png" />. Finally, let
+
A form of the Sylvester [[inclusion-and-exclusion principle]] specialized to sieve theory (cf. also [[Sieve method]]). Let $\mathcal{A}$ be a finite integer sequence and, for any integer $q$, denote by $\mathcal{A}_q$ the subsequence of elements of $\mathcal{A}$ that are multiples of $q$. Let $\mathcal{P}$ be a set of [[prime number]]s, and, for $z \ge 2$, let $P(z) = \prod_{p\in\mathcal{P},\,p< z} p$. Finally, let
 +
$$
 +
S(\mathcal{A}, \mathcal{P} ,z) = \sharp \{ a \in \mathcal{A} \ : \ (a,P(z)) = 1 \}
 +
$$
 +
denote the  "sifting function" associated with $\mathcal{A}$ and $\mathcal{P}$. The Buchstab identity asserts that, for $2 \le z_1 \le z$,
 +
\begin{equation}\label{eq:1}
 +
S(\mathcal{A}_q, \mathcal{P} ,z) = S(\mathcal{A}_q, \mathcal{P} ,z_1) - \sum_{p\in \mathcal{P},\,z_1 \le p < z} S(\mathcal{A}_{pq}, \mathcal{P} ,p) \ .
 +
\end{equation}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111030/b1110309.png" /></td> </tr></table>
+
The identity is useful for deriving a lower-bound sieve estimate from an upper bound sieve estimate (or vice versa) as follows. If the parameter $z_1$ is sufficiently small, then the quantity $S(\mathcal{A}_q, \mathcal{P} ,z_1)$ on the right-hand side of (a1) usually can be estimated asymptotically. Thus, if an upper bound for each of the terms $S(\mathcal{A}_{pq}, \mathcal{P} ,p)$ on the right-hand side of \eqref{eq:1} is known, then a lower bound for the sifting function on the left-hand side of \eqref{eq:1} can be deduced.
  
denote the  "sifting function"  associated with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111030/b11103010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111030/b11103011.png" />. The Bukhstab identity asserts that, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111030/b11103012.png" />,
+
====References====
 
+
<table>
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111030/b11103013.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
<TR><TD valign="top">[a1]</TD> <TD valign="top"> H. Halberstam,  H.-E. Richert,   "Sieve methods" , Acad. Press  (1974) {{ZBL|0298.10026}}</TD></TR>
 
+
</table>
The identity is useful for deriving a lower-bound sieve estimate from an upper bound sieve estimate (or vice versa) as follows. If the parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111030/b11103014.png" /> is sufficiently small, then the quantity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111030/b11103015.png" /> on the right-hand side of (a1) usually can be estimated asymptotically. Thus, if an upper bound for each of the terms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b111/b111030/b11103016.png" /> on the right-hand side of (a1) is known, then a lower bound for the sifting function on the left-hand side of (a1) can be deduced.
 
  
====References====
+
{{TEX|done}}
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  H. Halberstam,  H.-E. Richert,  "Sieve methods" , Acad. Press  (1974)</TD></TR></table>
 

Revision as of 20:23, 21 September 2017

A form of the Sylvester inclusion-and-exclusion principle specialized to sieve theory (cf. also Sieve method). Let $\mathcal{A}$ be a finite integer sequence and, for any integer $q$, denote by $\mathcal{A}_q$ the subsequence of elements of $\mathcal{A}$ that are multiples of $q$. Let $\mathcal{P}$ be a set of prime numbers, and, for $z \ge 2$, let $P(z) = \prod_{p\in\mathcal{P},\,p< z} p$. Finally, let $$ S(\mathcal{A}, \mathcal{P} ,z) = \sharp \{ a \in \mathcal{A} \ : \ (a,P(z)) = 1 \} $$ denote the "sifting function" associated with $\mathcal{A}$ and $\mathcal{P}$. The Buchstab identity asserts that, for $2 \le z_1 \le z$, \begin{equation}\label{eq:1} S(\mathcal{A}_q, \mathcal{P} ,z) = S(\mathcal{A}_q, \mathcal{P} ,z_1) - \sum_{p\in \mathcal{P},\,z_1 \le p < z} S(\mathcal{A}_{pq}, \mathcal{P} ,p) \ . \end{equation}

The identity is useful for deriving a lower-bound sieve estimate from an upper bound sieve estimate (or vice versa) as follows. If the parameter $z_1$ is sufficiently small, then the quantity $S(\mathcal{A}_q, \mathcal{P} ,z_1)$ on the right-hand side of (a1) usually can be estimated asymptotically. Thus, if an upper bound for each of the terms $S(\mathcal{A}_{pq}, \mathcal{P} ,p)$ on the right-hand side of \eqref{eq:1} is known, then a lower bound for the sifting function on the left-hand side of \eqref{eq:1} can be deduced.

References

[a1] H. Halberstam, H.-E. Richert, "Sieve methods" , Acad. Press (1974) Zbl 0298.10026
How to Cite This Entry:
Buchstab identity. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Buchstab_identity&oldid=41914
This article was adapted from an original article by H. Diamond (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article