Erdős–Ginzburg–Zivの定理
概要
Erdős–Ginzburg–Zivの定理（Erdős–Ginzburg–Ziv theorem）とは、$n\ge1$ について、任意の $2n-1$ 個の整数の中から和が $n$ で割り切れる $n$ 個を選べるという加法的整数論の定理である。$n$ が素数 $p$ のときは、$\mathbb{F}_p$ 上の 2 本の多項式に Chevalley–Warning の定理を当てて示し、和が $0$ の $p$ 個の選び方の個数が $p$ を法として $1$ であることまで分かる。主張は積について閉じているので一般の $n$ に及び、同じ議論で位数 $n$ の有限アーベル群でも成り立つ。$0$ と $1$ を $n-1$ 個ずつ並べた $2n-2$ 個では成り立たない。
前提知識: 合同式, 有限体, Chevalley–Warningの定理
整数をいくつか並べたとき、その中から和が $n$ で割り切れるものを選べるか。選ぶ個数を問わなければ、$n$ 個の整数があれば十分である（鳩の巣原理 の命題「連続する項の和の整除」）。ところが「ちょうど $n$ 個を選ぶ」と個数を指定すると、必要な整数の個数は $2n-1$ に増える。これが Erdős–Ginzburg–Ziv の定理（1961 年）であり、加法的整数論で「和が $0$ になる部分列」を調べる零和問題の代表的な定理である。
証明は 2 段に分かれる。$n$ が素数 $p$ のときは、有限体 $\mathbb{F}_p$ 上の 2 本の多項式に Chevalley–Warningの定理 を当てる。一般の $n$ は、主張が積について閉じていること（$m$ と $n$ で成り立てば $mn$ でも成り立つこと）から素数の場合に帰着する。同じ議論は有限アーベル群の上でもそのまま通る。$2n-1$ を $2n-2$ に減らせないことも簡単な例で分かる。
主張
以下、「$k$ 個の整数 $a_1,\dots,a_k$」は重複を許す並びとし、「その中から $n$ 個を選ぶ」とは、相異なる添字 $i_1,\dots,i_n$ を選ぶことをいう。同じ値の整数が何度現れてもよいが、1 つの項を 2 回使うことはできない。
$n\ge1$ を整数とする。任意の $2n-1$ 個の整数 $a_1,\dots,a_{2n-1}$ の中から、和が $n$ で割り切れる $n$ 個を選べる。
証明は prf-egz-group で、次の 3 つを組み合わせる。素数 $p$ の場合は、$\mathbb{F}_p$ 上の多項式の共通零点の個数を Chevalley–Warningの定理 で数える（thm-egz-prime）。部分群と商群の両方で主張が成り立てば全体でも成り立つ（lem-egz-extension）。有限アーベル群は、素数位数の商を 1 つずつはがしていくと自明群に達する。
整数を $n$ で割った余りだけが問題なので、これは 合同式 の言葉で、$\mathbb{Z}/n\mathbb{Z}$ の元の並び $2n-1$ 個から和が $0$ になる $n$ 個を選べる、という主張である。$\mathbb{Z}/n\mathbb{Z}$ を一般の有限アーベル群に取り替えても同じことが成り立つ。
$G$ を位数 $n$ の有限アーベル群とし、演算を加法で書く。$G$ の元の任意の並び $g_1,\dots,g_{2n-1}$（重複を許す）に対し、相異なる添字 $i_1,\dots,i_n$ で
$$
g_{i_1}+\dots+g_{i_n}=0
$$
となるものがある。
thm-egz-main は thm-egz-group の $G=\mathbb{Z}/n\mathbb{Z}$ の場合である。実際、整数 $a_1,\dots,a_{2n-1}$ の $n$ を法とする類 $\bar a_i\in\mathbb{Z}/n\mathbb{Z}$ に thm-egz-group を当てると、相異なる添字 $i_1,\dots,i_n$ で $\bar a_{i_1}+\dots+\bar a_{i_n}=0$、すなわち $n\mid a_{i_1}+\dots+a_{i_n}$ となるものが得られる。どちらの $2n-1$ も最小である（prop-egz-sharp とその後の注意）。
直感
なぜ $2n-1$ 個なのかは、反対側から見ると分かりやすい。和が $n$ で割り切れる $n$ 個を選べない並びを作ろうとすると、同じ余りを $n$ 個そろえてはいけないので、各余りは $n-1$ 回までしか使えない。余りを $0$ と $1$ の 2 種類だけにして $n-1$ 個ずつ並べると、どう選んでも和は $1$ 以上 $n-1$ 以下になる（prop-egz-sharp）。定理は、余りの種類をどう工夫しても、この $2n-2$ 個より長い並びは作れないと言っている。
素数 $p$ の場合の証明は、「添字の集合 $I$ を選ぶ」ことを「$x_i\neq0$ となる $i$ の集合が $I$ である点 $x\in\mathbb{F}_p^{\,2p-1}$ を選ぶ」ことに読み替える。$x_i^{p-1}$ は $x_i\neq0$ かどうかを $1,0$ で表すので、$I$ の大きさと $I$ の上の和が 2 本の多項式の値として書ける。変数が $2p-1$ 個あるのに次数の和は $2p-2$ なので、Chevalley–Warning の定理が使える。
- $n=2$：3 個の整数のうち 2 個は偶奇が等しく、その和は偶数である。2 個（たとえば $0,1$）では成り立たない。
- $n=3$：5 個の整数を 3 で割った余りを見る。ある余りが 3 回以上現れればその 3 個を選ぶ。そうでなければ各余りは 2 回以下で、5 個なので 3 種類の余り $0,1,2$ がすべて現れ、1 個ずつ選ぶと和 $0+1+2=3$ は 3 で割り切れる。
- $n=4$：$0,0,0,1,1,1,2$ の 7 個からは $0+1+1+2=4$ が選べる。$0,0,0,1,1,1$ の 6 個では、4 個を選ぶとどれも $0$ と $1$ を少なくとも 1 個ずつ含み、和は $1,2,3$ のどれかで 4 で割り切れない。
証明
素数の場合
素数 $p$ について、有限体 $\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$ の元 $x$ は、$x\neq0$ なら $x^{p-1}=1$、$x=0$ なら $x^{p-1}=0$ を満たす（Fermatの小定理）。この「$0$ かどうかを判定する冪」を使うと、「$p$ 個を選んで和を $0$ にする」という条件を多項式の零点で表せる。証明から、選び方の個数についての合同式まで出てくる。
$p$ を素数とし、$a_1,\dots,a_{2p-1}\in\mathbb{F}_p$ とする。$p$ 元の添字集合 $I\subset\{1,\dots,2p-1\}$ で $\sum_{i\in I}a_i=0$ となるものの個数を $N$ とすると、
$$
N\equiv1\pmod p
$$
である。とくに $N\ge1$ であり、$a_1,\dots,a_{2p-1}$ の中から和が $0$ の $p$ 個を選べる。
$\mathbb{F}_p$ 上の $2p-1$ 変数の多項式
$$
f_1=\sum_{i=1}^{2p-1}x_i^{\,p-1},\qquad f_2=\sum_{i=1}^{2p-1}a_ix_i^{\,p-1}
$$
を考える。$\deg f_1=p-1$、$\deg f_2\le p-1$ なので、次数の和は $2p-2$ 以下で、変数の個数 $2p-1$ より小さい。共通零点の集合を $V\subset\mathbb{F}_p^{\,2p-1}$ とすると、Chevalley–Warningの定理 の定理「Chevalley–Warningの定理」により $\lvert V\rvert$ は $p$ で割り切れる。
$x\in\mathbb{F}_p^{\,2p-1}$ の台を $I(x):=\{i\mid x_i\neq0\}$ とする。$x_i^{p-1}$ は $i\in I(x)$ なら $1$、それ以外なら $0$ なので、
$$
f_1(x)=\lvert I(x)\rvert\cdot1,\qquad f_2(x)=\sum_{i\in I(x)}a_i
$$
である。したがって $x\in V$ であるのは、$\lvert I(x)\rvert$ が $p$ で割り切れ、かつ $\sum_{i\in I(x)}a_i=0$ のときに限る。$0\le\lvert I(x)\rvert\le2p-1<2p$ なので、$\lvert I(x)\rvert$ は $0$ か $p$ である。
台が $\emptyset$ の点は $x=0$ の 1 つだけである。台が与えられた $p$ 元集合 $I$ に等しい点は、$i\in I$ の座標を $\mathbb{F}_p^\times$ から自由に選んで $(p-1)^p$ 個ある。よって
$$
\lvert V\rvert=1+N\,(p-1)^p
$$
である。$(p-1)^p\equiv(-1)^p\equiv-1\pmod p$ である（$p$ が奇数なら $(-1)^p=-1$、$p=2$ なら $1\equiv-1\pmod 2$）。$\lvert V\rvert\equiv0\pmod p$ と合わせて $1-N\equiv0\pmod p$、すなわち $N\equiv1\pmod p$ を得る。$\square$
Chevalley–Warningの定理 の節「Erdős–Ginzburg–Ziv の定理」の証明は、同じ 2 本の多項式に、自明でない共通零点の存在（同じ記事の系「Chevalley の定理」）を当てている。上の証明は解の個数の合同式そのものを使うので、選び方が少なくとも 1 つあるだけでなく、その個数が $p$ を法として $1$ であることまで分かる。
$p=3$、並び $0,0,1,1,2$ を考える。和が $3$ で割り切れる 3 個の選び方は、$0$ を 1 個（2 通り）、$1$ を 1 個（2 通り）、$2$ を選ぶ $2\cdot2=4$ 通りである。同じ余りを 3 個そろえる選び方はない（どの余りも 2 回以下）。$N=4\equiv1\pmod3$ で、thm-egz-prime と合っている。
素数の場合には、ほかに Cauchy–Davenportの定理 の記事の定理「Erdős–Ginzburg–Zivの定理（素数の場合）」の証明（2 元集合の和の大きさを使う）と、Alo99 Proposition 8.2 の永久式（パーマネント）の補題による証明がある。
積について閉じていること
一般の $n$ への移行は、部分群と商群に分けて行う。
$G$ を有限アーベル群、$H$ をその部分群とし、$k:=\lvert G/H\rvert$、$m:=\lvert H\rvert$ とおく。商群 $G/H$ と $H$ の両方で thm-egz-group の主張が成り立てば、$G$ でも成り立つ。
$\lvert G\rvert=km$ である（Lagrangeの定理）。$G$ の元の並び $g_1,\dots,g_{2km-1}$ をとり、$\pi\colon G\to G/H$ を商写像とする。
取り出し． 残っている項が $2k-1$ 個以上ある限り、そのうち $2k-1$ 個の $\pi$ による像に $G/H$ での主張を当てると、$\pi$ の像の和が $0$ になる $k$ 個、すなわち和が $H$ に入る $k$ 個がある。これを取り除く。$j$ 組を取り除いたあとの残りは $2km-1-jk$ 個で、これが $2k-1$ 以上であるのは $j\le2m-2$ のときである。よって、互いに交わらない $k$ 元の添字集合 $T_1,\dots,T_{2m-1}$ で、和 $h_j:=\sum_{i\in T_j}g_i$ がすべて $H$ に入るものが得られる。
和を選ぶ． $H$ の元の並び $h_1,\dots,h_{2m-1}$ に $H$ での主張を当てると、相異なる $j_1,\dots,j_m$ で $h_{j_1}+\dots+h_{j_m}=0$ となるものがある。$T:=T_{j_1}\cup\dots\cup T_{j_m}$ は互いに交わらない $k$ 元集合 $m$ 個の和集合なので $km$ 個の添字からなり、
$$
\sum_{i\in T}g_i=h_{j_1}+\dots+h_{j_m}=0
$$
である。$\square$
$G=\mathbb{Z}/km\mathbb{Z}$、$H=k\mathbb{Z}/km\mathbb{Z}\cong\mathbb{Z}/m\mathbb{Z}$（$G/H\cong\mathbb{Z}/k\mathbb{Z}$）とすると、lem-egz-extension は「thm-egz-main が $k$ と $m$ で成り立てば $km$ でも成り立つ」という整数の言葉の乗法性になる。整数で言い直すと、$2km-1$ 個から和が $k$ で割り切れる $k$ 個組を $2m-1$ 組取り出し、各組の和を $k$ で割った商 $2m-1$ 個に $m$ での主張を当てる、という議論である。
$k=2$、$m=3$ として、11 個の整数 $1,1,1,1,1,1,2,2,3,4,5$ から和が $6$ で割り切れる 6 個を選ぶ。
- 偶奇で 2 個ずつ取り出す． 和が偶数の 2 個組を、残りが 3 個以上ある限り取り出す。たとえば $\{1,1\},\{1,1\},\{1,1\},\{2,2\},\{3,5\}$ の 5 組がとれ、$4$ が残る。各組の和は $2,2,2,4,8$ である。
- 商に 3 での主張を当てる． 和を $2$ で割った商は $1,1,1,2,4$ の 5 個である。3 で割った余りは $1,1,1,2,1$ なので、余り $1$ の 3 個（たとえば $1,1,1$）の和 $3$ が 3 で割り切れる。
- 組を合わせる． 対応する 3 組 $\{1,1\},\{1,1\},\{1,1\}$ を合わせた 6 個の和は $6$ で、$6$ で割り切れる。
商の選び方を $1,1,4$（余り $1,1,1$）にすれば、組 $\{1,1\},\{1,1\},\{3,5\}$ から和 $12$ の 6 個が得られる。取り出し方や選び方は一通りではないが、どの段でも主張が保証する範囲の個数が残っている。
一般の場合
$\lvert G\rvert=n$ についての帰納法で thm-egz-group を示す。$n=1$ なら $G=\{0\}$ で、1 個の項 $g_1=0$ を選べばよい。
$n\ge2$ とする。$G$ の真の部分群のうち位数が最大のもの $H$ をとる（$\{0\}$ は真の部分群なので存在する）。$G/H$ の部分群は $H$ を含む $G$ の部分群と対応し、$H$ の取り方からそれは $H$ と $G$ だけなので、$G/H$ には自明でない真の部分群がない。$H\neq G$ なので $G/H\neq\{0\}$ で、その元 $x\neq0$ をとると、$x$ が生成する巡回群は $G/H$ 全体で、その位数 $d\ge2$ が合成数 $d=ab$（$1< a< d$）なら $ax$ が生成する部分群は位数 $b$ の真の部分群になって矛盾する。よって $G/H$ は素数位数 $p$ の巡回群で、加法群として $\mathbb{F}_p$ と同型であり、thm-egz-prime により $G/H$ で主張が成り立つ。$\lvert H\rvert=n/p< n$ なので、帰納法の仮定により $H$ でも成り立つ。lem-egz-extension により $G$ で成り立つ。$\square$
$G=\mathbb{Z}/n\mathbb{Z}$ とすれば thm-egz-main が従う。$n$ の素因数分解 $n=p_1p_2\cdots p_s$ に沿って、$\mathbb{Z}/n\mathbb{Z}\supset p_1\mathbb{Z}/n\mathbb{Z}\supset p_1p_2\mathbb{Z}/n\mathbb{Z}\supset\cdots$ と 1 段ずつ素数の場合を積み上げている、と見てもよい。
$2n-1$ が最小であること
$n\ge1$ とする。$0$ を $n-1$ 個、$1$ を $n-1$ 個並べた $2n-2$ 個の整数からは、和が $n$ で割り切れる $n$ 個を選べない。
$n=1$ なら並びは空で、1 個も選べない。$n\ge2$ とし、$n$ 個を選んだとき、その中の $1$ の個数を $j$ とする。$0$ も $1$ も $n-1$ 個しかないので $j\le n-1$ かつ $n-j\le n-1$、すなわち $1\le j\le n-1$ である。和は $j$ なので $n$ で割り切れない。$\square$
同じ構成は位数 $n$ の巡回群 $G$ では、$G$ の生成元 $g$ と $0$ を $n-1$ 個ずつ並べた並びになり、$j g\neq0$（$1\le j\le n-1$）から thm-egz-group の $2n-1$ も最小である。
仮定を外したときの反例
thm-egz-group の条件を 1 つずつ変えると、次のように結論が成り立たなくなる。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 並びの長さが $2n-1$（$2n-2$ にする） | $\mathbb{Z}/n\mathbb{Z}$ の $0$ と $1$ を $n-1$ 個ずつ（prop-egz-sharp） | 和が $0$ の $n$ 項の存在 |
| 選ぶ項数 $n$ が群の位数（元の位数の最大値 $e$ に替え、長さ $2e-1$ から $e$ 項を選ぶ） | $G=(\mathbb{Z}/e\mathbb{Z})^2$（$e\ge2$）の $(0,0),(1,0),(0,1),(1,1)$ を $e-1$ 個ずつ並べた $4e-4$ 項（$4e-4\ge2e-1$） | 和が $0$ の $e$ 項の存在 |
1 行目は prop-egz-sharp である。2 行目：$G$ の元の位数は $e$ 以下で、$(1,0)$ の位数が $e$ なので最大値は $e$ である。$e$ 項を選び、$(0,0),(1,0),(0,1),(1,1)$ を選んだ個数を $c_{00},c_{10},c_{01},c_{11}$（それぞれ $e-1$ 以下）とする。和が $0$ なら $c_{10}+c_{11}$ と $c_{01}+c_{11}$ はともに $e$ の倍数で、$0$ 以上 $2e-2$ 以下なので $0$ か $e$ である。両方 $0$ なら $c_{00}=e$、片方だけ $e$ なら（たとえば $c_{10}+c_{11}=e$、$c_{01}+c_{11}=0$）$c_{10}=e$ となり、どちらも $e-1$ 以下に反する。両方 $e$ なら
$$
c_{00}=e-(c_{10}+c_{11})-(c_{01}+c_{11})+c_{11}=c_{11}-e<0
$$
となって矛盾する。よって和が $0$ の $e$ 項はない。$4e-4$ 項から $2e-1$ 項を抜き出しても同じである。
この例が示すように、thm-egz-group で $n$ を群の位数とすることは外せない。$G$ が巡回群なら位数と元の位数の最大値は一致する。
関連する定数
選ぶ個数を指定しなければ、条件はずっと弱くなる。
$n\ge1$ とする。任意の $n$ 個の整数の中から、1 個以上を選んでその和を $n$ で割り切れるようにできる。$n-1$ 個（$1$ を $n-1$ 個）では成り立たない。
前半は 鳩の巣原理 の命題「連続する項の和の整除」（部分和 $s_0=0,s_1,\dots,s_n$ のうち 2 つの余りが等しい）である。後半：$1$ を $j$ 個（$1\le j\le n-1$）選ぶと和は $j$ で、$n$ で割り切れない。$\square$
有限アーベル群 $G$ で、どの長さ $\ell$ の並びも和が $0$ の空でない部分列をもつような最小の $\ell$ を $G$ の Davenport定数 $D(G)$ という。prop-egz-unrestricted は $D(\mathbb{Z}/n\mathbb{Z})=n$ を意味する。Erdős–Ginzburg–Ziv の定理は、部分列の長さを $n$ に固定したときの同じ種類の問いに答えている。
関連項目
- 前提: 合同式, 有限体, Chevalley–Warningの定理, 商群
- 別証明: Cauchy–Davenportの定理, Combinatorial Nullstellensatz
- 比較: Davenport定数, 鳩の巣原理
- 発展: 多項式法
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
