2017-09-10

ロスによるエルデシュ・トゥーラン予想の解決

等間隔に並ぶ素数を追い求めて

$A(x)$ を $x$ に関する $A$ -数列の最大項数とします(この記事ではRothに従って $x$ や $y$ も正整数を表します)。Rothは以下のErdős-Turánによる予想

integers.hatenablog.com

Erdős-Turán予想 $\ \ \ A(x) = o(x), \quad (x \to \infty).$

を1953年までに解決しました*1。彼はその直後、より精密な定理

定理 (Roth, 1953) $a(x):=x^{-1}A(x)$ とする。このとき、漸近公式

$\displaystyle a(x) = O\left(\frac{1}{\log \log x}\right), \quad (x \to \infty)$

が成り立つ。

を証明しています。この記事ではRothの論文に従って、定理の証明を解説します。Szemerédiの定理に続く最初の大成果です。なお、彼はこの二年後にFields賞受賞理由となる有名なRothの定理を証明しています。

基本事項

基本事項の番号はErdős-Turánの記事の続きとします。

基本事項４ $a, b, u_i$ は正整数。このとき、 $au_1+b, au_2+b, \dots, au_r+b$ が $A$ -数列であることと $u_1, u_2, \dots, u_r$ が $A$ -数列であることは同値。

この簡単な事実から次がわかります：

補題１ $N$ を正整数とするとき、 $A(N)$ は長さ $N$ の等差数列から部分列として $A$ -数列を選び出せる数の最大値に等しい。

$a+b < 2a+ b < \dots < aN+b$ から $A$ -部分列 $au_1+b < au_2+b < \cdots < au_r+b$ を取り出した際、 $N$ に関する $A$ -数列 $1 \leq u_1 < u_2 < \cdots < u_r \leq N$ が付随します。

もう一つ基本事項を用意しておきます。

基本事項５ 正整数 $x, y$ に対して

1. $\ a(xy) \leq a(y),\quad$ 2. $\ a(x) \leq (1+yx^{-1})a(y),\quad$ 3. $\ x^{-1}\leq a(x) \leq 1$

が成立する。

証明. 基本事項３より $A(xy) \leq xA(y)$ なので1. が従う。また、

$\displaystyle A(x) \leq A\left( \left( \left[\frac{x}{y} \right]+1 \right)y\right) \leq \frac{x+y}{y}A(y)$

が成り立つ。理由: $\left( \left[\frac{x}{y}\right]+1 \right)y > x$ より左側の不等式が成立。右側は最初に述べた不等式から

$\displaystyle \left[\frac{x}{y}\right]+1 \leq \frac{x}{y}+1 = \frac{x+y}{y}$

に注意すれば成立することがわかる。よって、両端を比較することにより2. が示された。3. は定義より明らか。 Q.E.D.

指数和の評価１

以下、 $M$ に関する $A$ -数列 $u_1, \dots, u_{U}$ を固定します( $M$ も $u_i$ も正整数)。実数 $\theta$ に対して $e(\theta) := e^{2\pi\sqrt{-1}\theta}$ という記号を用います( $\left|e(\theta)\right|=1$ )。 $\alpha$ を実数とします。このとき、指数和 $S$ を

$\displaystyle S=S(\alpha):=\sum_{k=1}^Ue(\alpha u_k)$

で定義します。 $S$ に対し、補助的な指数和 $S'$ を導入します。

補題２ $\alpha \in \mathbb{R}$ に対して、整数 $h, \$ 正整数 $q, \$ 実数 $\beta$ が存在して

1. $\ h, q$ は互いに素 $,\quad$ 2. $\ \displaystyle \alpha = \frac{h}{q}+\beta,\quad$ 3. $\ q \leq \sqrt{M},\quad$ 4. $\ \displaystyle q\left|\beta\right| \leq \frac{1}{\sqrt{M}}$

が成り立つ。

証明. これはDirichletの近似定理ディリクレの近似定理 - INTEGERS

