2018-12-18

限定素数大富豪

素数大富豪

この記事は素数大富豪Advent Calendarの16日目の記事です。

adventar.org

おかげさまで私が考案したトランプゲーム『素数大富豪』は忘れ去られることなく、今もプレイヤーを増やし続けながら盛り上がっていると実感します。素数大富豪を愛する皆様に本当に感謝しています。

素数大富豪の研究が進むと色々と見えてくることがあり、例えば先手がかなり有利なゲームのようです。そこで、マモさんは先手有利を軽減するための遊び方を提言してくださっております。

先手有利を軽減するプレイ方法の紹介 - まもめも

他にも、ルール自体をある程度変更した素数大富豪で遊ぶことを提言してくださっている方もおられます。ruia_primeさんのb進素数大富豪やicqk3さんのガウス素数大富豪などがあります。

この記事では私も新しい素数大富豪の遊び方を一つ提案しようと思います。その名も『限定素数大富豪』。

発想の経緯

オリジナルの素数大富豪の発想の経緯は

integers.hatenablog.com

に書きました。また、最近になって梟老堂さんの『素数大富豪Lv. 0』が販売されました。

まずはこれらのゲームの分析を行いたいと思います。

素数大富豪は大富豪をベースとして考案されたゲームですが、出来上がったゲームはゲーム進行の型に限っても大富豪とは異なる要素を幾つか含んでいます(山札の存在や複数枚出しにおける十進法読みなど)。このようなゲームの型に基づいたゲームを『素数大富豪型ゲーム』と呼ぶことにしましょう。つまり、『素数大富豪型ゲーム』というトランプゲームの分類を新たに作り、素数大富豪と素数大富豪Lv. 0はともに素数大富豪型ゲームに属すというわけです。

素数大富豪は『素数大富豪型ゲーム』であって、更に『素数の暗記・博打要素』を持ったゲームとなっています。これは『素数コレクター』になるという新しい楽しみも生み出しました。大きい素数を知っているほどゲームに有利になるため、暗記が得意な人や素数大富豪で勝てるようになりたい人はどんどん大きい素数を覚えていっており、大会上位のプレイヤーは既に7枚出し以上を標準装備しつつあります(素数の暗記要素)。また、必ずしも勝つことにはこだわらないが、大きい素数と出会い、面白い語呂合わせを発見することを喜びとするような人々も現れました(素数の博打(=出会い)要素)。

一方で、暗記は基本的にはゲーム中に行うことではないため、(手札の引きが運なのは大富豪型である以上仕方ないですが、与えられた手札を用いてどういう戦略を取るかという)純粋な頭脳戦として遊ぼうと思ったときにたくさん暗記している人とそうでない人の間に大きな格差が生まれてしまいます。 $1001$ チェックなどの特殊な戦略があってそれはそれで面白いのですが、暗記格差が大きいとあまり有効ではありません。この辺の悩みはもりしーさんの記事にも書かれています。(多くの人間がそうだと思いますが)暗記が苦手な人にとっては、たとえ戦略を立てるのが上手であったとしても、素数大富豪はあまり強くなれないゲームとなってしまいます。

このようなある種のデメリットがありながら、素数大富豪のルールをこのようにデザインした理由は『ゲームで扱える素数の個数』が非常に多いことに多大なる魅力を感じたためです。素数好きとしてこの点で素数大富豪のルールに満足し、ゲーム性におけるデメリットの排除は必要に応じて素数大富豪の派生を作っていただければよいと判断しました。

素数大富豪Lv. 0はそうして作られた派生ゲームと見ることができます。『素数大富豪型ゲーム』でありながら、プレイヤー間格差を少なくするために『素数の暗記・博打要素』を著しく減らすことに成功しています。他にも素数大富豪はトランプゲームなので偶数が手札にたくさんあると初心者のうちは捌きにくいといった問題がありましたが、素数大富豪Lv. 0はカードの枚数も調整されています。また、カードデザインもとても素晴らしいです。ですが、ここでは『素数の暗記・博打要素』がどのように変更されたかをもう少し詳しく見ていきます。

『素数の暗記要素』は『ゲームで扱える素数の個数』を単純に減らすことによって実現されています。素数大富豪Lv. 0では基本的には一枚出しか二枚出ししかできず、カードの特殊効果で三枚出しを一部許しています。三枚出しができる場合も各カードが一桁でなければならないという制限を設けることによって三桁を超えることがありません(この制限がなければ三枚出しで六桁まで可能になってしまう)。ちなみに素数大富豪Lv. 0で出せる最大の素数は $1913$ です。一方で、扱える素数の個数が少なくても例えば三桁の素数を全て覚えている人は多くないでしょうから暗記要素(という素数大富豪の一つの楽しさ)が完全になくなったわけではありません。

『素数の博打要素』は『素数の暗記要素』が減ったことによって連動して減っています。また、各カードにヒントが書いてあるので更に減ります。それでも、ヒントが奇数である場合は「右からつけるのか」・「左からつけるのか」という運要素があります。このように博打要素(という素数大富豪の一つの楽しさ)も完全になくなったわけではありません。ちなみに素数大富豪では $n$ 枚出しで間違えると $n$ 枚手札が増えるというペナルティがありました。エゴサなどしているとこの点についてもっといい方法があったのではという指摘をよく見ます。ペナルティといいつつ手札を増やす戦略にもなりますし、オリジナルのルールは現行のままでよいと考えていますが、初心者向けにはペナルティを一律一枚とするというケースもよくあってペナルティが少なくてもゲームは可能です。素数大富豪Lv. 0では思い切ってペナルティなしとなっています(なお、10のカードがペナルティの特殊効果を持っている)。

素数大富豪Lv. 0はこのように『素数の暗記・博打要素』を減らしたゲームになっていますが、そのことによって『素数大富豪型ゲーム』の戦略性の部分が際立っています。なので、素数大富豪の持つ独特なフレイバーを味わいつつ対戦ゲームとして十分に楽しめる仕上がりになっていると感じます。

素数大富豪Lv. 0はもちろん素数コレクターには物足りないものとなっていますが、それは『素数の暗記・博打要素』のもつデメリットを減らすために作られたゲームである以上仕方のないことですし、『Lv. 0』は初心者向けなので、そこから興味を持っていただいた方には素数大富豪を遊んでもらうというのが本来の目的の一つでもあります。

素数大富豪Lv. 0をやってみて、私は『素数大富豪型ゲーム』のもつ戦略ゲーとしての面白さを再認識しました。素数大富豪は素数を暗記したらそれで最強というわけではありません。暗記の度合いによってプレイヤー間格差は生じますが、暗記レベルが同じプライヤー同士の戦いにおいては『戦略』も非常に重要になります。というのも、与えられた手札に対して組める素数は一般にたくさんあるので、どれが最善の出し方であるかを短時間で判断するのはとても頭を使うのです。

一方で、素数大富豪Lv. 0は三枚出しまでしかできないために、素数大富豪の『素数大富豪型ゲーム』としての面白さが一部失われているとも言えます。そこで私は次のような欲求に駆られました。

『素数の暗記・博打要素』をなくし『素数大富豪型ゲーム』の戦略性を著しく際立たせた頭脳ゲームでありながら、にもかかわらず『ゲームで扱える素数の個数』は膨大である

