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

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

http://stagnationpoint-y.tumblr.com/post/168336222377/prime-knot-912-150mm-150mm-%E9%89%9B%E7%AD%86-%E3%82%A2%E3%82%AF%E3%83%AA%E3%83%AB%E7%B5%B5%E5%85%B7-%E3%82%B1%E3%83%B3%E3%83%88%E7%B4%99-%E4%BA%A4%E7%82%B9%E6%95%B09

stagnationpoint-y.tumblr.com

でした。

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

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

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

定理１ 正整数 $n$ に対して、 $T(n)$ を $k(k-1), \ (k=1, 2, \dots, n)$ が $\bmod{m}$ でどの二つをとっても相異なる値となるような最小の $2$ 以上の整数 $m$ と定義する。このとき、 $T(n)$ は $2n-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。

定理の証明

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

$m \geq 2n-1.$
$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)$ が相異なる値を取るようなものがあったとして固定する。

補題１ 任意の奇素数 $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.

補題２ 任意の奇素数 $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.

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

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

を満たすようにとる。ここで、 $(2, q)$ は $2$ と $q$ の最大公約数を表す。 $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$

であるが、 $p$ と $q$ がともに $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$ として選べるので、この議論により $m$ は $3$ より大きい素因数を二つ以上もてないことがわかる。すると残るケースは $m=pq$ ( $p$ は $3$ より大きい素数で $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.

命題２ $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. $m$ が $2$ の冪乗であって、 $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-k$ と $l+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]$ は必ず素数を含む。

補題３ 任意の正整数 $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. より $2n-1 \leq T(n)$ がわかる。残るは $S(n) \leq 2.4n$ であるが、 $n < 13$ の場合は直接計算で確かめられる。 $n \geq 13$ のとき、奇素数 $p \in [2n-1, 2.4n]$ をとる。命題２の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.

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