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)$ である。
前提知識: 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$ である。
$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}
$$
である。
実数 $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
$$
が成り立つ。
$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 の評価。区間の端の点を半分に数える流儀の食い違い量で述べられている)。
実数列 $(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
$$
である。
$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}$ より細かい偏りは見えない)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する