Szemerédiの定理

要点：1 から 2 は密度の定義から直ちに従う。2 から 1 は、1 が破れているときに等差数列を含まない有限集合を大きく離して並べ、正の上密度をもち $k$ 項の等差数列を含まない無限集合を作る。

1：右辺に定義を代入すると $\frac1M\sum_{x,y,z}f(x)g(y)h(z)\sum_t\zeta^{-t(x-2y+z)}$ であり、離散Fourier変換と反転公式 の補題「1 の $n$ 乗根の冪の和（復習）」により内側の和は $x-2y+z\equiv0$ のとき $M$、そうでなければ $0$ である。
2：$M$ が奇数なので $t\mapsto-2t$ は $\mathbb{Z}/M\mathbb{Z}$ の全単射であり、$\sum_t\lvert\widehat g(-2t)\rvert^2=\sum_t\lvert\widehat g(t)\rvert^2$ である。1 と Cauchy–Schwarzの不等式 から
$$ \lvert\Lambda\rvert\le\frac{\max\lvert\widehat h\rvert}M\Bigl(\sum_t\lvert\widehat f(t)\rvert^2\Bigr)^{1/2}\Bigl(\sum_t\lvert\widehat g(t)\rvert^2\Bigr)^{1/2}=\frac{\max\lvert\widehat h\rvert}M\cdot M\,\sigma(f)\,\sigma(g) $$
である。もう一方も同じである。$\square$

$j=0,1,\dots,Q$ について $j\theta$ の小数部分 $\{j\theta\}\in[0,1)$ を考える。$Q+1$ 個の数を $Q$ 個の区間 $[\frac iQ,\frac{i+1}Q)$（$i=0,\dots,Q-1$）に入れると、鳩の巣原理 により同じ区間に入る $j< j'$ がある。$q:=j'-j$ とすると $1\le q\le Q$ で、$q\theta$ と整数 $\lfloor j'\theta\rfloor-\lfloor j\theta\rfloor$ の差は $\{j'\theta\}-\{j\theta\}$ なので、絶対値は $1/Q$ 未満である。$\square$

仮定から $N\ge2^{22}$、$\alpha^2N\ge4$、$\sqrt N\ge2^{11}\alpha^{-2}$ である。
段 1（区間を 3 つに分ける）。 $I_1:=[1,\lfloor N/3\rfloor]$、$I_2:=(\lfloor N/3\rfloor,\lfloor 2N/3\rfloor]$、$I_3:=(\lfloor2N/3\rfloor,N]$（整数の区間）とおくと、$\lvert I_2\rvert\ge\frac{N-2}3$、$\lvert I_1\rvert+\lvert I_3\rvert\le\frac{2N+2}3$ である。$\lvert A\cap I_2\rvert<\frac\alpha2\lvert I_2\rvert$ なら、$\lvert A\cap(I_1\cup I_3)\rvert>\alpha(\lvert I_1\rvert+\lvert I_3\rvert)+\frac\alpha2\lvert I_2\rvert$ なので、$I_1\cup I_3$ での $A$ の密度は $\alpha\bigl(1+\frac{N-2}{4N+4}\bigr)\ge\frac{6\alpha}5$ より大きい（$N\ge14$）。よって $I_1$ か $I_3$ の一方で密度が $\frac65\alpha\ge\alpha+\frac{\alpha^2}5$ を超え、その長さは $\lfloor N/3\rfloor\ge N/4\ge\alpha^2\sqrt N/2^{11}$ 以上なので、それを $P$ とすればよい。以下、$B:=A\cap I_2$ が $\lvert B\rvert\ge\frac\alpha2\lvert I_2\rvert\ge\frac{\alpha N}7$ を満たすとする。
段 2（数え上げ）。 $M:=2N+1$ とし、$[N]$ を $\mathbb{Z}/M\mathbb{Z}$ の部分集合とみる。$x,y,z\in[N]$ について $\lvert x+z-2y\rvert\le2N-2< M$ なので、$x+z\equiv2y\pmod M$ と $x+z=2y$ は同値である。$\mathbf 1_A$ を $A$ の指示関数とし、$f:=\mathbf 1_A-\alpha\mathbf 1_{[N]}$ とおく。

