インテジャーズ

INTEGERS

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

孙智伟による素数表現関数

この記事は日曜数学 Advent Calendar 2017 - Adventarの10日目の記事です。9日目はru_sackさんによる

http://stagnationpoint-y.tumblr.com/post/168336222377/prime-knot-912-150mm-150mm-鉛筆-アクリル絵具-ケント紙-交点数9
stagnationpoint-y.tumblr.com

でした。

今日は中国人数学者孙智伟(Zhi Wei Sun)による素数を表現する関数に関する定理および予想を紹介します。

みなさんの数学への思いや日曜数学の成果・興味がある数学トピックなどについて自由にお話しください。
面白さを読者が共感できるように「自分はなぜそのトピックを面白いと思ったのか」を熱く書いてもらえると嬉しいです。

素数表現関数です。自明に熱く面白いので、多くの方に読んでいただけますと嬉しいです。

定理1 正整数nに対して、T(n)k(k-1), \ (k=1, 2, \dots, n)\bmod{m}でどの二つをとっても相異なる値となるような最小の2以上の整数mと定義する。このとき、T(n)2n-2より大きい「素数または2の冪乗」のうち最小のものである。

定理2 正整数nに対して、S(n)2k(k-1), \ (k=1, 2, \dots, n)\bmod{m}でどの二つをとっても相異なる値となるような最小の2以上の整数mと定義する。このとき、S(n)2n-2より大きい素数のうち最小のものである。特に、S\colon \mathbb{N} \to \mathbb{N}素数表現関数である*1

定理の証明

命題1 m, n \geq 2k(k-1), \ (k=1, \dots, n)\bmod{m}で相異なる値をとるような整数とする。このとき、次が成り立つ。

  1. m \geq 2n-1.
  2. n \geq 15かつm \leq 2.4nならばmは素数であるか2の冪乗である。

証明. 1. の証明: m \leq 2n-2と仮定する。このとき、n \geq m/2+1に注意する。mが偶数ならば

\displaystyle \left(\frac{m}{2}+1\right)\left(\frac{m}{2}+1-1\right)-\frac{m}{2}\left(\frac{m}{2}-1\right) = m \equiv 0 \pmod{m}

となって矛盾する。mが奇数のときは、n \geq \frac{m+3}{2}なので

\displaystyle \frac{m+3}{2}\left(\frac{m+3}{2}-1\right)-\frac{m-1}{2}\left(\frac{m-1}{2}-1\right) = 2m \equiv 0 \pmod{m}

となってこの場合も矛盾する。2. の証明は準備が必要なので少し後で証明する。 Q.E.D.

n \geq 15, m \in [2n-1, 2.4n]なる整数n, mであって、k(k-1) \bmod{m}, \ (k=1, \dots, n)が相異なる値を取るようなものがあったとして固定する。

補題1 任意の奇素数pに対して、m \neq 2pである。

証明. m=2pとする。このとき、

\displaystyle \frac{p+3}{2}\left(\frac{p+3}{2}-1\right) - \frac{p-1}{2}\left(\frac{p-1}{2}-1\right) = 2p \equiv 0 \pmod{2p}

が成り立つので、\frac{p+3}{2} > nでなければならない。すると、2n-1 \leq p=m/2 \leq 1.2nとなるが、このような不等式は今の状況では成り立ち得ない。 Q.E.D.

補題2 任意の奇素数pに対して、p^2 \nmid mである。

証明. m=p^2qと書けたと仮定する(pは奇素数でqは正整数)。k=\frac{p+1}{2}, \ l=k+pq \leq 2pqとおく。このとき、

\displaystyle l(l-1)-k(k-1)=(l-k)(l+k-1)=pq(pq+2k-1) \equiv 0 \pmod{p^2q}

なので、2pq \geq l > nでなければならない。p > 3ならば

\displaystyle n < \frac{2m}{p} \leq \frac{2}{5}m \leq \frac{2}{5}\cdot 2.4n < n

となって矛盾する。また、p=3のときは

\displaystyle n < l=2+3q=2+\frac{m}{3} \leq 2 + 0.8n \leq n

で矛盾する(n \geq 15に注意)。 Q.E.D.

命題1の2. の証明. n \geq 15, m \leq 2.4nとする。mが素数でも2の冪乗でもないと仮定して矛盾を導く。補題1、2よりm=pq (pは奇素数でq > 2pで割れない)と仮定してよいことがわかる。k \in [1, \frac{q}{(2, q)}]

\displaystyle k \equiv \frac{1-p}{2} \pmod{\frac{q}{(2, q)}}

を満たすようにとる。ここで、(2, q)2qの最大公約数を表す。l=k+pとおく。このとき、

l(l-1)-k(k-1) = p(2k-1+p) \equiv 0 \pmod{pq}

が成り立つので、n < lでなければならない。qが偶数であると仮定すると、q \geq 4であり、

\displaystyle l \leq p+\frac{q}{2} = \frac{m}{q}+\frac{m}{2p} \leq \frac{m}{4}+\frac{m}{6} = \frac{5}{12}m \leq \frac{5}{12} \cdot 2.4n = n

となって矛盾するので、qは奇数である。

\displaystyle l \leq p+q = \frac{m}{p}+\frac{m}{q} \leq \left(\frac{1}{p}+\frac{1}{q}\right)\cdot 2.4n

であるが、pqがともに3より大きければ

