等差数列に関するロスの定理

等差数列に関するロートの定理は、自然数の部分集合における等差数列の存在に関する加法組合せ論の結果である。1953年にクラウス・ロートによって初めて証明された^。[1]ロートの定理は、の場合のセメレディの定理の特殊ケースである。 ${\displaystyle k=3}$

自然数のサブセットAが正の上密度を持つとは、

${\displaystyle \limsup _{n\to \infty }{\frac {|A\cap \{1,2,3,\dotsc ,n\}|}{n}}>0}$。

等差数列に関するロスの定理 (無限バージョン) : 正の上密度を持つ自然数のサブセットには、3 項等差数列が含まれます。

定理の別の、より定性的な定式化は、のサブセットであるセイラム・スペンサー集合の最大サイズに関するものです。を、3 項等差数列 を含まないの最大のサブセットのサイズとします。${\displaystyle [N]=\{1,\dots ,N\}}$${\displaystyle r_{3}([N])}$${\displaystyle [N]}$

等差数列に関するロスの定理（有限バージョン）：。${\displaystyle r_{3}([N])=o(N)}$

の上限と下限を改善することは、まだ未解決の研究課題です。 ${\displaystyle r_{3}([N])}$

この方向での最初の結果は1927年のファンデルワールデンの定理であり、十分に大きいNに対して、整数を色で着色すると項等差数列が得られることを述べています。 ^[2]${\displaystyle 1,\dots ,n}$${\displaystyle r}$${\displaystyle k}$

その後、1936年にエルデシュとトゥランは、正の密度を持つ整数の任意の部分集合には任意長の等差数列が含まれるという、はるかに強力な結果を予想しました。1942年に、ラファエル・サレムとドナルド・C・スペンサーは、サイズ の3-AP フリー集合（つまり、3項等差数列を持たない集合）の構成を提供し、^[3]エルデシュとトゥランの追加の予想である、ある に対して が成り立つという予想を反証しました。^[4]${\displaystyle {\frac {N}{e^{O(\log N/\log \log N)}}}}$${\displaystyle r_{3}([N])=N^{1-\delta }}$${\displaystyle \delta >0}$

1953 年、ロスはフーリエ解析法を用いて長さ 3 の等差数列を必ず含むことを証明し、当初の予想を部分的に解決しました。最終的に、1975 年にセメレディは組合せ論的手法を用いてセメレディの定理を証明し、当初の予想を完全に解決しました。

ロスによって与えられた最初の証明では、フーリエ解析法が使用されました。後に、セメレディの正則性補題を使用した別の証明が与えられました。

1953 年、ロスはフーリエ解析を使用しての上限を証明しました。以下はこの証明の概略です。 ${\displaystyle r_{3}([N])=O\left({\frac {N}{\log \log N}}\right)}$

関数のフーリエ変換を次の式を満たす 関数と定義する。${\displaystyle f:\mathbb {Z} \rightarrow \mathbb {C} }$${\displaystyle {\ワイドハット {f}}}$

${\displaystyle {\widehat {f}}(\theta )=\sum _{x\in \mathbb {Z} }f(x)e(-x\theta )}$、

どこ。 ${\displaystyle e(t)=e^{2\pi it}}$

を の 3-AP フリー部分集合とします。証明は 3 つのステップで進みます。 ${\displaystyle A}$${\displaystyle \{1,\dots ,N\}}$

1. a が大きなフーリエ係数を持つことを示します。${\displaystyle A}$
2. この部分数列に制限すると密度が増加するような の部分数列が存在することを推論します。${\displaystyle \{1,\dots ,N\}}$${\displaystyle A}$
3. ステップ 2 を繰り返して、 の上限を取得します。${\displaystyle |A|}$

関数については、定義する ${\displaystyle f,g,h:\mathbb {Z} \rightarrow \mathbb {C} ,}$

${\displaystyle \Lambda (f,g,h)=\sum _{x,y\in \mathbb {Z} }f(x)g(x+y)h(x+2y)}$