• $A$ は 3 項の等差数列を含まないので、$x,z\in A$、$y\in B$、$x+z=2y$ なら $x=y=z$ であり、$\Lambda(\mathbf 1_A,\mathbf 1_B,\mathbf 1_A)=\lvert B\rvert$ である。
• $y\in I_2$ なら $\frac N3< y\le\frac{2N}3$ なので、$x+z=2y$ を満たす $(x,z)\in[N]^2$ は $\min(2y-1,\,2N-2y+1)>\frac{2N}3-1\ge\frac N2$ 組ある。よって $\Lambda(\mathbf 1_{[N]},\mathbf 1_B,\mathbf 1_{[N]})\ge\frac N2\lvert B\rvert$ である。
• $\sigma(\mathbf 1_{[N]})=\sqrt N$、$\sigma(\mathbf 1_B)=\sqrt{\lvert B\rvert}$、$\sigma(f)^2=\alpha N(1-\alpha)\le\alpha N$ である。
  $\mathbf 1_A=\alpha\mathbf 1_{[N]}+f$ を $\Lambda(\mathbf 1_A,\mathbf 1_B,\mathbf 1_A)$ の第 1・第 3 成分に代入して展開すると、主の項 $\alpha^2\Lambda(\mathbf 1_{[N]},\mathbf 1_B,\mathbf 1_{[N]})$ と、$f$ を含む 3 つの項になる。後者は lem-szt-count の 2 により、$F:=\max_t\lvert\widehat f(t)\rvert$ とおくと合わせて $F\sqrt{N\lvert B\rvert}\,(2\alpha+\sqrt\alpha)\le3\sqrt\alpha\,F\sqrt{N\lvert B\rvert}$ 以下である。よって
  $$ \lvert B\rvert\ge\frac{\alpha^2N}2\lvert B\rvert-3\sqrt\alpha\,F\sqrt{N\lvert B\rvert} $$
  であり、$\alpha^2N\ge4$ から $\frac{\alpha^2N}2\lvert B\rvert-\lvert B\rvert\ge\frac{\alpha^2N}4\lvert B\rvert$ なので
  $$ F\ge\frac{\alpha^{3/2}}{12}\sqrt{N\lvert B\rvert}\ge\frac{\alpha^{3/2}}{12}\sqrt{\frac{\alpha N^2}7}=\frac{\alpha^2N}{12\sqrt7}\ge\eta N,\qquad\eta:=\frac{\alpha^2}{32} $$
  である。すなわち、ある $t$ について $\theta:=t/M$ とおくと $\bigl\lvert\sum_{x=1}^Nf(x)e^{-2\pi ix\theta}\bigr\rvert\ge\eta N$ である。

段 3（短い等差数列に分ける）。 $Q:=\lfloor\sqrt N\rfloor$、$L:=\lfloor\eta Q/(4\pi)\rfloor$ とおく。$Q\ge\sqrt N/2\ge2^{10}\alpha^{-2}$ なので $\eta Q/(4\pi)\ge8/\pi>2$ であり、$L\ge\eta Q/(8\pi)\ge\alpha^2\sqrt N/2^{11}$ である。lem-szt-dirichlet の $q$（$1\le q\le Q$、$\langle q\theta\rangle<1/Q$）をとる。各 $r=1,\dots,q$ について、$[N]$ の中の $q$ で割った余りが $r$ と合同な数を小さい順に並べた公差 $q$ の等差数列を、先頭から $L$ 項ずつに区切る（最後の 1 つは $L$ 項より短くてもよい）。こうして $[N]$ を、公差 $q$ の等差数列 $P_1,\dots,P_m$ に分ける。
$P=\{a,a+q,\dots,a+(\ell-1)q\}$（$\ell\le L$）の上では、$x=a+jq$ について $\lvert e^{-2\pi ix\theta}-e^{-2\pi ia\theta}\rvert\le2\pi j\langle q\theta\rangle\le2\pi L/Q\le\eta/2$ である。$\lvert f\rvert\le1$ なので、$f(P):=\sum_{x\in P}f(x)=\lvert A\cap P\rvert-\alpha\lvert P\rvert$ とおくと
$$ \eta N\le\Bigl\lvert\sum_{x=1}^Nf(x)e^{-2\pi ix\theta}\Bigr\rvert\le\sum_{j=1}^m\bigl(\lvert f(P_j)\rvert+\tfrac\eta2\lvert P_j\rvert\bigr)=\sum_j\lvert f(P_j)\rvert+\tfrac\eta2N $$
である。$\sum_jf(P_j)=\lvert A\rvert-\alpha N=0$ なので、正の部分 $f(P_j)_+:=\max(f(P_j),0)$ について $\sum_jf(P_j)_+=\frac12\sum_j(\lvert f(P_j)\rvert+f(P_j))\ge\frac{\eta N}4$ である。
段 4（長い等差数列を選ぶ）。 $L$ 項より短い $P_j$ は $q\le Q$ 個以下なので、それらの要素数の合計は $QL$ 未満で、$QL\le\eta Q^2/(4\pi)\le\eta N/(4\pi)<\eta N/8$ である。また $f(P_j)_+\le\lvert P_j\rvert$ である。よって長さがちょうど $L$ の $P_j$ について $\sum f(P_j)_+>\frac{\eta N}8$ である。そのような $P_j$ は $N/L$ 個以下なので、ある $P_j$ で $f(P_j)>\frac{\eta L}8$、すなわち $\lvert A\cap P_j\rvert>(\alpha+\frac{\alpha^2}{256})L$ となる。この $P_j$ を $P$ とすればよい。$\square$

