Farey Symbol for arithmetic subgroups of \({\rm PSL}_2(\ZZ)\)

AUTHORS:

  • Hartmut Monien (08 - 2011)

based on the KFarey package by Chris Kurth. Implemented as C++ module for speed.

class sage.modular.arithgroup.farey_symbol.Farey

Bases: object

A class for calculating Farey symbols of arithmetics subgroups of \({\rm PSL}_2(\ZZ)\).

The arithmetic subgroup can be either any of the congruence subgroups implemented in Sage, i.e. Gamma, Gamma0, Gamma1 and GammaH or a subgroup of \({\rm PSL}_2(\ZZ)\) which is given by a user written helper class defining membership in that group.

REFERENCES:

INPUT:

  • \(G\) - an arithmetic subgroup of \({\rm PSL}_2(\ZZ)\)

EXAMPLES:

Create a Farey symbol for the group \(\Gamma_0(11)\):

sage: f = FareySymbol(Gamma0(11)); f
FareySymbol(Congruence Subgroup Gamma0(11))

Calculate the generators:

sage: f.generators()
[
[1 1]  [ 7 -2]  [ 8 -3]  [-1  0]
[0 1], [11 -3], [11 -4], [ 0 -1]
]

Pickling the FareySymbol and recovering it:

sage: f == loads(dumps(f))
True

Calculate the index of \(\Gamma_H(33, [2, 5])\) in \({\rm PSL}_2(\ZZ)\) via FareySymbol:

sage: FareySymbol(GammaH(33, [2, 5])).index()
48

Calculate the generators of \(\Gamma_1(4)\):

sage: FareySymbol(Gamma1(4)).generators()
[
[1 1]  [-3  1]
[0 1], [-4  1]
]

Calculate the generators of the example of an index 10 arithmetic subgroup given by Tim Hsu:

sage: from sage.modular.arithgroup.arithgroup_perm import HsuExample10
sage: FareySymbol(HsuExample10()).generators()
[
[1 2]  [-2  1]  [ 4 -3]
[0 1], [-7  3], [ 3 -2]
]

