大篩

同義語:大篩法大篩の不等式large sievelarge sieve inequality

概要

大篩(large sieve)とは、三角多項式 $S(\alpha)=\sum_{M<n\le M+N}a_ne(n\alpha)$ の値の 2 乗を、法 $1$ で $\delta$ 以上離れた点の上で足したものが $(N-1+\delta^{-1})\sum\lvert a_n\rvert^2$ 以下になるという解析的な原理と、それによる篩の方法である。双対性と Montgomery–Vaughan の Hilbert 型の不等式から証明でき、定数は最良である。点を分母 $Q$ 以下の既約分数にとると、法 $p$ の $\omega(p)$ 個の類を避ける集合の元の個数が $(N-1+Q^2)/L$ 以下になる。$\omega(p)$ が大きい場面に強く、短い区間の素数の上界や Bombieri–Vinogradov の定理に使われる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 篩法, Cauchy–Schwarzの不等式, Dirichlet指標

大篩(large sieve)は、三角多項式 $S(\alpha)=\sum_na_ne(n\alpha)$ の値の 2 乗を、互いに離れた点の上で足しても $\sum_n\lvert a_n\rvert^2$ の定数倍で抑えられる、という解析的な原理と、それを整数の集合の篩に使う方法の総称である。ここで $e(\alpha):=e^{2\pi i\alpha}$ である。篩い落とす剰余類の個数 $\omega(p)$ が $p$ とともに増えるときに強い評価を与え、$\omega(p)$ が有界な場面を得意とする Brunの篩 や Selbergの篩 と対になる(Bom87 §1, pp. 6–7)。
起源は Linnik の 1941 年の短い論文で、Linnik はこれを平方非剰余の分布に使った。Rényi が系統的に研究して数論に応用し、1965 年の Roth と Bombieri の仕事のあと広く使われるようになった。解析的な原理に整理したのは Davenport と Halberstam である(Mon78 §1, p. 547)。乗法的な形は Bombieri–Vinogradovの定理 の証明の柱であり、Chenの定理 でも主要な道具である(Mon78 p. 547、p. 562)。
この記事では、最良の定数 $N-1+\delta^{-1}$ をもつ大篩の不等式(thm-ls-main)を、双対性と Hilbert 型の不等式から証明し、篩の形(thm-ls-sieve)に直して応用する。

大篩の不等式

以下、$M$ は整数、$N$ は正の整数、$a_n$($M< n\le M+N$)は複素数とし、
$$ S(\alpha):=\sum_{M< n\le M+N}a_ne(n\alpha),\qquad\|a\|^2:=\sum_{M< n\le M+N}\lvert a_n\rvert^2 $$
とおく。$\|\alpha\|$ は実数 $\alpha$ から最も近い整数までの距離である。

大篩の定数

$0< \delta\le\frac12$ とする。実数 $\alpha_1,\dots,\alpha_R$ が $\delta$ だけ離れている とは、$r\ne s$ なら $\|\alpha_r-\alpha_s\|\ge\delta$ であることをいう。すべての $M$、すべての $a_n$、$\delta$ だけ離れたすべての点の組について
$$ \sum_{r=1}^R\lvert S(\alpha_r)\rvert^2\le\Delta\,\|a\|^2 $$
が成り立つような $\Delta$ の最小値を $\Delta(N,\delta)$ と書き、大篩の定数 という。この形の不等式を 大篩の不等式 という。

$\lvert S\rvert$ は $M$ をずらしても変わらない($S$ に $e(K\alpha)$ が掛かるだけ)ので、$\Delta(N,\delta)$ は $M$ によらない。点が 1 つで $a_n=e(-n\alpha_1)$ なら $\lvert S(\alpha_1)\rvert^2=N^2=N\|a\|^2$ なので $\Delta(N,\delta)\ge N$ である。等間隔の点を使うと $\delta^{-1}$ 程度の下界も出る(Mon78 §2, p. 548)。大篩の要点は、$\Delta(N,\delta)$ がこの二つの自明な下界の和を大きく超えないことである。
Gallagher による $\Delta(N,\delta)\le\pi N+\delta^{-1}$ の短い証明は Bombieri–Vinogradovの定理 の節「大篩の不等式」にある。ここでは定数を $N-1+\delta^{-1}$ まで下げる。

