2016-09-28

昨夜、次の問題がTwitterのTLで話題になっていました。

この前気になった「連続する二数の二乗和が素数」となり隣接するもの(例 1201と1301)を調べてみたら結構たくさんあった。なんか法則性あるかな？
— miyamo (@DMiyamo3) 2016年9月26日

(続き)
1,2,3のとき
1^2+2^2=5, 2^2+3^2=13
から
99,100,101のとき
19801, 20201(計算略)
までで8個ある。中心の数を書き出すと、
2, 5, 25, 30, 35, 70, 85, 100, ...
2以外は5の倍数。なんで？
— miyamo (@DMiyamo3) 2016年9月26日

この問題に興味がある方は挑戦してみてください(大学入試問題に出来る程度の難易度？)。

この記事では $n^2+(n+1)^2$ が素数になることと三角数のとある関係性(Sierpińskiの定理)を紹介したいと思います。

三角数 $\displaystyle T_n=\frac{n(n+1)}{2}$ に関して最近書いた記事としては
integers.hatenablog.com
があります(幾つかの数値が掲載されています)。

次が紹介したい定理です：

定理 (Sierpiński) $n^2+(n+1)^2$ が合成数であることと、或る自然数 $m, l$ が存在して

$T_n=T_m+T_l$

が成り立つことは同値である。

例えば、 $T_8=36, \ T_{10}=55, \ T_{13}=91$ なので

$T_{13}=T_{8}+T_{10}$

が成り立ちますが、

$13^2+14^2=169+196=365$

は確かに合成数です。

一方、 $T_{19}=190$ は(先ほどの数値表を眺めれば分かるように)二つの三角数の和として表すことはできず、

$19^2+20^2=761$

は確かに素数になっています。

互いに素な二平方和に関する定理

integers.hatenablog.com
において、「自然数が二つの平方数の和として表されるための必要十分条件はその自然数の素因数分解に現れる $4n+3$ 型素数の指数が全て偶数であること」を証明しました*1。

実は、「二つの平方数が互いに素である」という条件を課した場合についても精密な定理が知られています：

定理自然数が二つの互いに素な平方数の和として表されるための必要十分条件は、その自然数が奇数または単偶数( $4$ で割れないような偶数)であり、 $4n+3$ 型の素因数を持たないことである。更に、自然数 $N$ がその条件を満たすとき、 $N=a^2+b^2$ ( $a, b$ は互いに素な整数)と書き表す方法の場合の数を $\rho_2(N)$ とすると、 $\rho_2(N)=2^{t+2}$ が成り立つ。ただし、 $t$ は $N$ の $4n+1$ 型素因数の個数を表す。

例えば、 $25=5^2$ の場合にチェックしてみましょう。先の記事で紹介したJacobiの定理を用いると $r_2(25)=12$ となり*2、実際

$25=0^2+(\pm 5)^2=(\pm 5)^2+0^2=(\pm 3)^2+(\pm 4)^2=(\pm 4)^2+(\pm 3)^2$

の $12$ 通りの二平方和としての表示があることが分かりますが、互いに素という条件をつけると

$25=(\pm 4)^2+(\pm 7)^2=(\pm 7)^2+(\pm 4)^2$

の $8$ 通りになり、上記定理から導かれる $\rho_2(25)=2^{1+2}=8$ に合致します。

この定理の証明はそれなりの準備が必要なので、ここでは紹介しません。将来的に書けると嬉しいですが、とりあえずNiven-Zuckerman-Montgomeryの"An introduction to the theory of numbers"の§3.6を参考文献としてあげておきます。

Sierpińskiの定理の証明

$f(n)=n^2+(n+1)^2$ とおく。

$f(n)=p$ が素数のとき

$T_n=T_m+T_l$ なる自然数 $m, l$ が存在したと仮定して矛盾を導く。 $m \geq l$ と仮定してよい。このとき

$\displaystyle \frac{n(n+1)}{2}=\frac{m(m+1)}{2}+\frac{l(l+1)}{2}$

であり、

$p=n^2+(n+1)^2 = (m-l)^2+(m+l+1)^2$ ー①

と変形できる。素数 $p$ が二平方和として表されているので $p$ は $4n+1$ 型であるが、そのような素数を二平方和として表す方法は本質的に*3一通りのはずである。