ようなゲームを作りたい。12/10の朝にこのように思って電車の中で考えたのが『限定素数大富豪』です。副産物的ゲーム要素としてトレーディングカードゲームが持つコレクト要素やデッキ構築の楽しみのような要素があると思っています。

ルール

前置きが長くなってしまいましたが、テストプレイができていないので細かい調整ができていません(申し訳ございません)。なので、ここではゲームのアイデアだけを述べさせていただきます。

大きな特徴：各対戦毎に出すことのできる数の集合 $S$ を用意する。

集合 $S$ は三毎出し以上で出せる素数 $N$ 個と合成数出しで出すことの出来る合成数とその素因数分解データの組 $M$ 個からなります。( $N$ と $M$ は調整次第としますが、例えば $N=50$ や $M=10$ はどうでしょう*1。)

各プレイヤーは $S$ の元が書かれた紙(または画面)を手元に置いてそれを参照しながらプレイします。基本的には素数大富豪と同じルールですが、カードの出し方を次のように変更します。

二枚出し以下とラマヌジャン革命については変更なし。
それ以外の数については $S$ に書かれている数しか(成立手としては)出せない。

カードの大きさと枚数は正しいが上記以外の出し方で場にカードを出した場合はとりあえずペナルティとしておきましょう(手札を増やしたい場面があると思うので)。

ルールは以上です。 $S$ の作り方としては例えば次のようなものが考えられると思います。

各プレイヤー $i$ が集合 $S_i$ を用意し、 $S:=\bigcup_iS_i$ とする。
二人対戦の場合、 $S$ は後手が用意する。
$S$ をランダム生成するプログラムを用意する。

1. 2. の場合、素数コレクト要素やTCGのデッキ構築の楽しみがあると思います。2. は先手有利を軽減できるかもしれません。また、『限定素数大富豪』には $S$ を作成する面倒がありますが、3. が出来ればそれはかなり軽減できるでしょう。

基本的な数を除いて出せる数が $S$ に制限されることから『限定』素数大富豪という名前にしました。付けた後にカイジの『限定ジャンケン』の存在を思い出しました。
また、合成数出しという特殊ルールを忘れた上で、 $S$ を素数に限定しなければ『ランダム大富豪』のようなゲームも作ることは出来ます。

*1:桁を増やすレベルでもっと多い方がいいかもしれません。また、「 $A$ 枚出し以下では少なくとも $B$ 組以上ずつ」というな調整も必要でしょう( $QK$ のような強さを持つものが量産されかねないため)。下の1. による方法で $S$ を定める場合は「 $B$ 組未満ならばそれらは棄却」のようにしてもいいかもしれません。

2018-12-14

置換の符号に関する相互法則

好きな証明

これは鯵坂もっちょ氏企画のAdvent Calendarの十二番目の記事です。

adventar.org

幾つかの置換を考えて、その符号を考察します。以下、置換およびその符号についての基礎知識を仮定します。

高校数学の美しい物語で読むことができる記事としては

mathtrain.jp

などがあります。必要となる基本事項を幾つか列挙しておきます。

少なくとも二元をもつ全順序有限集合 $X$ を考えて、 $X$ 上の置換のなす群を $S_X$ と表す。
$\sigma \in S_X$ の符号 $\mathrm{sign}(\sigma)$ は $(-1)^{N(\sigma)}$ と定義される。ただし、 $N(\sigma)$ は $\sigma$ の転倒数*1。
$\mathrm{sign}\colon S_X \to \{\pm 1\}$ は準同型写像。つまり、 $\mathrm{sign}(\sigma\circ\tau)=\mathrm{sign}(\sigma)\mathrm{sign}(\tau)$ が成り立つ。
逆元について $\mathrm{sign}(\sigma)=\mathrm{sign}(\sigma^{-1})$ が成り立つ。
巡回置換 $(a_1, \dots, a_k)$ の符号は $(-1)^{k+1}$ である。

転置が引き起こす置換

$m, n$ をどちらか一方は $2$ 以上であるような正整数とし、集合 $X=\{1, 2, \dots, mn\}$ に或る全順序 ${<}_1$ が入っているとする(必ずしも通常の順序でなくてもよい)。 $X$ の元を小さい順に、最初の $n$ 個は左から右へ並べ、 $n+1$ 個目から $2n$ 個目までは次の行へ移ってまた左から右へと次々に並べ、 $(m\times n)$ -行列の形に並べる。

つまり、並べ終わった行列が $A=(a_{ij})_{1\leq i \leq m, 1\leq j \leq n}$ であったとすると、 $a_{ij} \ {<}_1 \ a_{kl}$ であるための必要十分条件は「 $i < k$ 」または「 $i=k$ かつ $j < l$ 」である(辞書式順序)。

この行列の転置行列を $B=(b_{ij})_{1\leq i \leq n, 1\leq j \leq m}$ とする。つまり、 $b_{ij}=a_{ji}$ が成り立つ。この $B$ の各成分を先ほどと同じルールで順序付ける。すなわち、 $b_{ij} \ {<}_2 \ b_{kl}$ を「 $i < k$ 」または「 $i=k$ かつ $j < l$ 」で定義する。

これは $X$ 上の別の全順序を定めており、 ${<}_1$ で小さい方から数えて $h$ 番目の数を ${<}_2$ で小さい方から数えて $h$ 番目の数に写すことによって $X$ 上の一つの置換が得られる。この置換 $t_{mn}^{{<}_1} \in S_X$ を転置が引き起こす置換と呼ぶことにしよう。

以上のように文章で表現すると分かりづらいかもしれないが、具体例を見れば簡単である。

$m=3, n=4$ , $X=\{1, 2, \dots, 12\}$ で

$\displaystyle 11 \ {<}_1 \ 2 \ {<}_1 \ 5 \ {<}_1 \ 7 \ {<}_1 \ 10 \ {<}_1 \ 4 \ {<}_1 \ 9 \ {<}_1 \ 8 \ {<}_1 \ 6 \ {<}_1 \ 3 \ {<}_1 \ 1 \ {<}_1 \ 12$

と $X$ に全順序が入っていたとする。このとき、行列 $A$ は

$\displaystyle A=\begin{pmatrix} 11 & 2 & 5 & 7 \\ 10 & 4 & 9 & 8 \\ 6 & 3 & 1 & 12 \end{pmatrix}$

であり、その転置行列 $B$ は

$\displaystyle B=\begin{pmatrix} 11 & 10 & 6 \\ 2 & 4 & 3 \\ 5 & 9 & 1 \\ 7 & 8 & 12 \end{pmatrix}$

であるから、新しい全順序は

$\displaystyle 11 \ {<}_2 \ 10 \ {<}_2 \ 6 \ {<}_2 \ 2 \ {<}_2 \ 4 \ {<}_2 \ 3 \ {<}_2 \ 5 \ {<}_2 \ 9 \ {<}_2 \ 1 \ {<}_2 \ 7 \ {<}_2 \ 8 \ {<}_2 \ 12$

となる。よって、このときの転置が引き起こす置換は

$\displaystyle t_{34}^{{<}_1}=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ 8 & 10 & 7 & 3 & 6 & 1 & 2 & 9 & 5 & 4 & 11 & 12 \end{pmatrix}$

