Erdős–Turánの不等式

同義語:Erdős-Turánの不等式Erdős–Turán の不等式Erdős–Turán inequality

概要

Erdős–Turánの不等式(Erdős–Turán inequality)とは、実数 $x_1,\dots,x_N$ の小数部分の食い違い量 $D_N$ を、正の整数 $H$ について $D_N\le\frac{C_1}{H+1}+C_2\sum_{h=1}^H\frac1h\bigl\lvert\frac1N\sum_ne^{2\pi ihx_n}\bigr\rvert$ と指数和で上から評価する不等式である。Weyl の一様分布判定法の定量版で、Fejér 核による平滑化と、点の分布関数が傾き $-1$ より速く下がらないことから $C_1=\frac{28}3$、$C_2=\frac8{3\pi}$ で証明できる。応用として、黄金比の倍数の列の食い違い量は $O((\log N)^2/N)$ である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 1を法とする一様分布, Fejérの定理, 三角多項式

Erdős–Turánの不等式(Erdős–Turán inequality)は、実数 $x_1,\dots,x_N$ の小数部分が区間 $[0,1)$ にどれだけ偏りなく散らばっているかを測る量(食い違い量 $D_N$)を、指数和の平均
$$ S_h:=\frac1N\sum_{n=1}^Ne(hx_n),\qquad e(x):=e^{2\pi ix} $$
の大きさで上から評価する不等式である。どの正の整数 $H$ についても
$$ D_N\le\frac{C_1}{H+1}+C_2\sum_{h=1}^{H}\frac{\lvert S_h\rvert}h $$
の形が成り立つ($C_1,C_2$ は絶対定数)。Erdős と Turán が 1948 年に示した(ET48)。
1を法とする一様分布 の Weyl の判定法は「すべての $h\ne0$ で $S_h\to0$ なら一様分布する」と述べるが、偏りがどれだけ速く $0$ に近づくかは教えない。Erdős–Turán の不等式はその定量版で、有限個の振動数 $h\le H$ の指数和だけから偏りの上界を与える。右辺の第 1 項は、$H$ より細かい振動を見ないことの代償である。
この記事では食い違い量を定義し、Fejér 核による平滑化で $C_1=\frac{28}3$、$C_2=\frac8{3\pi}$ の形を証明する(thm-et-main)。応用として、黄金比の倍数の列 $\{n\varphi\}$ の食い違い量が $O((\log N)^2/N)$ であることを示す。多項式の根の偏角の分布についての Erdős と Turán の別の不等式や、加法的基底についての Erdős–Turán 予想は、名前が同じだが別の主題である。

食い違い量

実数 $t$ の小数部分を $\{t\}:=t-\lfloor t\rfloor$ と書き、$0\le a< b\le1$ について $A_N([a,b)):=\#\{n\le N\mid\{x_n\}\in[a,b)\}$ とおく(1を法とする一様分布 と同じ記号)。

食い違い量

実数 $x_1,\dots,x_N$ の 食い違い量(discrepancy)を
$$ D_N:=\sup_{0\le a< b\le1}\Bigl\lvert\frac{A_N([a,b))}N-(b-a)\Bigr\rvert $$
と定める。$a=0$ に限った上限を $D_N^*$ と書く(star discrepancy)。無限列 $(x_n)$ については、最初の $N$ 項の食い違い量を $D_N$ と書く。

定義から $D_N^*\le D_N\le2D_N^*$ である($[a,b)=[0,b)\setminus[0,a)$ による)。また $D_N\ge\frac1N$ である(点 $\{x_1\}$ を左端とする長さ $\varepsilon$ の区間で $\frac1N-\varepsilon$ 以上になる)。
点の分布を 1 つの関数で表しておく。$0\le t<1$ について
$$ R(t):=\frac{A_N([0,t))}N-t $$
とおき、周期 $1$ で $\mathbb R$ に延長する。$R(0)=0$ で、$t\to1-0$ で $R(t)\to0$ である。

