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$ の長方形状にもカードを並べ、それらを見比べて転倒がどれだけ起きているかをカウントするという極めて初等的な組み合わせ作業であり、そうして平方剰余の相互法則などという整数論史上に残る美しい定理の証明が得られるというのは見事と言う他ない。