ファン・デル・ヴェルデンの定理

ファン・デル・ヴェルデンの定理は、ラムゼー理論における定理である。ファン・デル・ヴェルデンの定理は、任意の正の整数 rとkに対して、ある数Nが存在し、整数 {1, 2, ..., N } がそれぞれrつの異なる色で着色されている場合、等差数列において少なくともk個の要素が同じ色である整数が存在することを述べている。そのような最小のNは、オランダの数学者BL ファン・デル・ヴェルデンにちなんで名付けられたファン・デル・ヴェルデン数W ( r ,  k )である。^[1]

これは 1921 年にピエール ジョゼフ アンリ ボーデによって推測されました。ヴァーデンは 1926 年にそれを聞き、1927 年にBeweis einer Baudetschen Vermutung [ボーデの予想の証明]というタイトルで証明を発表しました。^{[2] [3] [4]}

例

例えば、r = 2 の場合、赤と青の2色があります。W ( 2, 3) は8より大きいです。これは、次のように {1, ..., 8} の整数を色分けできるためです。

1	2	3	4	5	6	7	8
B	R	R	B	B	R	R	B

同じ色の整数を3つ重ねても等差数列になりません。しかし、等差数列を作らずに9番目の整数を最後に加えることはできません。赤い9を加えると、赤い3、6、9は等差数列になります。逆に、青い9を加えると、青い1、5、9は等差数列になります。

実際、このような数列を作らずに1から9までを色分けする方法はありません（例を挙げれば証明できます）。したがって、W (2, 3) は9です。

未解決の問題

rとkのほとんどの値に対してW ( r , k )の値を決定することは未解決の問題です。定理の証明は上限のみを提供します。たとえば、 r = 2 およびk = 3 の場合、以下に示す議論は、長さ 3 の単色の等差数列が存在することを保証するために、整数 {1, ..., 325} を 2 色で着色するだけで十分であることを示しています。しかし、実際には、325 という上限は非常に緩く、必要な整数の最小数は 9 個だけです。整数 {1, ..., 9} をどのように着色しても、1 色の整数が均等に 3 つ存在することになります。

r = 3 かつk = 3の場合、定理によって与えられる境界は 7(2·3 ⁷  + 1)(2·3 ^{7·(2·3 7  + 1)}  + 1)、つまり約 4.22·10 ¹⁴⁶¹⁶です。しかし実際には、長さ 3 の単色数列を保証するのにそれほど多くの整数は必要ありません。必要なのは 27 個だけです。（また、{1, ..., 26} を 3 色で塗り分けることも可能で、その場合、長さ 3 の単色等差数列は存在しません。例えば、

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26
R	R	G	G	R	R	G	B	G	B	B	R	B	R	R	G	R	G	G	B	R	B	B	G	B	G

未解決の問題は、一般的な上限を任意の「合理的な」関数に減らす試みである。ロナルド・グラハムは、 W (2, k ) < 2 ^{k 2}を示すことに対して1000ドルの賞金を提示した。^[5]さらに、彼はより一般的な非対角ファンデルワールデン数を含む彼の予想の証明に対して250ドルの賞金を提示し、W (2; 3, k ) ≤ k ^O(1)を述べ、数値的証拠はW (2; 3, k ) = k ^{2 + o(1)}を示唆していると述べた。ベン・グリーンはこの後者の予想を反証し、任意のrに対してW (2; 3, k ) < k ^rとなる超多項式反例を証明した。^[6]現在知られている最良の上限はティモシー・ガワーズによるもので、^[7]彼は

${\displaystyle W(r,k)\leq 2^{2^{r^{2^{2^{k+9}}}}},}$

まず、ファン・デル・ワールデンの定理の強化版であるセメレディの定理について同様の結果を確立した。それ以前に最もよく知られていた上界はサハロン・シェラによるもので、まずファン・デル・ワールデンの定理をさらに強化したヘイルズ・ジューエットの定理の結果を証明した。