双対性

$c_{nr}$($1\le n\le N'$、$1\le r\le R$)を複素数とし、$D\ge0$ とする。次の 2 つは同値である。

  1. すべての $x_n$ について $\sum_r\bigl\lvert\sum_nc_{nr}x_n\bigr\rvert^2\le D\sum_n\lvert x_n\rvert^2$。
  2. すべての $y_r$ について $\sum_n\bigl\lvert\sum_rc_{nr}y_r\bigr\rvert^2\le D\sum_r\lvert y_r\rvert^2$。

1 を仮定する。$L_n:=\sum_rc_{nr}y_r$、$x_n:=\overline{L_n}$ とおくと、Cauchy–Schwarzの不等式 と 1 から
$$ \sum_n\lvert L_n\rvert^2=\Bigl\lvert\sum_r y_r\sum_nc_{nr}x_n\Bigr\rvert\le\Bigl(\sum_r\lvert y_r\rvert^2\Bigr)^{1/2}\Bigl(D\sum_n\lvert L_n\rvert^2\Bigr)^{1/2} $$
で、両辺を $(\sum_n\lvert L_n\rvert^2)^{1/2}$ で割れば 2 を得る。逆も同じ($c_{nr}$ の役割を入れ替える)。$\square$

行列とその随伴の作用素ノルムが等しいことの言い換えである(Mon78 Lemma 2, p. 550)。大篩の不等式の双対は
$$ \sum_{M< n\le M+N}\Bigl\lvert\sum_ry_re(n\alpha_r)\Bigr\rvert^2\le\Delta\sum_r\lvert y_r\rvert^2 $$
であり、左辺を展開すると $n$ についての和は等比数列の和になって計算できる。対角の項が $N\sum\lvert y_r\rvert^2$ を与え、残りの項の評価が次の不等式に帰着する。

Hilbert 型の不等式

Hilbert は $\bigl\lvert\sum_{r\ne s}w_r\overline{w_s}/(r-s)\bigr\rvert\le C\sum\lvert w_r\rvert^2$ を示し、最良の定数は $\pi$ である(Mon78 §6, p. 554)。Montgomery と Vaughan は整数 $r$ を、間隔が $\delta$ 以上の実数に置き換えた。

Montgomery–Vaughan の不等式

実数 $\lambda_1,\dots,\lambda_R$ が $r\ne s$ について $\lvert\lambda_r-\lambda_s\rvert\ge\delta>0$ をみたすとする。このとき任意の複素数 $w_r$ について
$$ \Bigl\lvert\sum_{r\ne s}\frac{w_r\overline{w_s}}{\lambda_r-\lambda_s}\Bigr\rvert\le\frac\pi\delta\sum_r\lvert w_r\rvert^2. $$

固有ベクトルで計算する

$C=(C_{sr})$ を $C_{sr}=(\lambda_s-\lambda_r)^{-1}$($r\ne s$)、$C_{rr}=0$ で定める。$C$ は実の交代行列なので、正規行列として ユニタリ行列 で対角化でき、固有値は純虚数 $i\mu_1,\dots,i\mu_R$ である。左辺の和は $\overline{w}^{\mathsf T}Cw$ の符号を変えたものなので、絶対値は $\max_j\lvert\mu_j\rvert\sum\lvert w_r\rvert^2$ 以下である。よって、$Cw=i\mu w$、$\sum\lvert w_r\rvert^2=1$ をみたす固有ベクトル $w$ について $\mu^2\le\pi^2\delta^{-2}$ を示せばよい。
$\mu^2=\sum_s\lvert(Cw)_s\rvert^2=\sum_s\sum_{r\ne s}\sum_{t\ne s}\frac{w_r\overline{w_t}}{(\lambda_s-\lambda_r)(\lambda_s-\lambda_t)}$ を、$r=t$ の項 $\Sigma_1:=\sum_r\lvert w_r\rvert^2\sum_{s\ne r}(\lambda_r-\lambda_s)^{-2}$ と $r\ne t$ の項に分ける。$r\ne t$ では
$$ \frac1{(\lambda_s-\lambda_r)(\lambda_s-\lambda_t)}=\frac1{\lambda_r-\lambda_t}\Bigl(\frac1{\lambda_s-\lambda_r}-\frac1{\lambda_s-\lambda_t}\Bigr) $$
である。$\sigma_r:=\sum_{s\ne r}(\lambda_s-\lambda_r)^{-1}$ とおくと、$s\ne r,t$ についての和は $\sigma_r-\sigma_t+\frac2{\lambda_r-\lambda_t}$ になる($s=t$ と $s=r$ の項を補う)。したがって $r\ne t$ の項は
$$ \sum_{r\ne t}\frac{w_r\overline{w_t}\,\sigma_r}{\lambda_r-\lambda_t}-\sum_{r\ne t}\frac{w_r\overline{w_t}\,\sigma_t}{\lambda_r-\lambda_t}+2\sum_{r\ne t}\frac{w_r\overline{w_t}}{(\lambda_r-\lambda_t)^2} $$
である。第 1 項は $\sum_rw_r\sigma_r\overline{(Cw)_r}=\sum_rw_r\sigma_r\overline{i\mu w_r}=-i\mu\sum_r\sigma_r\lvert w_r\rvert^2$、第 2 項は $\sum_t\overline{w_t}\sigma_t\cdot(-(Cw)_t)=-i\mu\sum_t\sigma_t\lvert w_t\rvert^2$ で、両者は打ち消し合う。第 3 項は $\lvert w_r\overline{w_t}\rvert\le\frac12(\lvert w_r\rvert^2+\lvert w_t\rvert^2)$ により $2\Sigma_1$ 以下である。よって $\mu^2\le3\Sigma_1$ である。
最後に、$\lambda$ を小さい順に並べると $\lvert\lambda_r-\lambda_s\rvert\ge\delta\lvert r-s\rvert$ なので、各 $r$ について $\sum_{s\ne r}(\lambda_r-\lambda_s)^{-2}\le2\delta^{-2}\sum_{k\ge1}k^{-2}=\frac{\pi^2}{3}\delta^{-2}$ であり、$\Sigma_1\le\frac{\pi^2}3\delta^{-2}$、$\mu^2\le\pi^2\delta^{-2}$ を得る。$\square$

この証明は Mon78 Theorem 2(pp. 554–556)の議論を、固有ベクトルを最初にとる形に整えたものである。次の系は、点を法 $1$ で考えるための形である。

正弦の形

実数 $\alpha_1,\dots,\alpha_R$ が $\delta$ だけ離れているとき、任意の複素数 $w_r$ について
$$ \Bigl\lvert\sum_{r\ne s}\frac{w_r\overline{w_s}}{\sin\pi(\alpha_r-\alpha_s)}\Bigr\rvert\le\frac1\delta\sum_r\lvert w_r\rvert^2. $$

点を整数だけずらして並べる

正の整数 $K$ をとり、$RK$ 個の実数 $\lambda_{r,m}:=\alpha_r+m$($1\le m\le K$)と $w_{r,m}:=(-1)^mw_r$ を考える。$(r,m)\ne(s,n)$ なら $\lvert\lambda_{r,m}-\lambda_{s,n}\rvert\ge\delta$ である($r=s$ なら差は $0$ でない整数、$r\ne s$ なら $\|\alpha_r-\alpha_s\|\ge\delta$)。thm-ls-mv を当てる。$r=s$ の項の和 $\sum_r\lvert w_r\rvert^2\sum_{m\ne n}\frac{(-1)^{m-n}}{m-n}$ は、$(m,n)$ と $(n,m)$ の項が打ち消し合って $0$ である。残りを $K$ で割ると
$$ \Bigl\lvert\sum_{r\ne s}w_r\overline{w_s}\sum_{\lvert k\rvert< K}\Bigl(1-\frac{\lvert k\rvert}K\Bigr)\frac{(-1)^k}{\alpha_r-\alpha_s+k}\Bigr\rvert\le\frac\pi\delta\sum_r\lvert w_r\rvert^2 $$
である($k=m-n$ の組は $K-\lvert k\rvert$ 個)。$\beta\notin\mathbb Z$ について部分分数展開 $\frac{\pi}{\sin\pi\beta}=\lim_{L\to\infty}\sum_{\lvert k\rvert\le L}\frac{(-1)^k}{\beta+k}$ が成り立ち(Mon78 p. 556)、内側の和はこの部分和の算術平均なので、$K\to\infty$ で $\frac{\pi}{\sin\pi(\alpha_r-\alpha_s)}$ に収束する。両辺を $\pi$ で割れば主張を得る。$\square$

最良の定数

大篩の不等式(Selberg の定数)

$0< \delta\le\frac12$ とし、実数 $\alpha_1,\dots,\alpha_R$ が $\delta$ だけ離れているとする。このとき
$$ \sum_{r=1}^R\lvert S(\alpha_r)\rvert^2\le(N-1+\delta^{-1})\,\|a\|^2 $$
である。すなわち $\Delta(N,\delta)\le N-1+\delta^{-1}$。

双対性で $N+\delta^{-1}$ を出し、点を細かくして $1$ を削る

段 1:$N+\delta^{-1}$。 lem-ls-duality により、すべての $y_r$ について $\sum_n\lvert\sum_ry_re(n\alpha_r)\rvert^2\le(N+\delta^{-1})\sum_r\lvert y_r\rvert^2$ を示せばよい。左辺を展開すると
$$ \sum_{r,s}y_r\overline{y_s}\sum_{M< n\le M+N}e(n(\alpha_r-\alpha_s))=N\sum_r\lvert y_r\rvert^2+\sum_{r\ne s}u_r\overline{u_s}\,\frac{\sin\pi N(\alpha_r-\alpha_s)}{\sin\pi(\alpha_r-\alpha_s)} $$
である。ここで等比数列の和 $\sum_{M< n\le M+N}e(n\beta)=e(\tau\beta)\frac{\sin\pi N\beta}{\sin\pi\beta}$($\tau:=M+\frac{N+1}2$、$\beta\notin\mathbb Z$)を使い、$u_r:=y_re(\tau\alpha_r)$ とおいた。$\sin\pi N\beta=\frac1{2i}(e^{i\pi N\beta}-e^{-i\pi N\beta})$ と分けると、第 2 項は
$$ \frac1{2i}\sum_{r\ne s}\frac{u_re^{i\pi N\alpha_r}\,\overline{u_se^{i\pi N\alpha_s}}}{\sin\pi(\alpha_r-\alpha_s)}-\frac1{2i}\sum_{r\ne s}\frac{u_re^{-i\pi N\alpha_r}\,\overline{u_se^{-i\pi N\alpha_s}}}{\sin\pi(\alpha_r-\alpha_s)} $$
で、cor-ls-sine からそれぞれの絶対値は $\frac1{2\delta}\sum\lvert y_r\rvert^2$ 以下である。よって $\Delta(N,\delta)\le N+\delta^{-1}$。
段 2:$N-1+\delta^{-1}$。 正の整数 $K$ をとり、$T(\beta):=S(K\beta)=\sum_na_ne(nK\beta)$ とおく。$T$ の係数は $K(M+1)$ から $K(M+N)$ までの $K(N-1)+1$ 個の連続する整数の上にあり、係数の 2 乗の和は $\|a\|^2$ である。$RK$ 個の点 $\beta_{r,k}:=(\alpha_r+k)/K$($0\le k< K$)は $\delta/K$ だけ離れている。実際、$r=s$、$k\ne l$ なら差は $(k-l)/K$ で最も近い整数まで $1/K$ 以上、$r\ne s$ なら整数 $m$ について $\lvert\alpha_r-\alpha_s+k-l-mK\rvert/K\ge\|\alpha_r-\alpha_s\|/K\ge\delta/K$ である。$T(\beta_{r,k})=S(\alpha_r+k)=S(\alpha_r)$ なので、段 1 を $T$ に当てると
$$ K\sum_r\lvert S(\alpha_r)\rvert^2=\sum_{r,k}\lvert T(\beta_{r,k})\rvert^2\le\bigl(K(N-1)+1+K\delta^{-1}\bigr)\|a\|^2 $$
である。$K$ で割って $K\to\infty$ とすればよい。$\square$

段 1 は Mon78 Corollary 2(p. 556)、段 2 は同所 p. 559 の追記にある Cohen の工夫である。定数 $N-1+\delta^{-1}$ は Selberg が Beurling の関数を使って得たもので(Mon78 Theorem 3, p. 559)、次の例が示すとおり、これ以上は下げられない。

等号が成り立つ例

整数 $R\ge2$、$j\ge1$ をとり、$N=Rj+1$、$\delta=1/R$、$\alpha_r=r/R$($1\le r\le R$)、区間を $0\le n\le Rj$($M=-1$)とし、$a_n=1$($R\mid n$)、$a_n=0$(それ以外)とする。$\|a\|^2=j+1$ で、$e(n\alpha_r)=1$($R\mid n$)だから $S(\alpha_r)=j+1$、
$$ \sum_r\lvert S(\alpha_r)\rvert^2=R(j+1)^2=(Rj+R)(j+1)=(N-1+\delta^{-1})\|a\|^2 $$
である。Mon78 p. 559 は、Selberg がこの型の場合にしか等号が起きないことを示したと述べている。

篩としての大篩

点を分母が $Q$ 以下の既約分数にとる。

既約分数の上の和

$Q\ge1$ について
$$ \sum_{q\le Q}\ \sum_{a\in(\mathbb Z/q\mathbb Z)^\times}\lvert S(a/q)\rvert^2\le(N-1+Q^2)\,\|a\|^2. $$
ここで $a$ は $0\le a< q$、$\gcd(a,q)=1$ をみたす整数を動く。

異なる既約分数は $Q^{-2}$ だけ離れているので、$Q\ge2$ なら thm-ls-main を $\delta=Q^{-2}$ で使えばよい。

詳しくは

$a/q\ne a'/q'$ と整数 $m$ について $\frac aq-\frac{a'}{q'}-m$ の分子 $aq'-a'q-mqq'$ は $0$ でない整数なので、差は $\frac1{qq'}\ge Q^{-2}$ 以上である。$Q=1$ なら左辺は $\lvert S(0)\rvert^2\le N\|a\|^2$(Cauchy–Schwarzの不等式)である。$\square$