計数補題 を満たすものとします。 を定義します。すると となります。 ${\displaystyle f,g:\mathbb {Z} \rightarrow \mathbb {C} }$${\displaystyle \sum _{n\in \mathbb {Z} }|f(n)|^{2},\sum _{n\in \mathbb {Z} }|g(n)|^{2}\leq M}$${\displaystyle \Lambda _{3}(f)=\Lambda (f,f,f)}$${\displaystyle |\Lambda _{3}(f)-\Lambda _{3}(g)|\leq 3M\|{\widehat {fg}}\|_{\infty }}$

計数補題は、とのフーリエ変換が「近い」場合、2 つの間の3 項等差数列の数も「近い」はずであることを示しています。を の密度とします。関数(つまり の指示関数)、および を定義します。次に、計数補題をとに適用することでステップ 1 を導き出すことができます。これにより、となるような ものが存在することがわかります。${\displaystyle f}$${\displaystyle g}$${\displaystyle \alpha =|A|/N}$${\displaystyle A}$${\displaystyle f=\mathbf {1} _{A}}$${\displaystyle A}$${\displaystyle g=\alpha \cdot \mathbf {1} _{[N]}}$${\displaystyle f}$${\displaystyle g}$${\displaystyle \theta}$

${\displaystyle \left|\sum _{n=1}^{N}(1_{A}-\alpha )(n)e(\theta n)\right|\geq {\frac {\alpha ^{2}}{10}}N}$。

ステップ 1から、まず、文字が各サブ進行でほぼ一定になる ように、比較的大きなサブ進行に分割できることを示します。${\displaystyle \theta }$${\displaystyle [N]}$${\displaystyle x\mapsto e(x\theta )}$

補題 1:とします。普遍定数 に対して であると仮定します。すると、すべての に対して となる長さの等差数列に分割することが可能です。${\displaystyle 0<\eta <1,\theta \in \mathbb {R} }$${\displaystyle N>C\eta ^{-6}}$${\displaystyle C}$${\displaystyle [N]}$${\displaystyle P_{i}}$${\displaystyle N^{1/3}\leq |P_{i}|\leq 2N^{1/3}}$${\displaystyle \sup _{x,y\in P_{i}}|e(x\theta )-e(y\theta )|<\eta }$${\displaystyle i}$

次に、補題 1 を適用して部分数列への分割を取得します。次に、ステップ 1 で大きな係数が生成されたという事実を使用して、これらの部分数列の 1 つに密度増分が必要であることを示します。 ${\displaystyle \theta }$

補題 2:を の 3-AP フリー部分集合とし、およびとする。このとき、および となるような部分進行が存在する。${\displaystyle A}$${\displaystyle [N]}$${\displaystyle |A|=\alpha N}$${\displaystyle N>C\alpha ^{-12}}$${\displaystyle P\subset [N]}$${\displaystyle |P|\geq N^{1/3}}$${\displaystyle |A\cap P|\geq (\alpha +\alpha ^{2}/40)|P|}$

ここでステップ 2 を繰り返します。 を番目の反復後の の密度とします。および が成り立ちます。まず、最大 ステップ後に が2 倍になる (つまり、となる) ことを確認します。最大 ステップ後に、再び2 倍になります(つまり、 となる) 。 であるため、このプロセスは最大 ステップ後に終了する必要があります。 ${\displaystyle a_{t}}$${\displaystyle A}$${\displaystyle t}$${\displaystyle \alpha _{0}=\alpha ,}$${\displaystyle \alpha _{t+1}\geq \alpha +\alpha ^{2}/40.}$${\displaystyle \alpha }$${\displaystyle T}$${\displaystyle \alpha _{T}\geq 2\alpha _{0}}$${\displaystyle 40/\alpha +1}$${\displaystyle \alpha }$${\displaystyle \alpha _{T}\geq 4\alpha _{0}}$${\displaystyle 20/\alpha +1}$${\displaystyle \alpha \leq 1}$${\displaystyle O(1/\alpha )}$

を反復後の現在の進行の大きさとします。補題2により、いつでもプロセスを続行できるため、プロセスが終了すると次の式が得られます。また、部分進行に移行すると、集合の大きさは立方根だけ減少することに注意してください。したがって、 ${\displaystyle N_{t}}$${\displaystyle t}$${\displaystyle N_{t}\geq C\alpha _{t}^{-12},}$${\displaystyle N_{t}\leq C\alpha _{t}^{-12}\leq C\alpha ^{-12}.}$

