加法的組み合わせ論

加法組合せ論は数学の組合せ論の一分野です。加法組合せ論の主要な研究分野の 1 つは逆問題です。つまり、和集合 $A + B$ のサイズが小さい場合、 $A$ と $B$ の構造について何が言えるでしょうか。整数の場合、古典的なフライマンの定理は、多次元等差数列の観点からこの質問に対する部分的な答えを提供します。

もう 1 つの典型的な問題は、 $| A$ $|$ と $|$ $B$ $|$ に関して $| A$ $+$ $B$ $|の下限値を見つけることです。これは、$ $|$ $A$ $+$ $B$ $|$ が十分に小さいという情報が与えられている場合、逆問題と見なすことができ、構造的な結論は $A$ または $B の$ いずれかが空集合であるという形になります。ただし、文献では、このような問題は直接問題と見なされることもあります。このタイプの例としては、エルデシュ–ハイルブロン予想(制限された和集合の場合) やコーシー–ダベンポートの定理などがあります。このような問題に取り組むために使用される方法は、組合せ論、エルゴード理論、解析学、グラフ理論、群論、線型代数法、多項式法など、さまざまな数学の分野から来ていることがよくあります。

加法組合せ論の歴史

加法的な組合せ論は組合せ論のかなり新しい分野ですが（実際、加法的な組合せ論という用語は、2012 年にTerence TaoとVan H. Vuが著書で作った造語です）、それよりずっと古い問題であるCauchy-Davenport の定理は、この分野における最も基本的な結果の 1 つです。

コーシー・ダベンポートの定理

$A$ と $B が$ 素数 $pに対する$ 巡回群 $ℤ/ p ℤ$ の有限部分集合であるとすると、次の不等式が成り立ちます。

|A+B|\geq \min(|A|+|B|-1,p)

ヴォスパーの定理

和集合 $A + B$ の濃度に関する不等式がわかったので、逆問題、つまり $A$ と $B$ のどのような条件で等式が成り立つのかを問うのは自然なことです。この問いに答えるのは Vosper の定理です。 $| A |,| B | \geq 2$ (つまり、エッジケースを除く) と仮定し、

|A+B|\leq |A|+|B|-1\leq p-2,

すると、 $A$ と $B は$ 同じ差を持つ等差数列になります。これは、加法組合せ論でよく研究される構造、つまり等差数列の代数構造と比較した $A + B$ の組合せ構造を示しています。

プルンネケ・ルザ不等式

加法的な組合せ論における有用な定理は、Plünnecke-Ruzsa 不等式です。この定理は、 $A$ の倍加定数に関して $| nA - mA |$ の濃度の上限を与えます。たとえば、Plünnecke-Ruzsa 不等式を使用すると、有限体におけるフライマンの定理のバージョンを証明できます。

基本的な概念

集合に対する演算

$A$ と $Bを$ アーベル群の有限部分集合とする。すると、和集合は次のように定義される。

A+B=\{a+b:a\in A,b\in B\}.

例えば、 ${1,2,3,4} + {1,2,3} = {2,3,4,5,6,7}と書くことができます。同様に、$ $A$ と $B$ の差集合を次のように定義できます。

AB=\{ab:a\in A,b\in B\}.

集合 $A$ とそれ自身とのk重和集合は次のように表される $。$

kA=\underbrace {A+A+\cdots +A} _{k{\text{ 項 }}}=\{a_{1}+\cdots +a_{k}:a_{1}\in A,\dots ,a_{k}\in A\},

混同してはいけない

k\cdot A=\{ka:a\in A\}.

倍加定数

$A を$ アーベル群の部分集合とする。倍加定数は、和集合が元の大きさ $|$ $A$ $|$ と比較してどれだけ大きいかを表す。A の倍加定数を次のように定義する $。$ $|A+A|$

K={\dfrac {|A+A|}{|A|}}。

ルザ距離

$A$ と $Bを$ アーベル群の2つの部分集合とする。この2つの集合間のルザ距離を次のように定義する。

d(A,B)=\log {\dfrac {|AB|}{\sqrt {|A||B|}}}.

ルザの三角不等式は、ルザ距離が三角不等式に従うことを主張します。

d(B,C)\leq d(A,B)+d(A,C).

しかし、 $d (A, A)は$ ゼロにはならないので、Ruzsa距離は実際にはメトリックではありません。

参照

参考文献

引用

Tao, T., Vu, V. (2012).加法的な組み合わせ論ケンブリッジ: ケンブリッジ大学出版局.
Green, B. (2009 年 1 月 15 日). Additive Combinatorics Book Review. https://www.ams.org/journals/bull/2009-46-03/S0273-0979-09-01231-2/S0273-0979-09-01231-2.pdf から取得。