Mon78 (20)(p. 559)はこれを定数 $N+Q^2$ の形で書く。$q=1$ の項は $\lvert S(0)\rvert^2$ である。$S(0)$ が集合の元の個数になるように $a_n$ を選び、各 $q$ の項を下から抑えると篩の評価になる。

一つの法での下からの評価

$q$ を平方因子をもたない正の整数とし、$q$ の各素因数 $p$ について、$a_n\ne0$ となる $n$ が法 $p$ の $\omega(p)$ 個の剰余類($0\le\omega(p)< p$)に入らないとする。このとき
$$ \sum_{a\in(\mathbb Z/q\mathbb Z)^\times}\lvert S(a/q)\rvert^2\ge h(q)\,\lvert S(0)\rvert^2,\qquad h(q):=\prod_{p\mid q}\frac{\omega(p)}{p-\omega(p)}. $$

素数の場合と中国剰余定理

$q=p$ が素数のとき。 $Z(h):=\sum_{n\equiv h\ (p)}a_n$ とおくと、$\sum_{a=0}^{p-1}e(a(n-m)/p)$ は $n\equiv m$ で $p$、それ以外で $0$ なので $\sum_{a=0}^{p-1}\lvert S(a/p)\rvert^2=p\sum_h\lvert Z(h)\rvert^2$ である。$Z(h)$ は $\omega(p)$ 個の $h$ で $0$ なので、Cauchy–Schwarzの不等式 から $\lvert S(0)\rvert^2=\lvert\sum_hZ(h)\rvert^2\le(p-\omega(p))\sum_h\lvert Z(h)\rvert^2$ である。よって
$$ \sum_{a=1}^{p-1}\lvert S(a/p)\rvert^2=p\sum_h\lvert Z(h)\rvert^2-\lvert S(0)\rvert^2\ge\Bigl(\frac p{p-\omega(p)}-1\Bigr)\lvert S(0)\rvert^2. $$
一般の $q$。 素因数の個数についての帰納法による。$q=q_1q_2$($q_1,q_2>1$、互いに素)とし、どちらについても主張がすべての数列について成り立つとする。$b\in(\mathbb Z/q_2\mathbb Z)^\times$ を固定し、数列 $a_ne(nb/q_2)$ に $q_1$ の場合を当てる。この数列の $0$ でない項の位置は $a_n$ と同じなので仮定をみたし、
$$ \sum_{c\in(\mathbb Z/q_1\mathbb Z)^\times}\Bigl\lvert S\Bigl(\frac c{q_1}+\frac b{q_2}\Bigr)\Bigr\rvert^2\ge h(q_1)\lvert S(b/q_2)\rvert^2 $$
である。中国剰余定理 により、$\frac c{q_1}+\frac b{q_2}=\frac{cq_2+bq_1}{q}$ は、$(c,b)$ が動くとき法 $1$ で $(\mathbb Z/q\mathbb Z)^\times$ の分数をちょうど一度ずつとる。$b$ について足し、$q_2$ の場合を使うと $\sum_{a}\lvert S(a/q)\rvert^2\ge h(q_1)h(q_2)\lvert S(0)\rvert^2$ である。$\square$

