インテジャーズ

INTEGERS

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

90:Moserの定理

90\varphi (n) = \pi (n)が成り立つような最大の整数です。ここで、\varphi (n)はEulerのトーシェント関数であり、\pi (x)は素数個数関数。実際、\varphi (90)=\pi (90)=24が成り立ちます。\varphi (n) = \pi (n)が成り立つようなn2, 3, 4, 8, 10, 14, 20, 90の8つあります。

この記事ではMoserによって1951年に証明された次の定理のSannaによる証明(2012年)を紹介します:

Moserの定理 n \geq 91ならば \varphi (n) > \pi (n)が成り立つ。

Bonseの不等式

n番目の素数は、例によってp_nと表しましょう。Moserの定理の証明には30:この数の持つ或る性質 - INTEGERSで証明したBonseの不等式を用います:

Bonseの不等式 k \geq 4ならば p_{k+1}^2 < p_1\cdots p_k が成り立つ。

T_n(x)の評価

整数n\geq 2および実数x \geq 0に対して、T_n(x)を「x以下の整数であって、nと互いに素であるようなもの全体のなす集合」とします。このとき、次のようにT_n(x)を下から評価できます。ただし、\omega (n)前回の記事で導入した数論的関数です。

補題 \ \ \displaystyle \#T_n(x) \geq \frac{x}{\omega (n)+1}-2^{\omega (n)-1}.

証明. 包含原理によって

\displaystyle \# T_n(x) = \sum_{d \mid n}\mu (d)\left[ \frac{x}{d}\right]

が成り立つ。ここで、\mu (d)はMöbius関数(例えば、n=p^aq^b (p, qは相異なる素数で、a, bは自然数)のときは、

T_n(x) = [ x ] - \#\{ x以下のpの倍数\}- \#\{ x以下のqの倍数\}+\#\{x以下のpqの倍数\}

である。なお、最初の式においてx=nを考えると

\displaystyle \varphi (n) = \sum_{d\mid n}\mu (d)\frac{n}{d} -①

となる*1 )。よって、

\displaystyle \#T_n(x) = x\sum_{d \mid n}\frac{\mu (d)}{d} - \sum_{d \mid n}\mu(d)\left\{ \frac{x}{d} \right\} \geq x\sum_{d \mid n}\frac{\mu (d)}{d}-\sum_{d \mid n, \ \mu (d) =1}1

を得る。第二項は\mathrm{prime}(n)から偶数個の素因数を選ぶ場合の数に他ならないため、\varepsilon_n\omega (n)が偶数か奇数かに応じて0または1と定めるとき、

\displaystyle \sum_{d \mid n, \ \mu (d) =1}1 = \binom{\omega (n)}{0} + \binom{\omega (n)}{2} + \cdots + \binom{\omega (n)}{\omega (n)-\varepsilon_n} = 2^{\omega (n)-1}

と計算できる。第一項については①を適用することにより、

\displaystyle \#T_n(x) \geq x\frac{\varphi (n)}{n} - 2^{\omega (n)-1}

が示された。ここで、

\displaystyle \frac{\varphi (n)}{n} = \prod_{p \in \mathrm{prime}(n)}\frac{p-1}{p} \geq \prod_{i=2}^{\omega (n)+1}\frac{i-1}{i} = \frac{1}{\omega (n)+1}

と評価できる。最後の等号は"望遠鏡積"である*2。以上により、所望の不等式評価が得られた。 Q.E.D.

証明

n \geq 2のtotativesを素数か素数でないかによって分ける:

T_n(n) = (T_n(n) \cap \mathbb{P}) \sqcup (T_n(n) \setminus \mathbb{P}).

ただし、\mathbb{P}は素数全体のなす集合。第一項については\#(T_n(n) \cap \mathbb{P}) = \pi (n) - \omega (n)である。
p^{(n)}nを割り切らない最小の素数とする(30:この数の持つ或る性質 - INTEGERSで言及したように、n \geq 3ならばp^{(n)} < nである)。写像