において $a \mapsto q, \ b \mapsto h, \ n \mapsto [\sqrt{M}]$ とすればよい。 $(h, q)=1$ とできるのは明らか。 Q.E.D.

補題２によって存在する $h, q, \beta$ を取って固定し、 $m < \sqrt{M}$ なる正整数 $m$ に対し、指数和 $S'$ を

$\displaystyle S'=S'(m):=\frac{a(m)}{q}\sum_{r=1}^qe\left( \frac{rh}{q} \right) \sum_{n=1}^Me(\beta n)$

と定義します。 $S'$ は $h, q, \beta$ の選択に依る量ですが、 $q > 1$ ならば $S'=0$ となります。

理由: $(h, q)=1$ なので $h/q$ が整数でないことに注意すれば、等比数列の和の公式によって

$\displaystyle \sum_{r=1}^qe\left( \frac{rh}{q} \right) = \frac{e(h/q)\left(1-e(h)\right)}{1-e(h/q)} = 0$

である。

この節の目標は次の評価を示すことです：

補題３ 上記設定において

$\left|S-S'\right| = Ma(m)-U+O(m\sqrt{M})$

が成り立つ。

証明. まず、

$\displaystyle S= \frac{1}{mq}\sum_{r=1}^q\sum_{n=1}^M\sum_{\substack{n \leq u_k < n+mq \\ u_k \equiv r \pmod{q}}}e(\alpha u_k)+O(mq)$

と書くことができる。理由: $u_k, m, q$ に対して $n \leq u_k < n+mq$ を満たすような整数 $n$ は

$u_k-mq+1, \ u_k-mq+2, \ \dots, \ u_k-1, u_k$

の丁度 $mq$ 個である。固定している $u_k$ のうち、 $mq \leq u_k \leq M$ を満たすものについては上記 $mq$ 個の数は全て $[1, M]$ に属す。従って、

$\displaystyle \frac{1}{mq}\sum_{r=1}^q\sum_{n=1}^M\sum_{\substack{n \leq u_k < n+mq \\ u_k \equiv r \pmod{q}}}e(\alpha u_k)$ −①

における $e(\alpha u_k)$ の係数は $1$ である。 $u_k < mq$ なる $u_k$ 達は高々 $mq$ 個しかなく、 $e(\alpha u_k)$ の係数は $1$ 未満なので、その寄与は $O(mq)$ である。以上の考察から $S$ の書き換えが従う。

次に、①の内側の和について

$\displaystyle e(\alpha u_k) = e\left( \frac{rh}{q} \right) e(\beta n) + O(mq\left| \beta \right|)$

と変形できることに注意する。理由: $\displaystyle \alpha = \frac{h}{q}+\beta$ なので $\displaystyle e(\alpha u_k) = e\left( \frac{h}{q}u_k\right) e(\beta u_k).$

一つ目については $u_k \equiv r \pmod{q}$ なので $\displaystyle e\left(\frac{h}{q}u_k\right) = e\left( \frac{rh}{q} \right).$ また、 $n \leq u_k < n+mq$ なので $u_k=n+w_k, \ 0\leq w_k < mq$ と書け、

$e(\beta u_k) = e(\beta n+\beta w_k) = e(\beta n)e(\beta w_k)$

である。ここで

$e(\beta w_k) = 1+(e(\beta w_k)-1) = 1+O(\left|\beta w_k\right|) = 1+O(mq\left|\beta\right|)$

なので( $\left|\beta w_k\right| < 1$ に注意)、

$\displaystyle e(\alpha u_k) = e\left( \frac{rh}{q} \right) e(\beta n)\left( 1+O(mq\left|\beta \right|) \right) = e\left( \frac{rh}{q} \right) e(\beta n) + O(mq\left| \beta \right|)$

がわかった。また、①の内側の和は高々 $A(m)$ 項の和である。理由: $n \leq u_k < n+mq$ , $u_k \equiv r \pmod{q}$ に関する和であるが、これは $[n, n+mq)$ にある長さ $m$ の等差数列のうち $A$ -数列をなす部分のみをわたっている。従って、補題１から高々 $A(m)$ 項である。

