この記事から複数記事用いて「ハイパーグラフ除去補題」の証明を行います。
参考文献
T. Tao, A variant of the hypergraph removal lemma, J. Combin. Theory Ser. A 113 (2006), 1257–1280.
T. Tao, The Gaussian primes contain arbitrarily shaped constellations, J. Anal. Math. 99 (2006), 109–176.
多次元版Szemerédiの定理
正整数に対して、とする。また、を正整数として、集合の上漸近密度を
で定義する。内の形状とはの相異なる点の有限族のことをいう。すなわち、は有限集合で、である。形状がである星座とはを用いてと表される有限族のことをいう。
これは一応今回の主役ではないが、副産物として証明される。
有限加法群に対するSzemerédiの定理
空でない有限集合と関数 に対して、期待値を
と定義する。これまで同様ビッグオー記号やスモールオー記号を使用する。は絶対値が或るで押さえられて、が成り立つ。の以外の依存パラメータをのように添え字を付ける形で表す。は特性関数。
正整数に対して、とする。
有限加法群に対する多次元Szemerédi 多次元版Szemerédiの定理の証明. 任意の形状について、それを含むような(集合として)より大きな形状に対して多次元版Szemerédiの定理の主張を証明できればよい。よって、任意に整数をとって、の元達からなる形状に対して証明する。また、この形状は原点対称であるから、としては零でないことを保証できればよい。とすると、とするとき が成り立つようないくらでも大きい整数が存在する。そのようなをとって固定し、とする。とする(これらは有限加法群である)。に対して、群準同型写像をと定める。で標準射影およびを表すは単射である。とする。このとき、
である。よって、 有限加法群に対するSzemerédiの定理より、のみに依存するが存在して
でなければならない。すなわち、任意のに対してとなるようなが少なくとも個存在する。そのようなのうち、であるようなものをとる(であるようなものは高々個しかないので、はには依存しないことに注意して、を十分大きくとればであるようなものが存在しなくてはならないことがわかる)。なので、であり、と定める。である。次に、を考えて、と定める(は第一成分を取り出す射影)。このとき、である。第一成分を取り出すこととをとることは可換であることから、である。従って、任意のに対してが成り立つ。一方、であることから、
が成り立つ。よって、の取り方から、任意のに対してが示された。であることからである。とすることによって、所望の星座が無数に存在することもわかる。 Q.E.D.
ハイパーグラフ
グラフの辺は二頂点を結ぶものであるが、複数の頂点を連結させたハイパーエッジを考えたものをハイパーグラフという。
ここでは、連結させる頂点の個数を一定にしたハイパーグラフのみを扱う。
一様ハイパーグラフが通常のグラフである。
有限集合上の加法族に関する基礎知識は仮定する(で記述していたが、有限集合上の加法族に関する一般論を展開しているため、としても同様のことが成り立つ): タオのセメレディ論文の§6を読む (その一) - INTEGERS
定義から明らかに
が成り立つ(は加法族の合併)。のアトム全体のなす集合をで表すと、
なる評価ができることがわかる。
ハイパーグラフ除去補題
次が今回の主定理:
が成り立つようなものをとる。このとき、各に対して或るが存在して
が成り立つ。更に、に対して部分加法族が存在して、
かつ任意のに対して
が成り立つ。
加法族の複雑度の評価から、が成り立つことに注意。
ハイパーグラフ除去補題 有限加法群に対するSzemerédiの定理の証明. 最初にが
で生成されている場合に証明する。
を仮定する。としてよい*1。このとき、ハイパーグラフ系を, , と定める。に対してを
と定義する。はに依存しないため、であることがわかる。群準同型 を
と定める。このとき、
が成り立つ。は全射である。理由: は任意のに対して を含む*2。よって、最初に設けた仮定よりがわかる。また、任意のに対してでもある*3。すると、任意のに対して、, となるようなを取れば(は何でもよい)、となる。
よって、は群準同型であることからのによる一様被覆なのでGT1,4の補題を適用でき、
であることから①と仮定より
を得る。よって、ハイパーグラフ除去補題より毎にが存在して、
および
が成り立つ(後半は期待値の定義よりわかる)。なお、多次元Szemerédiの導出には加法族の複雑度に関する主張は不要である。①より
なので、これと②より
が成り立つ。よって、或るが存在して
となる(以下、固定)。理由: そのようなが存在しなかったと仮定すると、に注意して
となって矛盾する。
は超平面 に含まれているので、はの各点で重になっているが、制限写像は単射となる。よって、に注意して、
が成り立つ。の全射性から
である。③と④を合わせると
となって所望の漸近挙動に到達する。以下、最初に設けた仮定をはずす。とし、をゼロ写像とする。を
が生成するの部分群とする。の代表系を一つとる。に対して
とすると、
となる。これより、高々個の例外を除くに対してが成り立つ。理由: が成り立つようなの個数がより大きかったとする。すると、
となって矛盾する。 なるについて、最初のケースを, として適用すると(を考えたことによっての像がとなって適用可能であることが分かる)
が得られる。よって、
となって証明が完了する。 Q.E.D.
重み付きハイパーグラフ除去補題
ハイパーグラフ除去補題を重みつきにバージョアップさせる(これを後々使いたい)。
が成り立つようなものをとる。このとき、各に対して或るが存在して
が成り立つ。更に、に対して部分加法族が存在して,
かつ任意のに対して
が成り立つ。
に対して、となるようなをとって とする。このとき、, が成り立つのでハイパーグラフ除去補題になる。
証明. に対して、
とを定義すると、を合成していることからである。今、
と仮定していることから、
が得られる。理由: であれば が成り立つので、
と仮定すると
となって矛盾する。 従って、ハイパーグラフ除去補題によって複雑度の条件等適切な性質を満たす達が存在して
が成り立つ。毎に
が成り立つので
が得られる。 Q.E.D.