Mon78 p. 561 はこの種の不等式に Johnsen と Gallagher の簡単な証明があると述べている。cor-ls-farey と合わせると次の定理を得る。

大篩の篩の形(Montgomery)

$\mathcal A$ を区間 $(M,M+N]$ の整数の集合とし、$Q\ge1$ 以下の各素数 $p$ について、$\mathcal A$ は法 $p$ の $\omega(p)$ 個の剰余類($0\le\omega(p)< p$)と交わらないとする。このとき
$$ \#\mathcal A\le\frac{N-1+Q^2}{L},\qquad L:=\sum_{q\le Q}\mu^2(q)\prod_{p\mid q}\frac{\omega(p)}{p-\omega(p)} $$
である($\mu$ は Möbius関数)。

$a_n:=1$($n\in\mathcal A$)、$a_n:=0$(それ以外)とおくと $S(0)=\#\mathcal A=\|a\|^2$ である。平方因子をもたない $q\le Q$ の素因数はすべて $Q$ 以下なので、lem-ls-local と cor-ls-farey から $L\,(\#\mathcal A)^2\le\sum_{q\le Q}\mu^2(q)\sum_a\lvert S(a/q)\rvert^2\le(N-1+Q^2)\#\mathcal A$ である。$\square$

Mon78 p. 561 はこの評価を定数 $N+Q^2$ で述べ、Montgomery によるとし、Selberg の篩で得られる評価に匹敵すると注意している。$\omega(p)$ が大きいほど $L$ が大きくなり評価が強くなる。これが「大きな」篩の名の由来である(Mon78 p. 561)。

