generators of principal congruence subgroups and Sage package - MathOverflow

generators of principal congruence subgroups and Sage package

2012-07-03T23:38:42Z

I'm trying to find an explicit minimal set of generators for principal congruence subgroups of $\mathrm{SL}_{2}(\mathbb{Z})$, $\Gamma(N)$ for $N$ all powers of $2$. I know the question has been asked before as to how to find a minimal set of generators for congruence subgroups of special linear groups in the $n = 2$ case, and it was mentioned that there is an algorithm for computing this using Farey symbols. There is a package for Sage written by Chris Kurth which I would like to download, but it seems that I can't find a working link to it. I guess my main questions are as follows:

1) Can anyone tell me how to get this KFarey package on Sage? (Unfortunately, it's probably impractical for large $N$...)

2) Does anyone have any other practical idea as to how to find a minimal set of generators for each $\Gamma(2^{n})$? In particular, if anyone happened to know the answer even for $\Gamma(4)$, it would be greatly helpful to me in the short term.

3) (In case explicit generators cannot easily be found) does anyone know how to compute the abelianization of each $\Gamma(2^{n})$?

Thanks very much!

Jeff

Answer by Igor Rivin for generators of principal congruence subgroups and Sage package

2012-07-04T00:36:00Z

I cannot help you with Sage, but doubtlessly someone will step up.
The Farey method has its genesis (I believe) in this paper by Kulkarni (American Journal, 1991). Not the easiest paper to read, but probably not the hardest :)
The quotient of $\mathbb{H}^2$ by $\Gamma_0(4)$ is isometric to the regular ideal octahedron. The combinatorics of the covering (of the modular orbifold) can be obtained by baricentrically subdividing each face into six triangles, painting them alternatively black and white, and thinking of each pair of adjacent triangles as an unfolded modular orbifold (the modular orbifold being a doubled triangle, with black top side and white bottom side). For more on this line of thinking, check out my antique arxiv preprint called "Triangulations into Groups" -- this gives an algorithm for constructing generators for a subgroup of $PSL(2, \mathbb{Z})$ corresponding to a triangulation.

Answer by Dima Pasechnik for generators of principal congruence subgroups and Sage package

2012-07-04T05:58:50Z

The kfarey functionality is available in new versions of Sage, see Sage docs. You don't need to install anything extra. E.g. I can run the code given there:

$ sage 
----------------------------------------------------------------------
| Sage Version 5.1.beta6, Release Date: 2012-06-25                   |
| Type "notebook()" for the browser-based notebook interface.        |
| Type "help()" for help.                                            |
----------------------------------------------------------------------
**********************************************************************
*                                                                    *
* Warning: this is a prerelease version, and it may be unstable.     *
*                                                                    *
**********************************************************************
sage: F = FareySymbol(Gamma0(11)); F
FareySymbol(Congruence Subgroup Gamma0(11))
sage: F.generators()
[
[1 1]  [ 7 -2]  [ 8 -3]  [-1  0]
[0 1], [11 -3], [11 -4], [ 0 -1]
]
sage:

Here is the same for $\Gamma_0(4)$ and $\Gamma(4)$:

sage: F = FareySymbol(Gamma0(4)); F
FareySymbol(Congruence Subgroup Gamma0(4))
sage: F.generators()
[
[1 1]  [ 3 -1]  [-1  0]
[0 1], [ 4 -1], [ 0 -1]
]
sage:FareySymbol(Gamma(4)).generators()
[
[1 4]  [-15   4]  [ 5 -4]  [  9 -16]  [ 13 -36]
[0 1], [ -4   1], [ 4 -3], [  4  -7], [  4 -11]
]
sage:FareySymbol(Gamma(8)).generators()
[
[1 8]  [-63   8]  [137 -40]  [ 89 -32]  [ 289 -112]  [ 73 -32]
[0 1], [ -8   1], [ 24  -7], [ 64 -23], [  80  -31], [ 16  -7],

[-71  40]  [105 -64]  [ 161 -104]  [-79  56]  [ 9 -8]  [ 161 -208]
[-16   9], [ 64 -39], [  48  -31], [-24  17], [ 8 -7], [  24  -31],

[ 153 -208]  [  89 -128]  [-87 136]  [ 169 -272]  [-103  176]
[  64  -87], [  16  -23], [-16  25], [  64 -103], [ -24   41],

[ 17 -32]  [ 185 -424]  [ 217 -512]  [ 105 -256]  [-103  264]
[  8 -15], [  24  -55], [  64 -151], [  16  -39], [ -16   41],

[ 233 -608]  [-127  344]  [ 25 -72]  [ 121 -416]  [-119  424]
[  64 -167], [ -24   65], [  8 -23], [  16  -55], [ -16   57],

[-151  560]  [  33 -128]  [-175  824]  [  41 -200]  [  49 -288]
[ -24   89], [   8  -31], [ -24  113], [   8  -39], [   8  -47],

[  57 -392]
[   8  -55]
]