インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

ブルンの篩

Brunの定理を証明するためにBrunの篩を必要な分に限定してまとめます。Eratosthenesの篩についてはWikipediaの記事 エラトステネスの篩 - Wikipedia
の「理論的考察」の項をご覧ください。Brunの篩の方が変数が増えており、自由度が増していることがわかります。

記号

数論的関数およびMöbius関数\mu (n)については
integers.hatenablog.com
を、素数個数関数\pi (x)については
integers.hatenablog.com
を、\omega (n)については
integers.hatenablog.com
を、素数階乗x\#については
integers.hatenablog.com
を参照せよ。

注意: ここでは、実数xに対して x\#x以下の素数の積として定義しています。が、素数階乗という言葉を一般の実数に対して使う習慣はどうやらないようで、執筆者が誤解しておりました。時間が出来次第、表記を修正いたします。

x \in \mathbb{R}, S \subset \mathbb{R}に対し、

\displaystyle S_{\leq x} := \{ a \in S \mid a \leq x \}
のような記号を用いる。

和や積の記号に現れるpは素数を表す。

数論的関数\delta (n)

\displaystyle \delta (n) := \begin{cases}1 & n=1 \\ 0 & \text{otherwise}\end{cases}
で定める。

\mathrm{gcd}(n, m)nmの最大公約数。

数論的関数f(n)乗法的であるとは、f(nm)=f(n)f(m)が任意の互いに素な自然数のペア(n, m)に対して成立するときにいう。

