图兰筛法

在数论中，图兰筛法（Turán sieve）是一个用以估计满足特定条件的“筛选过的”正整数集大小的技巧，而这些条件一般都以同馀表示。这筛法由图兰·帕尔于1934年发展。

图兰·帕尔

描述

在筛法的术语中，图兰筛法是一种“组合筛法”，也就是一种透过小心应用容斥原理进行“筛选”的筛法。此种筛法可给出“筛选过的”的集合大小的上界。

设$A$为不大于$x$的正整数的集合，并假定$P$为质数的集合，然后设$A_{p}$是$A$中可为$P$中的质数$p$整除的数组成的集合；此外，可设$d$为$P$中的不同质数的乘积，在这种状况下，可相应地定义$A_{d}$为$A$中可被$d$整除的数的集合，并定义$A_{1}$为$A$本身。

设$z$为任意实数，而$P(z)$为$P$中不大于$z$的质数的乘积，那这筛法的目标就是估计下式：

$S(A,P,z)=\left\vert A\setminus \bigcup _{p\mid P(z)}A_{p}\right\vert .$

我们可以假定说在$d$为质数$p$的状况下，$\left|A_{d}\right|$可由下式估计：

$\left\vert A_{p}\right\vert ={\frac {1}{f(p)}}X+R_{p}$

而在$d$为相异质数$p$与$q$的乘积状况下，$\left|A_{d}\right|$可由下式估计：

$\left\vert A_{pq}\right\vert ={\frac {1}{f(p)f(q)}}X+R_{p,q}$

其中$X$是$A$的元素个数，而$f$则是一个使得$0\leq f(d)\leq 1$的函数。

设$U(z)=\sum _{p\mid P(z)}f(p).$，可得下式：

$S(A,P,z)\leq {\frac {X}{U(z)}}+{\frac {2}{U(z)}}\sum _{p\mid P(z)}\left\vert R_{p}\right\vert +{\frac {1}{U(z)^{2}}}\sum _{p,q\mid P(z)}\left\vert R_{p,q}\right\vert .$

应用

• 哈代—拉马努金定理─一个正整数$n$其相异的质因数个数$\omega (n)$的正常阶为$\log {\log {(n)}}$。
• 在高度的阶之下，几乎所有的整系数多项式都是不可约多项式。

参考资料

• Alina Carmen Cojocaru; M. Ram Murty. An introduction to sieve methods and their applications. London Mathematical Society Student Texts 66. Cambridge University Press. : 47–62. ISBN 0-521-61275-6. 
• Greaves, George. Sieves in number theory. Springer-Verlag. 2001. ISBN 3-540-41647-1. 
• Halberstam, Heini; Richert, H.-E. Sieve Methods. London Mathematical Society Monographs 4. Academic Press. 1974. ISBN 0-12-318250-6. MR 0424730. Zbl 0298.10026. 
• Christopher Hooley. Applications of sieve methods to the theory of numbers. Cambridge University Press. 1976: 21. ISBN 0-521-20915-3.