图兰筛法

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

图兰·帕尔

描述

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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 .}$

应用

• 哈代—拉马努金定理─一个正整数${\displaystyle n}$其相异的质因数个数${\displaystyle \omega (n)}$的正常阶（英语：normal order of an arithmetic function）为${\displaystyle \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.