[tex: ]

Hypergraph removal lemma から多次元版 Szemerédi への議論


この記事は、せきゅーんさんの Green-Tao 定理に関するブログに触発されて書いたものです。

 

 Hypergraph removal lemma から多次元 Szemerédi 定理の導出は、有限加法群版を経由する方法が日本ではポピュラーです。

が、Solymosi の方法をまねて、多次元版 Szemerédi の特別な場合である多次元版 corner 定理を経由して示すこともできます。これを以下で解説します。

これは、Gowers の論文「Hypergraph regularity and the multidimensional Szemerédi theorem」の序文で示唆されている方法です。

 アーベル群に親しみのある、筆者のような者には、こちらの手順の方が conceptual にわかりやすいかもしれません。

 

目次

  ・Hypergraph removal から 多次元 corner 定理

  ・多次元 corner 定理から多次元 Szemerédi (次の記事)

 \( i=1,\dots ,n \) に対して \(\overrightarrow{e}_i\in \mathbb{Z}^n\) を i 番目の方向を向いた単位ベクトルとし、あとの都合のため \( \overrightarrow{e}_0:=\overrightarrow{0} \) と置きます。

定義:

\( \mathbb{Z}^n\) の部分集合 C が corner であるとは、あるベクトル \( \overrightarrow{a}\in \mathbb{Z}^n\) と整数 \( d\) を用いて \[ C=\{ \overrightarrow{a}+d\overrightarrow{e}_i \mid 0\le i\le n \} \] の形に書けることとします。2 次元なら座標軸でできる直角二等辺三角形のことで、3 次元ならフレミングの左手のような形ということです。

 d=0 の場合は C は 1 点になってしまいますが、この場合も自明な corner として、一応 corner 扱いすることにします。

 部分集合 \( A\subset \mathbb{Z}^n \) が corner-free であるとは、自明でない corner を含まないこととします。この定義のもとで:

多次元 corner 定理