現在知られている の最良の下限は、すべての正の に対して であり、すべての十分に大きい に対して であるということです。^[8]${\displaystyle W(2,k)}$ ${\displaystyle \varepsilon }$ ${\displaystyle W(2,k)>2^{k}/k^{\varepsilon }}$ ${\displaystyle k}$

ファン デル ワールデンの定理の証明 (特殊な場合)

以下の証明はロン・グラハム、B・L・ロスチャイルド、ジョエル・スペンサーによるものである。^[9] ヒンチン^[10]はW ( r ,  k )を推定せずにこの定理のかなり簡単な証明を与えている。

の場合の証明W（2、3）

W (2, 3) 表

b	c ( n ): 整数の色
0	1	2	3	4	5
	R	R	B	R	B
1	6	7	8	9	10
	B	R	R	B	R
…	…
64	321	322	323	324	325
	R	B	R	B	R

上で述べた特別な場合、すなわちW (2, 3) ≤ 325 であることを証明します。c ( n )を整数 {1, ..., 325} の彩色とします。等差数列において、{1, ..., 325} の元のうち、同じ色の元が3つ見つかります。

{1, ..., 325}を65個のブロック{1, ..., 5}, {6, ..., 10}, ... {321, ..., 325}に分割すると、各ブロックは{5 b + 1, ..., 5 b + 5}の形をとり、 bは{0, ..., 64}の範囲にある。各整数は赤か青で色分けされているので、各ブロックは32通りの色で色分けされている。鳩の巣原理によ​​り、最初の33個のブロックの中には同じ色で色分けされているブロックが2つある。つまり、{0, ..., 32}の範囲に2つの整数b ₁とb ₂があり、

c (5 b ₁ + k ) = c (5 b ₂ + k )

全てのk は{1, ..., 5} に属する。3つの整数 5 b ₁ + 1、5 b ₁ + 2、5 b ₁ + 3 のうち、少なくとも2つは同じ色である。（鳩の巣原理を再び参照。）これらを 5 b ₁ + a ₁および 5 b ₁ + a ₂と呼ぶ。ここでa _{i は}{1, 2, 3} に属し、a ₁ < a _{2である。（}一般性を損なうことなく）これら2つの整数が両方とも赤であると仮定する。（両方とも青の場合は、以下で 「赤」と「青」を入れ替えるだけである。）

a ₃ = 2 a ₂  −  a ₁とします。5 b ₁ + a ₃が赤であれば、等差数列が求められます。5 b ₁  +  a _iはすべて赤です。

そうでなければ、5 b ₁ + a _3は青です。a 3 ≤ 5なので、 5 b ₁ + a _3はb ₁ブロックにあり、b _{2ブロックも}同じ色なので、5 b ₂ + a ₃も青です。

ここで、b ₃ = 2 b ₂  −  b ₁とします。すると、b ₃ ≤ 64 となります。整数 5 b ₃ + a ₃は ≤ 325 でなければなりません。この整数は何色でしょうか？

赤なら、5 b ₁ + a ₁、5 b ₂ + a ₂、5 b ₃ + a _3は赤の等差数列を形成します。青なら、5 b ₁ + a ₃、5 b ₂ + a ₃、5 b ₃ + a _3は青の等差数列を形成します。どちらにしても、これで終わりです。

の場合の証明W（3、3）

W(3, 3)表
g =2·3 ^{7·(2·3 7  + 1)}  、
m =7(2·3 ⁷  + 1)

b	c ( n ): 整数の色
0	1	2	3	…	メートル
	G	R	R	…	B
1	m + 1	m + 2	メートル+3	…	2メートル
	B	R	G	…	R
…	…
グラム	gm + 1	gm + 2	gm + 3	…	（グラム+1）メートル
	B	R	B	…	G

