k-AP自由数列 - INTEGERS

$k$ -AP自由数列とSzemerédiの定理

$k, N$ を正整数とします。長さ $k$ の等差数列を含まないような $N$ 以下の正整数からなる狭義単調増大数列のことを $N$ に関する $k$ -AP自由数列と呼ぶことにし、 $N$ に関する $k$ -AP自由数列として取り得る最大項数を $r_k(N)$ と定義します。

定理任意の正整数 $k$ に対して、 $r_k(N)=o_k(N), \ N \to \infty$ が成り立つ*1。

この定理はSzemerédiの定理と同値です。

integers.hatenablog.com

で証明した有限版Szemerédiの定理と無限版Szemerédiの定理の同値性を使います。

同値性の証明. 上の定理が成立すると仮定する。 $A \subset \mathbb{N}$ の上漸近密度が $\overline{d}(A) = \delta > 0$ であったとする。仮定より任意の正整数 $k$ に対して $k, \delta$ に依存する正整数 $N(k, \delta)$ が存在して、 $N \geq N(k, \delta)$ であれば $r_k(N) < \frac{\delta}{2}N$ が成り立つ。また、 $N \geq N(k, \delta)$ なる正整数であって $\#\{A \cap [N]\} \geq \frac{\delta}{2}N$ が成り立つようなものが存在する。ここで、 $[N]:=\{1, 2, \dots, N\}$ と定義している。この $N$ に対して $\#\{A\cap [N]\} > r_k(N)$ なので、 $A\cap [N]$ の元から構成される数列は $k$ -AP自由数列ではない。すなわち、 $A$ は長さ $k$ の等差数列を含む。つまり、無限版Szemerédiの定理が成立することがわかった。

次に、有限版Szemerédiの定理が成立すると仮定し、 $k$ を正整数とする。任意に $\varepsilon > 0$ をとる。このとき、 $N \geq N_{\mathrm{SZ}}(k, \varepsilon)$ なる $N$ に対して $N$ に関する $k$ -AP自由数列から構成される集合 $A$ は $\#A < \varepsilon N$ を満たす必要があるため、 $r_k(N) < \varepsilon N$ である。これは $r_k(N) = o_k(N), \ N \to \infty$ を意味する。 Q.E.D.

$r_k(N)$ の漸近挙動

Szemerédiの定理の精密化として、 $r_k(N)$ のより精密な漸近挙動を求めるという仕事があります。実際、 $r_3(N)=o(N)$ を最初に示したRothは

$\displaystyle r_3(N) = O\left(\frac{N}{\log \log N}\right),\quad N \to \infty$

が成り立つことまで示していました。

integers.hatenablog.com

これに対して、現状示されていることをまとめると次のようになっています。

O'Bryant and Bloom

$\displaystyle N2^{-\sqrt{8\log N}} \leq r_3(N) \ll \frac{(\log \log N)^4N}{\log N}, \quad N \gg 0.$

Green-Tao

$\displaystyle r_4(N) \ll \frac{N}{(\log N)^{\exists c > 0}}.$

O'Bryant and Gowers

$\displaystyle N\exp\left(-\lceil \log k\rceil 2^{\frac{\lceil \log k\rceil-1}{2}}\sqrt[\lceil \log k\rceil]{\log N}+\frac{1}{2\lceil \log k\rceil}\log \log N\right) \ll r_k(N) \ll \frac{N}{(\log \log N)^{2^{-2^{k+9}}}}.$

Erdős-Turán予想と関連する疑問

integers.hatenablog.com

で述べた

疑問正整数からなる集合 $A$ が任意の $\varepsilon > 0$ に対して

$\#\{A \cap [N]\} \gg_{\varepsilon} N^{1-\varepsilon}, \quad N \to \infty$

を満たすならば $A$ は任意の長さの等差数列を含むと言えるか？反例はあるか？

は実は否定的であることがわかります。反例の存在*2: $F(N):=2^{\sqrt{8\log N}}$ とする。O'Bryantの結果と平行移動の原理から、十分大きい整数 $M$ と任意の正整数 $k$ に対して、 $[2\cdot 3^kM, 3^{k+1}M]\cap \mathbb{Z}$ は

$\displaystyle \#A_k \geq \frac{3^kM}{F(3^kM)}$

を満たし長さ $3$ の等差数列を含まないような部分集合 $A_k$ を含む。 $A \subset \mathbb{N}$ を

$\displaystyle A:=\bigsqcup_{k=1}^{\infty}A_k$

と定義する。すると、定義より $A$ は長さ $3$ の等差数列を含まない(異なる $A_k$ 間の元で長さ $3$ の等差数列が出来ないように間隔が設定されている)。そうして、 $3^KM \leq N < 3^{K+1}M$ のとき

$\displaystyle \#\{A \cap [N]\} \geq \#\{A \cap [3^KM]\} = \sum_{k=1}^{K-1}\#A_k \geq \sum_{k=1}^{K-1}\frac{3^kM}{F(3^kM)} \gg \frac{N}{F(N)}$

が成り立つ。そうして、任意の $\varepsilon > 0$ に対して $N^{\varepsilon} \gg F(N)$ なので、 $A$ は反例になっている。 Q.E.D.

とりあえず正しい問題設定は次です：

問題正整数からなる集合 $A$ に対して

$\displaystyle \#\{A \cap [N]\} \gg \frac{N}{F(N)}, \quad N \to \infty$

が成り立つならば $A$ は必ず任意の長さの等差数列を含むと言えるような最良の関数 $F(N)$ は何か？

疑問は「Erdős-Turán予想は究極の予想か？」というものでした。まず、Erdős-Turán予想が成り立たない可能性も十分ありますが、成り立つとして話を進めます。任意の長さの等差数列を含むためにはある程度ランダムに数が分布している必要がありますが、Szemerédiの定理やErdős-Turán予想はそれぞれ密度が正、逆数和が発散するという定性的性質が十分なランダム性を保証すると言っています。その範疇になくても十分なランダム性を持つ集合の存在が示されていたり予想されたりしているのは以前述べた通りです。では、それらの例は $F(N)$ の存在によって一般的に統制されたものなのか、それともErdős-Turán予想が究極の予想であって、逆数和が収束するけれども十分ランダムな集合は例外的なものなのか、一体どちらなのでしょう？もし、前者であればErdős-Turán予想は究極の予想ではなく、逆数和の発散性を上手く制御した証明を見出すことは難しいかもしれないのかなあなどと考えています。

*1:漸近挙動の記号 $o_k$ の添字は $k$ 依存を表す。

*2:山田氏に教えていただきました。