$\alpha:=\lvert A\rvert/N$ とする。$\alpha=0$ なら明らかなので $\alpha>0$ とする。
段 1（繰り返し）。 $A_0:=A$、$N_0:=N$ とする。$A_i\subset[N_i]$ が 3 項の等差数列を含まず、密度 $\alpha_i:=\lvert A_i\rvert/N_i\ge\alpha$ をもち、$N_i\ge2^{22}\alpha^{-4}$（$\ge2^{22}\alpha_i^{-4}$）を満たす間は、lem-szt-increment の等差数列 $P=\{a+jq\mid0\le j< N_{i+1}\}$ をとり、$A_{i+1}:=\{j+1\mid a+jq\in A_i\}\subset[N_{i+1}]$ とおく。写像 $j\mapsto a+(j-1)q$ は単射で、$x+z=2y$ の形の関係を保ち、また反映するので、$A_{i+1}$ も 3 項の等差数列を含まない。こうして
$$ \alpha_{i+1}\ge\alpha_i+\frac{\alpha_i^2}{256},\qquad N_{i+1}\ge \gamma\sqrt{N_i},\qquad \gamma:=\frac{\alpha^2}{2^{11}} $$
が得られる。$N_i<2^{22}\alpha^{-4}$ となった最初の $i$ を $i^*$ とする。
段 2（繰り返しの回数）。 密度は増え続け、$1$ を超えない。$0\le j\le\log_2(1/\alpha)$ について、$\alpha_i\in[2^j\alpha,2^{j+1}\alpha)$ となる $i< i^*$ では 1 回ごとに密度が $(2^j\alpha)^2/256$ 以上増えるので、そのような $i$ は $256/(2^j\alpha)+1$ 個以下である。よって
$$ i^*\le\sum_{j\ge0}\frac{256}{2^j\alpha}+\log_2\frac1\alpha+1\le\frac{512}\alpha+\frac2\alpha=\frac{514}\alpha $$
である（$u\ge1$ について $\log_2u+1\le2u$）。$i^*$ が有限であることもこれから分かる。
段 3（$N$ の評価）。 $v_i:=\log N_i-2\log \gamma$ とおくと $v_{i+1}\ge v_i/2$ であり、$\gamma\le1$ なので $v_0\ge0$ である。よって $\log N_{i^*}\ge2\log \gamma+2^{-i^*}\log N$、すなわち $N_{i^*}\ge \gamma^2N^{2^{-i^*}}$ である。$N_{i^*}<2^{22}\alpha^{-4}$ と合わせると $N^{2^{-i^*}}<2^{44}\alpha^{-8}$ なので
$$ \log N<2^{i^*}\log\bigl(2^{44}\alpha^{-8}\bigr)\le2^{514/\alpha}\cdot2^{6/\alpha}=2^{520/\alpha} $$
である。ここで $u:=1/\alpha\ge1$ について $\log(2^{44}u^8)\le31+8(u-1)\le31u\le2^{6u}$ を使った。両辺の対数をとると $\log\log N<\frac{520\log2}\alpha<\frac{361}\alpha$、すなわち $\lvert A\rvert=\alpha N<361N/\log\log N$ である。$\square$

要点：$\{0,\dots,D-1\}^n$ の点のうち原点からの距離が等しいものを集めると、球面は真に凸なので $x+z=2y$ を満たす 3 点は $x=y=z$ しかない。これを $2D$ 進法の数字の並びとして整数に写すと、繰り上がりが起きないので関係 $x+z=2y$ が保たれる。