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

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.

• You write $((a c) (b d))$ instead of $((a b) (c d))$ in a couple of places; make sure that you haven't miscalculated based on that? Nov 29, 2021 at 4:36
• Oops I have fixed it. I think the calculations are correct (but let me know if I am wrong). Nov 29, 2021 at 4:44
• An alternative approach (which works) is to use the known presentation $\langle x,y, \mid x^2=y^3, x^4=1 \rangle$ of ${\rm SL}(2,{\mathbb Z})$ to show that the index of the subgroup generated by those three matrices is $6$, which is equal to the index of $\Gamma_0(4)$. Nov 29, 2021 at 8:48

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}.$$