$R$ の性質
  1. $D_N=\sup R-\inf R$ である。
  2. 実数 $x$ と $0\le s\le1$ について $R(x+s)-R(x)\ge-s$ である。
  3. $h\ne0$ について $\displaystyle\int_0^1R(t)e(-ht)\,dt=\frac{\overline{S_h}}{2\pi ih}$ である。
  1. $0\le a< b<1$ なら $\frac{A_N([a,b))}N-(b-a)=R(b)-R(a)$ である。$b=1$ なら $A_N([a,1))=N-A_N([0,a))$ から、この値は $-R(a)=R(0)-R(a)$ である。よって $D_N$ は $\lvert R(b)-R(a)\rvert$($a\ne b$)の上限で、それは $\sup R-\inf R$ に等しい。
  2. 周期性から $0\le x<1$ としてよい。$x+s<1$ なら $R(x+s)-R(x)=\frac{A_N([x,x+s))}N-s\ge-s$ である。$x+s\ge1$ なら $R(x+s)=R(x+s-1)$ で、$A_N([0,x))=N-A_N([x,1))$ から
    $$ R(x+s)-R(x)=\frac{A_N([0,x+s-1))+A_N([x,1))}N-s\ge-s $$
    である。
  3. $\{x_n\}=y_n$ と書く。$\int_0^1\mathbf 1[y_n< t]\,e(-ht)\,dt=\int_{y_n}^1e(-ht)\,dt=\frac{e(-hy_n)-1}{2\pi ih}$、$\int_0^1t\,e(-ht)\,dt=-\frac1{2\pi ih}$ なので
    $$ \int_0^1R(t)e(-ht)\,dt=\frac1N\sum_{n=1}^N\frac{e(-hy_n)-1}{2\pi ih}+\frac1{2\pi ih}=\frac1{2\pi ih}\cdot\frac1N\sum_{n=1}^Ne(-hx_n) $$
    である。$\square$
  1. は、$R$ が点のところで上に跳び、点のないところでは傾き $-1$ で下がる関数であることを述べている。この片側の傾きの制限が、主定理の証明の要になる。(3) から逆向きの評価が直ちに出る。
指数和は食い違い量で抑えられる

$h\ne0$ について $\lvert S_h\rvert\le2\pi\lvert h\rvert D_N$ である。

$c:=\int_0^1R$ とおくと、$\int_0^1e(-ht)\,dt=0$ なので (3) の積分は $\int_0^1(R(t)-c)e(-ht)\,dt$ に等しい。$\inf R\le c\le\sup R$ なので $\lvert R-c\rvert\le\sup R-\inf R=D_N$ であり、lem-et-r (1)・(3) から $\frac{\lvert S_h\rvert}{2\pi\lvert h\rvert}\le D_N$ である。$\square$

主定理

周期 $1$ の Fejér 核を
$$ K_H(t):=\sum_{\lvert h\rvert\le H}\Bigl(1-\frac{\lvert h\rvert}{H+1}\Bigr)e(ht)=\frac1{H+1}\Bigl(\frac{\sin\pi(H+1)t}{\sin\pi t}\Bigr)^2 $$
とおく。Fejérの定理 の Fejér 核 $F_H$ を使えば $K_H(t)=F_H(2\pi t)$ で、同じ記事の補題「Fejér 核の性質」から $K_H\ge0$、$K_H$ は偶関数、$\int_{-1/2}^{1/2}K_H=1$ である。さらに $0<\lvert t\rvert\le\frac12$ で $\lvert\sin\pi t\rvert\ge2\lvert t\rvert$ なので $K_H(t)\le\frac1{4(H+1)t^2}$ であり、$0< a<\frac12$ について
$$ \tau(a):=\int_{a<\lvert t\rvert\le1/2}K_H(t)\,dt\le\frac2{4(H+1)}\int_a^\infty\frac{dt}{t^2}=\frac1{2(H+1)a} $$
である。

Erdős–Turán の不等式

実数 $x_1,\dots,x_N$ と正の整数 $H$ について
$$ D_N\le\frac{28}{3(H+1)}+\frac8{3\pi}\sum_{h=1}^{H}\frac{\lvert S_h\rvert}h $$
が成り立つ。

Fejér 核で平滑化し、片側の傾きの制限で戻す