そこで、その項数を $A(m)-D(n, m, q, r)$ と表すことにする( $D(n, m, q, r) \geq 0$ )。以上わかったことをまとめると

$\begin{align}S&=\frac{1}{mq}\sum_{r=1}^q\sum_{n=1}^M(A(m)-D(n, m, q, r)) \left( e\left( \frac{rh}{q} \right) e(\beta n)+O(mq\left|\beta\right|) \right) +O(mq) \\ &= S'-\frac{1}{mq}\sum_{r=1}^qe\left( \frac{rh}{q} \right) \sum_{n=1}^Me(\beta n)D(n, m, q, r)+O(Mmq \left|\beta\right|)+O(mq) \\ &= S'-\frac{1}{mq}\sum_{r=1}^qe\left( \frac{rh}{q} \right) \sum_{n=1}^Me(\beta n)D(n, m, q, r)+O(m\sqrt{M})\end{align}$ −②

を得る。ここで、2つ目の等号には基本事項５の3. を使い、3つ目の等号には $q \leq \sqrt{M}, \ q\left|\beta\right| \leq 1/\sqrt{M}$ を用いた。

さて、 $q > 1 \Longrightarrow S'=0$ の議論を除いて、従ってこの議論中においては $(q, h)=1$ という性質を用いていない。故に、②において $\alpha = 0, \beta=0, h=0$ の場合を考えることができて、

$\displaystyle U=Ma(m)-\frac{1}{mq}\sum_{r=1}^q\sum_{n=1}^MD(n, m, q, r)+O(m\sqrt{M})$

を得る。よって、これらを組み合わせることにより

$\begin{align}\left|S-S'\right| &\leq \left| -\frac{1}{mq}\sum_{r=1}^qe\left( \frac{rh}{q} \right) \sum_{n=1}^Me(\beta n)D(n, m, q, r)\right| + O(m\sqrt{M}) \\ &\leq \frac{1}{mq}\sum_{r=1}^q\sum_{n=1}^MD(n, m, q, r) + O(m\sqrt{M}) \leq Ma(m)-U+O(m\sqrt{M})\end{align}$

が示された。 Q.E.D.

指数和の評価２

前節の結果をより特殊なケースに適用していきます。 $m$ を正の偶数、 $2N=m^4, \ u_1, \dots, u_U$ を $2N$ に関する極大 $A$ -数列とします。すなわち、

$U=A(2N)=2Na(2N) \leq 2Na(m)$ −③

が成り立ちます(最後の不等号は基本事項５の1. より)。 $u_1, \dots, u_U$ のうち偶数であるものが $2v_1, 2v_2, \dots, 2v_{V}$ であるとします。

$2 \leq 2v_1 < 2v_2 < \cdots < 2v_{V} \leq 2N$

から

$1 \leq v_1 < v_2 < \cdots < v_{V} \leq N$

という $A$ -数列が得られるので(基本事項４)、基本事項５の1. と合わせて

$V \leq A(N) \leq Na(m)$ −④

が成り立ちます。計算: $2N=m^4$ より $m$ は偶数なので

$A(N) = Na(N) = Na(m^4/2)=Na(m^3/2 \cdot m) \leq Na(m)$ .

$u_1, \dots, u_U$ のうち奇数であるものが $2w_1-1, \dots, 2w_{W}-1$ であったとすると $w_1, \dots, w_W$ は $N$ に関する $A$ -数列(基本事項４)なので

$A(2N) = V+W \leq V+A(N)$

であり、

$V \geq A(2N)-A(N) \geq 2Na(2N)-Na(m)$ −⑤

が得られます(④を使いました)。

定義実数 $\alpha$ に対して