${\displaystyle N\leq N_{t}^{3^{t}}\leq (C\alpha ^{-12})^{3^{O(1/\alpha )}}=e^{e^{O(1/\alpha )}}.}$

したがって望みどおりです。${\displaystyle \alpha =O(1/\log \log N),}$${\displaystyle |A|=O\left({\frac {N}{\log \log N}}\right),}$${\displaystyle \blacksquare }$

残念ながら、この手法はより大きな等差数列に直接一般化してセメレディの定理を証明することはできません。この証明の拡張は、1998年にティモシー・ガワーズが上記の証明をセメレディの定理を証明するために一般化するために高次フーリエ解析の分野を開発するまで、数学者にとって数十年にわたって難しかったのです。^[5]

以下は、 Szemerédi 正則性補題を使用した証明の概要です。

をグラフ、 とします。 となるすべてのに対してが成り立つとき、を -正則ペアと呼びます。 ${\displaystyle G}$${\displaystyle X,Y\subseteq V(G)}$${\displaystyle (X,Y)}$${\displaystyle \epsilon }$${\displaystyle A\subset X,B\subset Y}$${\displaystyle |A|\geq \epsilon |X|,|B|\geq \epsilon |Y|}$${\displaystyle |d(A,B)-d(X,Y)|\leq \epsilon }$

の分割が -正規分割であるのは、 ${\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{k}\}}$${\displaystyle V(G)}$${\displaystyle \epsilon }$

${\displaystyle \sum _{(i,j)\in [k]^{2},(V_{i},V_{j}){\text{ not }}\epsilon {\text{-regular}}}|V_{i}||V_{j}|\leq \epsilon |V(G)|^{2}}$。

このとき、セメレディ正則性補題は、任意の に対して、任意のグラフが最大で 個の部分への -正則分割を持つような定数が存在することを述べています。 ${\displaystyle \epsilon >0}$${\displaystyle M}$${\displaystyle \epsilon }$${\displaystyle M}$

また、頂点の - 正則集合の間にある三角形は、他の多くの三角形を伴わなければならないことも証明できます。これは三角形を数える補題として知られています。 ${\displaystyle \epsilon }$

三角形の数え上げ補題:をグラフとし、を の頂点の部分集合とし、 が何らかの に対してすべて-正則ペアとなるようなものとする。をそれぞれ辺密度とする。 の場合、が三角形を形成する3 組の数は少なくとも ${\displaystyle G}$${\displaystyle X,Y,Z}$${\displaystyle G}$${\displaystyle (X,Y),(Y,Z),(Z,X)}$${\displaystyle \epsilon }$${\displaystyle \epsilon >0}$${\displaystyle d_{XY},d_{XZ},d_{YZ}}$${\displaystyle d(X,Y),d(X,Z),d(Y,Z)}$${\displaystyle d_{XY},d_{XZ},d_{YZ}\geq 2\epsilon }$${\displaystyle (x,y,z)\in X\times Y\times Z}$${\displaystyle x,y,z}$${\displaystyle G}$

${\displaystyle (1-2\epsilon )(d_{XY}-\epsilon )(d_{XZ}-\epsilon )(d_{YZ}-\epsilon )\cdot |X||Y||Z|}$。

三角形計数補題とセメレディ正則補題を用いて、グラフ除去補題の特殊なケースである三角形除去補題を証明することができる。^[6]

三角形除去補題:すべての に対して、個以下の三角形を持つ頂点上の任意のグラフは、最大 個の辺を削除することによって三角形なしにすることができるようなが存在する。 ${\displaystyle \epsilon >0}$${\displaystyle \delta >0}$${\displaystyle n}$${\displaystyle \delta n^{3}}$${\displaystyle \epsilon n^{2}}$

これには、すべての辺が一意の三角形内にある頂点上のグラフに関する興味深い帰結があります。具体的には、これらのグラフはすべて辺を持っている必要があります。 ${\displaystyle G}$${\displaystyle N}$${\displaystyle G}$${\displaystyle o(N^{2})}$

