インテジャーズ

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

インテジャーズ

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

孙智伟さんによる新作定理

定理解説

\pi(x)x以下の素数の個数、p_nn番目の素数とします。

p_{13}=41, \ p_{14}=43, \ p_{15}=47なので

\pi (5\times 9)=5+9

\pi(6\times 7)=6+7

が成り立ちます。

また、8\times 998=7984, \ p_{1006}=7963, \ p_{1007}=7993より

\pi(8\times 998)=8+998

が成り立ちます。

こういったものは数遊びですが、次のようにまとめると数学の定理らしくなります:

定理1 m5以上の整数とする。このとき、或る正の整数nが存在して
\pi(mn)=m+n
が成り立つ。

この面白い定理は今年になってからRamanujan Journalに出版された孙智伟さんの新作論文において証明されています。実際には、先日紹介したGolombの定理
integers.hatenablog.com

を一般化するという方向性の研究を行うことによって定理1を導出します。

定理2 mを正の整数とする。集合S_m
\displaystyle S_m := \left\{ a \in \mathbb{Z} \ \left| \ \pi(n)=\frac{n+a}{m}, \quad ({}^{\exists} n \in \mathbb{Z}_{> 1})\right\} \right.
と定義し、整数S(m)
S(m):=\underset{k \in \mathbb{Z}_{> 0}}{\max} \{km-p_k\}
によって定める。このとき、
S_m=\{a \in \mathbb{Z} \mid a \leq S(m)\}
が成り立つ。

m \geq 2ならばS(m) \geq m-p_1 \geq 0となるので、定理2を認めれば0 \in S_mとなってGolombの定理が導出されることがわかります。

証明. a \in S_mを任意に取る。このとき、或るn > 1が存在して

\displaystyle k:= \pi (n) = \frac{n+a}{m}

が成り立つ。n \geq p_kなので、

a=km-n \leq km-p_k \leq S(m)

となって片方の包含関係が成り立つことがわかった。

次に、a \leq S(m)なる整数を任意に取る。a \in S_mを示せばよい。ここで、非負整数kに対してm元集合I_k

I_k := \{km-p_{k+1}+1, \dots, km-p_{k+1}+m=(k+1)m-p_{k+1}\}

と定義する。\displaystyle a \in \bigcup_{k=0}^{\infty}I_k であるか \displaystyle a \not \in \bigcup_{k=0}^{\infty}I_k であるかによって、場合分けを行って証明する。

例えば素数定理によって\displaystyle \lim_{k \to \infty}(km-p_k)=-\inftyであり、定義からすぐわかるように

\min I_{k+1} \leq \max I_k

である。従って、数直線上で整数点のみを考えた際、I_kに対してI_{k+1}が右へ移動する際は隙間は発生しない。I_kの移動でたどり着ける最大の整数はS(m)であり、kが大きくなるとI_kはどんどん左の方へシフトしていく。左へ移動する際にはギャップがあっても構わない。

\displaystyle a \not \in \bigcup_{k=0}^{\infty}I_kである場合を考える。このとき、上記考察より、或るkが存在して\max I_{k+1} < a < \min I_kが成立する。n:=(k+1)m-aとすれば

p_{k+1}+m-1 < n < p_{k+2}-m

が得られる。すると、

\displaystyle \pi (n) = k+1 = \frac{n+a}{m}

なのでa \in S_mである。

次に\displaystyle a \in \bigcup_{k=0}^{\infty}I_kである場合を考えよう。このとき、或るkが存在して、a \in I_kが成り立つ。すなわち、或る1-p_{k+1} \leq r \leq m-p_{k+1}なるrを用いてa=km+rと書ける。

或るn \geq p_{k+1}が存在して

\displaystyle \frac{n+r}{\pi (n)-k}=m ー①

が成り立つことを示す。これを示すことができれば、

\displaystyle \pi(n)=k+\frac{n+r}{m}=\frac{n+a}{m}

となって、a \in S_mが結論づけられる。

r=m-p_{k+1}のときは

\displaystyle \frac{p_{k+1}+r}{\pi(p_{k+1})-k} = p_{k+1}+r=m

なので、n=p_{k+1}に対して①が成立する。そこで、m > p_{k+1}+rと仮定する。\displaystyle \lim_{x \to \infty}\frac{\pi(x)}{x}=0より