である。 $t_{34}^{{<}_1}=(1 \ 8 \ 9 \ 5 \ 6)(2 \ 10 \ 4 \ 3 \ 7)$ と巡回置換の積に分解できるので、基本事項の3.と5.より $\mathrm{sign}(t_{34}^{{<}_1})=1$ であることがわかる*2。

一般的に転置が引き起こす置換の符号は次のように決定することができる。全順序 $(X, {<}_1)$ および $(X, {<}_2)$ は $t_{mn}^{{<}_1}$ の定義のために用意したもので、符号の定義は通常の全順序 $(X, <)$ を固定して行っていることに注意。

命題１ $\mathrm{sign}(t_{mn}^{{<}_1})=(-1)^{\frac{m(m-1)}{2}\cdot\frac{n(n-1)}{2}}.$

$\mathrm{sign}(t_{34}^{{<}_1})=(-1)^{\frac{3(3-1)}{2}\cdot\frac{4(4-1)}{2}}=(-1)^{18}=1$ で上の例と矛盾していない。

証明. Step 1. $h$ を ${<}_1$ で小さい方から数えて $h$ 番目の数に写すような $X$ 上の置換を $\sigma$ とする。このとき、

$\displaystyle t_{mn}^{{<}_1}=\sigma \circ t_{mn}^{<} \circ \sigma^{-1}$

が成り立つ。

理由: $1\leq i \leq m, 1 \leq j \leq n$ を満たす $(i, j)$ に対して、

$(i-1)n+j = (k-1)m+l, \quad 1 \leq k \leq n, \ 1 \leq l \leq m$

を満たす $(k, l)$ が一意的に定まる。これは行列 $A$ において $a_{ij}$ が ${<}_1$ で小さい方から数えて $h$ 番目の数であるとき、行列 $B$ において ${<}_2$ で小さい方から数えて $h$ 番目の数が $b_{kl}$ であるということなので、

$t_{mn}^{{<}_1}(a_{ij})=b_{kl}$

が成り立つ。また、 $(X, < )$ に対して $(m\times n)$ -行列を作ったときの $(i,j)$ 成分は $(i-1)n+j$ なので、

$\begin{align}\sigma \circ t_{mn}^{<} \circ \sigma^{-1}(a_{ij}) &= \sigma \circ t_{mn}^{<} \circ \sigma^{-1}(\sigma( (i-1)n+j) ) \\ &= \sigma \circ t_{mn}^{<}( (i-1)n+j) \\ &= \sigma ( (l-1)n+k) = a_{lk} = b_{kl} = t_{mn}^{{<}_1}(a_{ij})\end{align}$

と計算できる。よって、基本事項3. 4.より

$\displaystyle \mathrm{sign}(t_{mn}^{{<}_1})=\mathrm{sign}(\sigma)\cdot\mathrm{sign}(t_{mn}^{<})\cdot\mathrm{sign}(\sigma^{-1})=\mathrm{sign}(t_{mn}^{<})$

なので、以下 $\ < \ = \ {<}_1$ であると仮定しても一般性を失わない*3。

Step 2. $h_1 < h_2$ であるにもかかわらず $h_2 \ {<}_2 \ h_1$ であるようなものの個数をカウントすればよい。 $h_1$ が $A$ の $(i,j)$ 成分の数であり、 $h_2$ が $(k,l)$ 成分の数であるとする*4。このとき、 $h_1$ は $B$ の $(j,i)$ 成分の数であり、 $h_2$ は $(l,k)$ 成分の数である。 $h_1 < h_2$ という条件は「 $i < k$ 」または「 $k=i$ かつ $j < l$ 」であるが、 $k=i$ であるときは $j < l$ であることから $B$ においては $h_1$ より $h_2$ が下の行にあって $h_1 \ {<}_2 \ h_2$ である。 $i < k$ であるような $(k,i)$ の組は $\binom{m}{2}$ 通りあるが、そのような $(k,i)$ を固定する毎に、 $h_2 \ {<}_2 \ h_1$ となるための必要十分条件は $l < j$ であり、そのような $(l,j)$ は $\binom{n}{2}$ 通りある。よって、 $t_{mn}^{<}$ による転倒の総数は

$\displaystyle \binom{m}{2}\binom{n}{2} = {\frac{m(m-1)}{2}\cdot\frac{n(n-1)}{2}}$

に等しい。 Q.E.D.

これもしっかりと書くと分かりづらいかもしれないが、やっていることは単純である。Step 1.では $X$ の通常の全順序に基づいて行列 $A$ を作った場合への帰着を行っている(共役を取るだけ)。 $t_{34}^{<}$ を考えると

$\displaystyle A=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \end{pmatrix}$

であり、その転置行列 $B$ は

$\displaystyle B=\begin{pmatrix} 1 & 5 & 9 \\ 2 & 6 & 10 \\ 3 & 7 & 11 \\ 4 & 8 & 12 \end{pmatrix}$

であるため、

$\displaystyle t_{34}^{<}=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ 1 & 5 & 9 & 2 & 6 & 10 & 3 & 7 & 11 & 4 & 8 & 12 \end{pmatrix}$

である。また、上の具体例の場合、

$\displaystyle \sigma=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ 11 & 2 & 5 & 7 & 10 & 4 & 9 & 8 & 6 & 3 & 1 & 12 \end{pmatrix}$

および

$\displaystyle \sigma^{-1}=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ 11 & 2 & 10 & 6 & 3 & 9 & 4 & 8 & 7 & 5 & 1 & 12 \end{pmatrix}$

なので、

$\displaystyle t_{34}^{{<}_1}=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ 8 & 10 & 7 & 3 & 6 & 1 & 2 & 9 & 5 & 4 & 11 & 12 \end{pmatrix}$

と見比べて $\displaystyle t_{34}^{{<}_1}=\sigma \circ t_{34}^{<} \circ \sigma^{-1}$ が確認できる。帰着されると、Step 2.ではBのみに着目して

f:id:integers:20181213171344p:plain:w300

という順序で数を並べたときに転倒している数を数えればよい。

f:id:integers:20181213181702p:plain:w300

のように左下と右上の関係にあるペアのときに転倒が起きており、そのようなペアは行の成分と列の成分をそれぞれ二つずつ選ぶ毎に得られるため、 $\binom{m}{2}\binom{n}{2}$ 個ある。

系 $m, n$ が奇数とする。このとき、 $\mathrm{sign}(t_{mn})=(-1)^{\frac{m-1}{2}\cdot\frac{n-1}{2}}$ が成り立つ。

証明. $m,n$ が奇数であれば $(-1)^{mn}=-1$ なので、命題１と指数法則からわかる。Q.E.D.

おや？

二つの置換

以下、 $m, n$ は互いに素な $3$ 以上の奇数とする。

Zolotareff記号

$R_n=\{0, 1, \dots, n-1\}$ を $\mathbb{Z}/n\mathbb{Z}$ の完全代表系として指定し、 $0 < 1 < \cdots < n-1$ という全順序を考える。 $n$ と互いに素な整数 $a$ に対して、 $R_n$ の元を $a$ 倍して $R_n$ における剰余を取る写像は $R_n$ 上の置換を与える。この置換 $\tau_a^{(n)}$ の符号を

$\displaystyle \left[\frac{a}{n}\right]:=\mathrm{sign}(\tau_a^{(n)})$

という記号で表す(ガウス記号ではない)。

置換 $\pi_m^{(n)}$ とその符号

