多次元 corner から多次元 Szemerédi
これは、前の記事からの続きです。
ふたつの定理の主張を繰り返しておきます。
多次元 corner 定理
n を自然数とし、\( A\subset \mathbb{Z}^n \) を corner-free な部分集合とする。このとき \[ \# (A\cap [ -N,N ]^n) = o(N^n) \quad \text{ as } N\to \infty . \]
これは次の定理の特別な場合でした。
多次元 Szemerédi (星座) 定理:
\( S\subset \mathbb{Z}^n \) を与えられた有限集合とする。このとき、集合 \( A\subset \mathbb{Z}^n \) の中に S に相似な図形 (「S-星座」) がないとすると、\[ \# (A\cap [ -N,N]^n )=o(N^n) \quad \text{ as } N\to \infty . \]
多次元 Szemerédi 定理の証明を本格的に始める前に、S の取り方が定理の強さにどう影響するかを確認しておきましょう。
まず、S の平行移動は定理の主張の強さをまったく変えません。 とくに、S は原点を含んでいると仮定しても構いません (S が空集合でない限り・・・)。
また、与えられた S を、より大きいものでとりかえても定理の強さは変わらない (または、むしろ強くなる) ことも、すぐにわかると思います。なので、望むならば \( S\cup (-1)\cdot S \) を考えることで、S は -1 倍について対称であると仮定しても構いません。
とくに、私たちは「S-星座とは S の正整数倍の平行移動である」と定義していましたが、「零でない整数倍の平行移動」という若干緩い定義を採用してもよいです。
(符号を気にしているのは、corner の定義では \( \overrightarrow{a}+d\overrightarrow{e}_i\) に現れる整数係数 d の符号に条件をつけていなかったことと関係がありますが、そんなに深く気にすべきことではありません。)
さらに S を大きくすれば、S は \( \mathbb{Z}^n \) をアーベル群として生成すると仮定してもよいです。
さて、以上のことをすべて仮定したうえで、\( S=\{ v_0=\overrightarrow{0} , v_1,\dots , v_s \} \) とします。アーベル群の全射 \( \phi\colon\mathbb{Z}^s\twoheadrightarrow \mathbb{Z}^n \) を、基底ベクトル \( {e}_i \) を \( v_i \) に写すことにより定義します。
A が S-星座を含んでいないと仮定すると、逆像 \( \phi^{-1}(A)\subset \mathbb{Z}^s \) は非自明な corner を含みません。（対偶が正しいことが見て取れると思います。ここに星座の概念を緩めたことが効いています。）
この状況に多次元 corner 定理を適用したいです。 \( \phi ^{-1}(A) \) が corner-free なので、多次元 corner 定理により \[ \# \bigl( \phi ^{-1}(A) \cap [ -N,N]^s \bigr) =o(N^s)\quad \text{ as } N\to \infty \] がわかります。左辺と \( \# (A\cap [-N,N]^n) \) を結びつけなければなりません。
補題:
φ にのみ依存する正整数 D が存在し、任意の N と \( a\in [ -N,N]^n\) に対して、\[ \phi ^{-1}(a)\cap [ -DN,DN]^s \] は \( N^{s-n} \) 個以上の元を含む。
とくに、\( \phi ^{-1}(A)\cap [ -DN,DN]^s \) は少なくとも \( \# (A\cap [ -N,N]^n)\cdot N^{s-n} \) 個の元を含む。
証明 φ は全射なので、切断 \( σ\colon \mathbb{Z}^n\hookrightarrow \mathbb{Z}^s \) がとれます ( \( \phi\circ σ =\mathrm{id}_{\mathbb{Z}^n} \) となる群準同型ということです)。 また、ker (φ) は階数 s-n の自由アーベル群なので、基底 \( u_1,\dots ,u_{s-n}\in \mathrm{ker}(\phi )\) をとります。
ベクトルども \( σ(e_j),u_i \) は \( \mathbb{Z}^s \) の基底になっています。これらの成分の絶対値のうち、もっとも大きなものを D とおきます。（これらのベクトルは Kramer の公式または掃き出し法などアルゴリズミックにとってこられるので、D は望むならば φ の成分の絶対値の最大値の s 乗くらいで抑えられると思います。）
\( a\in [ -N,N]^n \) が任意に与えられていました。 このとき、次の \( N^{s-n}\) 個のベクトル \[ σ (a)+\sum _{i=1}^{s-n} c_iu_i \qquad ( \forall c_i\in [ -N, N], \quad \forall i=1,\dots ,s-n ) \tag{\(\bigstar \) }\] を考えます (実際は \( (2N+1)^{s-n}\) 個ですが、まあいいでしょう)。まず、これらがすべて、\( \phi ^{-1}(a)\) に属していることは暗算で分かるはずなので、確認してください。
σ (a) は φ で写すと a に戻る。
つぎに、σ(a) の各成分の絶対値は、nDN を超えません。なぜなら、\(a=\sum\limits _{j=1}^n a_j e_j \) (\( a_j\in [-N,N] \))と書けたとすると、\[ σ (a)=\sum _{j=1}^na_j σ(e_j) \] となりますが、この各成分は絶対値 DN 以下のものの n 個の和だからです。
同様の理由で、\( \sum\limits _{i=1}^{s-n} c_iu_i \) の各成分の絶対値は \( (s-n)DN \) を超えません。 こうして、式 (\(\bigstar \)) のベクトルはすべて、 \( [ -sDN,sDN]^s \) の中にあります。そこで、sD のことを改めて D と呼ぶことにすると、補題の主張をみたします。\( \blacksquare \)
補題を、補題の直前で得た評価と合わせると \[ \# (A\cap [ -N,N]^n)\cdot N^{s-n}\le \# (\phi ^{-1}(A)\cap [ -DN,DN]^s) = o((DN)^s)=o(N^s) \] したがって \[ \# (A\cap [ -N,N]^n)=o(N^{n}) \] となります。多次元 Szemerédi 定理が導かれました。