3 項等差数列のない集合を取ります。次に、のすべてのコピーである3 部グラフを構築します。の場合、頂点を頂点に接続します。同様に、 の場合、と接続します。最後に、 の場合、と接続します。 ${\displaystyle A}$${\displaystyle G}$${\displaystyle X,Y,Z}$${\displaystyle \mathbb {Z} /(2N+1)\mathbb {Z} }$${\displaystyle x\in X}$${\displaystyle y\in Y}$${\displaystyle y-x\in A}$${\displaystyle z\in Z}$${\displaystyle y\in Y}$${\displaystyle z-y\in A}$${\displaystyle x\in X}$${\displaystyle z\in Z}$${\displaystyle (z-x)/2\in A}$

この構成は、 が三角形を形成する場合、に属するすべての要素が得られるように設定されています。これらの数は、リストされた順序で等差数列を形成します。 の仮定により、この数列は自明でなければならないことがわかります。つまり、上にリストされた要素はすべて等しいということです。しかし、この条件は、 が における等差数列であるという主張と同等です。したがって、 のすべての辺は、正確に 1 つの三角形にあります。望ましい結論が続きます。${\displaystyle x,y,z}$${\displaystyle y-x,{\frac {z-x}{2}},z-y}$${\displaystyle A}$${\displaystyle A}$${\displaystyle x,y,z}$${\displaystyle \mathbb {Z} /(2N+1)\mathbb {Z} }$${\displaystyle G}$${\displaystyle \blacksquare }$

セメレディの定理は、元の予想を解決し、ロスの定理を任意の長さの等差数列に一般化しました。それ以来、この定理はさまざまな方法で拡張され、新しい興味深い結果を生み出してきました。

ファーステンバーグとカッツネルソン^[7]はエルゴード理論を用いて多次元バージョンを証明し、ライブマンとベルゲルソン^[8]はそれを多項式数列にも拡張した。最近では、グリーンとタオが、素数には任意の長さの等差数列が含まれるというグリーン・タオ定理を証明した。素数は密度0のサブセットであるため、彼らは、特定の疑似乱数条件を満たす密度0のサブセットに適用される「相対的な」セメレディ定理を導入した。後にコンロン、フォックス、およびジャオ^{[9] [10]は、}必要な疑似乱数条件を弱めることによってこの定理を強化した。2020年にブルームとシサスク^[11]は、発散するような任意の 集合には長さ3の等差数列が必ず含まれることを証明した。これは、そのような集合は実際には任意の長さの等差数列を含まなければならないという エルデシュの別の予想の最初の非自明なケースです。${\displaystyle A}$${\displaystyle \sum _{n\in A}{\frac {1}{n}}}$

ロスの定理の境界を改善する研究も行われている。ロスの定理の元々の証明の境界は、

${\displaystyle r_{3}([N])\leq c\cdot {\frac {N}{\log \log N}}}$

定数 に対してである。この上限は、長年にわたり、Szemerédi、^[12] Heath-Brown、^[13] Bourgain、^{[14] [15]}およびSanders [16] によって継続的に引き下げられてきた。^{[ 17]}現在（2020年7月）の最良の上限は、BloomとSisask ^[11]によるもので、彼らは絶対定数c>0の存在を示し、 ${\displaystyle c}$

${\displaystyle r_{3}([N])\leq {\frac {N}{(\log N)^{1+c}}}.}$

2023年2月にケリーとメカによるプレプリント^{[18] [19]}（後に出版^[20]）では、次のような新たな境界が示されました。

${\displaystyle r_{3}([N])\leq 2^{-\Omega ((\log N)^{1/12})}\cdot N}$。

4日後、ブルームとシサスクは結果の説明を記したプレプリント^[21]（後に出版^[22]）を発表し、議論を簡素化し、いくつかの追加の応用を生み出した。数か月後、ブルームとシサスクはのさらなる改良を得て、（証明なしに）彼らの技術がを示すために使用できると述べた。^[23]${\displaystyle r_{3}([N])\leq \exp(-c(\log N)^{1/9})N}$${\displaystyle r_{3}([N])\leq \exp(-c(\log N)^{5/41})N}$

反対に、3項等差数列を持たない最大の集合を構成する研究も行われている。最良の構成は、1946年にベーレンド^[24]がセーラムとスペンサーによる最初の構成を改良し、