集合 $Y=\{0,1,\dots, mn-1\}$ に通常の全順序 $0 < 1 < \cdots < mn-1$ を入れて $Y$ 上の置換 $\pi_m^{(n)}$ を以下のように定義する。まず、行列 $A$ を定義したときと同様の方法で $Y$ を並べかえて $(m\times n)$ -行列 $C$ を定義する。 $C$ の第一行は $R_n$ の元を小さい順に並べたものになっている。 $C$ の第一行に $\tau_m^{(n)}$ を施すことによって得られる $Y$ 上の置換を $\tau_{m, 1}^{(n)}$ と表す。一般に $1 \leq i \leq m$ に対して、 $C$ の第 $i$ 行は左から順に

$(i-1)n, \ (i-1)n+1, \dots, (i-1)n+n-1$

と並んでおり、これを

$(i-1)n+\tau_{m}^{(n)}(0), \ (i-1)n+\tau_{m}^{(n)}(1), \dots, (i-1)n+\tau_{m}^{(n)}(n-1)$

に置き換えることによって得られる $Y$ 上の置換を $\tau_{m, i}^{(n)}$ と表す。 $\tau_{m, i}^{(n)}$ は $\tau_m^{(n)}$ を $+(i-1)n$ だけ平行移動したものだから、転倒数は変わらない。すなわち、

$\displaystyle \mathrm{sign}(\tau_{m, i}^{(n)})=\left[\frac{m}{n}\right], \quad 1 \leq i \leq m$

が成り立つ。よって、 $\tilde{\tau}_m^{(n)}:=\tau_{m, m}^{(n)}\circ\cdots\circ\tau_{m, 2}^{(n)}\circ\tau_{m, 1}^{(n)} \in S_Y$ とすると

$\displaystyle \mathrm{sign}(\tilde{\tau}_{m}^{(n)})=\left[\frac{m}{n}\right]^m=\left[\frac{m}{n}\right]$

を得る( $m$ が奇数であることに注意)。 $C$ に $\tilde{\tau}_m^{(n)}$ を施して得られる行列を $D$ とする。 $1\leq j \leq n$ を固定し、 $D$ の第 $j$ 列を考察する。第 $j$ 列は上から下に

$\begin{align}&\tau_{m}^{(n)}(j-1) \\ &n+\tau_{m}^{(n)}(j-1) \\ &2n+\tau_{m}^{(n)}(j-1) \\ &\quad \dots \\ &(m-1)n+\tau_m^{(n)}(j-1)\end{align}$

と並んでいる。これらは法 $m$ の完全代表系をなす( $m, n$ は互いに素なので)。ここで、 $k=\left\lfloor \frac{m(j-1)}{n}\right\rfloor$ とおくと(これはガウス記号、整数部分) $\tau_m^{(n)}(j-1)=m(j-1)-nk$ であるが、 $0\leq j-1 < n$ なので $0 \leq \frac{m(j-1)}{n} < m$ であり、 $0 \leq k < m$ がわかる。以上の考察から、第 $j$ 列には $m(j-1)$ が丁度一つある。この $m(j-1)$ が第一行にくるように $D$ の第 $j$ 行を縦に巡回させる $Y$ 上の置換を $c_{m,j}^{(n)}$ と表す。これは $m$ 個の元の巡回置換の積であり、 $m$ は奇数でなので、基本事項5.より $c_{m, j}^{(n)}$ は偶置換である。以上の準備の元、置換 $\pi_m^{(n)} \in S_Y$ を

$\displaystyle \pi_m^{(n)}:=c_{m, n}^{(n)}\circ\cdots\circ c_{m, 2}^{(n)}\circ c_{m, 1}^{(n)}\circ\tilde{\tau}_{m}^{(n)}$

と定義する。今までの議論から $\pi_m^{(n)}$ の符号が決定されている：

命題２ $\displaystyle \mathrm{sign}(\pi_m^{(n)})=\left[\frac{m}{n}\right].$

具体例として、 $\pi_3^{(5)}$ を見てみよう。

$\displaystyle C=\begin{pmatrix} 0 & 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 & 9 \\ 10 & 11 & 12 & 13 & 14 \end{pmatrix}$

$\tau_{3, 1}^{(5)}$ を施すと

$\displaystyle \begin{pmatrix} 0 & 3 & 1 & 4 & 2 \\ 5 & 6 & 7 & 8 & 9 \\ 10 & 11 & 12 & 13 & 14 \end{pmatrix}$

続けて $\tau_{3, 2}^{(5)}, \tau_{3, 3}^{(5)}$ を施すと

$\displaystyle D= \begin{pmatrix} 0 & 3 & 1 & 4 & 2 \\ 5 & 8 & 6 & 9 & 7 \\ 10 & 13 & 11 & 14 & 12 \end{pmatrix}$

$c_{3, j}^{(5)} \ (1 \leq j \leq 5)$ を施すと

$\displaystyle E=\begin{pmatrix} 0 & 3 & 6 & 9 & 12 \\ 5 & 8 & 11 & 14 & 2 \\ 10 & 13 & 1 & 4 & 7 \end{pmatrix}$

となる。よって、

$\displaystyle \pi_{3}^{(5)} = \begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\ 0 & 3 & 6 & 9 & 12 & 5 & 8 & 11 & 14 & 2 & 10 & 13 & 1 & 4 & 7 \end{pmatrix}$

である。

$C$ に $\pi_m^{(n)}$ を施して得られる行列を $E$ とすると、構成から

$\displaystyle E \equiv \begin{pmatrix} 0 & m & 2m & \cdots & (n-1)m \\ n & n+m & n+2m & \cdots & n+(n-1)m \\ 2n & 2n+m & 2n+2m & \cdots & 2n+(n-1)m \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ (m-1)n & (m-1)n+m & (m-1)n+2m & \cdots & (m-1)n+(n-1)m \end{pmatrix} \pmod{mn}$

となっており、これは $m, n$ について対称的である。

Zolotareffの相互法則

$m$ と $n$ の役割を入れ替えることによって $\pi_n^{(m)} \in S_Y$ を定義することができる。 $m=3, n=5$ の場合の具体例を計算しよう。

$\displaystyle C'=\begin{pmatrix} 0 & 1 & 2 \\ 3 & 4 & 5 \\ 6 & 7 & 8 \\ 9 & 10 & 11 \\ 12 & 13 & 14 \end{pmatrix}$

$\tau_{5, 1}^{(3)}$ を施すと

$\displaystyle \begin{pmatrix} 0 & 2 & 1 \\ 3 & 4 & 5 \\ 6 & 7 & 8 \\ 9 & 10 & 11 \\ 12 & 13 & 14 \end{pmatrix}$

続けて $\tau_{5, 2}^{(3)}, \tau_{5, 3}^{(3)}, \tau_{5, 4}^{(3)}, \tau_{5, 5}^{(3)}$ を施すと

$\displaystyle D'= \begin{pmatrix} 0 & 2 & 1 \\ 3 & 5 & 4 \\ 6 & 8 & 7 \\ 9 & 11 & 10 \\ 12 & 14 & 13 \end{pmatrix}$

$c_{5, j}^{(3)} \ (1 \leq j \leq 3)$ を施すと

$\displaystyle E'=\begin{pmatrix} 0 & 5 & 10 \\ 3 & 8 & 13 \\ 6 & 11 & 1 \\ 9 & 14 & 4 \\ 12 & 2 & 7 \end{pmatrix}$