応用

短い区間の素数の個数の上界

$N\ge N_0$ について、区間 $(M,M+N]$ の素数の個数は
$$ \frac{2N}{\log N}\Bigl(1+O\Bigl(\frac{\log\log N}{\log N}\Bigr)\Bigr) $$
以下である($O$ の定数は $M$ によらない)。

$Q\ge2$ とし、$\mathcal A$ を区間の素数のうち $Q$ より大きいものとする。$\mathcal A$ は各素数 $p\le Q$ の剰余類 $0$ と交わらないので $\omega(p)=1$ で thm-ls-sieve が使え、$L=\sum_{q\le Q}\mu^2(q)/\varphi(q)$ である。平方因子をもたない $q$ について $\frac1{\varphi(q)}=\prod_{p\mid q}\sum_{k\ge1}p^{-k}$ は、素因数の集合がちょうど $q$ の素因数の集合である $n$ にわたる $\frac1n$ の和である。$n\le Q$ の素因数の積は $Q$ 以下なので、$L\ge\sum_{n\le Q}\frac1n\ge\log Q$ である。区間の素数で $Q$ 以下のものは $Q$ 個以下なので、素数の個数は $\frac{N+Q^2}{\log Q}+Q$ 以下である。$Q=N^{1/2}/\log N$ とおくと $\log Q=\frac12\log N-\log\log N$ で、主張を得る。$\square$