$c:=\int_0^1R$、$R_0:=R-c$ とおき、$M:=\sup\lvert R_0\rvert$ とする。lem-et-r (1) から $\sup R_0-\inf R_0=D_N$ なので $D_N\le2M$ である。また $\lvert R_0\rvert\le D_N\le1$ なので $M\le1$ である。$M=0$ なら示すことはないので $M>0$ とする。
段 1(平滑化した関数は小さい).$R_0$ は有界で、$\int_0^1R_0=0$、$h\ne0$ では $\int_0^1R_0(t)e(-ht)\,dt=\frac{\overline{S_h}}{2\pi ih}$ である(lem-et-r (3))。$K_H$ は三角多項式なので、
$$ G(x):=\int_{-1/2}^{1/2}R_0(x-t)K_H(t)\,dt=\sum_{0<\lvert h\rvert\le H}\Bigl(1-\frac{\lvert h\rvert}{H+1}\Bigr)e(hx)\int_0^1R_0(u)e(-hu)\,du $$
である($K_H$ の各項を積分し、$u=x-t$ と置いて周期性を使う)。$\lvert S_{-h}\rvert=\lvert S_h\rvert$ なので、すべての $x$ で
$$ \lvert G(x)\rvert\le\sum_{0<\lvert h\rvert\le H}\frac{\lvert S_h\rvert}{2\pi\lvert h\rvert}=\frac1\pi\sum_{h=1}^H\frac{\lvert S_h\rvert}h=:E $$
である。
段 2($R_0$ が大きい点の近くでは $G$ も大きい).$\sup R_0=M$ の場合を考える。$0<\eta< M$ をとり、$R_0(x_0)\ge\Delta:=M-\eta$ となる $x_0$ を選び、$a:=\Delta/4$ とする($a\le\frac14$)。$\lvert t\rvert\le a$ なら $s:=a-t\in[0,2a]$ で、lem-et-r (2)($R_0$ でも同じ)から
$$ R_0(x_0+a-t)=R_0(x_0+s)\ge R_0(x_0)-s\ge\Delta-a+t $$
である。$\lvert t\rvert>a$ では $R_0\ge-M$ を使う。$tK_H(t)$ は奇関数なので $\int_{\lvert t\rvert\le a}tK_H(t)\,dt=0$ であり、$\tau=\tau(a)$ と書くと
$$ G(x_0+a)\ge(\Delta-a)(1-\tau)-M\tau\ge\frac34\Delta-\Bigl(\frac34\Delta+M\Bigr)\tau $$
である。$\tau\le\frac1{2(H+1)a}=\frac2{(H+1)\Delta}$ なので
$$ E\ge G(x_0+a)\ge\frac34\Delta-\frac3{2(H+1)}-\frac{2M}{(H+1)\Delta} $$
であり、$\eta\to0$ とすると $E\ge\frac34M-\frac7{2(H+1)}$ を得る。
$\inf R_0=-M$ の場合は、$R_0(x_0)\le-\Delta$ となる $x_0$ をとり、$x_0-a$ で $G$ を評価する。$\lvert t\rvert\le a$ なら $s:=a+t\in[0,2a]$ で、(2) を $x=x_0-s$ に使うと $R_0(x_0-a-t)\le R_0(x_0)+s\le-\Delta+a+t$ であり、同じ計算で $-G(x_0-a)\ge\frac34\Delta-(\frac34\Delta+M)\tau$ となる。
段 3(まとめ).どちらの場合も $M\le\frac43E+\frac{14}{3(H+1)}$ であり、
$$ D_N\le2M\le\frac{28}{3(H+1)}+\frac8{3\pi}\sum_{h=1}^H\frac{\lvert S_h\rvert}h $$
である。$\square$

証明の流れは、$R_0$ をなめらかにした $G$ が「低い振動数の指数和だけで書ける」ことと、$R_0$ が傾き $-1$ より速く下がらないので「大きな値を幅 $\Delta$ の範囲で保つ」ことの組み合わせである。定数は改良でき、Vaa85 は Selberg の関数(区間の指示関数を上下から挟む三角多項式)を使って
$$ D_N\le\frac1{H+1}+2\sum_{h=1}^H\Bigl(\frac1{\pi h}+\frac1{H+1}\Bigr)\lvert S_h\rvert $$
を導いている(Vaa85 の Theorem 20 と、その後の p. 214 の評価。区間の端の点を半分に数える流儀の食い違い量で述べられている)。

Weyl の判定法の定量版

実数列 $(x_n)$ について、次は同値である。
(a) $(x_n)$ は 1 を法として一様分布する。
(b) $D_N\to0$。
(c) すべての $h\ne0$ で $S_h\to0$($S_h$ は最初の $N$ 項でとる)。