\displaystyle \lim_{n \to \infty}\frac{n+r}{\pi(n)-k}=\infty

であるため、

\displaystyle \frac{n+r}{\pi(n)-k} \geq m

を満たすp_{k+1}以上の整数nとして、最小のものを取ることができる。n=p_{k+1}とすればp_{k+1}+r \geq mとなって今の状況に反するため、n-1 \geq p_{k+1}が成り立つ。すると、nに対する最小性から

\displaystyle \frac{n+r}{\pi(n)-k}\geq m > \frac{(n-1)+r}{\pi(n-1)-k} ー②

が成り立つ。s=n-1+rt=\pi(n-1)-kとおく。n-1 \geq p_{k+1}よりt \geq 1である。さて、

\begin{align} s-t&=n-1+r-(\pi(n-1)-k) \\ &\geq n-1+(1-p_{k+1})-\pi(n-1)+k\\
&=(n-1-p_{k+1})-(\pi(n-1)-\pi(p_{k+1})) \\ &= \#\{p_{k+1} < d \leq n-1 \mid d\text{は合成数}\}\end{align}

と評価できる。つまり、s-tはある集合の元の個数以上なのでs\geq tであることがわかった。

もしnが素数であれば、\pi(n)=\pi(n-1)+1であるため、

\displaystyle \frac{n+r}{\pi(n)-k}=\frac{s+1}{t+1} \leq \frac{s}{t} = \frac{n-1+r}{\pi(n-1)-k}

となって、②に矛盾する。従ってnは合成数であり、②より

n+r \geq m(\pi(n)-k)=m(\pi(n-1)-k) > n-1+r

と評価できる。これはn+r=m(\pi(n)-k)、すなわち①が成立することを意味する。 Q.E.D.

こうして定理2が証明できましたが、気になるのはS(m)がどのような数かということです。それについても例えば次のような定理が示されています:

定理3 m3以上の整数とし、S(m)を定理2で定義された整数とする。このとき、
\displaystyle \frac{e^{m-1}}{m-1} < S(m) < (m-1)e^{m+1}
が成り立つ。

S(m)は素数の分布に関係する量ですが、証明にはRosser-Schoenfeld, Dusartの結果を用います。これらは素数定理のように緩いものではなく、p_nのしっかりとした不等式評価を与えるという研究で、コンピュータを用いて知られているRiemannゼータ関数の零点の情報を総動員して示すというタイプのもののため、とてもじゃないですがここでは証明をフォローすることはできません。彼らの結果は認めることにします。

証明. Dusartの結果により、k \geq 2ならば

p_k \geq k(\log k+\log \log k-1)

が成り立つので、k > e^{m+1}であれば

km-p_k \leq k(m-\log (k\log k) + 1) < 0

となる。従って、S(m)=km-p_kを実現するk[e^{m+1}]以下である。km-p_k < (m-1)kであることと合わせると

S(m) < (m-1)e^{m+1}

が得られた。あとは\displaystyle j:=\left[ \frac{e^{m-1}}{m-1}\right] < S(m)を示せばよい。

m=3ならばj=3 < 3\times 3-p_3 \leq S(3)である。従って、m \geq 4とする。このとき、j \geq 6なので、Rosser-Schoenfeld-Dusartの結果により

p_j \leq j(\log j+\log \log j)

が成り立つ。jの定め方から

\displaystyle \log j \leq \log \frac{e^{m-1}}{m-1}=m-1-\log (m-1) < m-1

なので、

\displaystyle jm-p_j \geq j(m-\log j)-j\log \log j > j(1+\log (m-1))-j\log (m-1)=j

と評価できる。これはj < S(m)を示している。 Q.E.D.

定理2と定理3を合わせることによって、その系として冒頭の定理1が証明されます:

定理1の証明. m=5, 6は実例を冒頭に述べた。そこで、m \geq 7とする。このとき、

\displaystyle m^2 < \frac{e^{m-1}}{m-1}

が成り立つ。よって、定理2・定理3より或る2以上の整数Nが存在して

\displaystyle \pi(N) = \frac{N+m^2}{m}=\frac{N}{m}+m

が成り立つ。この式からN/mは正の整数であることが従う。よって、n=N/mとすれば

\pi(mn)=n+m

となる。 Q.E.D.

