Fareyグラフ(Farey graph)とは、有理数と $\infty$ を頂点とし、既約分数 $\frac pq,\frac rs$ を $\lvert ps-qr\rvert=1$ のときに辺で結んだグラフである。各辺はちょうど 2 つの三角形に含まれ、辺を上半平面の半円として描くと辺どうしは交わらず、三角形が張る理想三角形が上半平面を重なりなく敷き詰める(Farey 分割)。$\operatorname{PGL}_2(\mathbb Z)$ は順序付きの三角形に単純推移的に働き、グラフの自己同型群に一致する。連分数の収束子はこのグラフの路をなし、Stern–Brocot 木や Ford の円とも対応する。
Fareyグラフ(Farey graph)は、有理数と無限遠点 $\infty$ を頂点とし、既約分数 $\frac pq,\frac rs$ を $\lvert ps-qr\rvert=1$ のときに辺で結んだグラフである。辺を上半平面 $\mathfrak H$ の半円(双曲平面の測地線)として描くと、辺どうしは交わらず、3 つずつ互いに結ばれた頂点が $\mathfrak H$ を隙間も重なりもなく敷き詰める理想三角形を作る。この敷き詰めを Farey 分割(Farey tessellation)という。モジュラー群 はこの図形の対称性として働き、グラフの自己同型群は $\operatorname{PGL}_2(\mathbb Z)$ に一致する。
この記事では、辺の三角形への入り方(prop-fg-triangles)、Farey 分割の定理(thm-fg-tessellation)、自己同型群の決定(thm-fg-automorphism)を証明し、連分数・Stern–Brocot木・Fordの円 との関係を述べる。辺を半円として描くこと(Farey の弧)と、$\operatorname{SL}_2(\mathbb Z)$ が弧を弧に移すことは Fordの円 の命題「Farey の弧と接点」で扱っている。
Fordの円 と同じく、$\widehat{\mathbb Q}:=\mathbb Q\cup\{\infty\}$ とし、互いに素な整数の組の列ベクトル $v=\binom pq$(原始ベクトル)で $\widehat{\mathbb Q}$ の元 $\frac pq$ を表す($q=0$ なら $\infty$)。$v$ と $-v$ は同じ点を表す。2 つの列ベクトルの行列式を $\det(v,w)$ と書く。$\lvert\det(v,w)\rvert$ は代表のとり方によらない。
頂点の集合を $\widehat{\mathbb Q}$ とし、原始ベクトル $v,w$ で表される 2 点を $\lvert\det(v,w)\rvert=1$ のときに辺で結んだグラフを Farey グラフ という。互いに辺で結ばれた 3 頂点の組を Farey 三角形 という。
$\infty=\binom10$ と $\frac pq$ の行列式は $q$ なので、$\infty$ の隣はちょうど整数 $\frac n1$ である。$0=\binom01$ の隣は $\frac1n$($n\in\mathbb Z$、$n\ne0$)と $\infty$ である。一般に $\frac pq$ の隣は、$pd-qb=1$ となる整数 $b,d$ を 1 組とると $\frac{b+np}{d+nq}$($n\in\mathbb Z$)の全体である(行列 $\begin{pmatrix}p&b\\q&d\end{pmatrix}$ は $\infty$ を $\frac pq$ に移し、prop-fg-triangles の 2 によりグラフの自己同型なので、$\infty$ の隣 $\frac n1$ を $\frac pq$ の隣に移す)。とくにどの頂点の次数も可算無限である。Fordの円 の定理「接するか離れるか」により、2 点が辺で結ばれることは、その 2 点の Ford の円が接することと同値である。
1:$\det(v,w)=\pm1$ なので $v,w$ は $\mathbb Z^2$ の基底で、第 3 の頂点の原始ベクトル $u$ は整数 $\alpha,\beta$ で $u=\alpha v+\beta w$ と書ける。$\det(v,u)=\beta\det(v,w)$、$\det(w,u)=-\alpha\det(v,w)$ なので、$u$ が $v,w$ の両方と辺で結ばれることは $\lvert\alpha\rvert=\lvert\beta\rvert=1$ と同値である。点としては $u$ と $-u$ は同じなので、第 3 の頂点は $v+w$ か $v-w$ が表す点で、$v,w$ が 1 次独立なのでこの 2 点は異なる。
2:$g$ は $\mathbb Z^2$ の自己同型なので原始ベクトルを原始ベクトルに移し、$\det(gv,gw)=\det g\cdot\det(v,w)=\pm\det(v,w)$ なので辺を辺に、辺でない組を辺でない組に移す。$g^{-1}$ が逆の写像を与える。
3:順序付きの Farey 三角形 $(x_1,x_2,x_3)$ の $x_1,x_2$ の原始ベクトル $v_1,v_2$ をとる。1 により $x_3$ は $v_1+v_2$ か $v_1-v_2$ の表す点で、後者なら $v_2$ を $-v_2$ に替えて、$x_3$ が $v_1+v_2$ の表す点になるようにできる。このとき $g:=(v_1\ v_2)\in\operatorname{GL}_2(\mathbb Z)$ は $(\infty,0,1)$ を $(x_1,x_2,x_3)$ に移す。よって任意の 2 つの順序付き三角形は $(\infty,0,1)$ を経由して移し合える。一意性:$g$ が $(\infty,0,1)$ を固定すれば $g\binom10=\varepsilon_1\binom10$、$g\binom01=\varepsilon_2\binom01$、$g\binom11=\varepsilon_3\binom11$($\varepsilon_i=\pm1$)で、最初の 2 式から $g\binom11=\binom{\varepsilon_1}{\varepsilon_2}$ なので $\varepsilon_1=\varepsilon_2=\varepsilon_3$、$g=\pm I$ である。$\operatorname{SL}_2(\mathbb Z)$ の推移性:$\det g=-1$ なら、$g$ に $(\infty,0,1)$ の頂点を入れ替える行列 $\begin{pmatrix}0&1\\1&0\end{pmatrix}$ を右から掛ければ、同じ三角形(頂点の順序だけが異なる)に移す行列式 $1$ の元が得られる。辺についても同じである。$\square$
$\operatorname{GL}_2(\mathbb Z)$ の元で $\widehat{\mathbb Q}$ に自明に働くのは $\pm I$ だけなので(3 の一意性)、$\operatorname{PGL}_2(\mathbb Z):=\operatorname{GL}_2(\mathbb Z)/\{\pm I\}$ が Farey グラフに忠実に作用し、順序付きの Farey 三角形の集合に単純推移的に作用する。Hat22 は行列式 $\pm1$ の整数行列による 1 次分数変換の全体 $\operatorname{LF}(\mathbb Z)$ について、辺を辺に移すこと(Proposition 3.1、p. 71)と、順序付きの三角形を移し合う元がただ 1 つあること(Proposition 3.3、p. 75)を示している。
$x=[a_0;a_1,\dots,a_n]$ の収束子 $\frac{p_k}{q_k}$ は、連分数 の命題「隣り合う収束子の行列式」により $p_kq_{k-1}-p_{k-1}q_k=(-1)^{k-1}$($k\ge0$、$p_{-1}/q_{-1}=\frac10$)を満たすので、$\infty,\ \frac{p_0}{q_0},\ \frac{p_1}{q_1},\ \dots,\ \frac{p_n}{q_n}=x$ は Farey グラフの路である。たとえば $\frac{355}{113}=[3;7,16]$ では $\infty-3-\frac{22}7-\frac{355}{113}$ が路である。$3$ と $\frac{355}{113}$ は $3\cdot113-355=-16$ なので辺で結ばれない。
$\mathfrak H$ の中に Farey 三角形が張る理想三角形を、次の量で定める。原始ベクトル $v=\binom pq$、$w=\binom rs$ と $z\in\mathfrak H$ について
$$
h_{v,w}(z):=\frac{\operatorname{Re}\bigl[(p-qz)\,\overline{(r-sz)}\bigr]}{\operatorname{Im}z}
$$
とおく。$h_{v,w}=h_{w,v}$ であり、$v$ か $w$ の一方の符号を替えると $h_{v,w}$ の符号が替わる。
1:$\gamma=\begin{pmatrix}a&b\\c'&d\end{pmatrix}$、$\gamma v=\binom{p'}{q'}$ とする。$\gamma\binom z1=(c'z+d)\binom{\gamma z}1$ なので、行列式をとって
$$
p'-q'\gamma z=\det\Bigl(\gamma v,\tbinom{\gamma z}1\Bigr)=\frac{\det\bigl(\gamma v,\gamma\tbinom z1\bigr)}{c'z+d}=\frac{\det\bigl(v,\tbinom z1\bigr)}{c'z+d}=\frac{p-qz}{c'z+d}
$$
である(Fordの円 の定理「Ford の円板の置換」の証明と同じ計算)。$w$ についても同様なので、分子は $\lvert c'z+d\rvert^{-2}$ 倍になる。$\operatorname{Im}(\gamma z)=\operatorname{Im}z/\lvert c'z+d\rvert^2$(上半平面 の命題「作用の基本性質」)なので比は変わらない。
2:展開すると $\operatorname{Re}[(p-qz)\overline{(r-sz)}]=pr-(ps+qr)\operatorname{Re}z+qs\lvert z\rvert^2$ である。$q,s\ne0$ なら、これは $qs\bigl(\lvert z\rvert^2-2c\operatorname{Re}z+\frac pq\cdot\frac rs\bigr)=qs\bigl(\lvert z-c\rvert^2-c^2+\frac pq\cdot\frac rs\bigr)$ で、$c^2-\frac pq\cdot\frac rs=\varrho^2$ である。$q=0$、$p=\pm1$ なら $\pm(r-s\operatorname{Re}z)$ である。$\square$
Farey 三角形の 3 頂点は、和が $0$ になる原始ベクトル $v_1,v_2,v_3$ で表せる(prop-fg-triangles の 1 により第 3 の頂点は $\pm(v_1\pm v_2)$ の表す点なので、符号を選べばよい)。このような 3 つ組は全体の符号を除いて一意である($\varepsilon_1v_1+\varepsilon_2v_2+\varepsilon_3v_3=0$ と $v_1+v_2+v_3=0$ から $(\varepsilon_1-\varepsilon_3)v_1+(\varepsilon_2-\varepsilon_3)v_2=0$ で、$v_1,v_2$ は 1 次独立)。全体の符号を替えても $h$ は変わらない。
Farey 三角形 $T$ を和が $0$ の原始ベクトル $v_1,v_2,v_3$ で表し、
$$
\Delta(T):=\bigl\{z\in\mathfrak H\bigm| h_{v_1,v_2}(z)\le0,\ h_{v_2,v_3}(z)\le0,\ h_{v_3,v_1}(z)\le0\bigr\}
$$
とおく。不等号をすべて狭義にした集合を $\Delta^\circ(T)$ とする。
$T_0:=\{\infty,0,1\}$ を $v_1=\binom10$、$v_2=\binom01$、$v_3=\binom{-1}{-1}$ で表すと、lem-fg-h の 2 により 3 つの条件は $\operatorname{Re}z\ge0$、$\lvert z-\frac12\rvert\ge\frac12$、$\operatorname{Re}z\le1$ で、
$$
\Delta(T_0)=\Bigl\{z\in\mathfrak H\Bigm| 0\le\operatorname{Re}z\le1,\ \Bigl\lvert z-\frac12\Bigr\rvert\ge\frac12\Bigr\}
$$
は 3 本の Farey の弧 $E(\infty,0)$、$E(0,1)$、$E(1,\infty)$ で囲まれた理想三角形である。有限の頂点 $x_1< x_2< x_3$ をもつ Farey 三角形では、中央の $x_2$ は $x_1,x_3$ の中間数である(分母が正の代表 $u_1,u_3$ をとると、prop-fg-triangles の 1 により $x_2$ は $u_1+u_3$ か $u_1-u_3$ の表す点である。$q_1=q_3$ なら行列式から $q_1=q_3=1$ で、$u_1-u_3$ は $\infty$ を表す。$q_1>q_3$ なら $u_1=(u_1-u_3)+u_3$ は分母が正の 2 つのベクトルの和なので、$x_1$ は $u_1-u_3$ の表す点と $x_3$ の間にあり、$u_1-u_3$ の表す点は $x_1$ より小さい。$q_1< q_3$ なら同様に $u_3-u_1$ の表す点が $x_3$ より大きい)。分母が正の代表 $u_1,u_3$ をとり $v_1=u_1$、$v_3=u_3$、$v_2=-(u_1+u_3)$ とすると、lem-fg-h の 2 で $q_1q_3>0$、$q_1q_2<0$、$q_2q_3<0$ なので、$\Delta(T)$ は $[x_1,x_3]$ を直径とする半円の内側で、$[x_1,x_2]$ と $[x_2,x_3]$ を直径とする半円の外側の部分であり、$\Delta^\circ(T)$ は $[x_1,x_3]$ を直径とする開円板に含まれる。$\infty$ を頂点にもつ Farey 三角形は $\{\infty,n,n+1\}$($n\in\mathbb Z$)で、$\Delta^\circ$ は帯 $n< \operatorname{Re}z< n+1$ に含まれる。
lem-fg-h の 1 と、$\gamma$ が和が $0$ の 3 つ組を和が $0$ の 3 つ組に移すことから、$\gamma\in\operatorname{SL}_2(\mathbb Z)$ について
$$
\gamma\bigl(\Delta(T)\bigr)=\Delta(\gamma T),\qquad \gamma\bigl(\Delta^\circ(T)\bigr)=\Delta^\circ(\gamma T)
\qquad\text{(1)}
$$
が成り立つ。
1:Farey の弧 $E\ne E'$ をとる。Fordの円 の命題「Farey の弧と接点」により、$\gamma(E)=E(\infty,0)$ となる $\gamma\in\operatorname{SL}_2(\mathbb Z)$ があり、$\gamma(E')$ も Farey の弧で $\gamma(E)$ と異なる。$\gamma$ は $\mathfrak H$ の全単射なので、$E$ が虚軸 $E(\infty,0)$ の場合を示せばよい。$E'=E(r_1,r_2)$ とする。
$h_{v,w}(z)=0$ となる $z$ の全体は、lem-fg-h の 2 により、$v,w$ の表す 2 点を結ぶ Farey の弧である。したがって $\Delta(T)\setminus\Delta^\circ(T)$ は $T$ の 3 辺の Farey の弧の上にあり、thm-fg-tessellation は、Farey の弧の全体が $\mathfrak H$ を互いに重ならない理想三角形 $\Delta(T)$ に切り分けることを述べている。Hat22 は第 1 章で、中間数の規則で描いた図形の辺がちょうど行列式 $\pm1$ の組を結ぶこと(Proposition 1.1、p. 23)を示し、その弧が交わらないことを述べ(p. 24)、Spr17 §7(p. 16)は、Farey 分割が頂点の集合を $\mathbb Q\cup\{\infty\}$ とする双曲平面の理想三角形分割であることを述べている。
$\infty$ を頂点とする三角形 $\{\infty,n,n+1\}$ は、無限に多くの三角形が頂点 $\infty$ のまわりに扇形に並んだものである。これを $\gamma=\begin{pmatrix}p&b\\q&d\end{pmatrix}$ で移すと、有理点 $\frac pq$ のまわりにも無限に多くの三角形が扇形に集まる。一方、無理数 $x$ の上の半直線 $\{x+iy\mid y>0\}$ は、上から順に無限に多くの三角形を横切り、横切る辺の端点は $x$ に近づく(Hat22 Proposition 2.3、p. 44 の証明)。たとえば $x=\sqrt2=[1;2,2,\dots]$ では、辺 $\{1,2\}$、$\{1,\frac32\}$、$\{\frac43,\frac32\}$、$\{\frac75,\frac32\}$、$\{\frac75,\frac{10}7\}$、$\{\frac75,\frac{17}{12}\}$ を順に横切り、収束子 $1,\frac32,\frac75,\frac{17}{12}$ がすべて端点に現れる。$\frac43$ と $\frac{10}7$ は収束子でない。
$\operatorname{PGL}_2(\mathbb Z)$ の作用 $v\mapsto gv$ は、群の同型 $\operatorname{PGL}_2(\mathbb Z)\xrightarrow{\ \sim\ }\operatorname{Aut}(\text{Farey グラフ})$ を与える。
prop-fg-triangles の 2 により準同型が定まり、3 の一意性により単射である。全射を示す。自己同型 $\varphi$ は Farey 三角形を Farey 三角形に移すので、$(\varphi\infty,\varphi0,\varphi1)$ は順序付きの Farey 三角形であり、3 により $g(\infty,0,1)=(\varphi\infty,\varphi0,\varphi1)$ となる $g\in\operatorname{GL}_2(\mathbb Z)$ がある。$\psi:=g^{-1}\varphi$ が恒等写像であることを示せばよい。
まず次を使う。$\psi$ が辺 $\{v,w\}$ の両端と、その辺を含む一方の三角形の第 3 の頂点を固定すれば、他方の三角形の第 3 の頂点も固定する。実際、$\psi$ は $\{v,w\}$ を含む三角形の集合を自分に移し、prop-fg-triangles の 1 によりそれはちょうど 2 つなので、一方を固定すれば他方も固定する。
$\psi$ は $\infty,0,1$ を固定する。辺 $\{\infty,n\}$ を含む三角形は $\{\infty,n-1,n\}$ と $\{\infty,n,n+1\}$ なので、$n$ に関する帰納法で(正と負の両方向に)$\psi$ はすべての整数を固定する。次に分母 $q\ge2$ の既約分数 $x=\frac pq$ について、分母が $q$ より小さい点(と $\infty$)がすべて固定されていると仮定する。$1\le b\le q-1$ で $pb\equiv1\pmod q$ となる $b$ をとり、$a:=\frac{pb-1}q$、$c:=p-a$、$d:=q-b$ とおく。$v=\binom ab$、$w=\binom cd$ は $\det(v,w)=ad-bc=aq-bp=-1$ を満たすので、$\frac ab,\frac cd$(分母 $b,d$ は $1$ 以上 $q-1$ 以下)は辺で結ばれ、$v+w=\binom pq$ の表す $x$ は第 3 の頂点の一方である。他方 $v-w$ の表す点は分母が $\lvert b-d\rvert< q$ か $\infty$ である。帰納法の仮定によりこの 3 点は固定されるので、上の事実から $x$ も固定される。$\square$
行列式 $1$ の元は Farey 分割の理想三角形 $\Delta(T)$ を (1) のとおり $\mathfrak H$ の中で動かす。行列式 $-1$ の元、たとえば $x\mapsto-x$ は、$\mathfrak H$ の上では $z\mapsto-\bar z$ のように複素共役と組み合わせて働き、図形を裏返す。
Hat22 Proposition 3.3(p. 75)は、Farey 図形の順序付きの三角形を移し合う $\operatorname{LF}(\mathbb Z)$ の元がただ 1 つであることを、隣の三角形へ順に決まっていく議論で示している。上の証明はこの議論を分母に関する帰納法として書いたものである。
prop-fg-triangles と thm-fg-tessellation の条件は外せない。各行は条件を 1 つだけ替える。
| 替えた条件 | 例 | 成り立たなくなる結論 |
|---|---|---|
| 辺の条件 $\lvert\det\rvert=1$ を $\lvert\det\rvert\le2$ に弱める | $\frac11$ と $-\frac11$(行列式 $2$)を結ぶ単位半円 | 弧が交わらないこと:虚軸 $E(0,\infty)$ と $i$ で交わる |
| 頂点に $\infty$ を含める | $\mathbb Q$ だけを頂点とするグラフの辺 $\{0,1\}$ | 各辺がちょうど 2 つの三角形に含まれること:$\{0,1\}$ を含む三角形は $\{0,\frac12,1\}$ だけ |
| 行列の成分が整数で行列式が $\pm1$ | $x\mapsto2x$(行列 $\operatorname{diag}(2,1)$) | 自己同型であること:辺 $\{0,1\}$ が辺でない $\{0,2\}$ に移る |
| 三角形の内部 $\Delta^\circ$ どうしを比べる | 閉じた $\Delta(T_0)$ と $\Delta(\{\infty,-1,0\})$ | 重なりのないこと:虚軸の $\operatorname{Im}z\ge1$ の部分を共有する |
1 行目:$\binom11,\binom{-1}1$ の行列式は $1\cdot1-1\cdot(-1)=2$ で、$\lvert i\rvert=1$ なので $i$ は単位半円と虚軸の両方にある。2 行目:prop-fg-triangles の 1 により $\{0,1\}$ を含む三角形の第 3 の頂点は $\binom01\pm\binom11$ の表す $\frac12$ と $\infty$ で、$\infty$ を除くと $\frac12$ だけが残る。3 行目:$\det\bigl(\binom01,\binom21\bigr)=-2$。4 行目:$z=iy$($y\ge1$)は $\operatorname{Re}z=0$、$\lvert z\mp\frac12\rvert^2=y^2+\frac14\ge\frac14$ を満たし、両方に入る。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する