(b)⇒(a) は定義から明らかである。(a)⇒(c) は 1を法とする一様分布 の定理「Weyl の判定法」による(prop-et-converse からは (b)⇒(c) も直ちに出る)。(c)⇒(b):$\varepsilon>0$ について $\frac{28}{3(H+1)}<\varepsilon$ となる $H$ をとると、thm-et-main の右辺の和は有限個の $S_h$ の和なので $N\to\infty$ で $0$ に近づき、$\limsup_ND_N\le\varepsilon$ である。$\square$

(c)⇒(b)⇒(a) は、Weyl の判定法の難しい向き(指数和から一様分布)の、Stone–Weierstrassの定理 を使わない別証明になっている。

応用:無理数の倍数の列

$\theta$ が整数でないとき、等比数列の和の公式と $\lvert1-e(\theta)\rvert=2\lvert\sin\pi\theta\rvert\ge4\Vert\theta\Vert$ から
$$ \Bigl\lvert\sum_{n=1}^Ne(n\theta)\Bigr\rvert\le\frac2{\lvert1-e(\theta)\rvert}\le\frac1{2\Vert\theta\Vert} $$
である。ここで $\Vert\theta\Vert$ は $\theta$ と最も近い整数との距離である。$x_n=n\alpha$ では $S_h$ は $\theta=h\alpha$ の和なので、thm-et-main の右辺は $\sum_h\frac1{h\Vert h\alpha\Vert}$ で抑えられる。これが小さいのは、$h\alpha$ が整数に近づきにくいときである。

整数に近づきにくい数の和

実数 $\alpha$ と $0< c\le\frac12$ について、すべての正の整数 $q$ で $\Vert q\alpha\Vert\ge\frac cq$ が成り立つとする。正の整数 $H$ について $L:=\lfloor\log_2H\rfloor$ とおくと
$$ \sum_{h=1}^H\frac1{h\Vert h\alpha\Vert}\le\frac{(L+1)(L+4)}c $$
である。

2 進のブロックで点の間隔を使う

$0\le K\le L$ について $B_K:=\{h\mid2^K\le h<2^{K+1}\}$ とする。$h\ne h'\in B_K$ なら $0<\lvert h-h'\rvert<2^K$ なので $\Vert h\alpha-h'\alpha\Vert\ge\frac c{\lvert h-h'\rvert}>\frac c{2^K}$ であり、円周 $\mathbb R/\mathbb Z$ の上の点 $h\alpha$($h\in B_K$)は互いに $c2^{-K}$ より離れている。よって、$0$ を中心とする半径 $r$ の弧(長さ $2r$)に入る点は $\frac{2r2^K}c+1$ 個以下である。$B_K$ の点の $\Vert h\alpha\Vert$ を小さい順に $v_1\le v_2\le\cdots$ と並べると、$j\le\frac{2v_j2^K}c+1$ から $v_j\ge\frac{(j-1)c}{2^{K+1}}$ であり、また仮定から $v_j\ge\frac c{2^{K+1}}$ である。$B_K$ の元は $2^K$ 個なので
$$ \sum_{h\in B_K}\frac1{\Vert h\alpha\Vert}\le\frac{2^{K+1}}c\Bigl(1+\sum_{j=2}^{2^K}\frac1{j-1}\Bigr)\le\frac{2^{K+1}}c(2+K\log2)\le\frac{2^{K+1}(K+2)}c $$
である。$h\in B_K$ では $\frac1h\le2^{-K}$ なので $B_K$ の寄与は $\frac{2(K+2)}c$ 以下で、$K=0,\dots,L$ について足すと $\frac2c\cdot\frac{(L+1)(L+4)}2$ になる。$\square$

無理数の倍数の列の食い違い量

lem-et-badly の仮定のもとで、$x_n=n\alpha$ の食い違い量は、$N\ge1$ と $L:=\lfloor\log_2N\rfloor$ について
$$ D_N\le\frac{28}{3(N+1)}+\frac{4(L+1)(L+4)}{3\pi c\,N} $$
を満たす。とくに $D_N=O((\log N)^2/N)$ である。

$\lvert S_h\rvert\le\frac1{2N\Vert h\alpha\Vert}$ なので、thm-et-main で $H=N$ とし lem-et-badly を使えばよい。$\square$

黄金比の倍数の列

