制限された合計セット

加法的な整数論と組合せ論では、制限された和集合は次の形式を持つ。

${\displaystyle S=\{a_{1}+\cdots +a_{n}:\ a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}\ \mathrm {and} \ P(a_{1},\ldots ,a_{n})\not =0\},}$

ここで、 は体Fの有限の空でない部分集合であり、 はF上の多項式です。 ${\displaystyle A_{1},\ldots ,A_{n}}$ ${\displaystyle P(x_{1},\ldots ,x_{n})}$

が定数非ゼロ関数である場合、例えば任意の に対して、 は通常の和集合であり、の場合、で表される。${\displaystyle P}$${\displaystyle P(x_{1},\ldots ,x_{n})=1}$${\displaystyle x_{1},\ldots ,x_{n}}$${\displaystyle S}$ ${\displaystyle A_{1}+\cdots +A_{n}}$${\displaystyle nA}$${\displaystyle A_{1}=\cdots =A_{n}=A.}$

いつ

${\displaystyle P(x_{1},\ldots ,x_{n})=\prod _{1\leq i<j\leq n}(x_{j}-x_{i}),}$

Sは次のように書かれ、${\displaystyle A_{1}\dotplus \cdots \dotplus A_{n}}$${\displaystyle n^{\wedge }A}$${\displaystyle A_{1}=\cdots =A_{n}=A.}$

| S | > 0となるのは、${\displaystyle a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}}$${\displaystyle P(a_{1},\ldots ,a_{n})\not =0.}$

コーシー・ダベンポートの定理は、オーギュスタン・ルイ・コーシーとハロルド・ダベンポートにちなんで名付けられ、素数 pと素数位数巡回群の空でない部分集合AとBに対して、不等式^{[1] [2] [3]}が成り立つことを主張する。 ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$

${\displaystyle |A+B|\geq \min\{p,\,|A|+|B|-1\}}$

ここで、つまりモジュラー算術を使用しています。これは、ダイソン変換を使用して任意の（必ずしもアーベルではない）グループに一般化できます。がグループの部分集合である場合、^[4]${\displaystyle A+B:=\{a+b{\pmod {p}}\mid a\in A,b\in B\}}$${\displaystyle A,B}$${\displaystyle G}$

${\displaystyle |A+B|\geq \min\{p(G),\,|A|+|B|-1\}}$

ここで、 はの最小の非自明なサブグループのサイズです(そのようなサブグループが存在しない場合は に設定します)。${\displaystyle p(G)}$${\displaystyle G}$${\displaystyle 1}$

これを使ってエルデシュ・ギンツブルグ・ジフの定理を導くことができます。巡回群の2 n −1 個の元の列が与えられたとき、 nを法として合計がゼロになるn個の元が存在します。（ここでn は素数である必要はありません。）^{[5] [6]}${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

コーシー・ダベンポートの定理の直接的な帰結は、p −1 個以上の非ゼロ要素（必ずしも相異する必要はない）の任意のシーケンスSが与えられたとき、 のすべての要素はSの何らかの部分シーケンス（空の場合もある）の要素の和として表すことができる、ということである。^[7]${\displaystyle \mathbb {Z} /p\mathbb {Z} }$${\displaystyle \mathbb {Z} /p\mathbb {Z} }$

クネザーの定理はこれを一般アーベル群に一般化します。^[8]

1964年にポール・エルデシュ とハンス・ハイルブロンが提唱したエルデシュ・ハイルブロン予想は^、pが素数でAが体Z / p Zの空でない部分^集合で ある 場合に、${\displaystyle |2^{\wedge }A|\geq \min\{p,\,2|A|-3\}}$

${\displaystyle |n^{\wedge }A|\geq \min\{p(F),\ n|A|-n^{2}+1\},}$

ここで、A は体Fの有限な空でない部分集合であり、p ( F ) はFが標数pのとき素数pであり、Fが標数 0 のときp ( F ) = ∞ である。この結果の様々な拡張は、1996 年にNoga Alon、 MB Nathanson 、I. Ruzsaによって、^[11] 2002 年にQH Hou とZhi-Wei Sunによって、^[12] 2004 年に G. Karolyiによって与えられた^。[13]

様々な制限和集合の濃度の下限を研究するための強力なツールは、次の基本原理である、組合せ論的零点定理です。^{[14] を}体 上の多項式とします。における単項式の係数がゼロでなく、の全次数であるとします。が に対してとなるの有限部分集合である場合、となるようなが存在します。 ${\displaystyle f(x_{1},\ldots ,x_{n})}$${\displaystyle F}$ ${\displaystyle x_{1}^{k_{1}}\cdots x_{n}^{k_{n}}}$${\displaystyle f(x_{1},\ldots ,x_{n})}$${\displaystyle k_{1}+\cdots +k_{n}}$${\displaystyle f(x_{1},\ldots ,x_{n})}$${\displaystyle A_{1},\ldots ,A_{n}}$${\displaystyle F}$${\displaystyle |A_{i}|>k_{i}}$${\displaystyle i=1,\ldots ,n}$${\displaystyle a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}}$${\displaystyle f(a_{1},\ldots ,a_{n})\not =0}$

このツールは、1989年のN. AlonとM. Tarsiの論文^[15]に端を発し 、1995～1996年にAlon、Nathanson、Ruzsaによって開発され^[11] 、1999年にAlonによって再定式化されました^[14]。

• 組合せ論における多項式法

• Geroldinger, Alfred; Ruzsa, Imre Z. 編 (2009)。組合せ数論と加法群論。バルセロナの数学 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。ISBN 978-3-7643-8961-1.ZBL1177.11005  。​
• ナサンソン、メルヴィン B. (1996)。加法数論: 逆問題と和集合の幾何学。数学の大学院テキスト。第 165 巻。Springer - Verlag。ISBN 0-387-94655-1.ZBL0859.11003  。​

• ワイスタイン、エリック・W.「エルデシュ・ハイルブロン予想」。マスワールド。