2019-12-30

この前のブログに書いたやつが "zeta polynomial" だった件

以前の記事

oddie.hatenablog.com

で $[m]_q^{(n)}$ という組合せ量を定義しました。これは有限体 $\mathbb{F}_q$ 上の $n$ 次元ベクトル空間 $\mathbb{F}_q^n$ における部分空間の列

\begin{split} 0 = V_0 \subset V_1 \subset \cdots \subset V_m = \mathbb{F}_q^n \end{split}

の個数に等しいものでした。

この記事を書いてからしばらくして、たまたま読んでいた文献 [1] に載っていた zeta polynomial というやつがこれの一般化になっていることに気づきました！！

定義 $P$ を有限半順序集合とする． $P$ における長さ $n$ の multichain $x_0\leq x_1\leq\cdots\leq x_n$ の個数を $Z_P(n)$ とおき*1， $P$ の zeta polynomial という．

$Z_P(n)$ が $n$ の多項式であることは、等式

\begin{split} Z_P(n) = \sum_{k=0}^d b_k \binom{n}{k} \end{split}

からわかります。ここで $b_k$ は $P$ の長さ $k$ の chain $x_0\lt x_1\lt\cdots\lt x_k$ の個数で、 $d$ は $P$ の最大の chain の長さです。

$P$ として $\mathbb{F}_q^n$ の部分空間のなす半順序集合をとり、 $x_0=V_1,x_1=V_2,\cdots,x_{m-2}=V_{m-1}$ と対応させると、

\begin{split} [m]_q^{(n)} = Z_P(m-2) \end{split}

だったわけですね。

ちなみにこの zeta polynomial は、半順序集合の隣接代数（かなり雑に言えばグラフの隣接行列みたいなやつのなす代数）におけるゼータ関数というものと関係がありますが、Riemann ゼータ関数とかのゼータとは多分直接の関係はなさそうに思いました。

隣接代数のゼータ関数という名前の由来は、隣接代数のゼータ関数が隣接代数における Möbius 関数の逆元になっていることが、Riemann ゼータ関数の逆数は Möbius 関数の Dirichlet 級数であることに似ているのと大きく関係していそうに思います。

追記：隣接代数のゼータ関数の記事を書きました。

oddie.hatenablog.com

この中で zeta polynomial との関係についても解説しています。

参考文献

[1] Richard P. Stanley, Enumerative combinatorics, vol.1 (pdf)

[2] https://ncatlab.org/nlab/show/zeta+polynomial (2019年12月30日閲覧)

*1:[1] では $P$ における長さ $n-2$ の multichain $x_1\leq x_2\leq\cdots\leq x_{n-1}$ の個数としている．この定義は [2] によった．

2019-12-04

Hecke L 関数の岩澤-Tate 理論 (前編)

整数論調和解析アデールイデール

この記事はゼータ Advent Calendar 2019の4日目の記事です。

adventar.org

元々は一本の記事で書く予定でしたが、長くなりすぎてしまうため前編と後編に分けることにします。

この前編の記事では、岩澤-Tate 理論の解説の前提知識として、位相群上の調和解析の結果とアデール・イデールの定義と性質を準備します。

岩澤-Tate 理論のメインの解説は一週間後に後編の記事として投稿します。突然の予定変更で申し訳ありません。

はじめに
位相群上の調和解析
- Fourier 反転公式
- Poisson 和公式
アデールとイデール
参考文献

はじめに

私 Oddie は学生時代に Weil の Basic Number Theory のゼミをやっていたのですが、当時は内容の表面的な理解がやっとだったので、いずれテキストをもう一度読み直したいとしばらく思ってました。

そんな中、2019年10月19日（土）・20日（日）の２日間にわたって開催された数学イベント「マスパーティ」

mathparty.localinfo.jp

に参加した所、その企画の一つ「ロマンティック数学ナイトプライム＠ゼータ」においてたまたま岩澤-Tate のお話が出てきて、とても面白く講演を聴かせていただきました。

その後自分も何かアウトプットをしてみたい気持ちが湧いてきて、上のテキストの復習を兼ねて、記事をゼータ Advent Calendar に投稿することに決めました。