T_n(n/p^{(n)})\setminus \{ 1\} \to T_n(n) \setminus \mathbb{P}

m \mapsto mp^{(n)}

により定めると、これは明らかに単射である(m \in T_n(n/p^{(n)})ならばmp^{(n)} \leq nであり、mp^{(n)}nと互いに素な合成数である。よって、mp^{(n)} \in T_n(n)\setminus \mathbb{P}となって、写像がwell-definedであることが分かる)。よって、補題より

\displaystyle \#(T_n(n) \setminus \mathbb{P}) \geq \#(T_n(n/p^{(n)})) - 1 \geq \frac{n}{p^{(n)}}(\omega (n) + 1) - 2^{\omega (n)-1} - 1

と第二項を評価できる。すなわち、

\displaystyle \varphi (n) - \pi (n) = \frac{n}{p^{(n)}(\omega (n)+1)}-2^{\omega (n)-1}-\omega (n) -1 -②

が得られた。p_kk番目の素数、p_k\#素数階乗を表す記号とする。

p_k\# \leq n < p_{k+1}\#を満たすようなkが一意的に決まるので、そのようなkk^{(n)}と書く。このとき、次の主張が成立する:

主張 n \geq 716ならば \displaystyle \frac{n}{p^{(n)}} > (2^{k^{(n)}-1}+k^{(n)}+1)(k^{(n)}+1) が成り立つ。

まず、k^{(n)} \leq 6のときに直接確認することによって証明する。R(k^{(n)}) := (2^{k^{(n)}-1}+k^{(n)}+1)(k^{(n)}+1)とするとき、

R(1) < R(2) < R(3) < R(4) = 65, R(5) = 132, R(6) = 273

であり、

\displaystyle \frac{n}{p^{(n)}} \geq L(k^{(n)}) := \frac{\max \{716, p_{k^{(n)}}\#\}}{p_{k^{(n)}+1}}

に対して、

L(1) > L(2) > L(3) > L(4) = 65.09\cdots, L(5) = 177.69\cdots, L(6) = 1766,47\cdots

なので、k^{(n)} \leq 6に対してL(k^{(n)}) > R(k^{(n)})が確認できた。

k^{(n)} \geq 7の場合は、p^{(n)} \leq p_{k^{(n)}+1}、Bonseの不等式、p_7 > 2^4k^{(n)}+1 \leq 2^{k^{(n)}-4}により、

\begin{equation}\begin{split}\frac{n}{p^{(n)}} &\geq \frac{p_{k^{(n)}}\#}{p_{k^{(n)}+1}} > \sqrt{p_{k^{(n)}}\#} \geq \sqrt{p_6\#}\cdot 2^{4(k^{(n)}-6)} \\ &> 2^{4(k^{(n)}-6)+7} \geq 9\cdot 2^{2(k^{(n)}-4)} = (2^{k^{(n)}-1}+2^{k^{(n)}-4})\cdot 2^{k^{(n)}-4} \\ &\geq (2^{k^{(n)}-1}+k^{(n)}+1)(k^{(n)}+1)\end{split}\end{equation}

を得る。以上で主張が証明された。k^{(n)}の取り方より\omega (n) \leq k^{(n)}が成り立つので、

\displaystyle \frac{n}{p^{(n)}} > (2^{k^{(n)}-1}+k^{(n)}+1)(k^{(n)}+1) \geq (2^{\omega (n)-1}+\omega (n)+1)(\omega (n) +1).

従って、②と合わせることによって\varphi (n) > \pi (n)が証明された。n716未満の場合は直接確認を行うことによって、境界がn=90であることがわかる。Q.E.D.

*1:関係式\displaystyle \sum_{d \mid n}\varphi (d) = nにMöbius関数の反転公式(その一)を適用しても得られる。

*2:望遠鏡和については integers.hatenablog.com を参照してください。望遠鏡積という言葉は勝手に付けましたが、どんどん使っていきましょう笑。