ハイパーグラフ除去補題ー4
が負となるような状況は扱わない。
,
のアトム
に対して、
を
と定める。がgoodでなければ、或る
が存在して
が成り立つ。次の補題は殆どのアトムはgoodであることを意味する。
証明. 定義より
が成り立つので、
と評価できる。一つ目の和は
と評価できる。二つ目の和は
と評価できるが、正則化補題より
が成り立つので、エネルギーギャップ公式と合わせて
が得られ証明が完了する。 Q.E.D.
のときは
とする。カウンティング補題の証明は後回しにして、ハイパーグラフ除去補題の証明を先に完了させる。
カウンティング補題 ハイパーグラフ除去補題の証明. ハイパーグラフ除去補題の設定を考える(「このとき、」の直前まで)。
に対して
を
,
で定める。
とする。各
に対して、
とする(
が生成する
上の
加法族)。
である。
は
に依存して後で決まる整数とする(
は成立している)。また、
は正則化補題および後の議論で要求されるだけ十分成長速度の速い、
のみに依存して定まる関数とする。
以上の設定で正則化補題を適用することによって存在するおよび
をとる。この
達が除去補題が後半に主張する
加法族となる(証明はこれから)。次の不等式を思い出しておく。
後のの選択によって、
が約束されている。
各に対して、
を
と定義する。定義より、がわかる。
なので、補題より
と評価できる。各に対して
なので、
が得られるが、達の中で
が最小であることから、
が
に依存して十分成長速度が速ければ
が成り立つことがわかる。後でわかるようにであれば
となるように
は選択されるため、
が示されたことになる。後は示すべきことはのみである。そこで、
と仮定して、
に含まれるアトムを一つとる。
なので、それは
という形をしている(
)。この
達を固定した上で、
に対しては
とする。このとき、
はgoodではない。
理由: goodであったと仮定すると、カウンティング補題よりが
に依存して十分成長速度が速ければ
が成り立つ。goodの定義の①よりおよび
に対して
が成り立つので、が
に依存して十分成長速度が速ければ
と評価できる。の定数を
とすれば、
が
に依存して十分成長速度が速く、
が
に依存して十分大きければ
を得る。はこの時点で決定されている。
なので、
であれば、或る
が存在して
が成り立つことがわかった。整数に対する関数
は狭義単調減少かつ
であると仮定してよい。
に対する
の選択は、
かつ
を満たすものと定める。が(
に依存して)大きいとこのような
は決まらないが、目標に
という漸近挙動がある以上、そのような
については
と考えて問題ない。そうして、
となって矛盾する。
よって、はgoodではないので、定義より或る
が存在して
が成り立つことがわかる。なる
をとる(
の定義)。このとき、
なので、であれば
であるし、であっても
となって、定義より
が言える。しかし、
であったため矛盾する。 Q.E.D.
追記
その後、勉強はかなり進みましたがこのブログにはまとめないことにしました。