タイトルの Hecke $L$ 関数とは Hecke 指標に付随する $L$ 関数のことです。 Hecke 指標は Dirichlet 指標の拡張であり、Hecke $L$ 関数は Dirichlet $L$ 関数の拡張になっています。また、代数体に対して定義される Dedekind ゼータ関数は自明な Hecke 指標に付随する $L$ 関数となっています。

このような広いクラスの関数である Hecke $L$ 関数（の完備化）をある種の位相群 (イデール) 上の積分で表し、位相群上の調和解析の手法を用いて関数等式や解析接続などの性質を導くのが岩澤-Tate 理論の骨子です。

位相群上の調和解析

ここでは Fourier 解析を一般の局所コンパクトアーベル群上で行うことを考えます。

$G$ を局所コンパクトアーベル群とします。 $G$ から $\mathbb T = \{z\in\mathbb C||z|=1\}$ への連続準同型を $G$ の指標 (character) と呼びます。

$G$ の指標のなす群 $\widehat G$ を指標群といいます。開コンパクト位相を入れることで $G$ は局所コンパクトアーベル群となります。

$x\in G,\ \chi\in \widehat G$ に対して、 $\chi(x)\in\mathbb T$ を Pontryagin 双対性*1を考慮して $\langle x,\chi\rangle$ とペアリングの形に書きます。

Fourier 反転公式

$dx$ を $G$ の Haar 測度*2とし、 $f\in L^1(G)$ の Fourier 変換 (Fourier transform) $\widehat f$ を

\begin{split} \widehat f(\chi)=\int_G f(x)\overline{\langle x,\chi\rangle}dx \end{split}

で定義します。このとき $\widehat f\in C(\widehat G)$ です。

定理1 (Fourier 反転公式) $\widehat G$ の Haar 測度 $d\chi$ が存在して、 $f\in L^1(G)$ かつ $\widehat f\in L^1(\widehat G)$ ならば次が成り立つ。

\begin{split} f(x) = \int_{\widehat G}\widehat f(\chi)\langle x,\chi\rangle d\chi \end{split}

この $d\chi$ を $dx$ の双対測度 (dual measure) という。

同型 $G\cong \widehat G$ が存在すると仮定し、この同型によって $G$ と $\widehat G$ を同一視することを考えます。このとき $dx$ を適当な定数倍で置き換えると上の定理で $dx=d\chi$ とできます。この $dx$ を自己双対測度 (self-dual measure) といいます。

例2 $G=\mathbb R$ とします。 $y\in\mathbb R$ を指標 $\chi(x)=e^{2\pi\sqrt{-1}xy}$ に写すことで同型 $\mathbb R\cong\widehat{\mathbb R}$ が得られます。この同型による同一視の下、Fourier 変換は

\begin{split} \widehat f(y) = \int_{\mathbb R}f(x)e^{-2\pi\sqrt{-1}xy} dx \end{split}

であり、 Lebesgue 測度 $dx$ が自己双対測度です。定理1は通常の Fourier 反転公式になります。

Poisson 和公式

注意このパートはまだ私が理解できていない所があるため、間違いを含んでいる可能性があります。

$\Gamma$ を $G$ の離散部分群で $G/\Gamma$ がコンパクトとなるものとします。

\begin{split} \Gamma^\perp = \{\chi\in\widehat G|\langle x,\chi\rangle=1,\ x\in\Gamma\} \end{split}

を $\Gamma$ の零化部分群 (annihilataor) といいます。

命題3 $G/\Gamma$ の Haar 測度 $d\dot x$ が存在して以下が成り立つ。 $f \in C(G)\cap L^1(G)$ かつ級数 $\sum_{y\in\Gamma}f(x+y)$ は $x$ に関して広義一様に絶対収束すると仮定する。このとき

\begin{split} \int_{G/\Gamma}\left(\sum_{y\in\Gamma}f(x+y)\right)d\dot x = \int_{G}f(x)dx \end{split}

定理4 (Poisson 和公式) $dx$ を上の命題の $d\dot x$ が $\mathrm{vol} (G/\Gamma) = 1$ を満たすようにとっておく*3。 $f\in C(G)\cap L^1(G)$ は以下の二条件を満たすと仮定する：