\displaystyle \frac{1}{p}+\frac{1}{q} \leq \frac{2}{5} < \frac{5}{12}

なので、

\displaystyle l < \frac{5}{12} \cdot 2.4n = n

となって矛盾する。さて、mの任意の素因数をpとして選べるので、この議論によりm3より大きい素因数を二つ以上もてないことがわかる。すると残るケースはm=pq (p3より大きい素数でq=3)の場合のみとなった。このとき、

\displaystyle l \leq p+q = \frac{m}{3}+3 \leq \frac{2.4n}{3}+3=0.8n+3 \leq n

となって、結局矛盾する(n \geq 15に注意)。 Q.E.D.

命題2 n > 1, m \geq 2n-1とする。
1. mが素数または2の冪乗であるとする。このとき、任意のk, l \ (1 \leq k < l \leq n)に対して
k(k-1) \not \equiv l(l-1) \pmod{m}
が成り立つ。
2. m2の冪乗であって、m \leq 2.4nを満たすとする。このとき、或るk, l \ (1 \leq k < l \leq n)が存在して
2k(k-1) \equiv 2l(l-1) \pmod{m}
が成り立つ。

証明. 1. の証明: m=2^aとする(aは正整数)。n \leq \frac{m+1}{2} = 2^{a-1}+\frac{1}{2}よりn \leq 2^{a-1}である。任意の1 \leq k < l \leq nに対して0 < l-k < n \leq 2^{a-1}, 0 < l+k-1 < 2n \leq 2^aであることより

l(l-1)-k(k-1) = (l-k)(l+k-1) \not \equiv 0 \pmod{2^a}

がわかる(l-kl+k-1のパリティが異なることに注意)。次に、m=p (pは奇素数)とする。任意の1 \leq k < l\leq nに対して0 < l-k < n \leq \frac{p+1}{2} < p, 0 < l+k-1 < 2n-1 \leq pであることより

l(l-1)-k(k-1) = (l-k)(l+k-1) \not \equiv 0 \pmod{p}

である。2. の証明: 2k(k-1) \equiv 0 \pmod{4}が任意のk=1, \dots, nに対して成り立つので、m=2^a \ (a > 2)と仮定してよい。k=2^{a-2}, l=k+1とする。このとき、

2l(l-1)-2k(k-1) =2^a \equiv 0 \pmod{2^a}

が成り立つ。k < l = 2^{a-2}+1 < \frac{2^a}{2.4} \leq nであるから、証明が完了する。 Q.E.D.

Bertrandの仮説の拡張に関する研究は膨大であるが、次の事実を証明なしに用いることにする。

事実 13以上の整数nに対して、区間[2n-1, 2.4n]は必ず素数を含む。

補題3 任意の正整数nに対して、2n-1 \leq T(n) \leq S(n) \leq 2.4nが成り立つ。

証明. S(1)=T(1)=2より、n=1のときは正しいことがわかる。n \geq 2とする。2k(k-1) \ (k=1, \dots, n)\bmod{S(n)}で相異なる値をとるならば、k(k-1) \bmod{S(n)} \ (k=1, \dots, n)もそうなので、S(n) \geq T(n)であることがわかる。また、命題1の1. より2n-1 \leq T(n)がわかる。残るはS(n) \leq 2.4nであるが、n < 13の場合は直接計算で確かめられる。n \geq 13のとき、奇素数p \in [2n-1, 2.4n]をとる。命題2の1. より

k(k-1) \not \equiv l(l-1) \pmod{p}

が任意の1 \leq k < l \leq nに対して成り立つが、これは

2k(k-1) \not \equiv 2l(l-1) \pmod{p}

と同値であることに注意すると、S(n) \leq p \leq 2.4nが成り立つことがわかる。 Q.E.D.

定理1、2の証明. n=1, \dots, 14については直接確認できる。n \geq 15とする。補題3よりT(n) \in [2n-1, 2.4n]であるから、命題1の2. よりT(n)は素数または2の冪乗であることがわかる。そして、命題2の1. よりT(n)2n-2より大きい素数または2の冪乗のうち最小の整数であることが従う。同様に、補題3よりS(n) \in [2n-1, 2.4n]であり、命題1の2. および命題2の2. からS(n)は素数であることがわかる。命題2の1. よりS(n)2n-2より大きい最小の素数であることが従う。 Q.E.D.

関連する極めて興味深い予想

予想 正整数nに対して、s(n)を中心二項係数\binom{2n}{n} \ (k=1, \dots, n)\bmod{m}でどの二つをとっても相異なる値となるような最小の2以上の整数mと定義する。このとき、s(1), s(2), \dotsは全て素数であろう!

s(n)は素数表現関数と予想されています(しかも全ての素数を返すわけではない)。

\begin{align}&s(1)=2, \ s(2)=3, \ s(3)=5, \ s(4)=s(5)=s(6)=11, \ s(7)=s(8) = s(9)=23, \ s(10)=31, \dots, \\ &s(1983)=\cdots =s(2064) = 242519\end{align}

などなど。

日曜数学 Advent Calendar 2017 11日目の記事はPaya_payashiさんによる「芸術/自然と数学について紹介します。」です。

追記

定理2には「事実」を使う代わりにBertrandの仮説だけで十分な数学的帰納法を使ったより短い証明が存在することを飛鳥さんと彼のご友人に教えていただきました。

*1:だけでなく、全ての素数を表現する。