# Lists of Manin symbols over $$\QQ$$, elements of $$\mathbb{P}^1(\ZZ/N\ZZ)$$#

class sage.modular.modsym.p1list.P1List[source]#

Bases: object

The class for $$\mathbb{P}^1(\ZZ/N\ZZ)$$, the projective line modulo $$N$$.

EXAMPLES:

sage: P = P1List(12); P
The projective line over the integers modulo 12
sage: list(P)
[(0, 1), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (1, 11), (2, 1), (2, 3), (2, 5), (3, 1), (3, 2), (3, 4), (3, 7), (4, 1), (4, 3), (4, 5), (6, 1)]

>>> from sage.all import *
>>> P = P1List(Integer(12)); P
The projective line over the integers modulo 12
>>> list(P)
[(0, 1), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (1, 11), (2, 1), (2, 3), (2, 5), (3, 1), (3, 2), (3, 4), (3, 7), (4, 1), (4, 3), (4, 5), (6, 1)]


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

>>> from sage.all import *
True

N()[source]#

Return the level or modulus of this P1List.

EXAMPLES:

sage: L = P1List(120)
sage: L.N()
120

>>> from sage.all import *
>>> L = P1List(Integer(120))
>>> L.N()
120

apply_I(i)[source]#

Return the index of the result of applying the matrix $$I=[-1,0;0,1]$$ to the $$i$$’th element of this P1List.

INPUT:

• i – integer (the index of the element to act on).

EXAMPLES:

sage: L = P1List(120)
sage: L[10]
(1, 9)
sage: L.apply_I(10)
112
sage: L[112]
(1, 111)
sage: L.normalize(-1,9)
(1, 111)

>>> from sage.all import *
>>> L = P1List(Integer(120))
>>> L[Integer(10)]
(1, 9)
>>> L.apply_I(Integer(10))
112
>>> L[Integer(112)]
(1, 111)
>>> L.normalize(-Integer(1),Integer(9))
(1, 111)


This operation is an involution:

sage: all(L.apply_I(L.apply_I(i)) == i for i in range(len(L)))
True

>>> from sage.all import *
>>> all(L.apply_I(L.apply_I(i)) == i for i in range(len(L)))
True

apply_S(i)[source]#

Return the index of the result of applying the matrix $$S=[0,-1;1,0]$$ to the $$i$$’th element of this P1List.

INPUT:

• i – integer (the index of the element to act on).

EXAMPLES:

sage: L = P1List(120)
sage: L[10]
(1, 9)
sage: L.apply_S(10)
159
sage: L[159]
(3, 13)
sage: L.normalize(-9,1)
(3, 13)

>>> from sage.all import *
>>> L = P1List(Integer(120))
>>> L[Integer(10)]
(1, 9)
>>> L.apply_S(Integer(10))
159
>>> L[Integer(159)]
(3, 13)
>>> L.normalize(-Integer(9),Integer(1))
(3, 13)


This operation is an involution:

sage: all(L.apply_S(L.apply_S(i)) == i for i in range(len(L)))
True

>>> from sage.all import *
>>> all(L.apply_S(L.apply_S(i)) == i for i in range(len(L)))
True

apply_T(i)[source]#

Return the index of the result of applying the matrix $$T=[0,1;-1,-1]$$ to the $$i$$’th element of this P1List.

INPUT:

• i – integer (the index of the element to act on).

EXAMPLES:

sage: L = P1List(120)
sage: L[10]
(1, 9)
sage: L.apply_T(10)
157
sage: L[157]
(3, 10)
sage: L.normalize(9,-10)
(3, 10)

>>> from sage.all import *
>>> L = P1List(Integer(120))
>>> L[Integer(10)]
(1, 9)
>>> L.apply_T(Integer(10))
157
>>> L[Integer(157)]
(3, 10)
>>> L.normalize(Integer(9),-Integer(10))
(3, 10)


This operation has order three:

sage: all(L.apply_T(L.apply_T(L.apply_T(i))) == i for i in range(len(L)))
True

>>> from sage.all import *
>>> all(L.apply_T(L.apply_T(L.apply_T(i))) == i for i in range(len(L)))
True

index(u, v)[source]#

Return the index of the class of $$(u,v)$$ in the fixed list of representatives of $$\mathbb{P}^1(\ZZ/N\ZZ)$$.

INPUT:

• u, v – integers, with $$\gcd(u,v,N)=1$$.

OUTPUT:

• i – the index of $$u$$, $$v$$, in the P1list.

EXAMPLES:

sage: L = P1List(120)
sage: L[100]
(1, 99)
sage: L.index(1,99)
100
sage: all(L.index(L[i][0],L[i][1])==i for i in range(len(L)))
True

>>> from sage.all import *
>>> L = P1List(Integer(120))
>>> L[Integer(100)]
(1, 99)
>>> L.index(Integer(1),Integer(99))
100
>>> all(L.index(L[i][Integer(0)],L[i][Integer(1)])==i for i in range(len(L)))
True

index_of_normalized_pair(u, v)[source]#

Return the index of the class of $$(u,v)$$ in the fixed list of representatives of $$\mathbb{P}^1(\ZZ/N\ZZ)$$.

INPUT:

• u, v – integers, with $$\gcd(u,v,N)=1$$, normalized so they lie in the list.

OUTPUT:

• i – the index of $$(u:v)$$, in the P1list.

EXAMPLES:

sage: L = P1List(120)
sage: L[100]
(1, 99)
sage: L.index_of_normalized_pair(1,99)
100
sage: all(L.index_of_normalized_pair(L[i][0],L[i][1])==i for i in range(len(L)))
True

>>> from sage.all import *
>>> L = P1List(Integer(120))
>>> L[Integer(100)]
(1, 99)
>>> L.index_of_normalized_pair(Integer(1),Integer(99))
100
>>> all(L.index_of_normalized_pair(L[i][Integer(0)],L[i][Integer(1)])==i for i in range(len(L)))
True

lift_to_sl2z(i)[source]#

Lift the $$i$$’th element of this P1list to an element of $$SL(2,\ZZ)$$.

If the $$i$$’th element is $$(c,d)$$, this function computes and returns a list $$[a,b, c',d']$$ that defines a 2x2 matrix with determinant 1 and integer entries, such that $$c=c'$$ (mod $$N$$) and $$d=d'$$ (mod $$N$$).

INPUT:

• i – integer (the index of the element to lift).

EXAMPLES:

sage: p = P1List(11)
sage: p.list()[3]
(1, 2)

sage: p.lift_to_sl2z(3)
[0, -1, 1, 2]

>>> from sage.all import *
>>> p = P1List(Integer(11))
>>> p.list()[Integer(3)]
(1, 2)

>>> p.lift_to_sl2z(Integer(3))
[0, -1, 1, 2]


AUTHORS:

• Justin Walker

list()[source]#

Return the underlying list of this P1List object.

EXAMPLES:

sage: L = P1List(8)
sage: type(L)
<... 'sage.modular.modsym.p1list.P1List'>
sage: type(L.list())
<... 'list'>

>>> from sage.all import *
>>> L = P1List(Integer(8))
>>> type(L)
<... 'sage.modular.modsym.p1list.P1List'>
>>> type(L.list())
<... 'list'>

normalize(u, v)[source]#

Return a normalised element of $$\mathbb{P}^1(\ZZ/N\ZZ)$$.

INPUT:

• u, v – integers, with $$\gcd(u,v,N)=1$$.

OUTPUT:

• a 2-tuple (uu,vv) where $$(uu:vv)$$ is a normalized representative of $$(u:v)$$.

EXAMPLES:

sage: L = P1List(120)
sage: (u,v) = (555555555,7777)
sage: uu,vv = L.normalize(555555555,7777)
sage: (uu,vv)
(15, 13)
sage: (uu*v-vv*u) % L.N() == 0
True

>>> from sage.all import *
>>> L = P1List(Integer(120))
>>> (u,v) = (Integer(555555555),Integer(7777))
>>> uu,vv = L.normalize(Integer(555555555),Integer(7777))
>>> (uu,vv)
(15, 13)
>>> (uu*v-vv*u) % L.N() == Integer(0)
True

normalize_with_scalar(u, v)[source]#

Return a normalised element of $$\mathbb{P}^1(\ZZ/N\ZZ)$$, together with the normalizing scalar.

INPUT:

• u, v – integers, with $$\gcd(u,v,N)=1$$.

OUTPUT:

• a 3-tuple (uu,vv,ss) where $$(uu:vv)$$ is a normalized representative of $$(u:v)$$, and $$ss$$ is a scalar such that $$(ss*uu, ss*vv) = (u,v)$$ (mod $$N$$).

EXAMPLES:

sage: L = P1List(120)
sage: (u,v) = (555555555,7777)
sage: uu,vv,ss = L.normalize_with_scalar(555555555,7777)
sage: (uu,vv)
(15, 13)
sage: ((ss*uu-u)%L.N(), (ss*vv-v)%L.N())
(0, 0)
sage: (uu*v-vv*u) % L.N() == 0
True