級数 $\sum_{y\in\Gamma}f(x+y)$ が $x$ に関して広義一様に絶対収束する
級数 $\sum_{\chi\in\Gamma^\perp}\widehat f(\chi)$ が絶対収束する

このとき

\begin{split} \sum_{x\in\Gamma}f(x)=\sum_{\chi\in\Gamma^\perp}\widehat f(\chi) \end{split}

系5 $dx$ を定理4の条件を満たすものとする。同型 $G\cong\widehat G$ が存在すると仮定し、この同型によって $\Gamma\cong\Gamma^\perp$ とする。もし定理4の条件が $f$ と $\widehat f$ について成り立ち $\sum_{x\in\Gamma}f(x)\neq0$ ならば、 $dx$ は自己双対測度である。

証明ある $c\gt0$ によって $d\chi=cdx$ と書けます*4。Fourier 反転公式より

$\begin{split} f^{\wedge\wedge}(y) = \int_{G}\widehat f(x)\overline{\langle y,x\rangle}dx = c^{-1}\int_{\widehat G}\widehat f(\chi)\overline{\langle y,\chi\rangle}d\chi = c^{-1}f(-y) \end{split}$

となります。Poisson 和公式を $f$ と $\widehat f$ に用いて

\begin{split} \sum_{x\in\Gamma}f(x) = \sum_{\chi\in\Gamma^\perp}\widehat f(\chi) = c^{-1}\sum_{x\in\Gamma}f(x) \end{split}

を得るので $c=1$ です。証明終

例6 例2の状況を考えます。 $\Gamma=\mathbb Z$ とすると $\Gamma^\perp=\mathbb Z$ です。 $f$ を $\mathbb R$ 上の急減少関数*5とすると定理4の条件を満たし、

\begin{split} \sum_{x\in\mathbb Z}f(x) = \sum_{x\in\mathbb Z}\widehat f(x) \end{split}

が成り立ちます。これは通常の Poisson 和公式です。

アデールとイデール

大域体

有理数体 $\mathbb{Q}$ の有限次代数拡大を代数体 (number field) といい、これは代数的整数論における基本的な研究対象です。この代数体と類似した性質を持つ体として有限体 $\mathbb{F}_q$ 上の1次元関数体、つまり有理関数体 $\mathbb{F}_q(T)$ の有限次拡大体、があります。

代数体は標数 $0$ で $\mathbb{F}_q$ 上の1次元関数体は標数正であるなど、見かけはかなり異なっている二種類の体ですが、代数的整数論においてはほとんど同様な議論ができる場合が多いです。

そこで、これらの体を総称して大域体 (global field) と呼びます。

局所体

離散的でない局所コンパクト位相体を局所体 (local field) といいます。局所体は位相体としての同型を除いて次のいずれかになります：

$p$ 進数体 $\mathbb{Q}_p$ の有限次拡大体
有限体 $\mathbb{F}_q$ 上の形式的冪級数環 $\mathbb{F}_q[[T$ ]] の商体 $\mathbb{F}_q( (T) )$
実数体 $\mathbb{R}$
複素数体 $\mathbb{C}$

1と2の局所体を非アルキメデス的 (non-archimedian)、3と4の局所体をアルキメデス的 (archimedian) といいます。

大域体の素点

大域体 $K$ に適当な距離 (絶対値) を入れて完備化し、位相的に扱いやすくすることを考えます。

定義7 体 $K$ に対して、以下の三条件を満たす写像 $|\cdot|:K\to[0,\infty)$ を $K$ の絶対値 (absolute value) という。

(i) $|x|=0\Leftrightarrow x=0$
(ii) $|xy|=|x||y|$
(iii) $|x+y|\leq|x|+|y|$

$|0|=0,\ |x|=1\ (x\neq0)$ で定義される絶対値 $|\cdot|$ を自明な絶対値という。二つの絶対値 $|\cdot|, \ |\cdot|'$ は、ある $r\gt0$ が存在して ${|\cdot|}^r=|\cdot|'$ となるとき、同値であるという。

大域体 $K$ に対して $K$ の非自明な絶対値の同値類を $K$ の素点 (place) といいます。

$v$ を $K$ の素点とするとき、 $v$ の代表元 $|\cdot|$ に関する $K$ の完備化を $K_v$ で表します ( $|\cdot|$ のとり方によらない) 。このとき $K_v$ は局所体となることが知られています。

