Proving that a set generates $\Gamma_0(4)$

Question

I want to show that $$\Gamma_0(4) = \biggl\{\gamma = \pmatrix{a&b\cr c&d}\in {\rm SL}_2({\bf Z}) : c\equiv 0\pmod 4\biggr\}$$ is generated by the three matrices $$\pmatrix{1&1\cr 0&1},\quad\pmatrix{1&0\cr 4&1},\quad\hbox{and}\quad\pmatrix{-1&0\cr 0&-1}.$$ I tried to do this by showing that note that for any $\gamma = \bigl( {a\atop c}{b\atop d}\bigr) \in \Gamma_0(4)$, we have $$\pmatrix{a&b\cr c&d}\pmatrix{1&-n\cr 0&1} = \pmatrix{a & b-na\cr c&d-nc}\qquad\hbox{and}\qquad \pmatrix{a&b\cr c&d}\pmatrix{1&0\cr -4n&1} = \pmatrix{a-4nb & b\cr c-4nd&d}.$$ If $c$ is $0$ we are done, since $\gamma$ is in $\Gamma_0(4)$ in this case. Otherwise, if $|c|<|d|$, we can apply the division algorithm to get $q$ and $d'$ such that $|d| = |c|q + d'$ with $|d'| < |c|/2$, and the first transformation applied $q$ times produces a matrix whose bottom-left entry is $c$ and whose bottom-right entry is $d'$. On the other hand, if $d\ne 0$ and $|c|>4|d|$, then we can find $q$ and $c'$ such that $|c| = 4|d|q + c'$ where $|c'| < 2|d|$ and we apply the second transformation $q$ times to get a matrix with bottom-left entry $c'$. In each case, we have strictly reduced the quantity $\min\bigl\{|c|, 2|d|\bigr\}$, so the process must terminate with $|c| = 0$ or $|d|=0$. In the first case we have found an element of $\Gamma_0(4)$, and the second case cannot happen, since it would imply that $c = \pm 1$.

I think this is the right idea except that we're missing the case where $|d|\le |c|\le 4|d|$ (correct me if there are any other holes in the proof other than this). I'm just not sure what to do in this case.

Answer 1

I have found a roundabout proof that goes through $$\Gamma(2) = \biggl\{ \pmatrix {a&b\cr c&d} \in {\rm SL}_2({\bf Z}) : a,c\ \hbox{odd},\,b,d\ \hbox{even}\biggr\}.$$ $$\pmatrix{1&2\cr 0&1},\quad\pmatrix{1&0\cr 2&1},\quad\hbox{and}\quad\pmatrix{-1&0\cr 0&-1}$$ To see this, note that for a general matrix $\bigl({a\atop c}{b\atop d}\bigr) \in \Gamma(2)$, $$\pmatrix{a&b\cr c&d}\pmatrix{1&-2\cr 0&1} = \pmatrix{a & b-2a\cr c&d-2c}\qquad\hbox{and}\qquad \pmatrix{a&b\cr c&d}\pmatrix{1&0\cr -2&1} = \pmatrix{a-2b & b\cr c-2d&d}.$$ Suppose that $b\ne 0$. Since $|a|$ is odd and $|b|$ is even, they are not equal. if $|a|$ is larger, we use the division algorithm to find $q,r$ such that $|a| = |2b|q+r$, where $|r| < |b|$, and then apply the second transformation $q$ times to strictly reduce the absolute value of the top-left matrix entry. If $|b|$ is larger, we reduce the absolute value of the top-right entry in a similar fashion. We can keep doing this until $b=0$, in which case the matrix must be some integer power of $\bigl( {1\atop 2}{0\atop 1}\bigr)$, after possibly multiplying by $\bigl( {-1\atop 0}{0\atop-1}\bigr)$.

Now we claim that $\Gamma(2)$ and $\Gamma_0(4)$ are conjugate in ${\rm SL}_2({\bf Q})$, by the element $\bigl( {2\atop 0}{0\atop 1}\bigr)$. Indeed, for any $\gamma = \bigl({a\atop c}{b\atop d}\bigr) \in {\rm SL}_2({\bf Z})$, $$\pmatrix{ 1/2 & 0\cr 0&1} \pmatrix {a&b\cr c&d}\pmatrix{2&0\cr 0&1} = \pmatrix{ a/2 & b/2\cr 0&1}\pmatrix{2&0\cr 0&1} = \pmatrix{a&b/2\cr 2c&d},$$ and if $\gamma\in \Gamma(2)$ to begin with, then $2c$ is a multiple of $4$ so the result is in $\Gamma_0(4)$. On the other hand, $$\pmatrix{ 2 & 0\cr 0&1} \pmatrix {a&b\cr c&d}\pmatrix{1/2&0\cr 0&1} = \pmatrix{ 2 & b\cr 0&1}\pmatrix{1/2&0\cr 0&1} = \pmatrix{a&b\cr c/2&d}.$$ In this case, if $\gamma\in \Gamma_0(4)$, then $bc$ is even so $a$ and $d$ must be odd for $ad-bc$ to equal $1$. Since $c$ was a multiple of $4$, we have $c/2$ even and of course, so is $2b$, so the result is in $\Gamma(2)$. Finally, note that $$\pmatrix{ 1/2 & 0\cr 0&1} \pmatrix {1&2\cr 0&1}\pmatrix{2&0\cr 0&1} = \pmatrix{ 1&1\cr 0&1}$$ and $$\pmatrix{ 1/2 & 0\cr 0&1} \pmatrix {1&0\cr 2&1}\pmatrix{2&0\cr 0&1} = \pmatrix{ 1&0\cr 4&1},$$ so the generators of $\Gamma_0(4)$ are indeed $$\pmatrix{1&1\cr 0&1},\quad\pmatrix{1&0\cr 4&1},\quad\hbox{and}\quad\pmatrix{-1&0\cr 0&-1}.$$

I will leave the question open, in the hope that someone can bring my original approach to a conclusion or show that something is wrong with it. Thanks!