Ajtai-Szemerédiの定理のSolymosiによる証明

これは好きな証明Advent Calendarの22日目の記事です。

Ruzsa-Szemerédiの三角形除去補題からRothの定理を導出できることは有名ですが、SolymosiによってAjtai-Szemerédiの定理を導出することもできることが示されています。これが面白いので紹介します。

まず、三角形除去補題の主張を思い出しましょう。

定理 (三角形除去補題, Ruzsa-Szemerédi, 1974) 任意の正の数 $\varepsilon > 0$ に対して $0 < \delta < 1$ が存在して以下の主張が成立する: $G=G(V_1, V_2, V_3, E_{12}, E_{23}, E_{31})$ を $V_1, V_2, V_3$ が頂点集合(どれも空でない有限集合)で $E_{12}, E_{23}, E_{31}$ が辺集合(つまり、 $(i,j)=(1,2), (2,3), (3,1)$ に対して $E_{ij} \subset V_i \times V_j$ )であるような三部グラフであって

( $G$ の辺が作る三角形の個数) $\ \leq \delta \cdot \#V_1 \cdot \#V_2 \cdot \#V_3$

を満たすようなものとする。このとき、辺が作る三角形を一つも持たないような三部グラフ $G'=G'(V_1, V_2, V_3, E'_{12}, E'_{23}, E'_{31})$ が存在して、

$\displaystyle \#(E_{ij}\setminus E'_{ij}) \leq \varepsilon \cdot \#V_i \cdot \#V_j \quad ( (i,j)=(1,2), (2,3), (3,1) )$

が成り立つ。

次の系の形で使用します。

系 (Ruzsa-Szemerédi) 任意の正の数 $\varepsilon, c_i, c'_i > 0 \ (i=1, 2, 3)$ に対して或る番号 $N_0$ が存在して以下の主張が成立する: $N \geq N_0$ を整数とし、 $G=G(V_1, V_2, V_3, E_{12}, E_{23}, E_{31})$ を $c_iN \leq \#V_i \leq c_i'N \ (i=1,2,3)$ を満たし、 $G$ の各辺は丁度一つの(辺が作る)三角形に含まれるような三部グラフとする。このとき、

( $G$ の辺の数) $\ \leq \varepsilon N^2$

が成り立つ。

証明. $\delta$ を $\varepsilon'$ (後で指定)に対して三角形除去補題から定る数とし、 $G$ の辺の数を $n$ とする。vacuousに評価して $n$ は $N^2$ の $c'_i$ に依存した定数( $C_{c'_1, c'_2, c'_3}$ とする)倍で上から評価され、

$\displaystyle \frac{C_{c'_1, c'_2, c'_3}}{3c_1c_2c_3N_0} \leq \delta$

が成り立つような $N_0$ をとっているものとする。 $G$ の辺が作る三角形の個数は $G$ に関する仮定から $n/3$ なので、 $N_0$ の取り方から

( $G$ の辺が作る三角形の個数) $\ \leq \delta \cdot \#V_1 \cdot \#V_2 \cdot \#V_3$

が成立している。よって、三角形除去補題より $G$ から辺が作る三角形が一切ない状況にするために必要な辺の除去数は

$\displaystyle \varepsilon’(c'_1c'_2+c'_2c'_3+c'_3c'_1)N^2$

を超えない。一方で、 $G$ に関する仮定から上記必要な辺の除去数は $n/3$ である。よって、 $\varepsilon':=\frac{1}{3(c'_1c'_2+c'_2c'_3+c'_3c'_1)}\varepsilon$ とすればよい。 Q.E.D.

次にAjtai-Szemerédiの定理の主張を書きます。

定義 ( $\mathbb{Z}^2$ 内の)コーナーとは、整数 $a, b, d$ (ただし、 $d \neq 0$ )を用いて $\{(a, b), (a+d, b), (a, b+d)\}$ と表される $\mathbb{Z}^2$ の部分集合のことをいう。また、 $A \subset \mathbb{N}^2$ の上漸近密度 $\overline{d}(A)$ を

$\displaystyle \overline{d}(A):= \limsup_{N \to \infty}\frac{\#(A \cap [N]^2)}{N^2}$

と定義する。ここで、 $[N]=\{1, 2, \dots, N\}$ である。

定理 (Ajtai-Szemerédi, 1974) $A \subset \mathbb{N}^2$ は上漸近密度が正であればコーナーを含む。

では、Ajtai-Szemerédiの定理をRuzsa-Szemerédiの系から導出しましょう。格子点 $[N]^2$ と $4N-1$ 本の直線達を想像しながら読んでください。

証明. 対偶をとって証明する。 $A \subset \mathbb{N}^2$ がコーナーを持たないと仮定し、 $\varepsilon > 0$ を任意にとる。 $N_0$ をRuzsa-Szemerédiの系によって存在する番号とし、 $N \geq N_0$ とする(ただし、 $c_1=c_2=c_3=1, c'_1=c'_2=1, c'_3=2$ に対するもの)。三部グラフ $G=G(V_1, V_2, V_3, E_{12}, E_{23}, E_{31})$ を以下のように定める：

$V_1$ は $N$ 個の直線 $x=1, x=2, \dots, x=N$ のなす集合
$V_2$ は $N$ 個の直線 $y=1, y=2, \dots, y=N$ のなす集合
$V_3$ は $2N-1$ 個の直線 $x+y=2, x+y=3, \dots, x+y=2N$ のなす集合

とし、 $(i,j)=(1,2), (2, 3), (3,1)$ に対して、 $(v_i, v_j) \in V_i \times V_j$ が $E_{ij}$ に属するための必要十分条件は(平行でない)二直線 $v_i, v_j$ の交点(それはa prioriには $[N]^2$ にある)が $A_N:=A \cap [N]^2$ に属することとする。

構成から $G$ の辺が作る三角形は $A_N$ 内のコーナーおよび $A_N$ の元に対応するが、 $A_N$ 内にコーナーはないと仮定しているため $G$ の各辺は丁度一つの三角形に含まれており、 $G$ の辺の数は $3\#A_N$ に等しい。従って、Ruzsa-Szemerédiの系によって $\#A_N \leq \frac{\varepsilon}{3}N^2$ が示された。 $\varepsilon$ は任意なので、 $\overline{d}(A)=0$ が従う。 Q.E.D.

Ruzsa-Szemerédiの三角形除去補題は台となるグラフが $K_3$ であり、これを一般のuniform hypergraphに拡張したものがGowersおよびNagle-Rödl-Schacht-Skokanによるhypergraph removal lemma (=HRL)です。Taoの論文なんかだとHRLからFurstenberg-Katznelsonの定理の導出に「有限加法群に対するSzemerédiの定理」を経由しますが、Solymosiの方法を自然に高次元に拡張してHRLから高次元コーナー定理を証明した後に、高次元空間の星座をより高次元の空間内のコーナーに移行させるテクニックを用いてFurstenberg-Katznelsonの定理を導出できることを(Gowersの論文でも示唆されているとのことですが)甲斐さんに教えていただきました。

INTEGERS

数、特に整数に関する記事。

Ajtai-Szemerédiの定理のSolymosiによる証明