同様の議論により、 W (3, 3) ≤ 7(2·3 ⁷ +1)(2·3 ^{7·(2·3 7 +1)} +1)が成り立つことが示される。まず、整数を 7(2·3 7 + 1) 個の整数からなる 2·3 7·(2·3 7 + 1) + 1 個のグループに分割する^{。 最初の3}  ·  7 ^{·(2·3 7  + 1)}  + 1 個のグループのうち、2つは同じ色でなければならない。

これらの2つのグループをそれぞれ7個の整数からなる2×3 ⁷ +1個のサブグループに分割します。各グループの最初の3 ⁷  + 1個のサブグループのうち、2つのサブグループは必ず同じ色でなければなりません。これらの同じサブグループ内では、最初の4つの整数のうち2つは同じ色（例えば赤）でなければなりません。これは、同じサブグループ内に 赤の累乗、または異なる色（例えば青）の要素が存在することを意味します。

同じ色のサブグループが 2 つあるため、同じグループに 3 つ目のサブグループが存在します。このサブグループには、赤または青のいずれかであれば、 W (2, 3)の場合と同様の構成により、赤または青の累進帯が完成する要素が含まれます。この要素が緑であるとします。同じ色のグループが存在するため、そのグループには、特定した赤、青、緑の要素のコピーが含まれている必要があります。これで、同じ整数に「焦点を合わせる」赤の要素のペア、青の要素のペア、緑の要素のペアを見つけることができ、その色が何であれ、累進帯が完成するはずです。

一般的な場合の証明

W (2, 3)の証明は、W (32, 2) ≤ 33 であることを証明することに本質的に依存している。整数 {1,...,325} を 65 個の「ブロック」に分割し、各ブロックを 32 通りの方法で色分けする。そして、最初の 33 個のブロックのうち 2 個は同じ色でなければならないこと、そして反対色で色分けされたブロックが存在することを示す。同様に、W (3, 3) の証明は、

${\displaystyle W(3^{7(2\cdot 3^{7}+1)},2)\leq 3^{7(2\cdot 3^{7}+1)}+1.}$

色の数と数列の長さに関する 二重の帰納法によって、定理は一般に証明されます。

証拠

D次元等差数列(AP)は次の形式の数値で構成されます。

${\displaystyle a+i_{1}s_{1}+i_{2}s_{2}+\cdots +i_{D}s_{D}}$

ここで、 aは基点、sは正のステップサイズ、iは 0 からL  − 1までの範囲です。d次元AP は、すべてが同じ色である場合、ある種の彩色に対して 同次です。

D次元等差数列の利点は、上記の形式のすべての数に等差数列の「境界」の一部、つまり添え字iの一部がLに等しくなるものを加えることです。追加する辺は、最初のk個の iがLに等しく、残りのiがLより小さい辺です。

利点のあるD次元 APの境界は、次元 のこれらの追加の等差数列から 0 までです。0 次元等差数列は、インデックス値 における単一の点です。利点のあるD次元 AP は、各境界が個別に同質である場合に同質ですが、異なる境界が必ずしも同じ色である必要はありません。 ${\displaystyle d-1,d-2,d-3,d-4}$ ${\displaystyle (L,L,L,L,\ldots ,L)}$

次に、長さMinN以上の範囲にN色の割り当てを行うと、必ず利点のある同次D次元等差数列が含まれるように、最小の整数となるように量MinN( L , D , N )を定義します。

目標はMinNの大きさを上限とすることです。MinN ( L ,1, N )はファンデルワールデン数の上限であることに注意してください。以下の2つの帰納法があります。

補題1 —等差数列のすべての次元において、与えられた長さLに対して、 Dまでの利点を持つ最小値Nが既知であると仮定する。この式は、次元をD  + 1まで増加させた場合の最小値 Nの上限を与える。

すると、 ${\displaystyle M=\operatorname {MinN} (L,D,n)}$

${\displaystyle \operatorname {MinN} (L,D+1,n)\leq M\cdot \operatorname {MinN} (L,1,n^{M})}$

証拠

