-AP に対して、一様確率測度をに対して
と定義する。
に対して、が-長方形であるとは、を用いて
と表されるもののことをいう。に付随する写像をで定義する。
-長方形に対して、各毎に-AP を
で定義し、各毎に-AP を
で定義する。また、一様確率測度をに対して
と定義する。このとき、二重カウンティング恒等式
が成り立つ。
確率測度に対して、全変動を
で定義する。
証明. を任意にとる。このとき、
なので、
が成り立つ。とが重ならない部分は高々なので、
が得られる。は任意だったので証明が完了する。 Q.E.D.
APからなる集合が非有界であるとは、集合が非有界であることと定義する。非有界なとに対して、のに沿った上密度を
と定義し、のに沿った下密度を
と定義する。定義から明らかにが成り立つ。が成り立つとき、その値をのに沿った密度といい、と表す。
例1) の場合、はの上漸近密度で は下漸近密度、は漸近密度(自然密度)である。
例2) の場合、はのBanach上漸近密度で はBanach下漸近密度、はBanach漸近密度である(Banach上漸近密度しか使わない)。
は非有界とし、とする。任意のに対してが存在し、長さが以上のに対して
が成り立ち、いくらでも長さが大きいが存在して
が成り立つ。のに沿った密度が存在すれば、任意のに対してが存在して
が長さが以上のに対して成り立つ(定義の確認)。
注意) この記号設定においては、Szemerédiの定理は と簡潔に表現することができる。この同値性に関するは自明であるが、は次のように示す*1: を任意にとる。が成り立つと仮定すると、②より
が成り立つような-AP が存在する()。任意のに対してであると仮定すると
となって矛盾する。よって、或るが存在してとなる。これはが-APを含むことを示しており、は任意であるためSzemerédiの定理が従う。
証明. これは
からわかる。 Q.E.D.
証明. 劣加法性と背理法で示せる。 Q.E.D.
重要な概念を定義する。
とりあえずは自明に二重カウンティング性質を満たす。二重カウンティンング性質の威力は次の命題の形で発揮される。
(i) -AP に対して、高々個の例外を除いて-AP はに属する。
(ii) -長方形に対して、個の-AP がに属するならば、高々個の例外を除いて-AP はに属する。
証明. (i)の証明: は二重カウンティング性質の定義のものとし、は定義のものとのをとって再定義する。
とすると、である。また、補題1より
が成り立つので、の二重カウンティング性質をとして適用することにより、高々個の例外を除いて、に対して
である。
(ii)の証明: として、を
と定義する。このとき、二重カウンティング恒等式から
なので、である。よって、 の二重カウンティング性質をとして適用することにより主張が従う。 Q.E.D.
*1:セミナー中に飛鳥さんに指摘していただきました。