$K_v$ がアルキメデス的のとき $v$ をアルキメデス的 (または無限素点)、そうでないとき非アルキメデス的 (または有限素点) といい、それぞれ $v\mid\infty$ 、 $v\nmid\infty$ で表します。

$K$ の全ての無限素点の集合を $P_\infty$ と書くことにします。 $P_\infty$ は常に有限集合で、 $K$ が標数正のときは空集合になります。

$K_v$ の加法群としての Haar 測度 $d_vx$ をとると、 $K_v$ の絶対値 $|\cdot|_v$ が

\begin{split} d_v(xy)=|x|_vdv(y) \end{split}

で定まります。 $K_v=\mathbb R$ のとき $|x|_v=|x|$ (通常の絶対値) 、 $K_v=\mathbb C$ のとき $|x|_v=|x|^2$ (通常の絶対値の二乗) となります。

$v$ が有限素点のとき $|\cdot|_v$ は定義7の条件(iii)より強い条件

\begin{split}|x+y|\leq\max(|x|,|y|) \end{split}

を満たします。

以下しばらくの間 $v$ を有限素点とします。

\begin{split} \mathcal O_v = \{x\in K_v||x|_v\leq1\} \end{split}

とおくとこれは $K_v$ のコンパクトな部分環で、

\begin{split} \{x\in K_v||x|_v\lt1\} \end{split}

を唯一の極大イデアルとする局所環となります。実はこの極大イデアルは単項生成となるのでその生成元 (の一つ) を $\pi_v$ と書き、 $K_v$ の素元といいます。剰余体 $\mathcal O_v/\pi_v\mathcal O_v$ の位数を $q_v$ と書きます。このとき \begin{split} |\pi_v|_v=q_v^{-1} \end{split} が成り立ちます。

例8 $K=\mathbb Q$ とします。 $\mathbb Q$ の無限素点は通常の絶対値 $|\cdot|_\infty=|\cdot|$ に対応するものだけです。この素点を $\infty$ で表します。 $v=\infty$ のとき、 $K_v=\mathbb R$ です。

$\mathbb Q$ の有限素点は素数に対応します。つまり $p$ を素数として $p$ 進絶対値 $|\cdot|_p$ に対応するものです。この素点を $p$ で表します。

$v=p$ とします。このとき $K_v=\mathbb Q_p$ で、 $\mathcal O_v$ は $p$ 進整数環 $\mathbb Z_p$ になります。また $\pi_v=p$ ととることができ、 $q_v=p$ となります。

アデール

大域体の全ての完備化の情報を集めてできたものがアデールです。しかし、単に全ての素点での完備化の直積 $\prod_v K_v$ を考えると、これは局所コンパクトになりません。

定義9 $K$ のアデール環 (adele ring) $\mathbb A_K$ を $\mathcal O_v$ についての $K_v$ の制限直積として定義する： \begin{split} \mathbb A_K = \prod_v' K_v \end{split} ここで右辺は $\prod_v K_v$ の元 $x=(x_v)_v$ で、有限個の素点 $v$ を除いて $x_v \in \mathcal O_v$ を満たすものの集合を表す。

$\mathbb A_K$ は $\prod_v K_v$ の部分環で、その位相は以下のように定義されます (相対位相とは異なります) ：

$S$ を $P_\infty$ を含む $K$ の素点の有限集合として

\begin{split} \prod_{v\in S} U_v \times \prod_{v\notin S} \mathcal O_v \end{split}

という形の集合を考えます。ここで $U_v$ は $K_v$ における $0$ の任意の開近傍です。この形の集合を $0$ の基本近傍系として、加法群 $\mathbb A_K$ に位相群の構造を与えることができます。この位相で $\mathbb A_K$ は局所コンパクト位相環になります。

$x\in K$ は有限個の素点 $v$ を除いて $x\in\mathcal O_v$ を満たすという事実から対角準同型

\begin{split} K\ni x\mapsto(x,x,\cdots)\in\mathbb A_K \end{split}

が定まり、これによって $K\subset\mathbb A_K$ とみなします。このとき次が成り立ちます。

定理10 $K$ は $\mathbb A_K$ において離散的で、商 $\mathbb A_K/K$ はコンパクト。