${\displaystyle r_{3}([N])\geq N\exp(-c{\sqrt {\log N}})}$。

70年以上にわたって改良が加えられていないことから、ベーレンド集合は漸近的に3項進行のない最大の集合の大きさに非常に近いと推測される。^[11]これが正しければ、ケリー・メカ境界によってこの推測が証明される。

バリエーションとして、有限体上の類似の問題を考えることができます。有限体 を考え、 を3 項等差数列を含まない の最大の部分集合のサイズとします。この問題は、実際にはキャップ セット問題と同等であり、3 点が直線上にない の最大の部分集合を求めます。キャップ セット問題は、カード ゲームSetの一般化と見なすことができます。 ${\displaystyle \mathbb {F} _{3}^{n}}$${\displaystyle r_{3}(\mathbb {F} _{3}^{n})}$${\displaystyle \mathbb {F} _{3}^{n}}$${\displaystyle \mathbb {F} _{3}^{n}}$

1982年、ブラウンとビューラー^[25]は、初めて次のことを示しました。1995年、ロイ・メスラム^[26]は、ロスの定理のフーリエ解析的証明と同様の手法を使用して、次のことを示しました。この境界は、2012年にベイトマンとカッツ^[27]によって次のように改良されました。${\displaystyle r_{3}(\mathbb {F} _{3}^{n})=o(3^{n}).}$${\displaystyle r_{3}(\mathbb {F} _{3}^{n})=O\left({\frac {3^{n}}{n}}\right).}$${\displaystyle O(3^{n}/n^{1+\epsilon })}$

2016年、アーニー・クルート、フセヴォロド・レフ、ペーテル・パル・パハ、ジョーダン・エレンバーグ、ディオン・ギスウィットは、多項式法に基づく新しい手法を開発し、ことを証明した。^{[28] [29] [30]}${\displaystyle r_{3}(\mathbb {F} _{3}^{n})=O(2.756^{n})}$

最もよく知られている下限は、2023年12月にGoogle DeepMindの研究者が大規模言語モデル（LLM）を使用して発見したものです。^[31]${\displaystyle 2.2202^{n}}$

ロスの定理の別の一般化は、正の密度部分集合に対して、 3 項等差数列が存在するだけでなく、すべて同じ公差を持つ 3-AP が多数存在することを示しています。

ロスの定理（一般的な相違点を含む）：すべての に対して、 が存在し、任意の に対してが存在するので、が存在する。${\displaystyle \epsilon >0}$${\displaystyle n_{0}=n_{0}(\epsilon )}$${\displaystyle n>n_{0}}$${\displaystyle A\subset \mathbb {F} _{3}^{n}}$${\displaystyle |A|=\alpha 3^{n},}$${\displaystyle y\neq 0}$${\displaystyle |\{x:x,x+y,x+2y\in A\}|\geq (\alpha ^{3}-\epsilon )3^{n}.}$

が からランダムに選択される場合、の各値に対して数列が存在することが予想されます。したがって、公差定理によれば、正の密度を持つ それぞれに対して、公差を持つ 3-AP の数が予想数に近くなるような がいくつか存在します。 ${\displaystyle A}$${\displaystyle \mathbb {F} _{3}^{n},}$${\displaystyle \alpha ^{3}3^{n}}$${\displaystyle y}$${\displaystyle |A|}$${\displaystyle y}$${\displaystyle y}$

この定理は2005年にグリーンによって初めて証明され、^[32]はタワー関数がどこにあるかという境界を与えた。2019年にフォックスとファムは最近、境界を^{[33]に改良した。}${\displaystyle n_{0}={\text{tow}}((1/\epsilon )^{O(1)}),}$${\displaystyle {\text{tow}}}$${\displaystyle n_{0}={\text{tow}}(O(\log {\frac {1}{\epsilon }})).}$

同様の主張は3-APと4-APの両方にも当てはまります。^[34]しかし、この主張は5-APについては誤りであることが示されています。^[35]${\displaystyle \mathbb {Z} }$

• エドモンズ、チェルシー; クツコウ-アルギラキ、アンジェリキ;ポールソン、ローレンス C.ロスの等差数列に関する定理 (Isabelle/HOL における形式的証明の開発、形式的証明のアーカイブ)