Dirichletの近似定理
概要
Dirichletの近似定理（Dirichlet's approximation theorem）とは、任意の実数 $\alpha$ と正の整数 $N$ について、$1\le q\le N$ かつ $|q\alpha-p|<1/N$ を満たす整数 $p,q$ が存在するという定理であり、とくに $|\alpha-p/q|<1/q^2$ となる。証明は、$N+1$ 個の小数部分 $\{0\cdot\alpha\},\dots,\{N\alpha\}$ を長さ $1/N$ の $N$ 個の区間に入れる鳩の巣原理による。$\alpha$ が無理数なら $|\alpha-p/q|<1/q^2$ を満たす有理数は無限に多くの値をとる。上界は $1/(N+1)$ まで下げられるが、すべての実数に通用する上界としてはそれが最良である。
実数 $\alpha$ を分数 $p/q$ で近似するとき、分母 $q$ を勝手に決めてしまうと、分母 $q$ の分数は間隔 $1/q$ で並んでいるので、誤差 $|\alpha-p/q|$ は $1/(2q)$ 程度までしか保証されない。ところが分母を $1$ から $N$ までの中からうまく選んでよいことにすると、誤差を $1/(qN)$ 未満、とくに $1/q^2$ 未満にできる。これが Dirichlet の近似定理（Dirichlet's approximation theorem）であり、鳩の巣原理のもっとも有名な応用の一つである。
この定理から、どの無理数 $\alpha$ にも $|\alpha-p/q|<1/q^2$ を満たす分数 $p/q$ が無限にあることが従う。これは無理数を有理数で近似するときの精度の基準であり、Diophantus近似 の出発点になる。この記事では、定理を鳩の巣原理で証明し（thm-dat-main）、上界 $1/(N+1)$ まで改善した形とそれが最良であること（prop-dat-sharp）、無理数についての無限個の近似（cor-dat-infinite）、複数の実数の 1 次結合を小さくする形（prop-dat-linear-form）を示す。
定義と記号
実数 $x$ について、$x$ 以下の最大の整数を $\lfloor x\rfloor$（床関数）、小数部分を $\{x\}:=x-\lfloor x\rfloor\in[0,1)$ と書く。また $x$ から最も近い整数までの距離を
$$
\|x\|:=\min_{n\in\mathbb{Z}}|x-n|\in\Bigl[0,\frac12\Bigr]
$$
と書く。分数 $p/q$ と書くときは、つねに $p,q$ は整数で $q\ge1$ とする（既約とは限らない）。$|\alpha-p/q|=|q\alpha-p|/q$ なので、$\alpha$ を分母 $q$ の分数で近似することは、$q\alpha$ を整数 $p$ で近似することと同じであり、分母 $q$ で達成できる最小の $|q\alpha-p|$ は $\|q\alpha\|$ である。
$\alpha$ を実数、$N\ge1$ を整数とする。このとき
$$
1\le q\le N,\qquad |q\alpha-p|< \frac1N
$$
を満たす整数 $p,q$ が存在する。とくに
$$
\Bigl|\alpha-\frac pq\Bigr|< \frac1{qN}\le\frac1{q^2}
$$
である。
区間 $[0,1)$ を $N$ 個の半開区間
$$
I_t:=\Bigl[\frac tN,\frac{t+1}N\Bigr)\qquad(t=0,1,\dots,N-1)
$$
に分ける。これらは互いに交わらず、合わせると $[0,1)$ になる。$N+1$ 個の数 $\{0\cdot\alpha\},\{1\cdot\alpha\},\dots,\{N\alpha\}$ はどれも $[0,1)$ に属するので、それぞれちょうど 1 つの $I_t$ に入る。数が $N+1$ 個、区間が $N$ 個なので、鳩の巣原理 により、ある $0\le i< j\le N$ について $\{i\alpha\}$ と $\{j\alpha\}$ が同じ $I_t$ に入る。$I_t$ は長さ $1/N$ の半開区間なので、その 2 点の差は
$$
\bigl|\{j\alpha\}-\{i\alpha\}\bigr|< \frac1N
$$
を満たす。$q:=j-i$、$p:=\lfloor j\alpha\rfloor-\lfloor i\alpha\rfloor$ とおくと、$p,q$ は整数で $1\le q\le N$ であり、
$$
q\alpha-p=\bigl(j\alpha-\lfloor j\alpha\rfloor\bigr)-\bigl(i\alpha-\lfloor i\alpha\rfloor\bigr)=\{j\alpha\}-\{i\alpha\}
$$
なので $|q\alpha-p|<1/N$ である。両辺を $q$ で割ると $|\alpha-p/q|<1/(qN)$ であり、$q\le N$ から $1/(qN)\le1/q^2$ である。$\square$
この議論は HW60 §11.3（pp. 156–157）にある。証明は $p,q$ の存在を示すだけで、どの $q$ が選ばれるかは教えない。$|q\alpha-p|$ を最小にする $q$ を求めるには連分数を使う（連分数、Diophantus近似 の定理「収束子は最良近似である」）。
例
$\alpha=\sqrt2=1.41421\ldots$、$N=5$ とする。$j=0,1,\dots,5$ についての小数部分 $\{j\sqrt2\}$ は、小数第 4 位までで
$$
0,\quad 0.4142,\quad 0.8284,\quad 0.2426,\quad 0.6569,\quad 0.0711
$$
である。5 つの区間 $[0,0.2),[0.2,0.4),\dots,[0.8,1)$ のうち、2 つの数が入るのは $[0,0.2)$ だけで、そこには $j=0$ と $j=5$ が入る。$q=5-0=5$、$p=\lfloor5\sqrt2\rfloor-\lfloor0\rfloor=7$ であり、
$$
|5\sqrt2-7|=0.0710\ldots< \frac15,\qquad\Bigl|\sqrt2-\frac75\Bigr|=0.0142\ldots< \frac1{25}
$$
となる。$\frac75$ は $\sqrt2=[1;2,2,2,\dots]$ の収束子 $1,\frac32,\frac75,\frac{17}{12},\dots$ の一つである。
$\alpha=\pi$、$N=7$ とする。$\{j\pi\}$（$j=0,\dots,7$）は小数第 4 位までで
$$
0,\ 0.1416,\ 0.2832,\ 0.4248,\ 0.5664,\ 0.7080,\ 0.8496,\ 0.9911
$$
であり、幅 $\frac17=0.1428\ldots$ の 7 つの区間のうち 2 つの数が入るのは $[0,\frac17)$ だけで、$j=0,1$ である。したがって証明の手順が与えるのは $q=1$、$p=3$、すなわち $|\pi-3|=0.1415\ldots< \frac17$ である。一方、分母 $7$ 以下で最良なのは $|7\pi-22|=0.00885\ldots$ を与える $\frac{22}7$ である。thm-dat-main の結論は正しいが、証明の手順で得られる分数が最良とは限らない。
上界の改善と最良性
thm-dat-main の上界 $1/N$ は、$N+2$ 個の点を使うと $1/(N+1)$ まで下げられる。
$\alpha$ を実数、$N\ge1$ を整数とする。
- $1\le q\le N$、$|q\alpha-p|\le\dfrac1{N+1}$ を満たす整数 $p,q$ が存在する。
- $\alpha=\dfrac1{N+1}$ のとき、$1\le q\le N$ を満たすどの整数 $q$ とどの整数 $p$ についても $|q\alpha-p|\ge\dfrac1{N+1}$ である。したがって 1 の「$\le$」を「$<$」に置き換えた主張は成り立たない。
1：$N$ 個の数 $\{\alpha\},\{2\alpha\},\dots,\{N\alpha\}$ に $0$ と $1$ を加えた $N+2$ 個の数を小さい順に並べ、
$$
0=x_0\le x_1\le\dots\le x_N< x_{N+1}=1
$$
とする（$x_1,\dots,x_N$ は $\{j\alpha\}$（$1\le j\le N$）の並べ替えで、等しいものがあってもよい）。$N+1$ 個の差 $x_{k+1}-x_k$（$0\le k\le N$）の和は $1$ なので、そのうち少なくとも 1 つは $1/(N+1)$ 以下である。その $k$ について場合を分ける。
- $1\le k$ かつ $k+1\le N$ のとき：$x_k=\{i\alpha\}$、$x_{k+1}=\{j\alpha\}$（$i\neq j$、$1\le i,j\le N$）である。$i< j$ なら $q:=j-i$、$p:=\lfloor j\alpha\rfloor-\lfloor i\alpha\rfloor$、$i>j$ なら $q:=i-j$、$p:=\lfloor i\alpha\rfloor-\lfloor j\alpha\rfloor$ とおくと、$1\le q\le N-1$ で $|q\alpha-p|=|\{j\alpha\}-\{i\alpha\}|\le1/(N+1)$ である。
- $k=0$ のとき：$N\ge1$ なので $k+1\le N$ であり、$x_1=\{j\alpha\}$（$1\le j\le N$）である。$q:=j$、$p:=\lfloor j\alpha\rfloor$ とおくと $|q\alpha-p|=\{j\alpha\}\le1/(N+1)$ である。
- $k=N$ のとき：$N\ge1$ なので $k\ge1$ であり、$x_N=\{j\alpha\}$（$1\le j\le N$）である。$q:=j$、$p:=\lfloor j\alpha\rfloor+1$ とおくと $|q\alpha-p|=1-\{j\alpha\}\le1/(N+1)$ である。
2：$1\le q\le N$ なら $q$ は $N+1$ の倍数でないので、どの整数 $p$ についても $q-p(N+1)$ は $0$ でない整数であり、
$$ \Bigl|\frac q{N+1}-p\Bigr|=\frac{|q-p(N+1)|}{N+1}\ge\frac1{N+1} $$
である。$\square$
1 は HW60 §3.8 の Theorem 36（pp. 30–31）と同じ内容で、そこでは Farey 数列を使って証明されている。2 が示すように、$1\le q\le N$ という分母の範囲のもとで、すべての実数に通用する上界としては $1/(N+1)$ が最良である。
無理数の近似
$\alpha$ を無理数とする。$|\alpha-p/q|<1/q^2$ を満たす有理数 $p/q$ は無限に多くの異なる値をとる。さらに、そのような $p/q$ として既約分数を無限個とれる。
そのような有理数の値が有限個 $r_1,\dots,r_k$ しかないと仮定する。thm-dat-main の $N=1$ の場合から $k\ge1$ である。$\alpha$ は無理数なので各 $|\alpha-r_i|$ は正であり、その最小値を $\delta>0$ とする。$N>1/\delta$ を満たす整数 $N$ について thm-dat-main を使うと、$1\le q\le N$ と整数 $p$ で
$$
\Bigl|\alpha-\frac pq\Bigr|< \frac1{qN}\le\frac1N< \delta,\qquad\Bigl|\alpha-\frac pq\Bigr|< \frac1{q^2}
$$
となるものがある。1 つ目の不等式から $p/q$ はどの $r_i$とも異なり、2 つ目の不等式から $p/q$ は条件を満たすので、仮定に反する。
既約分数について：$|\alpha-p/q|<1/q^2$ とし、$d:=\gcd(p,q)$、$p':=p/d$、$q':=q/d$ とすると、$p'/q'=p/q$ は既約で、$q'\le q$ なので $|\alpha-p'/q'|<1/q^2\le1/q'^2$ である。値が異なる既約分数は異なるので、無限個の値から無限個の既約分数が得られる。$\square$
これは HW60 Theorem 185（p. 155）であり、§11.3（p. 157）で上の議論によって示されている。有理数 $\alpha=a/b$（$a,b$ は整数で $b\ge1$）では事情が違う。$p/q\neq\alpha$ なら $aq-bp$ は $0$ でない整数なので
$$
\Bigl|\alpha-\frac pq\Bigr|=\frac{|aq-bp|}{bq}\ge\frac1{bq}
$$
であり、これが $1/q^2$ より小さければ $q< b$ である。分母 $q< b$ で $|\alpha-p/q|<1$ となる分数は有限個なので、$\alpha$ と異なる値で $|\alpha-p/q|<1/q^2$ を満たすものは有限個しかない。こうして、$|\alpha-p/q|<1/q^2$ を満たす有理数が無限に多くの異なる値をとることは、$\alpha$ が無理数であることの特徴づけになる（無理数 の記事の定理「近似による無理数の特徴づけ」）。
すべての無理数に通用する指数としては、$2$ を大きくすることはできない。指数を $2+\varepsilon$ にすると成り立たない無理数があるからである。たとえば $\sqrt2$ について、$p/q$ を任意の分数とすると $p^2-2q^2$ は $0$ でない整数である（$\sqrt2$ は無理数）。$|\sqrt2-p/q|<1$ なら $0< p/q< \sqrt2+1$ なので
$$
\Bigl|\sqrt2-\frac pq\Bigr|=\frac{|2q^2-p^2|}{q^2\,(\sqrt2+p/q)}>\frac1{(2\sqrt2+1)\,q^2}
$$
であり、$|\sqrt2-p/q|\ge1$ のときもこの不等式は成り立つ。よって $\varepsilon>0$ について $|\sqrt2-p/q|<1/q^{2+\varepsilon}$ を満たす分数は、$q^{\varepsilon}<2\sqrt2+1$ を満たす有限個の $q$（各 $q$ について $p$ も有限個）に限られる。次数 $d$ の代数的数についての同じ型の下からの評価が Liouvilleの近似定理 である。一方、定数 $1$ は $1/\sqrt5$ まで改善でき、$\sqrt5$ はそれ以上大きくできない（Diophantus近似 の定理「Hurwitz の定理」）。
1 次形式への一般化
鳩の巣原理の議論は、1 つの数 $q\alpha$ の代わりに、いくつかの実数の整数係数の 1 次結合を整数に近づける問題にもそのまま使える。
$\alpha_1,\dots,\alpha_k$ を実数、$N\ge1$ を整数とする。このとき、すべてが $0$ ではない整数 $q_1,\dots,q_k$ と整数 $p$ で
$$
|q_i|\le N\quad(i=1,\dots,k),\qquad|q_1\alpha_1+\dots+q_k\alpha_k-p|< \frac1{N^k}
$$
を満たすものが存在する。
$m=(m_1,\dots,m_k)\in\{0,1,\dots,N\}^k$ について $L(m):=m_1\alpha_1+\dots+m_k\alpha_k$ とおく。$[0,1)$ を長さ $1/N^k$ の $N^k$ 個の半開区間 $[t/N^k,(t+1)/N^k)$（$t=0,\dots,N^k-1$）に分ける。$m$ は $(N+1)^k$ 通りあり、$(N+1)^k>N^k$ なので、鳩の巣原理 により相異なる $m\neq m'$ で $\{L(m)\}$ と $\{L(m')\}$ が同じ区間に入るものがある。$q_i:=m_i-m'_i$、$p:=\lfloor L(m)\rfloor-\lfloor L(m')\rfloor$ とおくと、$0\le m_i,m'_i\le N$ から $|q_i|\le N$、$m\ne m'$ から $q_i$ のどれかは $0$ でなく、
$$
q_1\alpha_1+\dots+q_k\alpha_k-p=L(m)-L(m')-p=\{L(m)\}-\{L(m')\}
$$
なので、その絶対値は $1/N^k$ 未満である。$\square$
$k=1$ のとき、$q_1\neq0$ で $|q_1|\le N$ であり、$q_1<0$ なら $(q_1,p)$ を $(-q_1,-p)$ に取り替えれば $1\le q_1\le N$ となるので、thm-dat-main が再び得られる。たとえば $\alpha_1=\sqrt2$、$\alpha_2=\sqrt3$、$N=3$ とすると、$|q_1|,|q_2|\le3$ で $\|q_1\sqrt2+q_2\sqrt3\|< \frac19$ となる組があるはずで、実際 $2\sqrt2+3\sqrt3=8.0245\ldots$ から $(q_1,q_2,p)=(2,3,8)$ が条件を満たす（誤差 $0.0245\ldots$）。
同じ分母で $k$ 個の数を同時に近似する形（$1\le q\le N^k$ と $|q\alpha_i-p_i|<1/N$）も、立方体 $[0,1)^k$ を $N^k$ 個の小さな箱に分ける同じ議論で示される（Diophantus近似 の命題「同時近似」、HW60 Theorem 200、p. 170）。また thm-dat-main は、平面の格子点についての Minkowskiの凸体定理 からも導かれる（同じ記事の命題「凸体定理による近似定理」）。
反例：条件を変えると崩れること
thm-dat-main・cor-dat-infinite の条件を 1 つずつ変えると、次のように結論が成り立たなくなる。
| 変える条件 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| 分母 $q$ を $1\le q\le N$ から選ぶ（thm-dat-main） → $q=N$ に固定する | $\alpha=\frac12$、$N=3$ | $\lvert3\alpha-p\rvert< \frac13$ となる整数 $p$ がある |
| 上界 $\frac1N$（thm-dat-main） → $\frac1{N+1}$ 未満にする | $\alpha=\frac1{N+1}$ | $1\le q\le N$ で $\lvert q\alpha-p\rvert< \frac1{N+1}$ となる $p,q$ がある |
| $\alpha$ が無理数（cor-dat-infinite） → 有理数にする | $\alpha=\frac12$ | $\lvert\alpha-p/q\rvert<1/q^2$ を満たす有理数が無限に多くの値をとる |
| 指数 $2$（cor-dat-infinite） → $2+\varepsilon$ にする | $\alpha=\sqrt2$ | $\lvert\alpha-p/q\rvert<1/q^{2+\varepsilon}$ を満たす有理数が無限に多くの値をとる |
1 行目：$|3\cdot\frac12-p|=|\frac32-p|\ge\frac12>\frac13$ である。$q$ を $1$ から $N$ の中で選べることが証明の鳩の巣原理の段階で使われていて、$q$ は 2 つの番号の差として決まるので、あらかじめ指定することはできない。なお $q=2$ を選べば $|2\cdot\frac12-1|=0$ である。
2 行目：prop-dat-sharp の 2 による。上界を $\frac1{N+1}$ より小さい数に置き換えることはできない。
3 行目：本文で見たとおり、$\alpha=a/b$ では $\alpha$ と異なる値の解は $q< b$ に限られ、有限個である。$\alpha=\frac12$ なら $q=1$ で $|\frac12-p|=\frac12<1$ となる $p=0,1$ の 2 つと、$\alpha$ 自身の値 $\frac12$ だけである（$\frac12=\frac24=\frac36=\cdots$ は表し方が無限にあるが、値は 1 つである）。cor-dat-infinite の証明では、$\alpha\neq r_i$ から $\delta>0$ とするところで無理数であることを使う。
4 行目：本文で示した $|\sqrt2-p/q|>1/((2\sqrt2+1)q^2)$ による。解は $q^{\varepsilon}<2\sqrt2+1$ の範囲に限られ、有限個である。指数 $2$ はすべての無理数に通用する指数としては最良である。
指数を $2$ より大きくできる無理数もある。ほとんどすべての実数については指数 $2$ が最良だが（Diophantus近似 の系「近似指数はほとんどすべての実数で 2」）、超越数 の記事の Liouville 数のように、どんな指数でも無限に解をもつ数がある（Liouvilleの近似定理）。
補足
thm-dat-main は、近似がよいことを「小さい整数値」に変える道具として使われる。$d$ を平方数でない正の整数とすると、$\sqrt d$ に定理を使って得られる $|X-Y\sqrt d|<1/Y$ の解から $|X^2-dY^2|< 1+2\sqrt d$ を満たす正の整数の組が無限に得られ、これが Pell方程式 $X^2-dY^2=1$ に自明でない解があることの証明の第一段になる（Pell方程式 の記事の補題「小さい値をとる組が無限にある」）。また、$0<|q\alpha-p|< \varepsilon$ となる $q$ をとって $q$ の倍数を順に見ると、無理数 $\alpha$ について小数部分 $\{n\alpha\}$ が $[0,1]$ で稠密であること（Kronecker の定理）が分かる（Diophantus近似 の定理「Kronecker の定理（1 次元）」）。
無理数 $\alpha$ の連分数の収束子 $p_n/q_n$ はすべて $|\alpha-p_n/q_n|<1/(q_nq_{n+1})\le1/q_n^2$ を満たす（連分数）。これは cor-dat-infinite の別証明を与え、どの分数が条件を満たすかを具体的に教える。逆に、$|\alpha-p/q|<1/q^2$ を満たす分数が収束子とは限らない（連分数 の記事の反例「よい近似がすべて収束子とは限らない」）が、$|\alpha-p/q|<1/(2q^2)$ を満たす既約分数は収束子である（Legendreの定理(連分数)）。鳩の巣原理による証明は連分数を使わない代わりに、prop-dat-linear-form や同時近似のような多次元の問題にそのまま広がる。
関連項目
- 前提: 鳩の巣原理, 無理数, 床関数
- 比較: 連分数, Minkowskiの凸体定理
- 例: Pell方程式
- 発展: Diophantus近似, Liouvilleの近似定理, Rothの定理
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
