2月 2013

Farey数列メモ

sukarabe 2013年2月22日 (金) コメントはまだありません

Hans Rademacher の Lectures on Elementary Number Theory に，ファレイ数列の基本性質 (隣り合った2つの分数$\frac{a}{b}$, $\frac{c}{d}$に対して$bc-ad=1$が成り立つこと) の帰納法による証明が載っているのだが (pp.8–10)， \[ \lambda=ak-bh, \quad \mu=-am+bl \] と置く部分が天下りでちょっとなあと，思っていた。次のように考えれば自然だろうと思う。

$\displaystyle \frac{h}{k} \leq \frac{a}{b} \leq \frac{l}{m}$ であるから，座標平面上で格子点 $A(k,h)$, $B(m,l)$, $P(b,a)$ を考えれば，格子点$P$は半直線$OA$, $OB$で挟まれた角領域にある。よって，\[ \begin{pmatrix} b\\a\end{pmatrix} = \mu \begin{pmatrix} k\\ h\end{pmatrix}+\lambda\begin{pmatrix} m\\ l\end{pmatrix} \qquad (\lambda\geq 0, \mu\geq 0) \] を満たす実数$\lambda$, $\mu$が存在する。この段階では$\lambda$, $\mu$は整数とは限らないが，上記の式を$\lambda$, $\mu$について解けば，\[ \lambda=\frac{ak-bh}{kl-hm}, \quad \mu=\frac{-am+bl}{kl-hm} \] となるから，$kl-hm=1$によって$\lambda$と$\mu$が整数となることが分かる。

帰納法による証明の概要は次の通り。位数$n-1$まで成立しているとして，位数$n$のファレイ数列の項$\frac{a}{b}$で位数$n-1$には含まれていない分数をとる。当然$b=n$である。この分数は，位数$n-1$のファレイ数列の隣り合った2項$\frac{h}{k}$, $\frac{l}{m}$ではさむことが出来る。このとき，\[ \frac{h}{k} \leq \frac{a}{b} \leq \frac{l}{m}, \quad kl-hm=1 \] が成り立つから，上記の議論によって，\[ a=\mu h+\lambda l, \quad b=\mu k+\lambda m \] となる。$b=n$だから，$\frac{a}{b}$はこのような分数全体の中で，分母が最小のものとして唯一に定まる。よって， $\mu=\lambda=1$ であり，\[ a=h+l, \quad b=k+m \] となる。あとの部分は簡単。