エマーパイムス

15 115

今日は1月15日

1番目のエマーパイムス15です。115もエマーパイムスです。

イチゴを食べたくなってきました。今、スターバックスでチョコラティ バナナ ココ フラペチーノを飲んでいますが。

エマーパイムス

エマーパイムスとは何か。それは、"emirpimes"をさっき私が発音してみて、更にカタカナにしてみたものです。発音があっているかは知りません。

素数の並びを反対にしても素数になるようなもの(ただし、回文素数は除く)をエマープと言うのでした:
integers.hatenablog.com

名前の由来は素数を英語にした"prime"を反対から読むと"emirp"になるからです。

次に、半素数を思い出しましょう:
integers.hatenablog.com

314=2\times 157のように二つの素数の積として表されるものが半素数でした。半素数は英語で"semiprime"です。

もう、おわかりですね?

そう、反対から読んでも半素数になるような半素数(ただし、元の半素数とは異なる)をsemiprimeを反対から読んでemirpimesと呼ぶのです。中国語のサイトで可逆半素數としているものもありました。

15=3\times 5, \quad 51=3\times 17

115=5\times 23, \quad 511= 7\times 73

となっているので、15115はエマーパイムスだとわかります。

ちなみに100番目の半素数314もエマーパイムスです(413=7\times59)。

551蓬莱なんかは素数でなくて全国民が悲しんだことと思われますが、大丈夫。
エマーパイムスです。

551=19\times 29, \quad 155= 5\times 31


1000以下のエマーパイムスは次の通り:

\begin{align}&15, 26, 39, 49, 51, 58, 62, 85, 93, 94, 115, 122, 123, 129, 143, 155, 158, 159, 169, 177,\\ 
&178, 183, 185, 187, 203, 205, 221, 226, 265, 289, 302, 314, 319, 321, 326, 327, 329, 335, \\
&339, 341, 355, 381, 394, 398, 413, 415, 437, 493, 497, 502, 511, 514, 533, 538, 551, 553, \\
&559, 562, 581, 586, 589, 622, 623, 629, 667, 685, 718, 723, 734, 766, 771, 781, 794, 817, \\
&835, 851, 871, 893, 899, 913, 921, 923, 926, 933, 951, 955, 961, 982, 985, 998\end{align}



なお、勢い余って「イチゴゴゴゴ...」となっても、155555555555555とちゃんと15桁で止めると

\begin{align}&155555555555555=5\times 31111111111111\\ &555555555555551=229\times 2426006792819\end{align}

とエマーパイムスになります。

Golombの定理

定理解説

素数個数関数\pi (x)に関するGolombの定理を紹介します。

証明に使うのは\displaystyle \lim_{x \to \infty}\frac{\pi(x)}{x}=0 –①のみです。これは素数定理から出ますが、素数定理を用いることなく初等的に導出できる点には注意しておきます。Golomb曰く、Eulerが既に示していたとのことです。Euler先生は何でもやってます。p_nn番目の素数を表します。

定理 (Golomb, 1962) m2以上の任意の整数とする。このとき、或る2以上の整数nが存在して、n\pi(n)の丁度m倍になる。

証明. 2以上の整数mを固定して、nの存在を示す。①より、kが十分大きければ

\displaystyle \frac{\pi(p_k)}{p_k} < \frac{1}{m}

となり、\displaystyle \frac{\pi (2)}{2} = \frac{1}{2} \geq \frac{1}{m}なので、

\displaystyle \frac{\pi(p_k)}{p_k} \geq \frac{1}{m}

が成り立つような最大の整数kが存在する。それをKとしよう。このとき、mK < p_{K+1}が成り立つ。というのも、もしmK \geq p_{K+1}であったと仮定すると、

\displaystyle \frac{\pi(p_{K+1})}{p_{K+1}} = \frac{K+1}{p_{K+1}} > \frac{K}{mK}=\frac{1}{m}

となってKの最大性に反するからである。よって、mK < p_{K+1}であり、Kの取り方からp_K \leq mKなので

\pi(p_K) \leq \pi (mK) < \pi(p_{K+1})

を得る。これは\pi(mK)=Kを意味し、

\displaystyle \frac{mK}{\pi(mK)} = m

が成り立つ。すなわち、n=mKと取れる。 Q.E.D.