次: 演習問題 上: 連分数と格子点 前: ミンコフスキーの定理

近似分数

一般の格子点

$xy$ 座標平面の二つの点 $\mathrm{A}(a,\ b),\ \mathrm{B}(c,\ d)$ をとる． ここで直線 $\mathrm{OA}$ と $\mathrm{OB}$ は平行でないとする．

整数$m,\ n$ に対してベクトル

$$\overrightarrow{\mathrm{OP}}=m\overrightarrow{\mathrm{OA}}+n\overrightarrow{\mathrm{OB}}$$

で定まる点 $\mathrm{P}$ を格子点という． ベクトル $\overrightarrow{\mathrm{OA}},\ \overrightarrow{\mathrm{OB}}$ を 単位として，原点から規則正しく排列された格子点，およびそれらの点を結ぶ線とそれらの線で囲まれた面の総体を(ベクトル $\overrightarrow{\mathrm{OA}},\ \overrightarrow{\mathrm{OB}}$で定まる格子という．基本ベクトル $\overrightarrow{e_1}=(1,\ 0),\ \overrightarrow{e_2}=(0，1)$で定まる格子を正方格子という．

ここで, $a,\ b,\ c,\ d$ を整数としさらに $ad-bc=\pm 1$ であるとする． 正方格子の格子点

$$\overrightarrow{\mathrm{OP}}=u\overrightarrow{e_1}+v\overrightarrow{e_2} =(u,\ v)\ \quad (u,\ v \in \mathbb{Z})$$

に対して

$$\left\{ \begin{array}{l} u=ma+nc\\ v=mb+nd \end{array} \right.$$

とすると，

$$\left\{ \begin{array}{l} m=\pm(ud-vc)\\ n=\pm(-ub+va) \end{array} \right.$$

と逆に解け，点$\mathrm{P}$は $\overrightarrow{\mathrm{OA}},\ \overrightarrow{\mathrm{OB}}$で定まる格子点

$$m\overrightarrow{\mathrm{OA}}+v\overrightarrow{\mathrm{OB}}$$

と一致する．逆も成り立つ．つまり格子点が一対一に対応し， ベクトル $\overrightarrow{\mathrm{OA}},\ \overrightarrow{\mathrm{OB}}$ で定まる格子と正方格子の格子が一致する．

連分数による実数の近似と格子

無理数 $\omega$ を近似分数で近似する過程は格子点でどのように作図されるのか．

$$\omega =\matrix{q_0}{1}{1}{0}\cdots\matrix{q_{k-1}}{1}{1}{0}\omega_{k} =\matrix{P_k}{P_{k-1}}{Q_k}{Q_{k-1}}\omega_{k}\\$$

で

$$\vecarray{P_{k+1}}{Q_{k+1}}=\vecarray{P_{k}q_k+P_{k-1}}{Q_{k}q_k+Q_{k-1}}$$

となるのであった． このとき点 $\mathrm{A}_k(Q_k,\ P_k)$とすると， 点$\mathrm{A}_k$は次のように作図される．

$xy$ 座標と正方格子を準備する．

まず直線 $y=\omega x$ を描く．この直線を $\omega 線$ と呼ぶ． $\mathrm{A_{-1}}(1,\ 0),\ \mathrm{A_{0}}(0,\ 1)$ とおく．直線 $x=1$上, $y=\omega x$ を越えない $y$ 座標最大の格子点が $\mathrm{A}_1(1,\ q_0)$ である．      次に $\mathrm{A}_{0}(0,\ 1)$を通り, $\overrightarrow{\mathrm{OA_1}}$ に平行な直線

$$l_1\ :\ \overrightarrow{\mathrm{OA_{0}}}+t\overrightarrow{\mathrm{OA_1}} =(t,\ tq_0+1)$$

を引く．

$$tq_0+1\ge\omega t\quad \iff\quad \dfrac{1}{\omega -q_0}\ge t$$

であるから， $\dfrac{1}{\omega -q_0}\ge t$ を満たす最大の整数 $q_1$ は，この直線 $\omega 線$ を越える直前の格子点を与える整数 $t$ であることがわかる．

この $t$ を $q_1$ とおく． このときその格子点が $\mathrm{A_2}$ である．つまり

$$\mathrm{A_2}(q_1,\ q_0q_1+1)$$

確かに

$$\matrix{q_0}{1}{1}{0}\matrix{q_1}{1}{1}{0}=\matrix{q_0q_1+1}{q_0}{q_1}{1}$$

なので $P_2=q_0q_1+1,\ Q_2=q_1$ である．

$\mathrm{A_{k-1}},\ \mathrm{A_{k}}$ が定まったときに 直線

$$\begin{eqnarray*} l_k&:&\overrightarrow{\mathrm{OA_{k-1}}}+t\overrightarrow{\mathrm{OA_{k}}}\\ &=&(Q_{k-1}+tQ_{k},\ P_{k-1}+tP_{k}) \end{eqnarray*}$$

を引く． $\mathrm{A_k}$ は一般に奇数なら $\omega 線$ の下に，偶数なら $\omega 線$ の上に ある．

$$\omega=\matrix{P_{k}}{P_{k-1}}{Q_{k}}{Q_{k-1}}\omega_k$$

つまり $\omega=\dfrac{\omega_kP_{k}+P_{k-1}}{\omega_kQ_{k}+Q_{k-1}}$ であるから，

$$\begin{eqnarray*} &&\omega (Q_{k-1}+tQ_{k})-(P_{k-1}+tP_{k})>0\\ &\iff&\dfrac... ...ff&(\omega_k-t)(P_{k}Q_{k-1}-P_{k-1}Q_{k})=(-1)^k(\omega_k-t)>0 \end{eqnarray*}$$

したがって， $\omega_k$ に下から($k$奇数のとき)，または上から($k$偶数のとき) もっとも近い $t$ を決定することは，直線 $l_k$ が $\omega 線$ を越える直前の格子点を 決定することと同値になり，この格子点が $\mathrm{A_k}$ である．

$t=1$ から$\mathrm{A_k}$を与える$t$までの各$t$の値に対して 順次線分 $\mathrm{A_{k-1}A_{k+1}}$上の格子点が定まり，これ以外にはない．

このように直線 $\mathrm{A_{k-1}A_{k+1}}$の傾きは $\omega 線$の傾きに近づき， $\omega 線$の両側にできる二つの折れ線 $\mathrm{A_{-1}A_1A_3A_5}\cdots$と $\mathrm{A_0A_2A_4A_6}\cdots$の間には格子点が一つも存在しない．

格子点 $\mathrm{A_k}$ は，$\mathrm{A_k}$と $\omega 線$ に関して同じ側にありその $x$ 座標が$\mathrm{A_k}$の $x$ 座標より小さいどの格子点より， $\omega 線$ に近い．

このことを定式化することにより次の定理が得られる．

定理 55
$\omega$ は与えられた無理数, $A$ は与えられた2より大きい正の定数であり， 整数$x$は$0<x \le A$にあるとする．

(1)

$\omega x-y$ を正で最小にする格子点$(x,\ y)$ は，$Q_{2n-1}<A$を満たす 最大の$2n-1$を$k$とするとき，線分 $\mathrm{A_k}\mathrm{A_{k+2}}$上の格子点で $x$ 座標が$A$を越えないものによって与えられる．

(2)

$y-\omega x$ を正で最小にする格子点$(x,\ y)$ は，$Q_{2n}<A$を満たす 最大の$2n$を$k$とするとき，線分 $\mathrm{A_k}\mathrm{A_{k+2}}$上の格子点で $x$ 座標が$A$を越えないものによって与えられる．

(3)

(ラグランジュの定理) $\vert\omega x-y\vert$ を最小にする $x$ と $y$ の整数値は

$$x=Q_n,\ \quad y=P_n$$

である．ただし, $P_n,\ Q_n$ は $\omega$ の連分数展開から得られる 近似分数 $\dfrac{P_n}{Q_n}$ で $A$ を越えない最大分母， すなわち $Q_n \le A <Q_{n+1}$となるものの分子分母である． ■

証明    

(1)

$\omega x-y$は$\omega 線$ と格子点 $(x,\ y)$ の $y$ 軸方向に関する距離であるが その大小と，格子点 $(x,\ y)$と $\omega 線$ との垂直距離の大小とは一致する． このことに注意すればすでに証明は済んでいる．

(2)

(1)と同様である．

(3)

上図のように，線分 $\mathrm{A_{k-1}A_{k+1}}$上の他の格子点を $\mathrm{B}$とし, $\mathrm{A_{k-1}A_{k+1}}$と$\omega 線$ との交点を $\mathrm{L}$とする． $\mathrm{OA_{k}}$ と $\mathrm{A_{k-1}A_{k+1}}$は平行なので 格子点 $\mathrm{A_{k}},\ \mathrm{A_{k-1}},\ \mathrm{B},\ \mathrm{A_{k+1}}$ と $\omega 線$ との距離は， $\mathrm{OA_{k}}$, $\mathrm{LA_{k-1}}$, $\mathrm{LB}$, $\mathrm{LA_{k+1}}$ と比例している．

線分 $\mathrm{BA}_{k+1}$の長さは線分 $\mathrm{OA}_{k}$の長さの整数倍であるから，

$$(\mathrm{LB}の長さ)\ge (\mathrm{OA}_{k}の長さ)$$

となり，この結果， 格子点 $\mathrm{B}$から$\omega 線$への距離は $\mathrm{A_{k}}$から$\omega 線$への距離以上である．

したがって題意をみたす格子点は $\mathrm{A_n}$ のなかで $x$ 座標が $A$ を超えない最大のものによって与えられる．□

一次形式 $x-\omega y$において$x$と$y$ は整数値のみをとるとし，さらに$y\ne 0$とする． このときこの一次形式の絶対値はいくらでも小さくすることができた． つまり無理数 $\omega$ は有理数 $\dfrac{P_n}{Q_n}$ で

$$\left\vert\omega-\dfrac{P_n}{Q_n}\right\vert<\dfrac{1}{{Q_n}^2}$$

と近似することができた． ところがここでもし近似有理数の分母の範囲に制限を加えるとどうなるか，というのがこの定理の趣旨である．この定理の証明は格子点の考察なしにおこなうこともできるが，格子点を用いる方がはるかに明瞭になる．

格子点の理論を用いて，無理数の近似の程度に関するさらに詳しい結果を紹介しよう．

定理 56 (ヴァーレンの定理)
     隣りあう二つの近似分数の少なくとも一方は

$$\left\vert\omega -\dfrac{P_n}{Q_n} \right\vert<\dfrac{1}{2{Q_n}^2}$$

を満たす． ■

証明

$\mathrm{A}(Q,\ P)$ と $\mathrm{B}(Q',\ P')$ を隣りあう二つの近似分数に対応する格子点とする．平行四辺形 $\mathrm{OACB}$ を作る． $Q'>Q$ とすれば $\mathrm{B}$ が $\mathrm{A}$ よりも $\omega$線に近い( $\mathrm{AM}>\mathrm{BN}$ )．ゆえに $\mathrm{AL}>\mathrm{BL}$ が成り立つ．

$$∴\quad \bigtriangleup \mathrm{LAM} >\bigtriangleup \mathrm{LBN}$$

したがって

$$\bigtriangleup \mathrm{OAM}+\bigtriangleup \mathrm{OBN}<\bigtriangleup \mathrm{OBA}=\dfrac{1}{2}$$

ゆえに $\bigtriangleup \mathrm{OAM}$ または $\bigtriangleup \mathrm{OBN}$のいずれかは $\dfrac{1}{4}$ より小さい．

しかるに

$$\bigtriangleup \mathrm{OAM}=\dfrac{1}{2} \left\vert Q(Q\ome... ...hrm{OBN}=\dfrac{1}{2} \left\vert Q'(Q'\omega-P') \right\vert$$

$$∴\quad \vert Q(Q\omega-P)\vert<\dfrac{1}{2},\ または\ \vert Q'(Q'\omega-P')\vert<\dfrac{1}{2}$$

つまり題意が示された． □
次: 演習問題 上: 連分数と格子点 前: ミンコフスキーの定理