$\varphi=\frac{1+\sqrt5}2$、$\psi=\frac{1-\sqrt5}2$ とする。正の整数 $q$ と、$q\varphi$ に最も近い整数 $p$ について、$(p-q\varphi)(p-q\psi)=p^2-pq-q^2$ は $0$ でない整数($\varphi$ は無理数)なので $\lvert p-q\varphi\rvert\ge\frac1{\lvert p-q\psi\rvert}$ である。$\lvert p-q\psi\rvert\le\lvert p-q\varphi\rvert+q\sqrt5\le(\sqrt5+\frac12)q$ から
$$ \Vert q\varphi\Vert\ge\frac c q,\qquad c=\frac1{\sqrt5+\frac12}=0.3654\ldots $$
であり、thm-et-kronecker から $\{n\varphi\}$ の食い違い量は $O((\log N)^2/N)$ である。実際の値は次のとおりである(点を並べ替えて lem-et-r (1) で計算した)。

$N$$10$$100$$1000$$10^4$$10^5$
$D_N$$0.18197$$0.02692$$0.00265$$0.000435$$0.0000513$
$ND_N$$1.82$$2.69$$2.65$$4.35$$5.13$
上界$4.10$$0.905$$0.160$$0.0286$$0.00404$

上界は実際の値の 20〜80 倍ほどで、表の範囲では $ND_N$ の増え方は $(\log N)^2$ よりずっと遅い。

反例:仮定を外すと成り立たないこと

外す仮定・替える条件例成り立たなくなる結論
右辺の第 1 項 $\frac{C_1}{H+1}$(落とす)$m=H+1$ 個の等間隔の点 $x_n=\frac nm$$D_N\le C_2\sum_{h\le H}\lvert S_h\rvert/h$(左辺は $\frac1{H+1}$、右辺は $0$)
$\Vert q\alpha\Vert\ge\frac cq$(thm-et-kronecker)Liouville の数 $\alpha=\sum_{k\ge1}10^{-k!}$$D_N=O((\log N)^2/N)$(無限個の $N$ で $D_N\ge\frac1{2\sqrt N}$)
表の確かめ

要点:等間隔の点では低い振動数の指数和がすべて $0$ になり、Liouville の数では点が有限個の格子点の近くに固まる。

確かめを開く

1 行目:$x_n=\frac nm$($1\le n\le m$)では、$1\le h\le m-1$ について $S_h=\frac1m\sum_ne(\frac{hn}m)=0$ である。一方、長さ $\frac1m$ 未満の区間で点を含まないものがあるので $D_m\ge\frac1m-\varepsilon$($\varepsilon>0$ は任意)であり、どの区間も $m(b-a)-1$ より多く $m(b-a)+1$ より少ない個数の点を含むので $D_m=\frac1m$ である。

2 行目:$q=10^{j!}$、$p$ を $\sum_{k\le j}10^{-k!}$ の $q$ 倍とすると、$\lvert\alpha-\frac pq\rvert\le2\cdot10^{-(j+1)!}\le\frac1{4q^3}$($j\ge3$)である。$N:=q^2$ とすると、$n\le N$ で $\lvert n\alpha-\frac{np}q\rvert\le\frac N{4q^3}=\frac1{4q}$ なので、$\{n\alpha\}$ はどれも格子 $\frac1q\mathbb Z$ から $\frac1{4q}$ 以内にある。区間 $(\frac iq+\frac1{4q},\frac{i+1}q-\frac1{4q})$ は長さ $\frac1{2q}$ で点を含まないので $D_N\ge\frac1{2q}=\frac1{2\sqrt N}$ であり、これは $(\log N)^2/N$ の定数倍では抑えられない。

1 行目は、thm-et-main の第 1 項の位数 $\frac1H$ が最良であることも示している(振動数 $H$ までの情報からは、$\frac1{H+1}$ より細かい偏りは見えない)。

関連項目

参考文献

[1]
Jeffrey D. Vaaler, Some extremal functions in Fourier analysis, Bulletin of the American Mathematical Society (N.S.), 1985, pp. 183–216(§8 の Theorem 20 と証明、p. 213–214。$\frac1{H+1}+2\sum(\frac1{\pi h}+\frac1{H+1})\lvert S_h\rvert$ の形は p. 214)
[2]
P. Erdős, P. Turán, On a problem in the theory of uniform distribution. I, Indagationes Mathematicae, 1948, pp. 370–378

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する