イデール

定義11 $K$ のイデール群 (idele group) $I_K$ を $\mathcal O_v^*$ についての $K_v^*$ の制限直積として定義する：

\begin{split} I_K = \prod_v' K_v^*\end{split}

ここで右辺は $\prod_v K_v^*$ の元 $x=(x_v)_v$ で、有限個の素点 $v$ を除いて $x_v \in \mathcal O_v^*$ を満たすものの集合を表す。

$I_K$ は $\mathbb A_K$ の単元群 $\mathbb A_K^\times$ に一致します。

$I_K$ に $\mathbb A_K$ からの相対位相を入れたものは位相群でない (逆元を取る演算 $x\mapsto x^{-1}$ が連続でない) ため、以下のように位相を定めます：

$S$ を $P_\infty$ を含む $K$ の素点の有限集合として

\begin{split} \prod_{v\in S} V_v \times \prod_{v\notin S} \mathcal O_v^*\end{split}

という形の集合を考えます。ここで $V_v$ は $K_v^*$ における $1$ の任意の開近傍です。この形の集合を $1$ の基本近傍系として $I_K$ に位相群の構造を与えます。この位相で $I_K$ は局所コンパクト位相群になります。

$x\in K^*$ は有限個の素点 $v$ を除いて $x\in\mathcal O_v^*$ を満たすという事実から対角準同型

\begin{split} K^*\ni x\mapsto(x,x,\cdots)\in I_K \end{split}

が定まり、これによって $K^*\subset I_K$ とみなします。商 $I_K/K^*$ を $K$ のイデール類群といいます。

定義12 $x=(x_v)_v\in I_K$ のイデールノルム $|x|_{\mathbb A}$ を

\begin{split} |x|_{\mathbb A} = \prod_v |x_v|_v \end{split}

で定義する。また $I_K$ の部分群 $\mathbb A_K^1$ を次で定める：

\begin{split} \mathbb A_K^1 = \{x\in I_K||x|_{\mathbb A} = 1\} \end{split}

このとき以下が成り立ちます。

定理13 (積公式) $x\in K^*$ のとき $|x|_{\mathbb A}=1$ 。すなわち $K^*\subset\mathbb A_K^1$ 。

定理14 $K^*$ は $\mathbb A_K^1$ において離散的で、商 $\mathbb A_K^1/K^*$ はコンパクト。

参考文献

www.asakura.co.jp

本稿は主にこのテキストの第IV章を参考に書きました。この章は次のテキストの Chapter VIIの内容を基に書かれています。

www.springer.com

位相群の調和解析については、次のテキストも参考にしました。

A Course in Abstract Harmonic Analysis - CRC Press Book

ここまで読んでくださりありがとうございました。

誤植や間違いなどありましたら、ご連絡いただけると助かります。

次回後編の投稿は、一週間後の12/11(水)を予定しています。

明日のゼータ Advent Calendar は tsujimotter さんの記事です。お楽しみに！

*1: $G$ と $G^{\wedge\wedge}$ が自然に同型であることであるという定理。

*2:つまり $dx$ は任意の $y\in G$ と任意の Borel 可測集合 $A\subset G$ に対し $dx(y+A)=dx(A)$ を満たす Radon 測度。

*3:この仮定がなぜ必要なのか理解できていません。

*4:Haar 測度は定数倍を除いて一意。

*5: $f\in C^\infty(\mathbb R)$ かつ任意の $m,n\geq0$ に対し $\sup_{x\in\mathbb R}\left|x^m\frac{d^nf}{dx^n}\right|\lt\infty$ ということ。

2019-09-10

q-combinatorics と有限体

組合せ論 q-類似有限体

ブログはかなり久しぶりの更新になります。

ツイッターで写像 $12$ 相の $q$ -類似やその幾何的実現という魅力的なワードを見かけたので、そのうちの $4$ つについて $q$ -類似と有限体を用いた実現を与えました。多項定理の $q$ -類似についても書きました。

drive.google.com

§3で $[m]_q^{(n)}$ と $F_q(n,m)$ という組合せ量を独自に導入しました。文献を調査した所、スターリング数や分割数の $q$ -類似もあることがわかったので、それらと $[m]_q^{(n)},F_q(n,m)$ の関係がわかったら面白いと思います。