となる。よって、

$\displaystyle \pi_{5}^{(3)} = \begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\ 0 & 5 & 10 & 3 & 8 & 13 & 6 & 11 & 1 & 9 & 14 & 4 & 12 & 2 & 7 \end{pmatrix}$

である。

$Y$ から $C$ と同様に定義される $(n\times m)$ -行列を $C'$ とし、 $C'$ に $\pi_n^{(m)}$ を施して得られる行列を $E'$ とする。すると、対称性から $E'$ は $E$ の転置行列となっている。従って、 $E$ の並びが定める $Y$ の全順序を $\prec$ とすれば

$\displaystyle \pi_{n}^{(m)}\circ (\pi_{m}^{(n)})^{-1} = t_{mn}^{\prec}$

が成り立つ。ただし、 $t_{mn}^{\prec}$ は $X=\{1, 2, \dots, mn\}$ で議論していたものを $Y=\{0, 1, \dots, mn-1\}$ に置き換えて考えたものである。先の具体例で見れば

$\displaystyle \pi_{5}^{(3)}\circ (\pi_{3}^{(5)})^{-1} = \begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\ 0 & 12 & 9 & 5 & 2 & 13 & 10 & 7 & 6 & 3 & 14 & 11 & 8 & 4 & 1 \end{pmatrix} = t_{35}^{\prec}$

を確かめることができる。

転置の引き起こす置換を別の二つの置換で表すことができたので、基本事項の3., 4.および系、命題２を組み合わせることによって次の定理が得られる。

定理 (Zolotareffの相互法則) $m, n$ を互いに素な $3$ 以上の奇数とする。このとき、

$\displaystyle \left[\frac{n}{m}\right]\left[\frac{m}{n}\right]=(-1)^{\frac{m-1}{2}\cdot\frac{n-1}{2}}$

が成り立つ。

おやおや？

平方剰余の相互法則

これはどこかで見たことがあるぞ。。。。平方剰余の相互法則に形が似ている！

平方剰余の相互法則については

mathtrain.jp

integers.hatenablog.com

などを参照のこと。前節までの置換の話は次のように平方剰余と結びつく。

Zolotareffの補題 $p$ を奇素数とし、 $a$ を $p$ と互いに素な整数とする。このとき、

$\displaystyle \left(\frac{a}{p}\right)=\left[\frac{a}{p}\right]$

が成り立つ。

証明. $g$ を法 $p$ の原始根とし、 $a \equiv g^k \pmod{p}$ であったとする。原始根は平方非剰余なので、

$\displaystyle \left(\frac{a}{p}\right) = \left(\frac{g}{p}\right)^k = (-1)^k$

である。一方、 $R_p$ の置換としての $g$ 倍写像は $p-1$ 個の元の巡回置換なので、基本事項5.より奇置換であるため、 $g^k$ 倍写像は符号が $(-1)^k$ である。すなわち、

$\displaystyle \left[\frac{a}{p}\right] = \left[\frac{g^k}{p}\right] = (-1)^k$

となって証明が完了する。 Q.E.D.

Zolotareffの補題とZolotareffの相互法則を合わせて次が証明されたことになる：

定理 (平方剰余の相互法則) $p, q$ を相異なる奇素数とする。このとき、

$\displaystyle \left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$

が成り立つ。

まとめ

以上はZolotareffによる平方剰余の相互法則の証明の紹介である。

G. Zolotareff, Nouvelle démonstration de la loi de réciprocité de Legendre, Nouvelles Annales de Mathématiques. 2e série. 11: (1872), 354–362.

ZolotareffはLegendre記号が置換の符号で表すことができることを見抜き(Zolotareffの補題)、転置の引き起こす置換の符号を転倒数を使った定義通りの計算と、別の二つの置換での表示を用いた計算の二通りの計算を比較することによって平方剰余の相互法則を導いた。

そこで行なわれている作業は、 $mn$ 枚の数字が書かれたカードを $m\times n$ の長方形状に並べてあるルールに従って並べ替え、それと対称的な方法で $n\times m$ の長方形状にもカードを並べ、それらを見比べて転倒がどれだけ起きているかをカウントするという極めて初等的な組み合わせ作業であり、そうして平方剰余の相互法則などという整数論史上に残る美しい定理の証明が得られるというのは見事と言う他ない。

*1: $i < j$ かつ $\sigma(i) < \sigma(j)$ が成り立つような $X$ の元の組 $(i, j)$ の個数。

*2:つまり、 $t_{34}^{{<}_1}$ は偶置換。

*3:つまり、ここからは $t_{mn}^{{<}_1}=t_{mn}^{<}$ である。

*4:つまり、 $h_1=(i-1)n+j, h_2=(k-1)n+l$ である。

2018-12-04

私の好きな証明たち

好きな証明

これは鯵坂もっちょ氏が企画されたアドベントカレンダー

好きな証明 Advent Calendar 2018 - Adventar

の４日目の記事です。今回は今までに執筆したブログ記事の中から私の好きな証明を幾つか選んで紹介したいと思います。

全ての頂点のx座標, y座標が整数であるような正五角形が存在しないことの証明
ネイピア数が無理数であることの好きな証明
素数が無数に存在することの好きな証明
バーゼル問題の好きな証明
代数学の基本定理の好きな証明
1000009が素数でないことの証明
特定の数の無限性に関するグラフを使った証明
ラマヌジャンのτが23の倍数になるための十分条件の証明
三木の恒等式の証明
アックス-グロタンディークの定理の証明
ファン・デル・ヴェルデンの定理の証明
高次元最密球充填の最近の進展における証明のアイデア
おまけ

全ての頂点のx座標, y座標が整数であるような正五角形が存在しないことの証明

予備知識: 【高校数学レベル】
全ての頂点が格子点*1であるような正五角形が存在したと仮定します。このとき、以下の図のように内部に別の正五角形を描きます。

f:id:integers:20181204052403p:plain:w400

この内部にある正五角形がまた全ての頂点が格子点であるような正五角形であることを示すことができれば、いくらでも小さい領域に格子点正五角形が存在することになって矛盾します。

f:id:integers:20181204053937p:plain:w400

図において、 $ACBO$ は平行四辺形であるため、 $\overrightarrow{OA}+\overrightarrow{OB}=\overrightarrow{OC}$ が成り立ちます。仮定より、 $\overrightarrow{OA}$ および $\overrightarrow{OB}$ は成分が整数であるようなベクトルなので、 $\overrightarrow{OC}$ も成分が整数であることがわかります。すなわち、 $C$ は格子点です。対称性より、内部の正五角形はの全ての頂点が格子点であることが証明されました。

正五角形を一般の正 $n$ 角形( $n \neq 4$ )にしても同様の定理が成り立ちます。一般の場合にも同様の証明が可能ですし、上記記事ではガウス整数環を用いた代数的証明も紹介しています。そこで円分多項式の既約性を使いますが、明日icqk3氏が証明を紹介してくださるそうです。

高校数学レベルで好きな証明をもう一つ紹介するならば、IMO2006 Problem 6 - INTEGERSが大変におすすめです。これは国際数学オリンピックの問題です。自分では解けませんでしたが、初めて読んだときに言葉にはできない美しさを感じました。

ネイピア数が無理数であることの好きな証明