$\begin{align} &f_1(\alpha) := \sum_{k=1}^Ue(\alpha u_k), \quad f_2(\alpha) := \sum_{k=1}^Ve(\alpha v_k) \\ &F_1(\alpha) := a(m)\sum_{n=1}^{2N}e(\alpha n), \quad F_2(\alpha) := a(m)\sum_{n=1}^Ne(\alpha n)\end{align}$

と $f_r(\alpha), \ F_r(\alpha)$ を定義する( $r=1, 2$ )。

③、④より

$f_r(\alpha ) = O(Na(m)), \quad F_r(\alpha) = O(Na(m)), \quad (r=1, 2)$ −⑥

です。

補題４ 任意の実数 $\alpha$ に対して

$\displaystyle f_r(\alpha)-F_r(\alpha) = O\left( N\{a(m)-a(2N)\}+N^{\frac{3}{4}} \right), \quad (r=1, 2)$

が成立する。

証明. (主張はそれらの選択に依らないものであるが)補題２のDirichlet近似を一つ選択して証明する。

$q=1, r=1$ の場合. $M=2N$ とすれば前節のセッティングで $f_1(\alpha)=S(\alpha)$ となっている。また、

$\displaystyle S' = a(m)e(h)\sum_{n=1}^{2N}e(\beta n)$

であり、 $\alpha = h+\beta$ なので $e(\alpha n) = e(\beta n)$ である。よって、 $F_1(\alpha)=S'$ となっている。補題３と③より

$\displaystyle f_1(\alpha)-F_1(\alpha) = O\left( 2Na(m)-U+O(m\sqrt{2N}) \right) = O\left( N\{a(m)-a(2N)\}+N^{\frac{3}{4}}\right)$

を得る。

$q=1, r=2$ の場合. $N$ に関する $A$ -数列 $v_1, \dots, v_{V}$ を考えると、その設定( $M=N$ )で $f_2(\alpha)=S(\alpha)$ となる。また、先ほどと同様に $F_2(\alpha) = S'$ である。よって、補題３と⑤より

$\displaystyle f_2(\alpha)-F_2(\alpha) = O\left( Na(m)-V+O(m\sqrt{2N}) \right) = O\left( N\{a(m)-a(2N)\}+N^{\frac{3}{4}}\right)$

を得る。

$q\neq 1$ の場合. この場合 $S'=0$ であったので、 $q=1$ の場合において $f_r(\alpha)-F_r(\alpha)$ を $f_r(\alpha)$ に置き換えた評価が成り立つ。よって、 $F_r(\alpha)$ を評価すればよい。ここで、Weyl Differencing - INTEGERSの補題１より

$\displaystyle \sum_{n=1}^Me(\alpha n) = O(\left\| \alpha \right\|^{-1})$ −⑦

が成り立つことを思い出す。上記記事の補題３に近い議論をする。すなわち、

$\displaystyle q > 1, \quad (q, h) = 1, \quad \alpha = \frac{h}{q}+\beta, \quad q \leq \sqrt{M}, \quad \left| \beta \right| \leq \frac{1}{q\sqrt{M}}$

であることから

$\displaystyle \left\| \alpha \right\| \geq \frac{1}{q} -\frac{1}{q\sqrt{M}} \geq \frac{1}{2\sqrt{M}}$

を得る。よって、 $r=1, 2$ に応じて $M=2N, N$ とすることにより

$\displaystyle F_r(\alpha) = a(m)\sum_{n=1}^Me(\alpha n) = a(m)O\left( \left\|\alpha \right\|^{-1}\right) = O\left( \sqrt{N} \right) = O\left( N^{\frac{3}{4}}\right)$

と評価できる(基本事項５の3. より $a(m) \leq 1$ に注意)。 Q.E.D.

命題１ 任意の実数 $\alpha$ に対して

$\displaystyle f_1(\alpha)f_2^2(-\alpha)-F_1(\alpha)F_2^2(-\alpha) = O\left( \{Na(m)\}^2\left( N\{a(m)-a(2N)\}+N^{\frac{3}{4}}\right) \right)$