まず、区間 1... Iのn色彩があれば、 kサイズのブロックのブロック色彩を定義できます。各kブロック内のk色のシーケンスをそれぞれ考慮して、一意の色を定義します。これをkブロック色彩と呼びます。長さlの n 色彩を k ブロック色彩すると、長さl/ kのn ^k色彩が生成されます。

つまり、サイズ の区間Iのn色分けが与えられた場合、それをMブロック化して長さ のn ^M色分けにすることができます。しかし、これはMinNの定義により、ブロック色分けにおいて長さLの 1 次元等差数列（利点付き）を見つけることができることを意味します。ブロック色分けとは、等間隔に配置されたブロックの列であり、すべて同じブロック色です。つまり、元の列には長さMのブロックが等間隔に配置され、内部の色の列が全く同じであるということです。 ${\displaystyle M\cdot \operatorname {MinN} (L,1,n^{M}))}$ ${\displaystyle \operatorname {MinN} (L,1,n^{M})}$

さて、 Mの定義により、これらのブロックのいずれか1つに、利益のあるd次元等差数列を見つけることができます。すべてのブロックは同じ色の配列を持つため、ブロックからブロックへ変換するだけで、すべてのブロックに同じ利益のあるd次元APが現れます。これはd  +  1次元等差数列の定義であり、同次的なd + 1次元APが得られます。新しいストライドパラメータs _{D  + 1}は、ブロック間の距離として定義されます。

しかし、利点も必要です。今得られる境界はすべて古い境界に、それらを同じ色のブロックに変換したものを加えたものです。なぜなら、i _D+1は常にLより小さいからです。これと異なる境界は、 のときの0次元点だけです。これは単一の点であり、自動的に同次になります。 ${\displaystyle i_{1}=i_{2}=\cdots =i_{D+1}=L}$

補題2 — MinN がLの1つの値とすべての可能な次元Dに対して既知であると仮定する。この場合、長さL  + 1に対して MinN を制限できる。

${\displaystyle \operatorname {MinN} (L+1,1,n)\leq 2\operatorname {MinN} (L,n,n)}$

証拠

MinN( L , n , n )の大きさの区間のn色分けが与えられれば、定義により、長さLでn次元の利益を持つ等差数列を見つけることができます。ただし、「利益」境界の数は色の数に等しいため、例えばk次元の同次境界の 1 つは、例えばp  <  k次元の同次利益境界のもう 1 つと同じ色である必要があります。これにより、k次元境界内の直線に沿って進み、 p 次元境界で終了し、終点を p 次元境界に含めることで、長さ L + 1 の等差数列 (次元 1) を構築できます。式で は、

もし

${\displaystyle a+Ls_{1}+Ls_{2}+\cdots +Ls_{D-k}}$ 同じ色です

${\displaystyle a+Ls_{1}+Ls_{2}+\cdots +Ls_{D-p}}$

それから

${\displaystyle a+L\cdot (s_{1}+\cdots +s_{D-k})+u\cdot (s_{D-k+1}+\cdots +s_{p})}$ 同じ色である

${\displaystyle u=0,1,2,\cdots ,L-1,L}$ つまり、u は長さL +1のシーケンスを作成します。

これは次元1のシーケンスを構築します。「利点」は自動的に得られます。任意の色の点を追加するだけです。この境界点を含めるには、ストライドの最大値だけ区間を長くする必要がありますが、これは区間のサイズよりも確実に小さくなります。したがって、区間のサイズを2倍にすることは確実に機能し、これが係数を2にする理由です。これでLに関する帰納法が完了します。

基本ケース：MinN(1, d , n ) = 1 、つまり、長さ1の同次d次元等差数列を求める場合、利点の有無にかかわらず、何もする必要はありません。したがって、これが帰納法の基礎となります。ファン・デル・ヴェルデンの定理自体は、 MinN( L ,1, N )が有限であるという主張であり、基本ケースと帰納法のステップから導かれます。^[11]

エルゴード理論

1978年にファーステンバーグとワイスはエルゴード理論を用いてこの定理の同等の形を証明した。^[12]