データ

  • \mathcal{A}\mathbb{N}_0の部分集合
  • x, y:実変数、n:自然数変数、s:自然数
  • \displaystyle \chi^{(2s)}(n) := \begin{cases}1 & \omega (n) \leq 2s \ \text{かつ} \ d\text{:square-free} \\ 0 & \text{otherwise} \end{cases}
  • \displaystyle \sigma^{(2s)}(n) := \sum_{d \mid n}\mu (d)\chi^{(2s)}(d)
  • \displaystyle S(\mathcal{A}; y\#, x) := \sum_{m \in \mathcal{A} \leq x}\delta (\mathrm{gcd}(m, y\#))
  • w(n)0 \leq w(n) \leq nなる乗法的な数論的関数
  • R_d(x)xに関する関数({}^{\forall}d \in \mathbb{N}
  • \displaystyle \mathcal{M}(y) := \prod_{p \leq y}\left( 1 -\frac{w(p)}{p} \right)
  • \displaystyle \rho(n) := \frac{w(n)}{n\prod_{p \mid n}\left( 1-\frac{w(p)}{p}\right)}(これは乗法的)
  • \displaystyle \mathcal{A}_d := \{ a \in \mathcal{A} \mid a \equiv 0 \pmod{d} \}{}^{\forall}d \in \mathbb{N}

仮定

(Hyp1) \ \ \ \displaystyle \# \mathcal{A}_{d, \leq x} = \frac{w(d)}{d}x+R_d(x) \ ({}^{\forall}d \in \mathbb{N})

(Hyp2) \ \ \ \displaystyle |R_d(x)| \leq w(d) ({}^{\forall}d \in \mathbb{N})

\chiを数論的関数とする。

(Hyp(\chi)) \ \ \ \displaystyle \delta (n) \leq \sigma_{\chi} (n) := \sum_{d \mid n}\mu (d)\chi (d)

Brunの篩

命題 (Hyp1), (Hyp(\chi))を仮定する。このとき、
\displaystyle S(\mathcal{A}; y\#, x) \leq x \mathcal{M}(y)\left( 1+\sum_{d \mid y\#, d > 1}\sigma_{\chi}(d)\rho (d) \right) + \sum_{d \mid y\#}|\chi (d)||R_d(x)|.

証明.

\begin{equation}\begin{split}S(\mathcal{A}; y\#, x) &= \sum_{m \in \mathcal{A}_{\leq x}}\delta (\mathrm{gcd}(m, y\#)) \\ &\leq \sum_{m \in \mathcal{A}_{\leq x}}\sigma_{\chi}(\mathrm{gcd}(m, y\#)) \\ &= \sum_{m \in \mathcal{A}_{\leq  x}}\sum_{d \mid \mathrm{gcd}(m, y\#)}\mu (d)\chi (d) \\ &= \sum_{d \mid y\#}\mu (d)\chi (d)\left( \sum_{m \in \mathcal{A}_{\leq x}, d\mid m}1 \right) \\ &= \sum_{d \mid y\#}\mu (d)\chi (d) \# \mathcal{A}_{d, \leq x} \\ &= \sum_{d \mid y\#}\mu (d)\chi (d) \left( \frac{w(d)}{d}x+R_d(x) \right) \\ &= x\sum_{d \mid y\#}\mu (d)\chi (d)\frac{w(d)}{d} + \sum_{d \mid y\#}\mu (d)\chi (d)R_d(x) \end{split}\end{equation}

と変形できるが、

\displaystyle \sum_{d \mid y\#}\mu (d)\chi (d) R_d(x) \leq \sum_{d \mid y\#}|\chi (d)||R_d(x)|

であるから、最初の項を評価すればよい。Möbiusの反転公式より

\begin{equation}\begin{split}x\sum_{d \mid y\#}\mu (d)\chi (d)\frac{w(d)}{d} &= x\sum_{d \mid y\#}\frac{w(d)}{d} \left( \sum_{d' \mid d}\mu \left( \frac{d}{d'} \right)\sigma_{\chi}(d') \right) \\ &= x\sum_{d' \mid y\#}\frac{\sigma_{\chi}(d')w(d')}{d'}\left( \sum_{d'' \mid \frac{y\#}{d'}}\mu (d'')\frac{w(d'')}{d''} \right) \\ &= x\sum_{d' \mid y\#}\sigma_{\chi} (d')\frac{w(d')}{d'}\prod_{p \mid \frac{y\#}{d'}}\left( 1 -\frac{w(p)}{p} \right) \\ &= x\mathcal{M}(y) \sum_{d' \mid y\#}\sigma_{\chi}(d')\frac{w(d')}{d'\prod_{p \mid d'}\left( 1-\frac{w(p)}{p}\right)} \\ &= x\mathcal{M}(y)\sum_{d' \mid y\#}\sigma_{\chi}(d')\rho (d') \\ &= x\mathcal{M}(y)\left( 1+\sum_{d' \mid y\#, d' > 1}\sigma_{\chi}(d')\rho (d') \right). \end{split}\end{equation}
Q.E.D.

補題1 非負整数kおよび自然数nに対して
\displaystyle \sum_{i=0}^k(-1)^i\binom{n}{i} = (-1)^k\binom{n-1}{k}
が成り立つ。

証明.

\displaystyle \text{L.H.S.} = 1+\sum_{i=1}^k(-1)^i\left\{ \binom{n-1}{i}+\binom{n-1}{i-1} \right\}
と変形できるので、望遠鏡和によって右辺に一致することが分かる。 Q.E.D.
望遠鏡和については
integers.hatenablog.com
を参照せよ。

補題2 (Hyp(\chi^{(2s)}))が成立する。

証明. \delta (n) \leq \sigma^{(2s)}(n)が示すべきことである。n=1のときは両辺ともに1なので成立。n > 1のときは

\begin{equation}\begin{split}\sigma^{(2s)}(n) &= \sum_{d \mid n}\mu (d)\chi^{(2s)}(d) \\ &= \sum_{k=1}^{2s}(-1)^{k}\binom{\omega (n)}{k} \ \text{(補題1より)}\\ &=  (-1)^{2s}\binom{\omega (n)-1}{2s} \\ &\geq 0 = \delta (n)\end{split}\end{equation}
となる。 Q.E.D.

補題3 自然数rに対して
\displaystyle \sum_{n=r}^{\infty}\binom{n}{r}\frac{x^n}{n!} = \frac{x^r}{r!}e^x
が成り立つ。

証明.

\displaystyle \text{L.H.S.} = \sum_{n=r}^{\infty}\frac{n!}{r!(n-r)!}\frac{x^r}{n!} = \frac{x^r}{r!}\sum_{n=r}^{\infty}\frac{x^{n-r}}{(n-r)!} = \text{R.H.S.}
Q.E.D.

定理 (Hyp1), (Hyp2)を仮定する。このとき、
\displaystyle {\small S(\mathcal{A}; y\#, x) \leq x\mathcal{M}(y)\left\{ 1+\frac{1}{(2s)!}\left( \sum_{p \leq y}\rho (p) \right)^{2s}\exp \left( \sum_{p \leq y}\rho (p) \right) \right\} + \left( 1+\sum_{p \leq y}w(p) \right)^{2s}.}

証明. 補題2より\chi^{(2s)}に関する命題が成立する。その右辺の二つの部分をそれぞれ評価する。

\displaystyle \sigma^{(2s)}(n) = \binom{\omega (n)-1}{2s} \leq \binom{\omega (n)}{2s}
なので、

\begin{equation}\begin{split} \sum_{d \mid y\#, d > 1}\sigma^{(2s)}(d)\rho (d) &\leq \sum_{d \mid y\#, d > 1}\binom{\omega (n)}{2s}\rho (d) \\ &= \sum_{2s \leq m \leq \pi (y)}\binom{m}{2s} \sum_{\substack{d \mid y\#, d > 1 \\ \omega (d) = m}}\rho (d) \\ &\leq \sum_{2s \leq m}\binom{m}{2s}\frac{1}{m!}\left( \sum_{p \leq y}\rho (p) \right)^m \\ &= \frac{1}{(2s)!}\left( \sum_{p \leq y}\rho (p) \right)^{2s}\exp \left( \sum_{p \leq y}\rho (p) \right) \end{split}\end{equation}

を得る。また、Hyp2および\chi^{(2s)}の定義から

\displaystyle \sum_{d \mid y\#}|\chi^{(2s)}(d)||R_d(x)| \leq \sum_{d \mid y\#, \omega (d) \leq 2s}w(d) \leq \left( 1+ \sum_{p \leq y}w(p) \right)^{2s}

と評価できるので、証明が完了する。 Q.E.D.