一年生の夢とLucasの合同式

一年生の夢(Freshman's dream)とは

$(X+Y)^n = X^n+Y^n$

のことを言います。中学生が展開を習ったときに

$(X+Y)^2=X^2+2XY+Y^2$

が正しいところを

$(X+Y)^2 =X^2+Y^2$

と間違えてしまうことはよく見かける光景だと思います。ちなみに二年生の夢(sophomore’s dream)もあるのですが、こちらは正しい式です：

$\begin{align}\int_0^1\frac{1}{x^x}dx &= \sum_{n=1}^{\infty}\frac{1}{n^n} \\ \int_0^1x^xdx &= -\sum_{n=1}^{\infty}(-n)^{-n}\end{align}$

mathtrain.jp

一年生の夢が成り立つ世界

最初の式ではどこで物事を考えるか明示していませんでしたが、標数 $p > 0$ の体係数多項式環では

$(X+Y)^p = X^p+Y^p$

が正しい式となります。理由は

integers.hatenablog.com

です(使うのはタイトルでリンク先に飛んでも違う話が書いてあります)。繰り返し適用すれば、任意の自然数 $k$ に対して

$(X+Y)^{p^k} = X^{p^k}+Y^{p^k}$

が成り立つこともわかります。

Lucasの合同式

1878年にLucasは二項係数に関する非常に美しい合同式を発表しています：

Lucasの合同式 $p$ を素数とし、非負整数 $n, m \ (n \geq m)$ をそれぞれ、

$\begin{align}n &= a_0+a_1p+\cdots +a_lp^i\\ m&= b_0+b_1p+\cdots + b_lp^l\end{align}$

と $p$ 進法表示する( $0 \leq a_i, b_i \leq p-1$ )。このとき、二項係数に関する合同式

$\displaystyle \binom{n}{m} \equiv \binom{a_0}{b_0}\binom{a_1}{b_1}\cdots \binom{a_l}{b_l} \pmod{p}$

が成り立つ。

パスカルの三角形に現れない二項係数については $\binom{0}{0}=1, \ \binom{a}{b}=0 \ (a < b)$ として扱います。この記事ではFineが1947に発表した証明を紹介します。この証明は二項定理と一年生の夢を用いた母関数表示による証明です。

証明. $\mathbb{F}_p[X]$ において

$\begin{align}\sum_{m=0}^n\binom{n}{m}X^m &= (1+X)^n= \prod_{i=0}^l(1+X)^{a_ip^i} = \prod_{i=0}^l(1+X^{p^i})^{a_i} \\ &= \prod_{i=0}^l\left( \sum_{b_i=0}^{a_i}\binom{a_i}{b_i}X^{b_ip^i} \right) \\ &= \prod_{i=0}^l\left( \sum_{b_i=0}^{p-1}\binom{a_i}{b_i}X^{b_ip^i} \right) \\ &= \sum_{b_0=0}^{p-1}\sum_{b_1=0}^{p-1}\cdots \sum_{b_l=0}^{p-1}\left(\prod_{i=0}^l\binom{a_i}{b_i}\right) X^{b_0+b_1p+\cdots +b_lp^l} \\ &= \sum_{m=0}^n \left( \prod_{i=0}^l\binom{a_i}{b_i} \right) X^m \end{align}$