これは Brun–Titchmarshの不等式 の $q=1$ の場合にあたり、法 $q$ の等差数列への拡張も同じ方法で得られる(Mon78 p. 561)。Mon78 p. 561 によれば、Montgomery と Vaughan は大篩の変種を使って $O$ の項を取り除き、区間の素数の個数が $2N/\log N$ 以下であることを示した。

平方数の個数

$\mathcal A$ を $N$ 以下の平方数の集合とし、区間を $(0,N]$、$Q=\lfloor N^{1/2}\rfloor$ とする。$\omega(2)=0$ とし、奇素数 $p$ について平方数は法 $p$ の 平方非剰余 の $\frac{p-1}2$ 個の類に入らないので $\omega(p)=\frac{p-1}2$、$\frac{\omega(p)}{p-\omega(p)}=\frac{p-1}{p+1}\ge\frac12$ である。$L$ の素数 $q=p$ の項だけを残すと $L\ge\frac12(\pi(Q)-1)$($\pi$ は 素数計数関数)で、thm-ls-sieve から
$$ \#\mathcal A\le\frac{4N}{\pi(N^{1/2})-1}\ll N^{1/2}\log N $$
である(素数定理 を使った)。実際の個数は $\lfloor N^{1/2}\rfloor$ なので、損失は $\log N$ の因子だけである。$\omega(p)$ が有界という前提で組み立てる Brunの篩 や Selbergの篩 は、このように法 $p$ の半分の類を落とす場面には向かない(Bom87 §1 の例 3, pp. 6–7)。

