整数全体の等差数列への分割に関するMirsky–Newmanの定理

しばらくブログの更新が止まっていてすいません．2018年に入ってから自分の数学の勉強が忙しく，なかなか小ネタを書く時間がありませんでした…．ただ書きたいネタ自体はいろいろあるので，ブログは続けていこうと思います．

今回は次の有名な定理を示します．

定理（Mirsky-Newman）．整数全体の集合 $\mathbb{Z}$ が，次のように $n(\geq 2)$ 個の互いに交わらない等差数列に分割されたとする：

$\mathbb{Z}=\displaystyle\coprod_{i=1}^n a_i+b_i\mathbb{Z}~~(b_1\geq b_2\geq\dots\geq b_n).$

このとき $b_1=b_2$ である．

特にこの定理から，整数全体を公差の相異なる2つ以上の等差数列に分割することは不可能であることがわかります．

よく知られた証明としてはSteinとShakarchiの複素解析の本に載っているものがありますが，最近私は簡単な別証明をひとつ思いついたので，それを以下に紹介します．

まず整数全体をどの等差数列に属するかによって $n$ 色に塗り分けます． $N$ を $b_1,b_2,\dots,b_n$ の十分大きい公倍数とすれば，色のパターンは $\{0,1,\dots,N-1\}$ を周期として繰り返し，また各色はこの周期に3つ以上含まれます．そこでこれら $N$ 個の色と同じ順に正 $N$ 角形の頂点を塗り分けることで，定理の証明は次の命題に帰着できます．

命題．正 $N$ 角形の頂点を $n(\geq 2)$ 色に塗り分けたとき，色 $i$ の点全体が正 $c_i$ 角形をなしていたとする．このとき $c_1\leq \dots\leq c_n$ とすると $c_1=c_2$ である．

問題の $N$ 角形の頂点を複素数平面上の $z^N-1=0$ の解全体と同一視します．このとき色 $i$ の点全体は正 $c_i$ 角形をなしているので，ちょうど $z^{c_i}-\alpha_i=0$ （ $\alpha_i$ は $|\alpha_i|=1$ なる複素数）の解全体に対応しています．よって次の式が成り立ちます：

$z^N-1=\displaystyle\prod_{i=1}^n(z^{c_i}-\alpha_i).$

ここで $c_1\leq \dots\leq c_n$ かつ $c_1\neq c_2$ と仮定すると，上式右辺を展開した式の $z^{c_1}$ の係数は $(-1)^{n-1}\alpha_2\alpha_3\dots\alpha_n\neq 0$ ですが，左辺の $z^{c_1}$ の係数は0なので矛盾しており，これで命題が示されました．

フィボナッチ・フリーク

数学の小ネタ集。

整数全体の等差数列への分割に関するMirsky–Newmanの定理