しかしながら、①の後者の表現については $(m+l+1)-(m-l)=2l+1 > 1$ と二数の差が $1$ より大なので、前者の表現とは相異なる。これは矛盾である。

$f(n)=N$ が合成数のとき

次の主張を示す：

主張 $2N$ は或る奇数 $u, v$ (ただし、ともに $3$ 以上)を用いて、 $2N=u^2+v^2$ と表すことができる。

$N$ を互いに素な二つの平方数の和として表す方法が本質的に二通り以上存在する場合:
一つは

$N=n^2+(n+1)^2$

であり、それとは異なる互いに素な二平方和としての表示を

$N=a^2+b^2$

とする( $a, b$ は互いに素(或いは $N$ が奇数)なので、 $b > a$ としてよい)。このとき、差 $b-a$ は $1$ ではないので、 $b-a > 1$ である。従って、

$2N=(b-a)^2+(a+b)^2$

が主張を示している。というのも、 $N$ は奇数なので $a, b$ のパリティは異なり、 $b-a$ および $a+b$ はともに $3$ 以上の奇数となるからである。

$N$ を互いに素な二つの平方数の和として表す方法が本質的に一通りの場合:
これは前節の定理を用いれば、 $4n+1$ 型の素数 $p$ および自然数 $e$ を用いて $N=p^e$ と表される場合であることが分かる(本質的に一通り $\Longleftrightarrow \rho_2(N)=8$ であることに注意)。今、 $N$ は合成数なので $e \geq 2$ である。

$e$ が偶数の場合:
$e=2e'$ とおくと、