予備知識: 【 $e$ の定義と実数の連続性】
ネイピア数 $e$ が無理数であることの証明を５つ紹介する記事を書きました。eが無理数であることの5通りの証明 - INTEGERS
その中のSondow氏による証明が比較的好きなので紹介します。

$I_1 := [2, 3]$ とし、閉区間 $I_n$ を次のように帰納的に定義します：

$I_{n}$ は $I_{n-1}$ を $n$ 等分してできる $n$ 個の小区間のうち、左から二番目のものとする。

$I_n=[ s_n, t_n]$ とすると、

$\displaystyle s_n=1+\frac{1}{1!}+\frac{1}{2!}+\cdots + \frac{1}{n!}, \ \ t_n = s_n+\frac{1}{n!}$

であって両方 $e$ に収束します。つまり、区間縮小法による確定実数が $e$ であることがわかりました：

$\displaystyle \bigcap_{n=1}^{\infty}I_n = \{ e \} \tag{1}$

さて、 $e$ が有理数であったと仮定しましょう。すると、 $n, m \in \mathbb{N}$ が存在して

$\displaystyle e=\frac{m}{n!}$

と書けます。一方、ある整数 $a$ が存在して

$\displaystyle I_n = \left[ \frac{a}{n!}, \frac{a+1}{n!}\right]$

と書けるので、 $e \in I_n$ であることから $e$ は $I_n$ の端点のいずれかに一致せざるを得ず、(1)に矛盾します。

素数が無数に存在することの好きな証明

予備知識: 【位相の定義】
素数が無数に存在することの標準的なものを含む幾つかの証明をユークリッド数と素数の無限性 - INTEGERSで紹介しました。標準的証明は難しくないですが、有名定理はいつもそうであるように、今ではたくさんの証明が知られています。180以上の証明を調べたサーベイ記事も存在します：

[1202.3670] Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 B.C.--2017) and another new proof

数ある証明の中で私が好きなのものはFurstenbergによる位相的証明とアデールを使った位相的証明です。

Furstenbergが学部生のときに発表した証明の概略は次のようなものでした。まず、整数全体集合 $\mathbb{Z}$ に或る位相を入れます。 $\pm 1$ 以外の任意の整数は或る素因数を持つため、集合の等式

$\displaystyle \mathbb{Z} \setminus \{\pm 1\} = \bigcup_p p\mathbb{Z} \tag{2}$

が成り立つことがわかります。ここで左辺は $\pm 1$ を除く全ての整数からなる集合であり、右辺の合併は全ての素数 $p$ にわたり、 $p\mathbb{Z}$ は $p$ の倍数全体集合です。

さて、Furstenbergが定義した位相は空集合以外の開集合は無限集合という性質をもつため、左辺は閉集合ではありません。というのも、閉集合であると仮定するとその補集合である $\{\pm 1\}$ が開集合となって、これは空集合ではない有限集合ですから矛盾です。

一方で、 $p\mathbb{Z}$ は閉集合になっていることが確認できます。ということは(2)式は「閉集合の合併が閉集合ではない」状態になっています。

位相の定義によれば「閉集合の有限個の合併は閉集合」でしたので、素数は無数になければなりません。

バーゼル問題の好きな証明

予備知識: 【大学初年度の微積】
バーゼル問題

$\displaystyle \zeta(2)=\sum_{n=1}^{\infty}\frac{1}{n^2}=\frac{\pi^2}{6}$

の証明もたくさん知られていますが、積分を使った証明が非常に簡明である一方で「何故その変数変換を思いついたんだ！？」という天才性を感じられて好きです。Calabiの証明が有名ですが、バーゼル問題の短くはないが好きな証明 - INTEGERSで紹介したKontsevich-Zagierによる証明が代数関数しか用いないという点で好きです。

まず、無限等比級数の和の公式から

$\displaystyle \int_0^1 \! \! \int_0^1 \frac{1}{1-xy}\frac{\mathrm{d}x\mathrm{d}y}{\sqrt{xy}}=3\zeta(2)$

がわかります。変数変換

$\displaystyle x=s^2\frac{1+t^2}{1+s^2}, \quad y=t^2\frac{1+s^2}{1+t^2}$

によって

$\displaystyle \int_0^1 \! \! \int_0^1 \frac{1}{1-xy}\frac{\mathrm{d}x\mathrm{d}y}{\sqrt{xy}} = 4\int_{s, t > 0, \ st \leq 1}\frac{\mathrm{d}s}{1+s^2}\frac{\mathrm{d}t}{1+t^2}$

と変形でき、更に $s \mapsto s^{-1}, \ t \mapsto t^{-1}$ と変数変換したものと組み合わせることによって

$\displaystyle \int_0^1 \! \! \int_0^1 \frac{1}{1-xy}\frac{\mathrm{d}x\mathrm{d}y}{\sqrt{xy}} = 2\int_0^{\infty}\frac{\mathrm{d}s}{1+s^2}\int_0^{\infty}\frac{\mathrm{d}t}{1+t^2} = 2\times \frac{\pi}{2}\times \frac{\pi}{2} = \frac{\pi^2}{2}$

となって証明が完了です。

さて、紹介記事のタイトルは「バーゼル問題の短くはないが好きな証明」ですが、上記積分による証明は短いです。実は積分による証明を紹介した後の二つ目の証明の紹介の方が本命で、とても好きな証明になっています。詳しくは記事を参照していただきたく思いますが、大雑把に言うと次のような証明になります。

半径 $\sqrt{N}$ の $4$ 次元球 $S$ を考えます。 $S$ に含まれる格子点(全座標が整数であるような点)の個数は $N \to \infty$ で $S$ の体積 $\frac{N^2}{2}\times \pi^2$ に漸近します(ここに $\pi^2$ が現れる！)。

一方、半径が $0, 1, \sqrt{2}, \sqrt{3}, \dots, \sqrt{N}$ の $4$ 次元球で $S$ を輪切りにして各 $4$ 次元球の面上にある格子点をカウンティングしていくことによって、その総和として $S$ に含まれる格子点を数えることができます。半径 $\sqrt{n}$ の $4$ 次元球の面上にある格子点の個数は $n$ を４つの平方数の和で表す表し方の総数に他なりませんから、それはヤコビの四平方和の定理で求めることができます。

このようにして計算した格子点の総数の漸近挙動の主要項( $N^2$ の係数)に $\zeta(2)$ が出現するため、バーゼル問題が証明されるという寸法です。

代数学の基本定理の好きな証明

予備知識: 【複素解析におけるコーシーの積分定理】
定数でない複素数係数の多項式は少なくとも一つの複素数根をもつという代数学の基本定理の証明もたくさん知られています。その中でも私が大好きなコーシーの積分定理を直接的に用いたBoasによる証明が大好きです。代数学の基本定理のCauchyの積分定理を用いた証明 - INTEGERS

証明の概略を述べます。背理法で証明するため、複素数根を持たないような定数でない複素数係数の多項式 $p(x)$ が存在したと仮定します。

まず、 $p(x)$ は実数を代入すると値が実数になるという性質を持っていると仮定してもよいことが確認できます。このとき、仮定と中間値の定理によって

$\displaystyle \int_0^{2\pi}\frac{\mathrm{d}\theta}{p(2\cos \theta)} \neq 0$

