# 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, )$$:

sage: FareySymbol(GammaH(8, )).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(alpha=1, fill=True, thickness=1, color='lightgray', color_even='white', zorder=2, linestyle='solid', show_pairing=True, tesselation='Dedekind', 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. 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
(-2, -1)
sage: F.pairing_matrices()
[  3  -1]
[ 40 -13]
sage: F.generators()**-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$$ 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 * gens * gens^-1 * gens
sage: g
[-628597   73008]
[-692130   80387]
sage: F.word_problem(g)
(4, 11, -9, 6)
sage: g = gens * gens^2 * gens^-1 * gens
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))