Hirzebruch–Jung continued fraction

hbghlyj

kuing.cjhb.site/forum.php?mod=viewthread&tid=9114
在本练习中，我们通过 Euclid 算法，将连分数联系到 \({{\mathrm{PSL}}}_2(\mathbb Z )\) 由 \(S, T\) 生成这一事实。
Classical modular group, Open Access (GTM,volume 288)
设 \(a,b\ge 1\) 为整数，\(a > b\)。
(a) 证明存在唯一的 \(q,r \in \mathbb Z \) 使得 \(a=qb-r\) 且 \(q \ge 2\) 且 \(0 \le r < b\) .
从 (a) 归纳定义 \(r_0=a\), \(r_1=b\), \(r_{i-1}=q_ir_i-r_{i+1}\) 和 \(0 \le r_ {i+1} < r_i\); 则存在 \(t>0\) 使 \(r_1>r_2>\dots> r_t>r_{t+1}=0\)。
(b) 证明 \(\gcd (a,b)=r_t\), 如果 \(\gcd (a,b)=1\) 那么\begin{aligned} \frac{a}{b}=q_1 - \frac{1}{q_2-\displaystyle {\frac{1}{\cdots -\displaystyle {\frac{1}{q_t}}}}}. \end{aligned}(c) 通过归纳证明
$$\begin{aligned} \begin{pmatrix} 0 &{} 1 \\ -1 &{} q_t \end{pmatrix} \cdots \begin{pmatrix} 0 &{} 1 \\ -1 &{} q_1 \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} r_t \\ 0 \end{pmatrix}. \end{aligned}$$
对任何 \(q \in \mathbb Z \), 记
$$\begin{aligned} \begin{pmatrix} 0 &{} 1 \\ -1 &{} q \end{pmatrix} \in \langle S,T \rangle \subseteq {{\mathrm{PSL}}}_2(\mathbb Z ) \end{aligned}$$
为 $S, T$的单词, and interpret the action of this matrix in terms of the reduction algorithm to the fundamental set for \({{\mathrm{PSL}}}_2(\mathbb Z )\).
(d) Let \(A=\begin{pmatrix} a &{} b \\ c &{} d \end{pmatrix} \in {{\mathrm{SL}}}_2(\mathbb Z )\). Show that \(\gcd (a,c)=1\) and conclude from (c) that there exists \(W \in \langle S,T \rangle \) such that
$$\begin{aligned} WA=\begin{pmatrix} 1 &{} b' \\ 0 &{} 1 \end{pmatrix} \end{aligned}$$
with \(b' \in \mathbb Z \). Conclude that \(\langle S,T \rangle ={{\mathrm{PSL}}}_2(\mathbb Z )\). (So how, in the end, does this procedure to write $A$ in terms of $S$ and $T$ relate to the one given by the reduction algorithm in Lemma 35.1.8?)

hbghlyj

(a) 令$q=\left\lceil a\over b\right\rceil$. 因为$a>b$, 所以$\frac ab>1$, 所以$q>2$.
(b) 首先$\gcd(a,b)|r_0,r_1$. 由$r_{i-1}=q_ir_i-r_{i+1}$, 从$\gcd(a,b)\mid r_{i-1},r_i$推出$\gcd(a,b)\mid r_{i+1}$. 归纳可证$\gcd(a,b)\mid r_i\forall i\in\{0,\dots,t\}$, 故$\gcd (a,b)\mid r_t$.
因为$r_{t+1}=0$, 所以$r_t\mid r_{t-1}$, 归纳可证$\gcd(a,b)\mid r_i\forall i\in\{0,\dots,t\}$, 故$r_t\mid a,b$, 故$r_t\mid\gcd(a,b)$, 故$r_t=\gcd(a,b)$.
如果 \(\gcd (a,b)=1\) 那么 $a=q_1b-r_2\implies\frac ab=q_1-\frac{r_2}b$

$b=q_2r_2-r_3\implies \frac b{r_2}=q_2-\frac{r_3}{r_2}\implies\cfrac ab=q_1-\cfrac1{q_2-\cfrac{r_3}{r_2}}$
如此继续到\[\frac{a}{b}=q_1 - \frac{1}{q_2-\displaystyle {\frac{1}{\cdots -\displaystyle {\frac{1}{q_{t-1}-\frac{r_t}{r_{t-1}}}}}}}. \]$r_{t-1}=q_tr_t-r_{t+1},r_{t+1}=0\implies\frac{r_{t-1}}{r_t}=q_t$, 因此\[\frac{a}{b}=q_1 - \frac{1}{q_2-\displaystyle {\frac{1}{\cdots -\displaystyle {\frac{1}{q_{t-1}-\frac1{q_t}}}}}}. \](c) $\begin{pmatrix} 0 &{} 1 \\ -1 &{} q_1 \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix}b\\r_1\end{pmatrix}$
可以验证$\begin{pmatrix} 0 &{} 1 \\ -1 &{} q_i \end{pmatrix}\begin{pmatrix}r_{i-1}\\r_i\end{pmatrix}=\begin{pmatrix}r_i\\r_{i+1}\end{pmatrix}$
所以$\begin{pmatrix} 0 &{} 1 \\ -1 &{} q_t \end{pmatrix} \cdots \begin{pmatrix} 0 &{} 1 \\ -1 &{} q_1 \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} r_t \\r_{t+1} \end{pmatrix}= \begin{pmatrix} r_t \\ 0 \end{pmatrix}.$
MatrixPower[{{0,-1},{1,0}},-1].MatrixPower[{{1,1},{0,1}},-q]//MatrixForm输出$\left(
\begin{array}{cc}
0&1\\
-1&q\\
\end{array}
\right)$,即$S^{-1}T^{-q}=\left(
\begin{array}{cc}
0&1\\
-1&q\\
\end{array}
\right)$
(d) 因为$A\in\mathrm{SL}_2(\mathbb Z)$, 所以$\det A=ad-bc=1$, 所以$\gcd(a,c)=1$.
由(c)知存在$W\in\langle S,T\rangle$使$W\begin{pmatrix} a \\ c\end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$
因为$\det W=1$, 所以$1=\det A=\det WA$, 因此$WA$的(2,2)元素为1, 即\[WA=\begin{pmatrix} 1 &{} b' \\ 0 &{} 1 \end{pmatrix}\]

hbghlyj

关于reduction algorithm in Lemma 35.1.8又见Math784第3页的例子:
给定$\gamma=\left(\begin{array}{cc}4 & 9 \\ 11 & 25\end{array}\right)∈PSL_2(\mathbb Z)$要表示为$S,T$
注意到$$\gamma T^{n}=\left(\begin{array}{cc}4 & 9 \\ 11 & 25\end{array}\right)\left(\begin{array}{cc}1 & n \\ 0 & 1\end{array}\right)=\left(\begin{array}{cc}4 & 4 n+9 \\ 11 & 11 n+25\end{array}\right), \gamma S=\left(\begin{array}{cc}4 & 9 \\ 11 & 25\end{array}\right)\left(\begin{array}{cc}0 & -1 \\ 1 & 0\end{array}\right)=\left(\begin{array}{cc}9 & -4 \\ 25 & -11\end{array}\right)$$选择 $n$ 减小矩阵 $γT^n$ 中的数。用 $S$ 交换列，可以选择 $n$（在我们的例子中 $n = −2$）使 $|d| < |c|$。然后$$\gamma T^{-2}=\left(\begin{array}{cc}4 & 1 \\ 11 & 3\end{array}\right) \implies\gamma T^{-2} S=\left(\begin{array}{cc}4 & 1 \\ 11 & 3\end{array}\right)\left(\begin{array}{cc}0 & -1 \\ 1 & 0\end{array}\right)=\left(\begin{array}{cc}1 & -4 \\ 3 & -11\end{array}\right)$$我们可以继续这个过程，现在通过乘以 $T^4$ （$T^3$ 也可以）来减少 $11\bmod 3$。最终得到$$\gamma=S T^{-3} S T^{-4} S T^{2}$$