インテジャーズ

INTEGERS

数、特に整数に関する記事。

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

A(x)xに関するA-数列の最大項数とします(この記事ではRothに従ってxyも正整数を表します)。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の記事の続きとします。

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

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

補題1 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 が付随します。

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

基本事項5 正整数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
が成立する。

証明. 基本事項3より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.

指数和の評価1

以下、Mに関するA-数列 u_1, \dots, u_{U}を固定します(Mu_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'を導入します。

補題2 \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}]+1とすればよい。(h, q)=1とできるのは明らか。 Q.E.D.

補題2によって存在する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

である

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

補題3 上記設定において
\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-数列をなす部分のみをわたっている。従って、補題1から高々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つ目の等号には基本事項5の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.

指数和の評価2

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

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

が成り立ちます(最後の不等号は基本事項5の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-数列が得られるので(基本事項4)、基本事項5の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_WNに関するA-数列(基本事項4)なので

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) −⑥

です。

補題4 任意の実数\alphaに対して
\displaystyle f_r(\alpha)-F_r(\alpha) = O\left( N\{a(m)-a(2N)\}+N^{\frac{3}{4}} \right), \quad (r=1, 2)
が成立する。

証明. (主張はそれらの選択に依らないものであるが)補題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'となっている。補題3と③より

\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'である。よって、補題3と⑤より

\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の補題1より

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

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

\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)

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

命題1 任意の実数\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)
が成り立つ。

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

\left|f_1f_2^2-F_1F_2^2\right| = \left|f_1(f_2^2-F_2^2)+F_2^2(f_1-F_1)\right| \leq \left|f_1(f_2+F_2)(f_2-F_2)\right| + \left| F_2^2(f_1-F_1)\right|

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

命題2 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)

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

Hardy-Littlewoodの円周法

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

命題3 任意の実数\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.

補題5 \ \ \ \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

なので、命題2と補題5より

\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) −⑧

です。命題1からは

\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{命題3}}{=}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)

なので、基本事項5の3. より \eta \leq 4c_1m^{-3} が成り立ちます。つまり、mが十分大きければ 、前節の条件 0 < \eta < 1/2 は満たされます。基本事項5の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

がいえました。ここで、基本事項5の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を取る計算を行っています。

命題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.

命題4より 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}に向かって繰り返し命題4を用いている)。さて、これは

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})となります。最後に、y0 \ll 2^{4^x} \leq y < 2^{4^{x+1}} なる正整数とすると、基本事項5の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の場合を指すこととします。