インテジャーズ

INTEGERS

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

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

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

adventar.org

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に評価してnN^2c'_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]^24N-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_1N個の直線 x=1, x=2, \dots, x=Nのなす集合
  • V_2N個の直線 y=1, y=2, \dots, y=Nのなす集合
  • V_32N-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_jE_{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の論文でも示唆されているとのことですが)甲斐さんに教えていただきました。