圖蘭·帕爾
在數論 中,圖蘭篩法 (Turán sieve)是一個用以估計滿足特定條件的「篩選過的」正整數 集大小的技巧,而這些條件一般都以同餘 表示。這篩法由圖蘭·帕爾 於1934年發展。
在篩法 的術語中,圖蘭篩法是一種「組合篩法」,也就是一種透過小心應用容斥原理 進行「篩選」的篩法。此種篩法可給出「篩選過的」的集合大小的上界。
設
A
{\displaystyle A}
為不大於
x
{\displaystyle x}
的正整數的集合,並假定
P
{\displaystyle P}
為質數的集合,然後設
A
p
{\displaystyle A_{p}}
是
A
{\displaystyle A}
中可為
P
{\displaystyle P}
中的質數
p
{\displaystyle p}
整除的數組成的集合;此外,可設
d
{\displaystyle d}
為
P
{\displaystyle P}
中的不同質數的乘積,在這種狀況下,可相應地定義
A
d
{\displaystyle A_{d}}
為
A
{\displaystyle A}
中可被
d
{\displaystyle d}
整除的數的集合,並定義
A
1
{\displaystyle A_{1}}
為
A
{\displaystyle A}
本身。
設
z
{\displaystyle z}
為任意實數,而
P
(
z
)
{\displaystyle P(z)}
為
P
{\displaystyle P}
中不大於
z
{\displaystyle z}
的質數的乘積,那這篩法的目標就是估計下式:
S
(
A
,
P
,
z
)
=
|
A
∖
⋃
p
∣
P
(
z
)
A
p
|
.
{\displaystyle S(A,P,z)=\left\vert A\setminus \bigcup _{p\mid P(z)}A_{p}\right\vert .}
我們可以假定說在
d
{\displaystyle d}
為質數
p
{\displaystyle p}
的狀況下,
|
A
d
|
{\displaystyle \left|A_{d}\right|}
可由下式估計:
|
A
p
|
=
1
f
(
p
)
X
+
R
p
{\displaystyle \left\vert A_{p}\right\vert ={\frac {1}{f(p)}}X+R_{p}}
而在
d
{\displaystyle d}
為相異質數
p
{\displaystyle p}
與
q
{\displaystyle q}
的乘積狀況下,
|
A
d
|
{\displaystyle \left|A_{d}\right|}
可由下式估計:
|
A
p
q
|
=
1
f
(
p
)
f
(
q
)
X
+
R
p
,
q
{\displaystyle \left\vert A_{pq}\right\vert ={\frac {1}{f(p)f(q)}}X+R_{p,q}}
其中
X
{\displaystyle X}
是
A
{\displaystyle A}
的元素個數,而
f
{\displaystyle f}
則是一個使得
0
≤
f
(
d
)
≤
1
{\displaystyle 0\leq f(d)\leq 1}
的函數。
設
U
(
z
)
=
∑
p
∣
P
(
z
)
f
(
p
)
.
{\displaystyle U(z)=\sum _{p\mid P(z)}f(p).}
,可得下式:
S
(
A
,
P
,
z
)
≤
X
U
(
z
)
+
2
U
(
z
)
∑
p
∣
P
(
z
)
|
R
p
|
+
1
U
(
z
)
2
∑
p
,
q
∣
P
(
z
)
|
R
p
,
q
|
.
{\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 .}
哈代—拉馬努金定理 ─一個正整數
n
{\displaystyle n}
其相異的質因數個數
ω
(
n
)
{\displaystyle \omega (n)}
的正常階 為
log
log
(
n
)
{\displaystyle \log {\log {(n)}}}
。
在高度的階之下,幾乎所有的整係數多項式都是不可約多項式 。