が示せます。一方、 $z=e^{\sqrt{-1}\theta}$ と変数変換すると、この積分は

$\displaystyle \frac{1}{\sqrt{-1}}\int_{|z|=1}\frac{\mathrm{d}z}{zp(z+z^{-1})}$

に等しいことがわかりますが、コーシーの積分定理よってこれは $0$ でなければならず矛盾します。

どの証明でも使うことになる「実数の連続性」と、要となる大道具「コーシーの積分定理」の使い方がよくわかる見事な証明と言えるでしょう。

1000009が素数でないことの証明

予備知識: 【二平方和の定理】
大きな数の素数判定は現代ならば基本的にはコンピュータに任せると思います。しかしながら、オイラーの時代には当然コンピュータはありませんでした。当時 $1000009$ が素数だという誤認があったようで、オイラーはコンピュータなしに $1000009$ が合成数であることを証明してみせる論文を書いています。それを紹介したのが記事オイラーの定理：1000009は素数ではない - INTEGERSです。

オイラーの証明の戦略は次のようなものです。自身が証明した二平方和の定理によれば、

$4$ で割った余りが $1$ であるような素数は順序を除いて丁度一通りに二平方和として表すことができる。

という主張が成り立ちます。 $1000009$ は $4$ で割った余りが $1$ であり、しかも

$1000009=1000^2+3^2$

という自明な二平方和の表示を持ちます。そこで、オイラーは $1000009$ の他の二平方和による表示があるかを非常に巧みに調べ上げ、ないということであれば素数と証明できたわけですが、

$1000009=972^2+235^2$

を発見したために $1000009$ が素数でないことが確定しました。

特定の数の無限性に関するグラフを使った証明

予備知識: 【凸包の定義】
記事良素数の無限性 - INTEGERS
で紹介したポメランスによる良素数の無限性証明における次の定理の証明手法が面白いです。

定理 $0 < a_1 < a_2 < a_3 < \cdots$ および $\displaystyle \lim_{n \to \infty}\frac{a_n}{n} = 0$ を満たすような実数列 $\{ a_n \}$ を考える。このとき、 $2a_n > a_{n-i}+a_{n+i}$ が任意の $0 < i < n$ に対して成立するような $a_n$ が無数に存在する。

$V:=\{(0, 0)\} \cup \{ (n, a_n) \mid n \in \mathbb{N} \} \subset \mathbb{R}^2$ とおいて、 $V$ の凸包を $S$ とします。このとき、 $S$ の境界は折れ線で表され、頂点が無数に存在します。このことを図を見て確認しましょう。

f:id:integers:20181204075204p:plain

この図の場合(一例)、 $A=(0,0)$ であり、 $B$ から $M$ がそれぞれ $(1, a_1)$ から $(12, a_{12})$ に対応しています。 $B, D, H, K, M$ が凸包 $S$ 上の頂点になっています。数列に関する極限の仮定より、原点と $(n, a_n)$ を結ぶ直線(例えば図の緑の直線)の傾きは $n \to \infty$ で $0$ に収束します。

なので、辺 $HK, KM$ のような $S$ の境界上の折れ線の傾きはどんどん水平になっていくことがわかります。一方、数列 $\{ a_n \}$ は狭義単調増加数列なので、実際に水平になることはあり得ません。このことから、凸包 $S$ の折れ線の頂点は無数に存在しなければならないことがわかりました。

$S$ の原点を除いた頂点の $y$ 座標は凸性から所望の不等式を満たすことがわかるため、定理の証明が完了します。例えば図の赤線の例は $2a_3 > a_1+a_5$ と $2a_3 > a_2+a_4$ を示しています。

良素数の無限性は未解決問題として提示されたものでしたが、ポメランスによる論文はとても短く、その簡明なる証明にも驚きました。

ラマヌジャンのτが23の倍数になるための十分条件の証明

予備知識: 【ラマヌジャンの $\tau$ 関数、平方剰余、五角数定理】
記事Ramanujanのτ関数の満たす合同式と23の不思議 - INTEGERSで紹介した

素数 $p \neq 23$ が法 $23$ において平方非剰余であるならば、 $\tau (p)$ は $23$ で割り切れる。

という定理の証明が好きです。

$\displaystyle \theta (x) := \prod_{m=1}^{\infty}(1-x^{m})$ とすると、ラマヌジャンのデルタに関して $\Delta \equiv q\theta (q)\theta (q^{23})\pmod{23}$ が成り立ちます。一方、五角数定理

$\displaystyle \theta (q) = \sum_{r=-\infty}^{\infty}(-1)^rq^{\frac{r(3r+1)}{2}}$

によって

$\displaystyle \tau (p) \equiv \sum_{p=1+\frac{r(3r+1)}{2}+\frac{23s(3s+1)}{2}}(-1)^{r+s} \pmod{23}$

が得られます。そうして

$\begin{equation}\begin{split} p &= 1+\frac{r(3r+1)}{2}+\frac{23s(3s+1)}{2} \\ &\equiv 1+\frac{r(3r+1)}{2}\\ &= \frac{36r^2+12r+24}{24} \\ &\equiv (6r+1)^2 \pmod{23}.\end{split}\end{equation}$

であることから、 $p$ が法 $23$ で平方非剰余であれば $\tau (p) \equiv 0 \pmod{23}$ であることがわかりました。

突然の五角数定理！

三木の恒等式の証明

予備知識: 【関-ベルヌーイ数、 $p$ 進数】
$n$ を $4$ 以上の整数とするとき、関-ベルヌーイ数 $B_k$ に関する次の式が成り立ちます( $\beta_k=B_k/k$ であり、 $H_n$ は第 $n$ 調和数)：

$\displaystyle \sum_{k=2}^{n-2}\beta_k\beta_{n-k}-\sum_{k=2}^{n-2}\binom{n}{k}\beta_k\beta_{n-k}=2H_n\beta_n$ .

これは三木の恒等式とよばれています。関-ベルヌーイ数に関する等式ですから母関数による証明なども可能ですが、どうやってこのようなエキゾチックな等式を発見したのかが気になります。実は三木先生による証明は驚くべき手法によるものでした。三木の恒等式のジョンソンの手法による証明 - INTEGERS

ジョンソンという人が関-ベルヌーイ数に関する或る $p$ 進関係式を与えており、それを上手く応用することによって関-ベルヌーイ数に関するクンマー合同式やクラウゼン-フォン=シュタウトの定理を始めとした $p$ 進的な結果を統一的に示すというプランを提示しました。

三木先生はジョンソンの $p$ 進関係式を $\bmod{p^2}$ に還元し、巧みな計算でそれを変形していきました。

その結果得られるものは、当然、関-ベルヌーイ数に関する或る $\bmod{p^2}$ 合同式です。 $p \geq n+3$ という仮定のもと、得られた合同式は

$\displaystyle \left(H_n\beta_n-\frac{1}{2}\sum_{k=2}^{n-2}\beta_k\beta_{n-k}+\frac{1}{2}\sum_{k=2}^{n-2}\binom{n}{k}\beta_k\beta_{n-k}\right) p \equiv 0 \pmod{p^2}$

でした。つまり、

$\displaystyle H_n\beta_n-\frac{1}{2}\sum_{k=2}^{n-2}\beta_k\beta_{n-k}+\frac{1}{2}\sum_{k=2}^{n-2}\binom{n}{k}\beta_k\beta_{n-k} \equiv 0 \pmod{p}$