>>> from sage.all import *
>>> L = P1List(Integer(120))
>>> (u,v) = (Integer(555555555),Integer(7777))
>>> uu,vv,ss = L.normalize_with_scalar(Integer(555555555),Integer(7777))
>>> (uu,vv)
(15, 13)
>>> ((ss*uu-u)%L.N(), (ss*vv-v)%L.N())
(0, 0)
>>> (uu*v-vv*u) % L.N() == Integer(0)
True

class sage.modular.modsym.p1list.export#

Bases: object

sage.modular.modsym.p1list.lift_to_sl2z(c, d, N)[source]#

Return a list of Python ints $$[a,b,c',d']$$ that are the entries of a 2x2 matrix with determinant 1 and lower two entries congruent to $$c,d$$ modulo $$N$$.

INPUT:

• c,d,N – Python ints or longs such that $$\gcd(c,d,N)=1$$.

EXAMPLES:

sage: lift_to_sl2z(2,3,6)
[1, 1, 2, 3]
sage: lift_to_sl2z(2,3,6000000)
[1, 1, 2, 3]

>>> from sage.all import *
>>> lift_to_sl2z(Integer(2),Integer(3),Integer(6))
[1, 1, 2, 3]
>>> lift_to_sl2z(Integer(2),Integer(3),Integer(6000000))
[1, 1, 2, 3]


You will get a ValueError exception if the input is invalid. Note that here gcd(15,6,24)=3:

sage: lift_to_sl2z(15,6,24)
Traceback (most recent call last):
...
ValueError: input must have gcd 1

>>> from sage.all import *
>>> lift_to_sl2z(Integer(15),Integer(6),Integer(24))
Traceback (most recent call last):
...
ValueError: input must have gcd 1


This function is not implemented except for N at most 2**31:

sage: lift_to_sl2z(1,1,2^32)
Traceback (most recent call last):
...
NotImplementedError: N too large

>>> from sage.all import *
>>> lift_to_sl2z(Integer(1),Integer(1),Integer(2)**Integer(32))
Traceback (most recent call last):
...
NotImplementedError: N too large

sage.modular.modsym.p1list.lift_to_sl2z_int(c, d, N)[source]#

Lift a pair $$(c, d)$$ to an element of $$SL(2, \ZZ)$$.

$$(c,d)$$ is assumed to be an element of $$\mathbb{P}^1(\ZZ/N\ZZ)$$. This function computes and returns a list $$[a, b, c', d']$$ that defines a 2x2 matrix, with determinant 1 and integer entries, such that $$c=c'$$ (mod $$N$$) and $$d=d'$$ (mod $$N$$).

INPUT:

• c,d,N – integers such that $$\gcd(c,d,N)=1$$.

EXAMPLES:

sage: from sage.modular.modsym.p1list import lift_to_sl2z_int
sage: lift_to_sl2z_int(2,6,11)
[1, 8, 2, 17]
sage: m = Matrix(Integers(),2,2,lift_to_sl2z_int(2,6,11)); m
[ 1  8]
[ 2 17]

>>> from sage.all import *
>>> from sage.modular.modsym.p1list import lift_to_sl2z_int
>>> lift_to_sl2z_int(Integer(2),Integer(6),Integer(11))
[1, 8, 2, 17]
>>> m = Matrix(Integers(),Integer(2),Integer(2),lift_to_sl2z_int(Integer(2),Integer(6),Integer(11))); m
[ 1  8]
[ 2 17]


AUTHOR:

• Justin Walker

sage.modular.modsym.p1list.lift_to_sl2z_llong(c, d, N)[source]#

Lift a pair $$(c, d)$$ (modulo $$N$$) to an element of $$SL(2, \ZZ)$$.

$$(c,d)$$ is assumed to be an element of $$\mathbb{P}^1(\ZZ/N\ZZ)$$. This function computes and returns a list $$[a, b, c', d']$$ that defines a 2x2 matrix, with determinant 1 and integer entries, such that $$c=c'$$ (mod $$N$$) and $$d=d'$$ (mod $$N$$).

INPUT:

• c,d,N – integers such that $$\gcd(c,d,N)=1$$.

EXAMPLES:

sage: from sage.modular.modsym.p1list import lift_to_sl2z_llong
sage: lift_to_sl2z_llong(2,6,11)
[1, 8, 2, 17]
sage: m = Matrix(Integers(),2,2,lift_to_sl2z_llong(2,6,11)); m
[ 1  8]
[ 2 17]