が成り立つ。

証明. 三角不等式によって

なので、⑥と補題４より所望の評価が得られる。 Q.E.D.

命題２ $0 < \eta < \alpha < 1-\eta$ であれば

$f_1(\alpha) = O\left( a(m)\eta^{-1}+N\{a(m)-a(2N)\}+N^{\frac{3}{4}}\right).$

証明. $\left\|\alpha\right\| = \min\{\alpha, 1-\alpha\} > \eta$ なので、⑦より

$\displaystyle F_1(\alpha) = a(m)O\left(\left\|\alpha\right\|^{-1}\right) = O\left(a(m)\eta^{-1}\right)$

である。よって、補題４と合わせて証明が終わる。 Q.E.D.

Hardy-Littlewoodの円周法

設定は前節と同じまま、Hardy-Littlewoodの円周法によって $a(m)$ に関する不等式を帰結します。

命題３ 任意の実数 $\eta$ に対して

$\displaystyle \int_{-\eta}^{1-\eta}f_1(\alpha)f_2^2(-\alpha)d\alpha = V \leq Na(m)$

が成り立つ。

証明. $\ f_r(\alpha)$ の定義より

$\begin{align} \int_{-\eta}^{1-\eta}f_1(\alpha)f_2^2(-\alpha)d\alpha &= \int_{-\eta}^{1-\eta}\sum_{h=1}^Ue(\alpha u_h)\sum_{k=1}^Ve(-\alpha v_k)\sum_{l=1}^Ve(-\alpha v_l) d\alpha \\ &= \sum_{h, k, l}\int_{-\eta}^{1-\eta}e\left( \alpha (u_h-v_k-v_l) \right)d\alpha\end{align}$

であり、 $e$ は周期 $1$ の関数なのでこの積分は $\eta$ に依らず

$\displaystyle \int_{-\eta}^{1-\eta}f_1(\alpha)f_2^2(-\alpha)d\alpha = \sum_{h, k, l}\int_{0}^{1}e\left( \alpha (u_h-v_k-v_l) \right)d\alpha$

となる。ここで、積分を実行すると

$\displaystyle \int_0^1e\left( \alpha(u_h-v_k-v_j)\right) d\alpha = \begin{cases}1 & (u_h=v_k+v_l) \\ 0 & (\text{otherwise})\end{cases}$

なので、

$\displaystyle \int_{-\eta}^{1-\eta}f_1(\alpha)f_2^2(-\alpha)d\alpha = \#\{(h, k, l) \mid u_h=v_k+v_l\}$

がわかった。今、 $u_1, \dots, u_{U}$ は $A$ -数列なので $u_h=v_k+v_l$ となるのは(それは $2u_h=2v_k+2v_l$ ということなので) $k=l, u_h=2v_k$ である場合に限る。つまり、上の集合の元の個数は $V$ に等しい。従って、④によって積分値を上から評価できる。 Q.E.D.

補題５ $\ \ \ \displaystyle \int_0^1\left|f_2(\alpha)\right|^2d\alpha = V \leq Na(m).$

証明. $\ \displaystyle f_2(\alpha) = \sum_{k=1}^Ve(\alpha v_k)$ より

$\displaystyle \left|f_2(\alpha)\right|^2 = \sum_{k=1}^Ve(\alpha v_k)\sum_{l=1}^Ve(-\alpha v_l) = \sum_{k, l}e\left( \alpha (v_k-v_l) \right)$

であり、

$\displaystyle \int_0^1e\left( \alpha (v_k-v_l)\right)d\alpha = \delta_{k, l}$

なので

$\displaystyle \int_0^1\left|f_2(\alpha)\right|^2d\alpha = \sum_{k, l}\delta_{k, l} = V$

と計算できる( $\delta_{k, l}$ はKroneckerデルタ)。 Q.E.D.

以下、 $\displaystyle 0 < \eta < \frac{1}{2}$ を満たすと仮定します。