大篩の最初の応用は、Linnik による平方非剰余の分布についての主張である。

Linnik の応用を開く

Bom87 Théorème 2(p. 7):任意の $\varepsilon>0$ について、最小の平方非剰余が $N^\varepsilon$ より大きいような素数 $p\le N$ の個数は、$\varepsilon$ だけによる定数で抑えられる。証明は、$N^\varepsilon$ 以下の素因数しかもたない $N$ 以下の整数(その個数は $N$ の定数倍以上ある)が、例外の素数 $p$ を法としてすべて平方剰余になることを使い、ex-ls-squares と同じく $\omega(p)=\frac{p-1}2$ の篩に持ち込む(同 pp. 7–8)。


乗法的な形。 Gauss和 で既約分数の点を Dirichlet指標 に移すと、原始指標についての和
$$ \sum_{q\le Q}\frac q{\varphi(q)}\sum_{\chi\ \text{原始的}}\Bigl\lvert\sum_na_n\chi(n)\Bigr\rvert^2\le(N-1+Q^2)\|a\|^2 $$
が cor-ls-farey から従う(Mon78 p. 561)。導き方と、2 つの数列の積の形の和への使い方は Bombieri–Vinogradovの定理 にある。この形は Dirichlet $L$ 関数の零点の個数の評価(零点密度評価の L 関数版)にも使われる(Bom87 §10, pp. 76–77)。

注意

成り立つこと外す条件反例成り立たなくなること
$\Delta(N,\delta)\le N-1+\delta^{-1}$点が $\delta$ だけ離れている同じ点 $\alpha$ を $R$ 回とり $a_n=e(-n\alpha)$左辺は $RN^2$ で、$R\to\infty$ で $(N-1+\delta^{-1})N$ を超える
定数を $N-1+\delta^{-1}$ より小さくできないなし(最良)ex-ls-equality等号
cor-ls-farey分母を $Q$ 以下に制限する$N=1$、$a_1=1$ とし、分母が $Q'\,(>Q)$ 以下の既約分数をすべて足す左辺は既約分数の個数 $\sum_{q\le Q'}\varphi(q)$ で、$Q'\to\infty$ で右辺 $Q^2$ を超える

1 行目は、定数が点の個数 $R$ によらないために間隔の仮定が欠かせないことを示す。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する