Calculate the generators of the group \(\Gamma' = \Gamma_0(8)\cap\Gamma_1(4)\) using a helper class to define group membership:

sage: class GPrime:
....:   def __contains__(self, M):
....:       return M in Gamma0(8) and M in Gamma1(4)
....:

sage: FareySymbol(GPrime()).generators()
[
[1 1]  [ 5 -1]  [ 5 -2]
[0 1], [16 -3], [ 8 -3]
]

Calculate cusps of arithmetic subgroup defined via permutation group:

sage: L = SymmetricGroup(4)('(1, 2, 3)')

sage: R = SymmetricGroup(4)('(1, 2, 4)')

sage: FareySymbol(ArithmeticSubgroup_Permutation(L, R)).cusps()
[-1, Infinity]

Calculate the left coset representation of \(\Gamma_H(8, [3])\):

sage: FareySymbol(GammaH(8, [3])).coset_reps()
[
[1 0]  [ 4 -1]  [ 3 -1]  [ 2 -1]  [ 1 -1]  [ 3 -1]  [ 2 -1]  [-1  0]
[0 1], [ 1  0], [ 1  0], [ 1  0], [ 1  0], [ 4 -1], [ 3 -1], [ 3 -1],
[ 1 -1]  [-1  0]  [ 0 -1]  [-1  0]
[ 2 -1], [ 2 -1], [ 1 -1], [ 1 -1]
]
coset_reps()

Left coset of the arithmetic group of the FareySymbol.

EXAMPLES:

Calculate the left coset of \(\Gamma_0(6)\):

sage: FareySymbol(Gamma0(6)).coset_reps()
[
[1 0]  [ 3 -1]  [ 2 -1]  [ 1 -1]  [ 2 -1]  [ 3 -2]  [ 1 -1]  [-1  0]
[0 1], [ 1  0], [ 1  0], [ 1  0], [ 3 -1], [ 2 -1], [ 2 -1], [ 2 -1],
[ 1 -1]  [ 0 -1]  [-1  0]  [-2  1]
[ 3 -2], [ 1 -1], [ 1 -1], [ 1 -1]
]
cusp_class(c)

Cusp class of a cusp in the FareySymbol.

INPUT:

c – a cusp

EXAMPLES:

sage: FareySymbol(Gamma0(12)).cusp_class(Cusp(1, 12))
5
cusp_widths()

Cusps widths of the FareySymbol.

EXAMPLES:

sage: FareySymbol(Gamma0(6)).cusp_widths()
[6, 2, 3, 1]
cusps()

Cusps of the FareySymbol.

EXAMPLES:

sage: FareySymbol(Gamma0(6)).cusps()
[0, 1/3, 1/2, Infinity]
fractions()

Fractions of the FareySymbol.

EXAMPLES:

sage: FareySymbol(Gamma(4)).fractions()
[0, 1/2, 1, 3/2, 2, 5/2, 3, 7/2, 4]
fundamental_domain(show_pairing=True, color_even='white', color='lightgray', thickness=1, zorder=2, alpha=1, tesselation='Dedekind', fill=True, linestyle='solid', ymax=1, **options)

Plot a fundamental domain of an arithmetic subgroup of \({\rm PSL}_2(\ZZ)\) corresponding to the Farey symbol.

OPTIONS:

  • fill – boolean (default True) fill the fundamental domain
  • linestyle – string (default: ‘solid’) The style of the line, which is one of ‘dashed’, ‘dotted’, ‘solid’, ‘dashdot’, or ‘–’, ‘:’, ‘-‘, ‘-.’, respectively
  • color – (default: ‘lightgray’) fill color; fill color for odd part of Dedekind tesselation.
  • show_pairing – boolean (default: True) flag for pairing
  • tesselation – (default: ‘Dedekind’) The type of hyperbolic tesselation which is one of ‘coset’, ‘Dedekind’ or None respectively
  • color_even – fill color for even parts of Dedekind tesselation (default ‘white’); ignored for other tesselations
  • thickness – float (default: \(1\)) the thickness of the line
  • ymax – float (default: \(1\)) maximal height

EXAMPLES:

For example, to plot the fundamental domain of \(\Gamma_0(11)\) with pairings use the following command:

sage: FareySymbol(Gamma0(11)).fundamental_domain()
Graphics object consisting of 54 graphics primitives

indicating that side 1 is paired with side 3 and side 2 is paired with side 4, see also paired_sides().

To plot the fundamental domain of \(\Gamma(3)\) without pairings use the following command:

sage: FareySymbol(Gamma(3)).fundamental_domain(show_pairing=False)
Graphics object consisting of 48 graphics primitives

Plot the fundamental domain of \(\Gamma_0(23)\) showing the left coset representatives:

sage: FareySymbol(Gamma0(23)).fundamental_domain(tesselation='coset')
Graphics object consisting of 58 graphics primitives

The same as above but with a custom linestyle:

sage: FareySymbol(Gamma0(23)).fundamental_domain(tesselation='coset', linestyle=':', thickness='2')
Graphics object consisting of 58 graphics primitives
generators()

Minimal set of generators of the group of the FareySymbol.

EXAMPLES:

Calculate the generators of \(\Gamma_0(6)\):

sage: FareySymbol(Gamma0(6)).generators()
[
[1 1]  [ 5 -1]  [ 7 -3]  [-1  0]
[0 1], [ 6 -1], [12 -5], [ 0 -1]
]

Calculate the generators of \({\rm SL}_2(\ZZ)\):

sage: FareySymbol(SL2Z).generators()
[
[ 0 -1]  [ 0 -1]
[ 1  0], [ 1 -1]
]

The unique index 2 even subgroup and index 4 odd subgroup each get handled correctly:

sage: FareySymbol(ArithmeticSubgroup_Permutation(S2="(1,2)", S3="()")).generators()
[
[ 0  1]  [-1  1]
[-1 -1], [-1  0]
]
sage: FareySymbol(ArithmeticSubgroup_Permutation(S2="(1,2, 3, 4)", S3="(1,3)(2,4)")).generators()
[
[ 0  1]  [-1  1]
[-1 -1], [-1  0]
]
genus()

Return the genus of the arithmetic group of the FareySymbol.

EXAMPLES:

sage: [FareySymbol(Gamma0(n)).genus() for n in range(16, 32)]
[0, 1, 0, 1, 1, 1, 2, 2, 1, 0, 2, 1, 2, 2, 3, 2]
index()

Return the index of the arithmetic group of the FareySymbol in \({\rm PSL}_2(\ZZ)\).

EXAMPLES:

sage: [FareySymbol(Gamma0(n)).index() for n in range(1, 16)]
[1, 3, 4, 6, 6, 12, 8, 12, 12, 18, 12, 24, 14, 24, 24]
level()

Return the level of the arithmetic group of the FareySymbol.

EXAMPLES:

sage: [FareySymbol(Gamma0(n)).level() for n in range(1, 16)]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
nu2()

Return the number of elliptic points of order two.

EXAMPLES:

sage: [FareySymbol(Gamma0(n)).nu2() for n in range(1, 16)]
[1, 1, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 2, 0, 0]
nu3()

Return the number of elliptic points of order three.

EXAMPLES:

sage: [FareySymbol(Gamma0(n)).nu3() for n in range(1, 16)]
[1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0]
paired_sides()

Pairs of index of the sides of the fundamental domain of the Farey symbol of the arithmetic group. The sides of the hyperbolic polygon are numbered 0, 1, … from left to right.

../../../_images/pairing.png

EXAMPLES:

sage: FareySymbol(Gamma0(11)).paired_sides()
[(0, 5), (1, 3), (2, 4)]

indicating that the side 0 is paired with 5, 1 with 3 and 2 with 4.

pairing_matrices()

Pairing matrices of the sides of the fundamental domain. The sides of the hyperbolic polygon are numbered 0, 1, … from left to right.

EXAMPLES:

sage: FareySymbol(Gamma0(6)).pairing_matrices()
[
[1 1]  [ 5 -1]  [ 7 -3]  [ 5 -3]  [ 1 -1]  [-1  1]
[0 1], [ 6 -1], [12 -5], [12 -7], [ 6 -5], [ 0 -1]
]
pairing_matrices_to_tietze_index()

Obtain the translation table from pairing matrices to generators.

The result is cached.

OUTPUT:

a list where the \(i\)-th entry is a nonzero integer \(k\), such that if \(k > 0\) then the \(i\)-th pairing matrix is (up to sign) the \((k-1)\)-th generator and, if \(k < 0\), then the \(i\)-th pairing matrix is (up to sign) the inverse of the \((-k-1)\)-th generator.

EXAMPLES:

sage: F = Gamma0(40).farey_symbol()
sage: table = F.pairing_matrices_to_tietze_index()
sage: table[12]
(-2, -1)
sage: F.pairing_matrices()[12]
[  3  -1]
[ 40 -13]
sage: F.generators()[1]**-1
[ -3   1]
[-40  13]
pairings()

Pairings of the sides of the fundamental domain of the Farey symbol of the arithmetic group.

The sides of the hyperbolic polygon are numbered 0, 1, … from left to right. Conventions: even pairings are denoted by -2, odd pairings by -3 while free pairings are denoted by an integer number greater than zero.

EXAMPLES:

Odd pairings:

sage: FareySymbol(Gamma0(7)).pairings()
[1, -3, -3, 1]

Even and odd pairings:

FareySymbol(Gamma0(13)).pairings()
[1, -3, -2, -2, -3, 1]

Only free pairings:

sage: FareySymbol(Gamma0(23)).pairings()
[1, 2, 3, 5, 3, 4, 2, 4, 5, 1]
reduce_to_cusp(r)

Transformation of a rational number to cusp representative.

INPUT:

r – a rational number

EXAMPLES:

sage: FareySymbol(Gamma0(12)).reduce_to_cusp(5/8)
[ 5  -3]
[12  -7]

Reduce 11/17 to a cusp of for HsuExample10():

sage: from sage.modular.arithgroup.arithgroup_perm import HsuExample10
sage: f = FareySymbol(HsuExample10())
sage: f.reduce_to_cusp(11/17)
[14 -9]
[-3  2]
sage: _.acton(11/17)
1
sage: f.cusps()[f.cusp_class(11/17)]
1
word_problem(M, output='standard', check=True)

Solve the word problem (up to sign) using this Farey symbol.

INPUT:

  • M – An element \(M\) of \({\rm SL}_2(\ZZ)\).
  • output – (default: 'standard') Should be one of 'standard', 'syllables', 'gens'.
  • check – (default: True) Whether to check for correct input and output.

OUTPUT:

A solution to the word problem for the matrix \(M\). The format depends on the output parameter, as follows.

  • standard returns the so called the Tietze representation, consists of a tuple of nonzero integers \(i\), where if \(i\) > 0 then it indicates the \(i`th generator (that is, ``self.generators()[0]`\) would correspond to \(i\) = 1), and if \(i\) < 0 then it indicates the inverse of the \(i\)-th generator.
  • syllables returns a tuple of tuples of the form \((i,n)\), where \((i,n)\) represents self.generators()[i] ^ n, whose product equals \(M\) up to sign.
  • gens returns tuple of tuples of the form \((g,n)\), \((g,n)\) such that the product of the matrices \(g^n\) equals \(M\) up to sign.

EXAMPLES:

sage: F = Gamma0(30).farey_symbol()
sage: gens = F.generators()
sage: g = gens[3] * gens[10] * gens[8]^-1 * gens[5]
sage: g
[-628597   73008]
[-692130   80387]
sage: F.word_problem(g)
(4, 11, -9, 6)
sage: g = gens[3] * gens[10]^2 * gens[8]^-1 * gens[5]
sage: g
[-5048053   586303]
[-5558280   645563]
sage: F.word_problem(g, output = 'gens')
((
[109 -10]
[120 -11], 1
),
 (
[ 19  -7]
[ 30 -11], 2
),
 (
[ 49  -9]
[ 60 -11], -1
),
 (
[17 -2]
[60 -7], 1
))
sage: F.word_problem(g, output = 'syllables')
((3, 1), (10, 2), (8, -1), (5, 1))