変数変換 $\alpha \mapsto 1-\alpha$ により

$\displaystyle \int_{\eta}^{1-\eta}\left|f_2^2(-\alpha)\right|d\alpha = \int_{\eta}^{1-\eta}\left|f_2^2(\alpha)\right|d\alpha$

なので、命題２と補題５より

$\displaystyle \int_{\eta}^{1-\eta}f_1(\alpha)f_2^2(-\alpha)d\alpha = O\left( \left\{a(m)\eta^{-1}+N\left( a(m)-a(2N)\right)+N^{\frac{3}{4}}\right\}Na(m)\right)$ −⑧

です。命題１からは

$\displaystyle \int_{-\eta}^{\eta}f_1(\alpha)f_2^2(-\alpha)d\alpha = \int_{-\eta}^{\eta}F_1(\alpha)F_2^2(-\alpha)d\alpha + O\left( \eta\left\{Na(m)\right\}^2\left(N\left\{a(m)-a(2N)\right\}+N^{\frac{3}{4}}\right)\right).$ −⑨

次は

$\displaystyle \int_{-\eta}^{\eta}F_1(\alpha)F_2^2(-\alpha)d\alpha = \int_{-\frac{1}{2}}^{\frac{1}{2}}F_1(\alpha)F_2^2(-\alpha)d\alpha + O\left( a^3(m)\eta^{-2}\right)$ . −⑩

理由: $\ \displaystyle \int_{-\frac{1}{2}}^{\frac{1}{2}}-\int_{-\eta}^{\eta} = \int_{\eta}^{\frac{1}{2}}+\int_{-\frac{1}{2}}^{-\eta}$ であり、

$\begin{align} \int_{\eta}^{\frac{1}{2}}F_1(\alpha)F_2^2(-\alpha)d\alpha + \int_{-\frac{1}{2}}^{-\eta}F_1(\alpha)F_2^2(-\alpha)d\alpha &= \int_{\eta}^{\frac{1}{2}}\left\{F_1(\alpha)F_2^2(-\alpha)+F_1(-\alpha)F_2^2(\alpha)\right\}d\alpha \\ &= \int_{\eta}^{\frac{1}{2}}\left\{F_1(\alpha)F_2^2(-\alpha)+\overline{F_1(\alpha)F_2^2(-\alpha)}\right\}d\alpha \\ &= 2\int_{\eta}^{\frac{1}{2}}\mathrm{Re}\left( F_1(\alpha)F_2^2(-\alpha) \right)d\alpha \quad \in \mathbb{R} \\ &\leq 2\int_{\eta}^{\frac{1}{2}}\left|F_1(\alpha)F_2^2(-\alpha)\right|d\alpha\end{align}$

と変形できる。ここで、 $0 < \alpha < 1/2$ のときは $\left\|\pm \alpha\right\| = \alpha$ なので、⑦より

$\displaystyle F_r(\pm \alpha) = O(a(m)\alpha^{-1})$

が $r=1, 2$ に対して成り立ち、

$\displaystyle \int_{\eta}^{\frac{1}{2}}\left|F_1(\alpha)F_2^2(-\alpha)\right|d\alpha = O\left( a^3(m)\int_{\eta}^{\frac{1}{2}}\frac{d\alpha}{\alpha^3}\right) = O\left( a^3(m)\left( \frac{\eta^{-2}}{2}-2 \right) \right)= O\left( a^3(m)\eta^{-2} \right)$

を得る。

と来て、最後に次の積分を計算します：

$\begin{align} \int_{-\frac{1}{2}}^{\frac{1}{2}}F_1(\alpha)F_2^2(-\alpha)d\alpha &= a^3(m)\int_{-\frac{1}{2}}^{\frac{1}{2}}\sum_{n=1}^{2N}e(\alpha n)\sum_{n'=1}^Ne(-\alpha n')\sum_{n''=1}^Ne(-\alpha n'')d\alpha \\ &= a^3(m)\sum_{n, n', n''}\int_{-\frac{1}{2}}^{\frac{1}{2}}e\left( \alpha (n-n'-n'') \right) d\alpha \\ &= a^3(m)\times \#\{n=n'+n'' \mid 1 \leq n \leq 2N, \ 1 \leq n', n'' \leq N\}.\end{align}$