>>> from sage.all import *
>>> from sage.modular.modsym.p1list import lift_to_sl2z_llong
>>> lift_to_sl2z_llong(Integer(2),Integer(6),Integer(11))
[1, 8, 2, 17]
>>> m = Matrix(Integers(),Integer(2),Integer(2),lift_to_sl2z_llong(Integer(2),Integer(6),Integer(11))); m
[ 1  8]
[ 2 17]


AUTHOR:

• Justin Walker

sage.modular.modsym.p1list.p1_normalize(N, u, v)[source]#

Computes the canonical representative of $$\mathbb{P}^1(\ZZ/N\ZZ)$$ equivalent to $$(u,v)$$ along with a transforming scalar.

INPUT:

• N – an integer

• u – an integer

• v – an integer

OUTPUT: If gcd(u,v,N) = 1, then returns

• uu – an integer

• vv – an integer

• ss – an integer such that $$(ss*uu, ss*vv)$$ is equivalent to $$(u,v)$$ mod $$N$$;

if $$\gcd(u,v,N) \not= 1$$, returns 0, 0, 0.

EXAMPLES:

sage: from sage.modular.modsym.p1list import p1_normalize
sage: p1_normalize(90,7,77)
(1, 11, 7)
sage: p1_normalize(90,7,78)
(1, 24, 7)
sage: (7*24-78*1) % 90
0
sage: (7*24) % 90
78

>>> from sage.all import *
>>> from sage.modular.modsym.p1list import p1_normalize
>>> p1_normalize(Integer(90),Integer(7),Integer(77))
(1, 11, 7)
>>> p1_normalize(Integer(90),Integer(7),Integer(78))
(1, 24, 7)
>>> (Integer(7)*Integer(24)-Integer(78)*Integer(1)) % Integer(90)
0
>>> (Integer(7)*Integer(24)) % Integer(90)
78

sage: from sage.modular.modsym.p1list import p1_normalize
sage: p1_normalize(50001,12345,54322)
(3, 4667, 4115)
sage: (12345*4667-54321*3) % 50001
3
sage: 4115*3 % 50001
12345
sage: 4115*4667 % 50001 == 54322 % 50001
True

>>> from sage.all import *
>>> from sage.modular.modsym.p1list import p1_normalize
>>> p1_normalize(Integer(50001),Integer(12345),Integer(54322))
(3, 4667, 4115)
>>> (Integer(12345)*Integer(4667)-Integer(54321)*Integer(3)) % Integer(50001)
3
>>> Integer(4115)*Integer(3) % Integer(50001)
12345
>>> Integer(4115)*Integer(4667) % Integer(50001) == Integer(54322) % Integer(50001)
True

sage.modular.modsym.p1list.p1_normalize_int(N, u, v)[source]#

Computes the canonical representative of $$\mathbb{P}^1(\ZZ/N\ZZ)$$ equivalent to $$(u,v)$$ along with a transforming scalar.

INPUT:

• N – an integer

• u – an integer

• v – an integer

OUTPUT: If gcd(u,v,N) = 1, then returns

• uu – an integer

• vv – an integer

• ss – an integer such that $$(ss*uu, ss*vv)$$ is congruent to $$(u,v)$$ (mod $$N$$);

if $$\gcd(u,v,N) \not= 1$$, returns 0, 0, 0.

EXAMPLES:

sage: from sage.modular.modsym.p1list import p1_normalize_int
sage: p1_normalize_int(90,7,77)
(1, 11, 7)
sage: p1_normalize_int(90,7,78)
(1, 24, 7)
sage: (7*24-78*1) % 90
0
sage: (7*24) % 90
78

>>> from sage.all import *
>>> from sage.modular.modsym.p1list import p1_normalize_int
>>> p1_normalize_int(Integer(90),Integer(7),Integer(77))
(1, 11, 7)
>>> p1_normalize_int(Integer(90),Integer(7),Integer(78))
(1, 24, 7)
>>> (Integer(7)*Integer(24)-Integer(78)*Integer(1)) % Integer(90)
0
>>> (Integer(7)*Integer(24)) % Integer(90)
78

sage.modular.modsym.p1list.p1_normalize_llong(N, u, v)[source]#

Computes the canonical representative of $$\mathbb{P}^1(\ZZ/N\ZZ)$$ equivalent to $$(u,v)$$ along with a transforming scalar.

INPUT:

• N – an integer

• u – an integer