多重バーコフ再帰定理 （Furstenberg and Weiss, 1978）—がコンパクト計量空間であり、が可換な同相写像である場合、、および増加列であって、${\textstyle X}$ ${\textstyle T_{1},\dots ,T_{N}:X\to X}$ ${\textstyle \exists x\in X}$ ${\textstyle n_{1}<n_{2}<\cdots }$ $${\displaystyle \lim _{j}d(T_{i}^{n_{j}}x,x)=0,\quad \forall i\in 1:N}$$

上記の定理の証明は繊細なので、読者には参照が必要です。^[12]この再帰定理により、ファンデルワールデンの定理をエルゴード理論的スタイルで証明することができます。

定理 （ファン・デル・ワールデン、1927年）—が有限個の部分集合に分割される場合、そのうちの1つには任意の長さの等差数列が無限個含まれる。 ${\textstyle \mathbb {Z} }$ ${\textstyle S_{1},\dots ,S_{n}}$ ${\textstyle S_{k}}$

$${\displaystyle \forall N,N',\;\exists |a|\geq N',\exists r\geq 1:\{a+ir\}_{i\in 1:N}\subset S_{k}}$$

証拠

それぞれの長さ に対して、長さ の等差数列を少なくとも1つ含む分割が少なくとも1つ存在することを示すだけで十分です。これが証明されれば、その等差数列を単一の集合に切り出し、このプロセスを繰り返して別の等差数列を作成できます。こうすることで、分割の1つに長さ の等差数列が無限に含まれます。次に、このプロセスを繰り返して、長さ の等差数列を無限に含む分割が少なくとも1つ存在し、その分割が求める分割であることがわかります。 ${\textstyle N}$ ${\textstyle N}$ ${\textstyle N}$ ${\textstyle N}$ ${\textstyle N}$ ${\textstyle N}$

計量 （実際は超計量） の下でコンパクトである状態空間 を考えます。集合 は を分割するので、すべての に対して となる明確に定義されたシーケンスが得られます。 ${\textstyle \Omega =(1:N)^{\mathbb {Z} }}$ $${\displaystyle d((x_{i}),(y_{i}))=\max\{2^{-\vert {i}\vert }:x_{i}\neq y_{i}\}.}$$ ${\textstyle S_{1},\dots ,S_{n}}$ ${\textstyle \mathbb {Z} }$ ${\textstyle z=(\dots ,z_{-1},z_{0},z_{1},\dots )=(z_{i})_{i}}$ ${\textstyle i\in S_{z_{i}}}$ ${\textstyle i}$

をシフト写像とし、 を列 のすべてのシフトの閉包とする。バーコフの多重再帰定理（写像 について）により、次を満たす列と整数が存在する。${\textstyle T:\Omega \to \Omega }$ $${\displaystyle T((x_{i})_{i})=(x_{i+1})_{i},}$$ ${\textstyle X=cl(\{T^{r}z:r\in \mathbb {Z} \})}$ ${\textstyle z}$ ${\textstyle T,T^{2},\dots ,T^{N}}$ ${\textstyle x\in X}$ ${\textstyle s\geq 1}$ $${\displaystyle d(T^{s}x,x),d(T^{2s}x,x),\dots ,d(T^{Ns}x,x)<{\frac {1}{4}}.}$$

は のシフトの閉包であり、は連続であるため、が に非常に近くなり、 がに非常に近くなる、などとなるようなシフトが存在する。${\textstyle X}$ ${\textstyle z}$ ${\textstyle T}$ ${\textstyle T^{m}z}$ ${\textstyle x}$ ${\textstyle T^{m}z}$ ${\textstyle T^{s}x}$ ${\textstyle T^{s+m}z}$ $${\displaystyle d(x,T^{m}z),d(T^{s}x,T^{m+s}z),\dots ,d(T^{Ns}x,T^{m+Ns}z)<{\frac {1}{4}}.}$$

