帰納的ステップ Szemerédiの定理の証明.
とすると写像
は全単射である(二進展開)。
とすると、或る
に対して
を含むが
は含まない。よって、記事9の補題と帰納的ステップにより
は
を導く。
が成り立つので、から開始することによって任意の
に対して
が成立することがわかった。特に
も成立するため、記事9の補題と命題よりSzemerédiの定理が従う。 Q.E.D.
のときは
と進行するが、実は議論を修正することによって
という進行も可能であり、この結果-APの存在が従う。ところが、更に記事9の命題の議論も修正が可能であり、
から
-APの存在性を示せる。これが記事7、記事8で実行したRothの定理の証明である。
帰納的ステップの証明でKeyとなるカウンティング補題を証明する。高次多重混合を複数回適用する。
(i) 任意の
(ii) 任意の
(iii) 任意の
を満たすと仮定する。
このとき、或る
証明. に関する帰納法で証明する。
-項の定数は
毎に変わるが、
は高々
回しか増えないので問題ない。
のときは
を任意にとっても成立する(
に注意)。よって、
として、
では示されたと仮定する。
はそれぞれ
に対するそれら以上のもので、記事6の混合補題(iii)の
に対して
,
が成り立つように選択する。このとき、
が存在して、任意の
に対して
が高々個の例外を除く
に対して成立する。
に対して
を
と定義すると、高々個の例外を除く
に対して
が成り立つ(と
での値が決まれば
は決まる)。
に対し、
を
の
-成分を
に変更したものと定義する。このとき、(iii)より
は
-APである。よって、
は-長方形である。(i)より
-AP
なので、高次多重混合により或る
が存在して
が高々個の例外を除く
について成立する。
と
は
成分まで一致しているので、
の定義と(ii)より左辺は
に等しい。従って、①より、任意のについて
が高々個を除く
について成立する。すなわち、
とすればよい。 Q.E.D.
*1:に注意。