n を自然数とし、\( A\subset \mathbb{Z}^n \) を corner-free な部分集合とする。このとき \[  \# (A\cap [ -N,N ]^n) = o(N^n) \quad \text{ as } N\to \infty .  \]

 

(帰結の式はつまり、A の密度 \( \displaystyle \lim\limits _{N\to \infty } \frac{\# (A\cap [ -N ,N]^n )}{(2N)^n}\) が 0 ということです。)

 多次元版 corner 定理は次の定理の特別な場合ですが、hypergraph removal lemma から証明しやすく、また (次の記事で説明するように) 次の定理を導く力があります。 

多次元 Szemerédi (星座) 定理:

\( S\subset \mathbb{Z}^n \) を与えられた有限集合とする。このとき、集合 \( A\subset \mathbb{Z}^n \) の中に S に相似な図形がないとすると、\[  \# (A\cap [ -N,N]^n )=o(N^n) \quad \text{ as } N\to \infty . \]

 S に相似な図形とは、S を正整数倍して平行移動することで得られる \( \mathbf{Z}^n \) の部分集合を指します。S-星座という用語で表すこともあります。

 

この記事では、hypergraph removal lemma (主張はせきゅーんさんの記事を参照) から多次元 corner 定理がしたがうこと、および、多次元 corner 定理から多次元 Szemerédi 定理がしたがうことを説明していきます。

 

Hypergraph removal から 多次元 corner 定理

Corner-free な集合 \( A\subset \mathbb{Z}^n \) が与えられたとします。

 

データの構成

集合 \( A\cap [ -N,N]^n\) を基にして、次の hypergraph 系を構成します。 まず、台集合は \( \{ 1,\dots ,n+1\} \) で、\(H\) は位数 \(n\) の部分集合全体 \( \begin{pmatrix} \{ 1,\dots ,n+1 \} \\ n \end{pmatrix} \) とします。

 番号 \( 1\le i\le n \) に対して、\( i\) 番目の頂点集合 \(V_i \) を
\[ V_i=\{ \mathbb{Z}^n \text{の中の ``} x_i=m \text{'' の形の超平面}\mid -N\le m\le N \} \] と定義します。\( x_i \) は \( \mathbb{Z}^n\) の i 番目の座標です。\( V_i \) の元の個数は 2N+1 です。n+1 番目の頂点集合は
\[ V_{n+1}=\{ \text{``}x_1+\dots +x_n=m \text{'' の形の超平面} \mid -nN\le m\le nN \} \] と定義します。元の個数は 2nN+1 です。

f:id:motivichomotopy:20181206131404j:plain\( \mathbb{Z}^3\) の場合。垂直な超平面が3方向と、ナナメが1方向

 次に、hypergraph removal lemma における「\( e\in H \) ごとに \( E_e\in \mathcal{A}_e \)」のデータを与えましょう。H の元 e を与えることは、\( j\in \{ 1,\dots ,n+1\} \) を与えることに同値でした。なので、各 \( j\) に対して部分集合 
\[ \bar{E}_j \subset \prod _{i\in \{ 1,\dots ,n+1 \} \setminus j} V_i \] 
を決めることになります(その上で \( E_j:=\bar{E}_j\times V_j \subset \prod\limits _{i=1}^{n+1} V_i \) と定める)。

 超平面 \( H_i\in V_i \) (\( i\in \{ 1,\dots ,n+1\} \setminus j\) )をひとつずつ与えると、その交わり \( \bigcap\limits _{i\in \{ 1,\dots ,n+1 \} \setminus j }H_i \) は \( \mathbb{Z}^n \) の中の 1 点となることに注意しましょう。この点が \( A\cap [ -N ,N]^n \) に属するとき、組 \( (H_1,\dots \widehat{H_j},H_{n+1}) \) は \( \bar{E}_j \) に属する、と決めることにします。言い換えると、 \[ E_j:= \Bigl\{ (H_1,\dots ,H_{n+1}) \Bigm| \bigcap _{\begin{subarray}{c}i=1 \\ (i\neq j)\end{subarray}}^{n+1} H_i \subset A\cap [ -N,N]^n \Bigr\} \subset \prod _{i=1}^{n+1}V_i \] と定めます。

 

補題:

A の中の corner 全体の集合と、集合 \( \bigcap\limits _{j=1}^{n+1}E_j \) の間には一対一対応がある。 この対応において、A の中の自明な corner と、すべての \( H_i \) が共通の点で交わるような組 \( (H_i)_i \) とがちょうど対応する。

 集合 \( \bigcap\limits _{j=1}^{n+1}E_j \) が \[ \bigl\{ (H_1,\dots ,H_{n+1}) \bigm| \begin{array}{c}\text{ 任意の } j \text{ に対して }H_1,\dots ,\widehat{H_j},\dots ,H_{n+1} \\ \text{ が }A\cap [ -N,N]^n\text{ の点で交わる} \end{array} \bigr\} \] と書けることから、補題が成り立つことは見て取れます。

補題:

組 \( (H_1,\dots ,H_{n+1}) \) が自明な corner に対応するとき、任意の成分 \( H_j \) は他の \( n\) 個の成分から復元できる。

 言い換えると、j 番目の成分を忘れる写像 \[  \bigcap _{i=1}^{n+1}E_i \to \prod _{\begin{subarray}{c}i=1 \\ (i\neq j)\end{subarray}}^{n+1} V_i \] は自明な corner の集合に制限すると、任意の j に対して単射である。

これは、\( H_j \) は必然的に、他の n 個の超平面の交わりとして与えられる点を通らねばならないからです。

 

条件と除去補題の発動 

 さて、このように hypergraph 系の構成をした状況で、A が corner-free であるという条件を発動します。Corner-free とは、A の中には corner は自明なものしかないということですから、\( A\cap [ -N,N]^n\) の中の corner の総数は単純に \( \#(A\cap [ -N,N]^n) \) です。準備したグラフの言葉で言うと、\( \# \left( \bigcap\limits _{j=1}^{n+1} E_j \right) =\#(A\cap [ -N,N]^n) \) ということです。とくに \[ \frac{\# \left( \bigcap\limits _{j=1}^{n+1} E_j \right)}{\# \prod\limits _{i=1}^{n+1}V_i } = O\left( \frac{\# A\cap [ -N,N]^n}{2nN\cdot (2N)^n} \right) \le O (\frac{1}{N})\] でこれは何があっても \( N\to \infty \) で 0 に向かいます。

 このとき removal lemma により、上手な \( E'_j\subset E_j \) のとり方があって、\( \bigcap _{j} E'_j =\emptyset  \) かつ \[ \# (E_j\setminus E'_j)=o (N^{n+1}) \quad \text{ as }N\to \infty \tag{HRL} \] が成り立ちます。\(E'_j\) は或る \( \bar{E}'_j\subset \prod\limits _{\begin{subarray}{c} i=1 \\ (i\neq j) \end{subarray}}^{n+1} V_i \) を用いて \( E'_j=\bar{E}'_j\times V_j \) の形で書かれています。

 一方、二番目に述べた補題により、「取り除いた edges の総数」\( \sum _{j}\# (\bar{E}_j\setminus \bar{E}'_j ) \) は corner の個数を下回ることはありません。これを見る一つの方法は、次のような部分集合の下降列 \[ \Bigl( E_1\cap \dots \cap E_{n+1}\Bigr) \supset\Bigl( E_1\cap \dots \cap E_n\cap E'_{n+1}\Bigr) \supset \dots \supset\Bigl( E_1\cap E'_2\cap \dots \cap E'_{n+1}\Bigr) \supset \emptyset  \]
を考え、隣り合う集合の差が、ふたつ目の補題により \( \bar{E}_j\setminus \bar{E}'_j\) に単射で行くことに気をつければよいです: \[ \begin{array}{rcl} E_1\cap \dots \cap & (E_j\setminus E'_j) & \cap \dots \cap E'_{n+1} \\ &\downarrow &\text{forget the j-th entry} \\ &\bar{E}_j\setminus \bar{E}'_j & \end{array}\] 
こうして:\[ \# ( A \cap [ -N,N]^n)\le\sum _{j}\# (\bar{E}_j\setminus \bar{E}'_j )=\sum _{j}\frac{\# (E_j\setminus E'_j)}{\# V_j } .\] 右辺の各項の評価は式 (HRL) で得たとおりですから、あわせると \[ \# ( A \cap [ -N,N]^n)\le \frac{o(N^{n+1})}{N}=o(N^n)  \] ということになります。これが多次元 corner 定理の主張でした。\( \blacksquare \)

 

今日はこのへんで。次の記事へ

 

書いてみて思ったが、方法がわかりやすいからではなく、自分で時間を費やしたから自分にとっては分かりやすいというだけかもしれない・・・。記事もそんなにコンパクトにはまとまらなかったし・・・。ごめんなさい