$2N=2p^{2e'}=(p^{e'})^2+(p^{e'})^2$

より主張が成立する。

$e$ が奇数の場合:
$e=2e'+1$ とおく( $e' \geq 1$ )。 $p$ は $4n+1$ 型素数なので

$p=a^2+b^2$

と二平方和で表すことができる( $a, b$ は自然数。 $b > a$ としてよい)。 $p$ は奇数なので、 $a, b$ のパリティは異なる。このとき、

$2N=2p^e= (p^{e'}(b-a) )^2+(p^{e'}(a+b) )^2$

より主張が成立する( $b-a=1$ の可能性はあるのであって、 $e' \geq 1$ が重要)。

以上で、主張が証明された( $N$ の定義から $N$ を互いに素な二つの平方数の和として表す方法は少なくとも一通りはあることに注意せよ)。

すると、自然数 $m, l$ が存在して $u=2m+1, \ v=2l+1$ と書ける。このとき、 $2N=u^2+v^2$ は

$2(n^2+(n+1)^2)=(2m+1)^2+(2l+1)^2$

と表され、変形すると

$T_n=T_m+T_l$

が得られる。 Q.E.D.

*1:平方数には $0$ を含みます。また、 $1$ の素因数分解は全ての素数に対する指数が $0$ と考えることにします。そうすると、 $1$ も $0^2+1^2$ などと二つの平方数の和として表されることに矛盾しません。

*2: $4n+1$ 型の約数の個数から $4n+3$ 型の約数を引いて $4$ 倍する。この場合、 $4n+3$ 型の約数はなく、 $4n+1$ 型の約数は $1, 5, 25$ の $3$ 個である。

*3:符号や順番の違いを除いての意。

Eulerの五角数定理

$\displaystyle \prod_{n=1}^{\infty}(1-x^n) = \sum_{m=-\infty}^{\infty}(-1)^mx^{\frac{m(3m+1)}{2}} = 1+\sum_{m=1}^{\infty}(-1)^m \left\{ x^{\frac{m(3m-1)}{2}}+x^{\frac{m(3m+1)}{2}} \right\}$

は非常に美しい定理です。収束半径は $1$ ですが、形式的冪級数の等式と考えるのがよいでしょう。

この定理は過去の記事で一度使ったことがあります：
integers.hatenablog.com

Eulerの五角数定理より偉い定理であるJacobiの三重積というものがあって
integers.hatenablog.com
integers.hatenablog.com
で既にお世話になっていますが、

Jacobiの三重積からEulerの五角数定理が得られることは
tsujimotter.hatenablog.com
で解説されています。

しかしながら、当然EulerはJacobiの三重積の前に五角数定理を証明していますし、Franklinによる組合せ論的な証明も知られています。

この記事では、Shanksによる代数計算に基づいた比較的簡明なる直接証明を紹介したいと思います。

Shanksの証明

$\begin{align}P_n &:=\prod_{k=1}^n(1-x^k)\\ S_n&:=1+\sum_{m=1}^n(-1)^m \left\{ x^{\frac{m(3m-1)}{2}}+x^{\frac{m(3m+1)}{2}} \right\}\\ Q_n&:=\sum_{k=0}^n(-1)^k\frac{P_n}{P_k}x^{kn+\frac{k(k+1)}{2}}\end{align}$

とおく( $P_0:=1$ )。このとき、

$S_n=Q_n$

が任意の自然数 $n$ に対して成立することを証明する。

$n \geq 1$ に対して $P_n=P_{n-1}-x^nP_{n-1}$ が成り立つので、

$\begin{align} Q_n &= \sum_{k=0}^{n-1}(-1)^k\frac{P_n}{P_k}x^{kn+\frac{k(k+1)}{2}} + (-1)^nx^{n^2+\frac{n(n+1)}{2}} \\ &= \sum_{k=0}^{n-1}(-1)^k\frac{P_{n-1}}{P_k}x^{kn+\frac{k(k+1)}{2}} + \sum_{j=0}^{n-1}(-1)^{j+1}x^n\frac{P_{n-1}}{P_j}x^{jn+\frac{j(j+1)}{2}} +(-1)^nx^{\frac{n(3n+1)}{2}}\end{align}$

と変形できる。次に、二つ目の和を次のように変形する：

$\displaystyle \sum_{j=0}^{n-1}(-1)^{j+1}x^n\frac{P_{n-1}}{P_j}x^{jn+\frac{j(j+1)}{2}}= \sum_{k=1}^{n-1}(-1)^kx^n\frac{P_{n-1}}{P_{k-1}}x^{(k-1)n+\frac{k(k-1)}{2}} + (-1)^nx^n\cdot x^{n(n-1)+\frac{n(n-1)}{2}}$

$\displaystyle \frac{1}{P_{k-1}}=\frac{1-x^k}{P_k}$ より、

$\begin{align}\sum_{j=0}^{n-1}(-1)^{j+1}x^n\frac{P_{n-1}}{P_j}x^{jn+\frac{j(j+1)}{2}}&= \sum_{k=1}^{n-1}(-1)^k(1-x^k)\frac{P_{n-1}}{P_k}x^{kn+\frac{k(k-1)}{2}}+(-1)^nx^{\frac{n(3n-1)}{2}}\\ &=\sum_{k=1}^{n-1}(-1)^k\frac{P_{n-1}}{P_k}x^{k(n-1)+\frac{k(k+1)}{2}}-\sum_{k=1}^{n-1}(-1)^k\frac{P_{n-1}}{P_k}x^{kn+\frac{k(k+1)}{2}}+(-1)^nx^{\frac{n(3n-1)}{2}}.\end{align}$

最初の変形と合わせると、

$\displaystyle Q_n=\sum_{k=0}^{n-1}(-1)^k\frac{P_{n-1}}{P_k}x^{k(n-1)+\frac{k(k+1)}{2}}+(-1)^n\left\{ x^{\frac{n(3n-1)}{2}}+x^{\frac{n(3n+1)}{2}}\right\}$

を得る。これは、

$Q_n-Q_{n-1} = S_n - S_{n-1}$

を意味する。

$S_1=1-(x+x^2)=(1-x)-x^2=Q_1$

なので、結局 $S_n=Q_n$ が示された。

すると、任意の自然数 $n$ に対して

$Q_n \equiv P_n \pmod{x^{n+1}}$

なので、

$S_n \equiv P_n \pmod{x^{n+1}}$

が成り立ち、これは五角数定理を意味する。 Q.E.D.

INTEGERS

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

n^2+(n+1)^2に関するシェルピンスキーの定理

互いに素な二平方和に関する定理

Sierpińskiの定理の証明

$f(n)=p$ が素数のとき

$f(n)=N$ が合成数のとき

オイラーの五角数定理の証明

Shanksの証明