エルデシュ・セメレディ定理

算術的組合せ論において、エルデシュ・セメレディの定理は、整数の有限集合 Aに対して、集合A + AとA · A (それぞれ、ペアワイズ和とペアワイズ積の集合) の少なくとも 1 つは、それよりもかなり大きな集合を形成することを述べています。より正確には、エルデシュ・セメレディの定理は、任意の空でない集合A ⊂ ℕに対して、 正の定数cとε が存在し、

${\displaystyle \max(|A+A|,|A\cdot A|)\geq c|A|^{1+\epsilon }}$。

これは1983年にポール・エルデシュとエンドレ・セメレディによって証明されました。^[1] 表記法| A |は集合Aの濃度を表します。

ペアワイズ和の集合はA + A = { a + b  : a , b ∈ A }であり、 Aの和集合と呼ばれます。

対積の集合はA · A = { a · b  : a , b ∈ A }であり、 Aの積集合と呼ばれます。AAとも表記されます。

この定理は、加法構造と乗法構造は共存できないという格言の一種である。また、実数直線には有限部分環や有限部分体に似た集合が含まれないという主張とも見ることができる。これは、現在では和積現象として知られている現象の最初の例であり、有限体を含むさまざまな環や体で成り立つことが知られている。^[2]

和積予想は、非公式には、任意の集合の和集合または積集合のいずれかが可能な限り大きくなければならないというものである。これはもともと、Aが整数、実数、複素数のいずれの集合であるかを予想するために1974年にエルデシュによって提唱されたものである。^[3] より正確には、任意の集合A ⊂ ℂに対して、

${\displaystyle \max(|A+A|,|AA|)\geq |A|^{2-o(1)}.}$

o (1)表記における漸近パラメータは| A |である。

A = {1, 2, 3, ..., n }のとき、漸近記法を用いて| A + A | = 2| A | − 1 = O (| A |)となり、| A |は漸近パラメータとなる。非公式には、これはAの和集合は増加しないことを意味する。一方、Aの積集合は、すべてのε > 0に対して| A ·​​ A | ≥ | A | ^{2 − ε}という形式の境界を満たす。これはエルデシュの乗算表問題と関連している。^{[4]この集合に対する}| A ·​​ A |の最良の下限値はKevin Fordによるものである。^[5]

この例は、ジェルジ・エレケスとイムレ・Z・ルザの和積問題^[6]の「和は少なく、積は多い」問題の一例である。彼らの結果の帰結として、等差数列のような小さな加法倍加を持つ任意の集合は、積集合の下限が| AA | = Ω(| A | ² log ⁻¹ (| A |))となる。Xu と Zhou は、^{指数がo (1) まで鋭い整数の等差数列の任意の稠密部分集合 A に対して、| AA | = Ω(| A | 2 log 1−2log(2)− o (1)} ( | A | ) )である^ことを^証明した[ 7 ]。

逆に、集合B = {2, 4, 8, ..., 2 ⁿ } は| BB | = 2| B | − 1を満たしますが、和が多数あります: 。この境界は、数の2進表現を考慮することから来ています。集合B は等比数列の例です。 ${\displaystyle |B+B|={\binom {|B|+1}{2}}}$

n個の数値のランダムな集合の場合、積集合と和集合の両方に濃度があります。つまり、高い確率で、和集合も積集合も重複要素を生成しません。 ${\displaystyle {\binom {n+1}{2}}}$

エルデシュとセメレディは、十分に滑らかな整数集合Aの例を示しており、その境界は

${\displaystyle \max\{|A+A|,|A\cdot A|\}\leq |A|^{2}e^{-{\frac {c\log |A|}{\log \log |A|}}}}$^[1 ]

これは、予想における o (1)項が必須であることを示している。

次のような仮説の極端なケースがよく研究されています。

• 和は少ないが積は多い（FSMP）： | A + A | ≪ | A |ならば、| AA | ≥ | A | ^{2− o (1)}、^[6]であり、
• 積は少ないが和は多い（FPMS）：| AA | ≪ | A |ならば| A + A | ≥ | A | ^{2− o (1)}。^[8]

次の表は、実数上の積和問題に関する進捗状況をまとめたものです。ジェルジ・エレケスの指数 1/4 とヨジェフ・ソリモシの指数 1/3は、引用文献の中では画期的な成果とみなされています。2009 年以降のすべての改善は、次の形式です。1/3⁠ + cであり、コニャギンとシュクレドフの議論の改良版である。 ^[9]

セメレディ・トロッター定理のみを用いた証明法は、トートの定理によりℂ ²上でセメレディ・トロッター定理が成り立つため、自動的に複素数にも拡張される。 ^[20] KonyaginとRudnev ^[21]は、複素数上の4/3の指数を一致させた。指数が次の形式の結果は、⁠4/3⁠ + c は複素数では一致していません。

