ゼロサム問題

数論において、ゼロ和問題とは有限アーベル群の構造に関するある種の組合せ問題である。具体的には、有限アーベル群Gと正の整数nが与えられたとき、サイズkのGの要素のすべてのシーケンスにn 個の項が含まれ、その合計が0になるようなkの最小値を求める問題である。

この分野における古典的な結果は、1961年にポール・エルデシュ、アブラハム・ギンツブルグ、アブラハム・ジブが証明した定理である。^{[1]彼らは、} nを法とする整数 群に対して、 ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

$${\displaystyle k=2n-1.}$$

明示的には、これは2 n − 1 個の整数の多重集合には、その要素の和がnの倍数となるサイズnの部分集合が存在するが、サイズ 2 n − 2の多重集合には同じことが当てはまらないことを示しています。(実際、下限は簡単にわかります。0のn − 1 個のコピーと1 の n − 1 個のコピーを含む多重集合には、和が n の倍数となる n 部分集合は含まれません。)この結果は、発見者にちなんでエルデシュ・ギンツブルグ・ジフの定理として知られています。また、コーシー・ダベンポートの定理から演繹することもできます。^[2]

この定理よりも一般的な結果としては、オルソンの定理、 ケムニッツの予想（2003年にクリスチャン・ライハーによって証明された^[3]）、重み付きEGZ定理（2005年にデビッド・J・グリンキエヴィッチによって証明された^[4]）などがあります。

• ダベンポート定数
• 部分集合の和の問題
• ゼロサムラムゼー理論

• Geroldinger, Alfred (2009)。「加法群論と非一意因数分解」。Geroldinger, Alfred、Ruzsa, Imre Z. (編著)。組合せ数論と加法群論。バルセロナの数学 CRM 上級コース。Elsholtz, C.; Freiman, G.; Hamidoune, YO; Hegyvári, N.; Károlyi, G.; Nathanson, M.; Solymosi, J .; Stanchescu, Y. Javier Cilleruelo、Marc Noy、Oriol Serra (DocCourse コーディネーター) による序文付き。バーゼル: Birkhäuser。pp. 1–86。ISBN 978-3-7643-8961-1.ZBL1221.20045  。​
• ナサンソン、メルヴィン B. (1996)。加法数論：逆問題と和集合の幾何学。数学大学院テキスト。第 165 巻。Springer - Verlag。ISBN 0-387-94655-1.ZBL0859.11003  。​

• 「エルデシュ-ギンツブルグ-ジフの定理」、数学百科事典、EMS Press、2001 [1994]
• PlanetMath エルデシュ、ギンツブルク、ジヴの定理
• 孫 志偉、「被覆システム、制限和集合、ゼロ和問題とその統一」

• ゼロサム問題 - 調査 (オープンアクセスジャーナル記事)
• ゼロサム・ラムゼー理論: グラフ、シーケンス、その他 (ワークショップのホームページ)
• Arie Bialostocki、「ゼロ和ツリー: 結果と未解決の問題の調査」NW Sauer (編)、RE Woodrow (編)、B. Sands (編)、集合と論理における有限および無限の組合せ論、Nato ASI Ser.、Kluwer Acad. Publ. (1993) pp. 19–29
• Y. Caro、「ゼロ和問題：概要」、離散数学、152（1996）pp.93-113