誤植や間違い等ございましたら、ご指摘くださると助かります。

2019/12/30追記：pdfにいくつかの変更を加えました。

2020/01/07追記：定理 1.1 と定理 2.2 の証明の記述に変更を加えました。

2018-05-27

ディガンマ関数

整数論特殊関数

ディガンマ関数と自然数の累乗の逆数和との関係についてのメモ。

ディガンマ関数

ディガンマ関数とは、ガンマ関数 $\Gamma(s)$ の対数微分

$\displaystyle \psi(s) = \frac{\mathrm{d}}{\mathrm{d}s}\log(\Gamma(s)) = \frac{\Gamma'(s)}{\Gamma(s)}$

で定義される関数 $\psi(s)$ です。

ガンマ関数の無限乗積表示

ガンマ関数の無限乗積表示について復習します。

命題１ 全ての $s\in\mathbb{C}$ に対して

$\displaystyle \frac{1}{\Gamma(s)} = s e^{\gamma s} \prod_{n=1}^{\infty}\left(1+\frac{s}{n}\right)e^{-s/n}$

が成り立つ．ここで $\gamma$ はオイラーの定数

$\displaystyle \gamma = \lim_{n\to\infty}\left(\sum_{k=1}^{n}\frac{1}{k}-\log n\right)$

である．

この命題の証明は

integers.hatenablog.com

にあります。

ディガンマ関数の性質１

命題１の両辺の対数微分をとると次が分かります：

定理１ $s \neq 0,-1,-2,\ldots$ に対して

$\displaystyle \psi(s) = -\gamma + \sum_{n=0}^{\infty} \left(\frac{1}{n+1} - \frac{1}{n+s} \right)$

が成り立つ．特に

$\psi(1) = -\gamma$

である．

さらに、定理１の等式の両辺を繰り返し微分すると次も分かります：

定理２ $k$ を正整数とする． $s \neq 0,-1,-2,\ldots$ に対して

$\displaystyle {\psi}^{(k)}(s) = {(-1)}^{k-1} k! \sum_{n=0}^{\infty} \frac{1}{(n+s)^{k+1}}$

が成り立つ．特に

$\displaystyle {\psi}^{(k)}(1) = {(-1)}^{k-1} k! \zeta(k+1)$

である．

このようにディガンマ関数の導関数の $s=1$ での値はゼータ値と関係しています。

次に $s=2,3,4,\ldots$ での値を見ていきます。

ディガンマ関数の性質２

定理３ $n$ を正整数とする． $s \neq 0,-1,-2,\ldots$ に対して

$\displaystyle \psi(s+n) = \psi(s) + \sum_{k=0}^{n-1} \frac{1}{s+k}$

が成り立つ．特に

$\displaystyle \psi(n+1) = -\gamma + \sum_{k=1}^{n} \frac{1}{k}$

である．

証明．ガンマ関数の関数等式 $\Gamma(z+1)=z\Gamma(z)$ の両辺の対数微分をとると

$\displaystyle \psi(z+1) - \psi(z) = \frac{1}{z}$

が分かり， $z=s,s+1,\ldots,s+n-1$ について辺々加えると第一の等式を得る．この等式において $s=1$ とおけば第二の等式を得る．証明終

また定理３の両辺を繰り返し微分することにより次も分かります：

定理４ $n,k$ を正整数とする． $s \neq 0,-1,-2,\ldots$ に対して

$\displaystyle {\psi}^{(k)}(s+n) = {\psi}^{(k)}(s) + {(-1)}^{k} k! \sum_{m=0}^{n-1} \frac{1}{{(s+m)}^{k+1}}$

が成り立つ．特に

$\displaystyle {\psi}^{(k)}(n+1) = {(-1)}^{k} k! \left( -\zeta(k+1) + \sum_{m=1}^{n} \frac{1}{{m}^{k+1}} \right)$

である．

2018-05-05

ニムゲームと排他的論理和

組合せゲーム理論

ニムと呼ばれる二人で行うゲームの必勝法と、それにまつわる演算を紹介します。

ニム

ニムは二人のプレイヤーがいくつかの石の山から石を交互に取り合うゲームです。ニムのルールはいろいろバリエーションがありますが、次のルールを考えます。

ニムのルール

石の山をいくつか用意する。
二人のプレーヤーは交互に $1$ 個以上石を取る。このとき、複数の山にまたがっては取れないが、一つの山からは何個でも取れる。
取れる石が無くなったら負け。

後でルール２を変えたゲームも考えます。

以下では、ニムの局面を非負整数の順序対で表します。

例： $(4,2,1)$ は、 $1$ 番目の山に $4$ 個、 $2$ 番目の山に $2$ 個、 $3$ 番目の山に $1$ 個石がある局面。

Grundy値

ニムの局面には、Grundy値という非負整数値が定まります。

Grundy値の定義と性質については

fibonacci-freak.hatenablog.com

にあります。そこに書かれているように、Grundy値が $0$ の局面は後手必勝、nonzeroの局面は先手必勝です。

ニムの局面 $(n_1,\ldots,n_k)$ のGrundy値を $G(n_1,\ldots,n_k)$ と表すことにすると、局面 $(n_1,\ldots,n_k)$ は局面 $(n_1),\ldots,(n_k)$ の直和*1だから、上の記事の第一定理より、

\begin{split} G(n_1,\ldots,n_k)&= G(n_1) \oplus \cdots \oplus G(n_k) \\&= n_1 \oplus \cdots \oplus n_k \end{split}

ここで $\oplus$ は二進記数法の各桁ごとの排他的論理和です。この「二進記数法の各桁ごとの排他的論理和」のことも単に排他的論理和と呼びます。

例： $11 \oplus 5 = {1011}_2 \oplus {101}_2 = {1110}_2=14$

よって次の結果を得ます：

定理１ ニムの局面 $(n_1,\ldots,n_k)$ が後手必勝 $\Leftrightarrow$ $n_1 \oplus \cdots \oplus n_k = 0$

これをもとにしたニムの必勝法の手順は

ニム（複数山の石取りゲーム）の必勝法 | 高校数学の美しい物語

の「ニムの必勝法の概略」にあります。その記事では「後手必勝」のことを単に「必勝形」と呼んでいます。

$N$ -ニム

$N$ を自然数とします。上のニムのルールにおいて、一つの山から取れる石の個数を $1$ 以上 $N$ 以下に変更したゲームを考えます。区別のため、このゲームを $N$ -ニムと呼ぶことにします*2。

$N$ -ニムの局面も同じく順序対で表し、 $N$ -ニムの局面 $(n_1,\ldots,n_k)$ のGrundy値を $G_N(n_1,\ldots,n_k)$ と表すことにすると、

\begin{split} G_N(n_1,\ldots,n_k)&= G_N(n_1) \oplus \cdots \oplus G_N(n_k) \\&= (n_1 \ \mathrm{mod} \ N+1) \oplus \cdots \oplus (n_k \ \mathrm{mod} \ N+1) \end{split}

ここで自然数 $k$ に対して $n \ \mathrm{mod} \ k$ は、整数 $n$ を $k$ で割った余り( $0$ 以上 $k-1$ 以下)を返す関数です。

まとめると次の結果となります：

定理２ $N$ -ニムの局面 $(n_1,\ldots,n_k)$ が後手必勝 $\Leftrightarrow$ $(n_1 \ \mathrm{mod} \ N+1) \oplus \cdots \oplus (n_k \ \mathrm{mod} \ N+1) = 0$

$3$ -ニムの必勝法

$N=3$ の場合について必勝法を考えます。

系 $3$ -ニムの局面 $(n_1,\ldots,n_k)$ が後手必勝 $\Leftrightarrow$ $n_1, \ldots , n_k$ のうち、 $4$ で割って $1$ 余るものの個数、 $2$ 余るものの個数、 $3$ 余るものの個数の偶奇が一致する。

証明．定理２から明らか。証明終わり

この系をもとに具体的な必勝法の手順を考えます。 $(n_1,\ldots,n_k)$ を $3$ -ニムの先手必勝の局面とします。 $n_1, \ldots , n_k$ のうち、 $4$ で割って $i(i=0,1,2,3)$ 余るものの個数を $a_i$ とおいて、 $a_1,a_2,a_3$ の偶奇で場合分けします。系により次の二つの場合に分かれます。