ここで、 $\#\{n=n'+n'' \mid 1 \leq n \leq 2N, \ 1 \leq n', n'' \leq N\}=N^2$ です。

従って、

$\begin{align} a^2(m) &= \left\{ N^2a(m)\right\}^{-1}\int_{-\frac{1}{2}}^{\frac{1}{2}}F_1(\alpha)F_2^2(-\alpha)d\alpha \\ &\stackrel{\text{⑩}}{=} \left\{N^2a(m)\right\}^{-1} \left( \int_{-\eta}^{\eta}F_1(\alpha)F_2^2(-\alpha)d\alpha + O\left( a^3(m)\eta^{-2}\right) \right) \\ &\stackrel{\text{⑨}}{=} \left\{N^2a(m)\right\}^{-1} \Biggl( \int_{-\eta}^{\eta}f_1(\alpha)f_2^2(-\alpha)d\alpha \\ &\ \ \ \ \ \ \ \ \ \ + O\left( \eta\left\{Na(m)\right\}^2\left(N\left\{a(m)-a(2N)\right\}+N^{\frac{3}{4}}\right)\right)+O\left(a^3(m)\eta^{-2}\right)\Biggr) \\ &\stackrel{\text{⑧}}{=} \left\{N^2a(m)\right\}^{-1}\Biggl( \int_{-\eta}^{1-\eta}f_1(\alpha)f_2^2(-\alpha)d\alpha \\ &\ \ \ \ \ \ \ \ \ \ +O\left( \left\{a(m)\eta^{-1}+N\left(a(m)-a(2N)\right)+N^{\frac{3}{4}}\right\}Na(m)\right) \\ & \ \ \ \ \ \ \ \ \ \ +O\left( \eta\left\{Na(m)\right\}^2\left(N\left\{a(m)-a(2N)\right\}+N^{\frac{3}{4}}\right)\right) + O\left( a^3(m)\eta^{-2}\right) \Biggr) \\ &\stackrel{\text{命題３}}{=}O\left(N^{-1}+a(m)N^{-1}\eta^{-1}+a(m)-a(2N)+N^{-\frac{1}{4}}\right. \\ &\left. \ \ \ \ \ \ \ \ \ \ \ \ \ \ +\eta a(m) \left(N\left\{a(m)-a(2N)\right\}+N^{\frac{3}{4}}\right)+a^2(m)N^{-2}\eta^{-2} \right)\\ &=O\left(a(m)N^{-1}\eta^{-1}+a^2(m)N^{-2}\eta^{-2}+\left\{\eta Na(m)+1\right\}\left\{a(m)-a(2N)+N^{-\frac{1}{4}}\right\} \right)\end{align}$

と計算できました。以下、 $c_i$ はパラメータに依らない絶対正定数とします。 $\delta:=N^{-1}\eta^{-1}$ として $2N=m^4$ に注意すると、

$a^2(m) < c_1\left\{a(m)\delta +a^2(m)\delta^2+(\delta^{-1}a(m)+1)\left(a(m)-a(m^4)+m^{-1}\right)\right\}$

と書き換えられます。 $x$ を正の整数とし、 $m:=2^{4^x}, \ b(x):=a(m)$ としましょう。すると、最終的に

帰結次の不等式が成り立つ:

$b^2(x) < c_1\left\{ b(x)\delta + b^2(x)\delta^2+(\delta^{-1}b(x)+1)\left(b(x)-b(x+1)+2^{-4^x}\right)\right\}.$

が得られました。

Rothの定理の導出

ここまでに円周法を使った評価を行いましたが、前節の最終帰結からRothの定理を導出する部分は初等的ながらも技巧的で面白いです。