• v – an integer

OUTPUT: If gcd(u,v,N) = 1, then returns

• uu – an integer

• vv – an integer

• ss – an integer such that $$(ss*uu, ss*vv)$$ is equivalent to $$(u,v)$$ mod $$N$$;

if $$\gcd(u,v,N) \not= 1$$, returns 0, 0, 0.

EXAMPLES:

sage: from sage.modular.modsym.p1list import p1_normalize_llong
sage: p1_normalize_llong(90000,7,77)
(1, 11, 7)
sage: p1_normalize_llong(90000,7,78)
(1, 77154, 7)
sage: (7*77154-78*1) % 90000
0
sage: (7*77154) % 90000
78

>>> from sage.all import *
>>> from sage.modular.modsym.p1list import p1_normalize_llong
>>> p1_normalize_llong(Integer(90000),Integer(7),Integer(77))
(1, 11, 7)
>>> p1_normalize_llong(Integer(90000),Integer(7),Integer(78))
(1, 77154, 7)
>>> (Integer(7)*Integer(77154)-Integer(78)*Integer(1)) % Integer(90000)
0
>>> (Integer(7)*Integer(77154)) % Integer(90000)
78

sage.modular.modsym.p1list.p1list(N)[source]#

Return the elements of the projective line modulo $$N$$, $$\mathbb{P}^1(\ZZ/N\ZZ)$$, as a plain list of 2-tuples.

INPUT:

• N (integer) – a positive integer (less than 2^31).

OUTPUT:

A list of the elements of the projective line $$\mathbb{P}^1(\ZZ/N\ZZ)$$, as plain 2-tuples.

EXAMPLES:

sage: from sage.modular.modsym.p1list import p1list
sage: list(p1list(7))
[(0, 1), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6)]
sage: N = 23456
sage: len(p1list(N)) == N*prod([1+1/p for p,e in N.factor()])
True

>>> from sage.all import *
>>> from sage.modular.modsym.p1list import p1list
>>> list(p1list(Integer(7)))
[(0, 1), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6)]
>>> N = Integer(23456)
>>> len(p1list(N)) == N*prod([Integer(1)+Integer(1)/p for p,e in N.factor()])
True

sage.modular.modsym.p1list.p1list_int(N)[source]#

Return a list of the normalized elements of $$\mathbb{P}^1(\ZZ/N\ZZ)$$.

INPUT:

• N – integer (the level or modulus).

EXAMPLES:

sage: from sage.modular.modsym.p1list import p1list_int
sage: p1list_int(6)
[(0, 1),
(1, 0),
(1, 1),
(1, 2),
(1, 3),
(1, 4),
(1, 5),
(2, 1),
(2, 3),
(2, 5),
(3, 1),
(3, 2)]

>>> from sage.all import *
>>> from sage.modular.modsym.p1list import p1list_int
>>> p1list_int(Integer(6))
[(0, 1),
(1, 0),
(1, 1),
(1, 2),
(1, 3),
(1, 4),
(1, 5),
(2, 1),
(2, 3),
(2, 5),
(3, 1),
(3, 2)]

sage: p1list_int(120)
[(0, 1),
(1, 0),
(1, 1),
(1, 2),
(1, 3),
...
(30, 7),
(40, 1),
(40, 3),
(40, 11),
(60, 1)]

>>> from sage.all import *
>>> p1list_int(Integer(120))
[(0, 1),
(1, 0),
(1, 1),
(1, 2),
(1, 3),
...
(30, 7),
(40, 1),
(40, 3),
(40, 11),
(60, 1)]

sage.modular.modsym.p1list.p1list_llong(N)[source]#

Return a list of the normalized elements of $$\mathbb{P}^1(\ZZ/N\ZZ)$$, as a plain list of 2-tuples.

INPUT:

• N – integer (the level or modulus).

EXAMPLES:

sage: from sage.modular.modsym.p1list import p1list_llong
sage: N = 50000
sage: L = p1list_llong(50000)
sage: len(L) == N*prod([1+1/p for p,e in N.factor()])
True
sage: L[0]
(0, 1)
sage: L[len(L)-1]
(25000, 1)

>>> from sage.all import *
>>> from sage.modular.modsym.p1list import p1list_llong
>>> N = Integer(50000)
>>> L = p1list_llong(Integer(50000))
>>> len(L) == N*prod([Integer(1)+Integer(1)/p for p,e in N.factor()])
True
>>> L[Integer(0)]
(0, 1)
>>> L[len(L)-Integer(1)]
(25000, 1)