三角不等式より、 について が直ちに成り立ちます 。しかし、構成上、となる数列は必ず となります。したがって となり、すべて の分割に含まれます。 ${\textstyle d(T^{m+is}z,T^{m+js}z)<{\frac {3}{4}}}$ ${\textstyle i,j=0,\dots ,N}$ ${\textstyle y,y'\in \Omega }$ ${\textstyle d(y,y')<1}$ ${\textstyle y_{0}={y'}\!\!{}_{0}}$ ${\textstyle z_{m}=z_{m+s}=\dots =z_{m+Ns}}$ ${\textstyle m,m+s,\dots ,m+Ns}$ ${\textstyle S_{z_{m}}}$

参照

• W ( n、r )のすべての既知の値に対するファンデルワールデン数と、未知の値に対する最良の既知の境界。
• ファンデルワールデンゲーム– プレイヤーが 1、2、...、Nの集合から整数を選び、長さnの等差数列を作ろうとするゲーム。
• ヘイルズ・ジュエット定理
• ラドーの定理
• セメレディの定理
• バーテル・レンデルト・ファン・デル・ワールデン

注記

1. ファン デル ワールデン、BL (1927)。 「Beweis einer Baudetschen Vermutung」。ニュー。アーチ。ウィスク。（ドイツ語で）。15 : 212–216 .
2. L、ファン デル ワールデン B. (1927)。 「Beweis einer Baudetschen Vermutung」。Nieuw Arch.Wiskunde。15 : 212–216 .
3. Soifer、Alexander (2015)、Soifer、Alexander (編)、「ファン デル ワールデンは誰の予想を証明したか?」、学者と国家: ファン・デル・ワールデンを求めて、バーゼル: Springer、pp.  379–401、doi :10.1007/978-3-0348-0712-8_38、ISBN 978-3-0348-0712-8、 2024年1月17日取得
4. L, van der WAERDEN B. (1971). 「Baudet予想の証明はいかにして発見されたか」. 『純粋数学研究』 . 『数学ぬりえブック』第33章に転載.
5. グラハム、ロン(2007). 「ラムゼー理論における私のお気に入りの問題のいくつか」. INTEGERS: 組合せ数論電子ジャーナル. 7 (2): #A15.
6. Klarreich, Erica (2021). 「数学者が構造と無秩序を100年前の問題に投げ込む」Quanta Magazine .
7. Gowers, Timothy (2001). 「セメレディの定理の新たな証明」 .幾何学と関数解析. 11 (3): 465– 588. doi :10.1007/s00039-001-0332-9. S2CID  124324198.
8. ゾルタン、ザボ(1990)。 「Lovász の局所補題の適用 - ファン デル ワールデン数の新しい下限」。ランダム構造とアルゴリズム。1 (3): 343–360。土井:10.1002/rsa.3240010307。
9. グラハム、ロナルド、ロスチャイルド、ブルース、スペンサー、ジョエル (1990).ラムゼー理論.ワイリー. ISBN 0471500461。
10. ヒンチン (1998、pp. 11–17、第 1 章)
11. Graham, RL ; Rothschild, BL (1974). 「算術級数に関するファン・デル・ワールデンの定理の簡潔な証明」.アメリカ数学会紀要. 42 (2): 385– 386. doi : 10.1090/S0002-9939-1974-0329917-8 .
12. Petersen, Karl E. (1983). 「第2章」. エルゴード理論. Cambridge Studies in Advanced Mathematics. Cambridge: Cambridge University Press. ISBN 978-0-521-38997-6。

参考文献

• Khinchin, A. Ya. (1998), Three Pearls of Number Theory, Mineola, NY: Dover, pp.  11– 17, ISBN 978-0-486-40026-6（第2版は1948年にロシア語で初版が出版された）

外部リンク

• オブライアント、ケビン。 「ファン・デル・ワールデンの定理」。マスワールド。
• オブライアント、ケビン＆ワイスタイン、エリック・W.「ファン・デル・ワールデン・ナンバー」。マスワールド。