$c_1 > 1$ ととっておきます(大きくするのは自由なので)。また、 $\delta :=(2c_1)^{-1}b(x)$ とします。このとき、

$\displaystyle \eta= N^{-1}\delta^{-1} = 4c_1m^{-4}a^{-1}(m)$

なので、基本事項５の3. より $\eta \leq 4c_1m^{-3}$ が成り立ちます。つまり、 $m$ が十分大きければ、前節の条件 $0 < \eta < 1/2$ は満たされます。基本事項５の3. より $b(x) \leq 1$ であり、

$\displaystyle c_1\delta= \frac{b(x)}{2}, \quad c_1\delta^2 = \frac{b^2(x)}{4c_1} \leq \frac{1}{4c_1}$

なので、

$\displaystyle c_1\left\{b(x)\delta+b^2(x)\delta^2\right\} \leq b^2(x)\left( \frac{1}{2}+\frac{1}{4c_1} \right) < \frac{3}{4}b^2(x)$

を得ます( $c_1 > 1$ に注意)。よって、前節の帰結から

$\displaystyle b^2(x) < c_2\left( b(x)-b(x+1)+2^{-4^x} \right), \quad x > c_3$

がいえました。ここで、基本事項５の1. より $b(x)$ は減少関数であることに注意します。

$\left( x < y \Longrightarrow b(x) = a(2^{4^x}) \geq a(2^{4^y}) = b(y). \right)$

従って、 $P > c_3$ なる整数に対して

$\displaystyle Pb^2(2P) \leq \sum_{x=P}^{2P-1}b^2(x) < c_4\left( b(P)-b(2P)+\frac{2c_4}{P} \right)$ −⑪

です。ここで、望遠鏡和と

$\displaystyle c_2\sum_{x=P}^{2P-1}2^{-4^x} \leq \frac{c_2P}{2^{4^P}} < \frac{2c_4^2}{P}$

と $c_4$ を取る計算を行っています。

命題４ $P > c_3$ かつ $2Pb(2P) > 4c_4$ という条件が満たされていれば

$2Pb(2P) < Pb(P)$

が成り立つ。

証明. 条件と⑪より

$\displaystyle 2Pb(2P) < \frac{1}{4c_4}\left\{ 2Pb(2P)\right\}^2 < P\left\{b(P)-b(2P)+\frac{4c_4}{2P} \right\} < Pb(P)$

である。 Q.E.D.

命題４より $c_3 < 2^{t_0} < 2^t$ であれば

$2^tb(2^t) \leq \max\left\{4c_4, 2^{t_0}b(2^{t_0})\right\} = c_5$

が成り立ちます( $2^t$ から $2^{t_0}$ に向かって繰り返し命題４を用いている)。さて、これは

$b(2^t) = O(2^{-t})$

に他なりません。 $b(x)$ は減少関数であったので、 $2^{t_0} < 2^t \leq x < 2^{t+1}$ であれば

$\displaystyle b(x) \leq b(2^t) \leq \frac{c_5}{2^t} = \frac{2c_5}{2^{t+1}} < \frac{2c_5}{x}$

であり、 $b(x) = O(x^{-1})$ となります。最後に、 $y$ を $0 \ll 2^{4^x} \leq y < 2^{4^{x+1}}$ なる正整数とすると、基本事項５の2. より

$\displaystyle a(y) \leq (1+2^{4^x}y^{-1})a(2^{4^x}) \leq 2b(x) < \frac{c_6}{x} < \frac{c_7}{\log \log y}$

となり、Rothの定理が証明されています。

写真はWikipediaのTuránの画像Bundesarchiv Bild 183-33149-0001, Leipzig, Universität, Professor Turan.jpgを二次利用しています。Rothの写真ではありません。

*1:普通Erdős-Turán予想と言ったらSzemerédiの定理のことを指す習慣がありますが、このブログでは、彼らの1936年の論文で明示されている $k=3$ の場合を指すこととします。