和積問題は、特に有限体上でよく研究されている。有限体カケヤ予想に触発されて、ウォルフは、任意の部分集合A ⊆ 𝔽 _p（pは（大きな）素数）に対して、絶対定数ε > 0に対してmax(| A + A |, | AA |) ≥ min( p , | A | ^{1+ ε} )が成り立つと予想した。この予想は、1990年代にウィグダーソン^{[22]によっても、}乱数抽出器に触発されて定式化されていた。

次の例により、和積問題は有限体では無条件に成立しないことに注意してください。

例: 𝔽 を有限体とし、 A = 𝔽 とします。すると、 𝔽 は加算と乗算に対して閉じているので、 A + A = AA = 𝔽となり、| A + A | = | AA | = | 𝔽 |となります。この異常な例は、 A を問題の体の任意の部分体とすること にまで拡張されます。

定性的には、積和問題は有限体上で解かれています。

定理（Bourgain、Katz、Tao （ 2004））：^[23] pを素数とし、A⊂𝔽pでpδ < | ^A | < _p1 ^{− δ}（0< δ <1）とする。このときmax(| A + A |,| AA |)≥cδ | _A | 1 + ^{ε （} ε = ε ( δ ) >0）となる。

Bourgain、Katz、Tao はこの定理を任意の体に拡張しました。非公式には、次の定理は、十分に大きな集合が加算または乗算によって増加しない場合、その集合は主に部分体の拡大体に含まれることを示しています。

定理 (Bourgain, Katz, Tao (2004)): ^[23] A を有限体𝔽の部分集合とし、ある0 < δ < 1に対して| A | > | 𝔽 | ^δとし、| A + A |, | AA | ≤ K | A |とする。すると、部分体G ⊂ 𝔽で| G | ≤ K ^{C _δ} | A |、元x ∈ 𝔽 \ {0}、集合X ⊂ 𝔽で| X | ≤ K ^{C _δ}が存在し、 A ⊆ xG ∪ Xとなる。

彼らは、定数C _{δ は}δとは無関係である可能性があることを示唆しています。

𝔽における有限体積和問題に対する定量的な結果は、通常、 A ⊂ 𝔽が𝔽の特性に対して小さい場合と大きい場合の2つのカテゴリに分類されます。これは、それぞれの設定で異なるタイプの手法が使用されるためです。

この領域では、𝔽 を特性pの体とします。体は常に有限であるとは限らないことに注意してください。この場合、𝔽の特性がゼロであれば、p制約は省略されます。

素数でない順序を持つ体では、A ⊂ 𝔽のp制約は、 A がどの部分体ともあまり大きな交差を持たないという仮定に置き換えることができる。この方向での最も優れた研究は、Li と Roche-Newton ^[30]によるもので、δ = ⁠の指数を達成した。1/19⁠上記の表の表記では。

pが素数であるとき𝔽 = 𝔽 _pのとき、和積問題はガラエフの次の結果により解決されているとみなされる: ^[31]

定理 (Garaev (2007)): A ⊂ 𝔽 _pとします。このとき、max(| A + A |, | AA |) ≫ min( p ^1/2 | A | ^1/2 , | A | ² p ^−1/2 )となります。

これは| A | ≥ p ^2/3の範囲で最適です。

^{この結果は2011年にVinh [32]}によって非素数位数の有限体に拡張された。

ブルガンとチャンは、十分な和または積を考慮する限り、 集合A ⊆ ℤの無条件成長を証明しました。

定理（Bourgain, Chang（2003））：^[33] b ∈ ℕとする。するとk ∈ ℕが存在し、すべてのA ⊆ ℤに対して、max(| kA |, | A ^{( k )} |) = max(| A + A + ⋯ + A |, | A ·​​ A · ⋯ ​​· A |) ≥ | A | ^bが成り立つ。

多くの研究において、加算と乗算は 1 つの式に結合されています。加算と乗算は共存できないというモットーにより、集合の加算と乗算の任意の非自明な組み合わせは成長を保証すると予想されます。有限の設定、または非自明なサブフィールドを持つフィールドでは、このようなステートメントにはさらなる制約が必要になることに注意してください。

興味のあるセットには以下が含まれます（ A ⊂ ℝの結果）。

• AA + A : スティーブンスとウォーレン^[34]は、 | AA + A | ≫ | A | ^{⁠ で}あることを示している^{3/2⁠ + ⁠3/170⁠ − o (1)}
• A ( A + A ) : マーフィー、ロッシュニュートン、シュクレドフ^[35]は、 | A ( A + A ) | ≫ | A | ^⁠であることを示している^{3/2⁠ + ⁠5/242⁠ − o (1)}
• A ( A + 1) : スティーブンスとウォーレン^[34]は、 | A ( A + 1) | ≫ | A | ^{⁠ で}あることを示している^{49/38⁠ − o (1)}
• AA + AA : StevensとRudnev ^[19]は、 | AA + AA | ≫ | A | ^{⁠ で}あることを示している^{127/80⁠ − o (1)}

• サムフリーセット
• 制限された合計セット
• 加法的な組み合わせ論
• 加法数論
• 乗法数論

• ハートネット、ケビン（2019年2月6日）。「奇妙なグリッドが単純な数字間の隠れたつながりを明らかにする方法」Quanta Magazine。