です。なんと、左辺が $p$ に依存していないではありませんか！！！！！

$n$ に対して条件を満たす素数は無数にありますので、左辺は $0$ でなければなりません！

アックス-グロタンディークの定理の証明

予備知識: 【可換環の基礎】
$\mathbb{C}^n$ から $\mathbb{C}^n$ への多項式写像が単射であれば全射であるというアックス-グロタンディークの定理を記事アックス−グロタンディークの定理 - INTEGERSで紹介しました。

背理法で証明するために単射であるが全射ではない $\mathbb{C}^n$ から $\mathbb{C}^n$ への多項式写像が存在したと仮定します。まず、単射性と非全射性をHilbertの零点定理を用いることによって等式で表現することができます。次に、この等式をJacobson環の基本性質を用いて或る有限体 $k$ 上で成立する式に還元します。そうして、それらの等式が $k^n$ から $k^n$ への単射であるが全射ではない写像の存在を意味することになってしまい、有限集合から自分自身への単射であるが全射ではない写像などあるわけがありませんので矛盾します。

無限の世界から有限の世界への旅による華麗なる証明と言えるでしょう。

ファン・デル・ヴェルデンの定理の証明

予備知識: 【特になし】
任意の正の整数 $k, m$ に対して、或る正の整数 $N(k, m)$ が存在して次が成り立つ: $N\geq N(k, m)$ なる任意の整数 $N$ に対して、 $1$ から $N$ までの整数をどのように $m$ 色に塗り分けたとしても、必ず同じ色で塗られた長さ $k$ の等差数列が存在する。

という定理の証明をファン・デル・ヴェルデンの定理 - INTEGERSで解説しています。

$k$ に関する帰納法で証明しますが、同じ色で塗られた長さ $k$ の等差数列=同色 $k$ -APから同色 $(k+1)$ -APを作るのは一筋縄ではいきません。そこで、証明を二重帰納的な構造にしてカラフルな車輪と呼んでいる製品を生産していきます。カラフルな車輪のスポークを増やすことが二重帰納法におけるもう一つのパラメータの変化ですが、スポークを増やす際には対角線論法の考え方を適用しています。その際、スポーク数が一つ少ない場合のカラフルな車輪の中で良いものを選び抜かないといけないのですが、その選択に「色塗りの変更」というテクニックを用います。すなわち、スポーク数の一つ少ないカラフルな車輪の様々なデータを色として管理するのです。

初等的ですが非常にアイデアに富んだ証明です。

高次元最密球充填の最近の進展における証明のアイデア

予備知識: 【フーリエ変換、保型形式】
最密球充填 - INTEGERSで離散幾何における最近の進展を解説しています。コーンとエルキースが $n$ 次元ユークリッド空間の $n$ 次元球による充填率のよい上からの評価を与えることに成功しているのですが、その証明は「シュワルツ関数の満たす双対性(ポアソン和公式)が $n$ 次元球による空間充填を制御する」というもので、かような現象の存在を知ってしまうと数学の世界に感服せずにはいられません。

$8$ 次元と $24$ 次元の場合にはコーン-エルキースのバウンドで最密構造が実現すると彼らは予想するに至り、それはすなわち魔法関数とでも呼びたくなるようなよい関数の存在を意味しますが、ヴィアゾフスカ達が実際に準モジュラー形式などを使ってそのような関数を構成してしまいました。

おまけ

ここに、等式

$\displaystyle \int_0^1(x^x)^{(x^x)^{(x^x)^{(x^x)^{(x^x)^{(x^x)^{(x^x)^{(x^x)^{\cdots}}}}}}}}\mathrm{d}x=\frac{\pi^2}{12}$

の証明の概略を紹介します。 $a^{a^{a^{a^{a^{a^{a^{a^{\cdots}}}}}}}}$ は $e^{-e} < a < e^{\frac{1}{e}}$ で収束するので、 $0 < x< 1$ のときは $e^{-\frac{1}{e}} < x^x < 1$ で、 $(x^x)^{(x^x)^{(x^x)^{(x^x)^{(x^x)^{(x^x)^{(x^x)^{(x^x)^{\cdots}}}}}}}}$ は収束することがとりあえずわかります。ランベルトの $W$ 関数*2を原点を通る単調増加な範囲で考えます。収束の範囲内で $y=a^{a^{a^{a^{a^{a^{a^{a^{\cdots}}}}}}}}$ とすると $a^y=y$ であることから、 $\log$ を取れば $y=\frac{-W(-\log a)}{\log a}$ が成り立つことがわかります。

ラグランジュの反転公式によってランベルトの $W$ 関数は $|t| < e^{-1}$ で

$\displaystyle W(t)=\sum_{n=1}^{\infty}\frac{(-n)^{n-1}}{n!}t^n$

なるテイラー展開を持ちます。 $0 < x < 1$ のとき $-e^{-1} \leq x \log x < 0$ なので、

$\begin{align}\int_0^1(x^x)^{(x^x)^{(x^x)^{(x^x)^{(x^x)^{(x^x)^{(x^x)^{(x^x)^{\cdots}}}}}}}}\mathrm{d}x&=\int_0^1\frac{-W(-x\log x)}{x\log x}\mathrm{d}x \\ &=\int_0^1\sum_{n=1}^{\infty}\frac{(-n)^{n-1}}{n!}(-x\log x)^{n-1}\mathrm{d}x\\ &=\sum_{n=1}^{\infty}\frac{n^{n-1}}{n!}\int_0^1x^{n-1}(\log x)^{n-1}\mathrm{d}x\end{align}$

と変形することができます。二年生の夢に出てくる積分公式

$\displaystyle \int_0^1x^{n-1}(\log x)^{n-1}\mathrm{d}x=\frac{(-1)^{n-1}}{n^n}(n-1)!$

によって

$\displaystyle\int_0^1(x^x)^{(x^x)^{(x^x)^{(x^x)^{(x^x)^{(x^x)^{(x^x)^{(x^x)^{\cdots}}}}}}}}\mathrm{d}x=\sum_{n=1}^{\infty}\frac{n^{n-1}}{n!}\frac{(-1)^{n-1}}{n^n}(n-1)!=\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{n^2}=\frac{1}{2}\zeta(2)$

と計算できました。バーゼル問題と合わせると証明が完了します。

*1:ここでは $x$ 座標および $y$ 座標がともに整数であるような二次元ユークリッド平面の点のこと。

*2: $y=xe^x$ の逆関数。

発想の経緯

ルール

転置が引き起こす置換

二つの置換

Zolotareff記号

置換とその符号

Zolotareffの相互法則

平方剰余の相互法則

まとめ

全ての頂点のx座標, y座標が整数であるような正五角形が存在しないことの証明

ネイピア数が無理数であることの好きな証明

素数が無数に存在することの好きな証明

バーゼル問題の好きな証明

代数学の基本定理の好きな証明

1000009が素数でないことの証明

特定の数の無限性に関するグラフを使った証明

ラマヌジャンのτが23の倍数になるための十分条件の証明

三木の恒等式の証明

アックス-グロタンディークの定理の証明

ファン・デル・ヴェルデンの定理の証明

高次元最密球充填の最近の進展における証明のアイデア

おまけ

置換 $\pi_m^{(n)}$ とその符号