Coverage for local/lib/python2.7/site-packages/sage/modular/arithgroup/congroup

([(0, 13, 0), (1, 1, 1), (2, 1, 1), (3, 1, 1), (4, 1, 1), (5, 1, 1), (6, 1, 1), (6, 1, 12), (5, 1, 12), (4, 1, 12), (3, 1, 12), (2, 1, 12), (1, 1, 12)], {1: [1], 13: [1, 12]})

"""

return (self._coset_reduction_data_first_coord(),

self._coset_reduction_data_second_coord())

def _reduce_coset(self, uu, vv):

r"""

Compute a canonical form for a given Manin symbol.

INPUT:

Two integers (uu,vv) that define an element of `(Z/NZ)^2`.

- uu -- an integer

- vv -- an integer

OUTPUT:

pair of integers that are equivalent to (uu,vv).

.. NOTE::

We do *not* require that gcd(uu,vv,N) = 1. If the gcd is

not 1, we return (0,0).

EXAMPLES:

An example at level 9::

sage: G = GammaH(9,[4]); G

Congruence Subgroup Gamma_H(9) with H generated by [4]

sage: a = []

sage: for i in range(G.level()):

....: for j in range(G.level()):

....: a.append(G._reduce_coset(i,j))

sage: v = list(set(a))

sage: v.sort()

sage: v

[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (3, 1), (3, 2), (6, 1), (6, 2)]

An example at level 100::

sage: G = GammaH(100,[3,7]); G

Congruence Subgroup Gamma_H(100) with H generated by [3, 7]

sage: a = []

sage: for i in range(G.level()):

....: for j in range(G.level()):

....: a.append(G._reduce_coset(i,j))

sage: v = list(set(a))

sage: v.sort()

sage: len(v)

361

This demonstrates the problem underlying :trac:`1220`::

sage: G = GammaH(99, [67])

sage: G._reduce_coset(11,-3)

(11, 96)

sage: G._reduce_coset(77, -3)

(11, 96)

"""

N = int(self.level())

u = uu % N

v = vv % N

first, second = self._coset_reduction_data()

if gcd(first[u][1], first[v][1]) != 1:

return (0,0)

if not u:

return (0, first[v][0])

if not v:

return (first[u][0], 0)

new_u = first[u][0]

d = first[u][1]

new_v = (first[u][2] * v) % N

H_ls = second[d]

if len(H_ls) > 1:

new_v = min([ (new_v * h)%N for h in H_ls ])

return (new_u, new_v)

def reduce_cusp(self, c):

r"""

Compute a minimal representative for the given cusp c. Returns

a cusp c' which is equivalent to the given cusp, and is in

lowest terms with minimal positive denominator, and minimal

positive numerator for that denominator.

Two cusps `u_1/v_1` and `u_2/v_2` are equivalent modulo `\Gamma_H(N)`

if and only if

.. MATH::

v_1 = h v_2 \bmod N\quad \text{and}\quad u_1 = h^{-1} u_2 \bmod {\rm gcd}(v_1,N)

.. MATH::

v_1 = -h v_2 \bmod N\quad \text{and}\quad u_1 = -h^{-1} u_2 \bmod {\rm gcd}(v_1,N)

for some `h \in H`.

EXAMPLES::

sage: GammaH(6,[5]).reduce_cusp(5/3)

1/3

sage: GammaH(12,[5]).reduce_cusp(Cusp(8,9))

1/3

sage: GammaH(12,[5]).reduce_cusp(5/12)

Infinity

sage: GammaH(12,[]).reduce_cusp(Cusp(5,12))

5/12

sage: GammaH(21,[5]).reduce_cusp(Cusp(-9/14))

1/7

sage: Gamma1(5).reduce_cusp(oo)

Infinity

sage: Gamma1(5).reduce_cusp(0)

"""

return self._reduce_cusp(c)[0]

def _reduce_cusp(self, c):

r"""

Compute a minimal representative for the given cusp c.

Returns a pair (c', t), where c' is the minimal representative

for the given cusp, and t is either 1 or -1, as explained

below. Largely for internal use.

The minimal representative for a cusp is the element in `P^1(Q)`

in lowest terms with minimal positive denominator, and minimal

positive numerator for that denominator.

Two cusps `u1/v1` and `u2/v2` are equivalent modulo `\Gamma_H(N)`

if and only if

- `v1 = h*v2 (mod N)` and `u1 = h^(-1)*u2 (mod gcd(v1,N))`

- `v1 = -h*v2 (mod N)` and `u1 = -h^(-1)*u2 (mod gcd(v1,N))`

for some `h \in H`. Then t is 1 or -1 as c and c' fall into

the first or second case, respectively.

EXAMPLES::

sage: GammaH(6,[5])._reduce_cusp(Cusp(5,3))

(1/3, -1)

sage: GammaH(12,[5])._reduce_cusp(Cusp(8,9))

(1/3, -1)

sage: GammaH(12,[5])._reduce_cusp(Cusp(5,12))

(Infinity, 1)

sage: GammaH(12,[])._reduce_cusp(Cusp(5,12))

(5/12, 1)

sage: GammaH(21,[5])._reduce_cusp(Cusp(-9/14))

(1/7, 1)

"""

c = Cusp(c)

N = int(self.level())

Cusps = c.parent()

v = int(c.denominator() % N)

H = self._list_of_elements_in_H()

# First, if N | v, take care of this case. If u is in \pm H,

# then we return Infinity. If not, let u_0 be the minimum

# of \{ h*u | h \in \pm H \}. Then return u_0/N.

if not v:

u = c.numerator() % N

if u in H:

return Cusps((1,0)), 1

if (N-u) in H:

return Cusps((1,0)), -1

ls = [ (u*h)%N for h in H ]

m1 = min(ls)

m2 = N-max(ls)

if m1 < m2:

return Cusps((m1,N)), 1

else:

return Cusps((m2,N)), -1

u = int(c.numerator() % v)

gcd = get_gcd(N)

d = gcd(v,N)

# If (N,v) == 1, let v_0 be the minimal element

# in \{ v * h | h \in \pm H \}. Then we either return

# Infinity or 1/v_0, as v is or is not in \pm H,

# respectively.

if d == 1:

if v in H:

return Cusps((0,1)), 1

if (N-v) in H:

return Cusps((0,1)), -1

ls = [ (v*h)%N for h in H ]

m1 = min(ls)

m2 = N-max(ls)

if m1 < m2:

return Cusps((1,m1)), 1

else:

return Cusps((1,m2)), -1

val_min = v

inv_mod = get_inverse_mod(N)

# Now we're in the case (N,v) > 1. So we have to do several

# steps: first, compute v_0 as above. While computing this

# minimum, keep track of *all* pairs of (h,s) which give this

# value of v_0.

hs_ls = [(1,1)]

for h in H:

tmp = (v*h)%N

if tmp < val_min:

val_min = tmp

hs_ls = [(inv_mod(h,N), 1)]

elif tmp == val_min:

hs_ls.append((inv_mod(h,N), 1))

if (N-tmp) < val_min:

val_min = N - tmp

hs_ls = [(inv_mod(h,N), -1)]

elif (N-tmp) == val_min:

hs_ls.append((inv_mod(h,N), -1))

# Finally, we find our minimal numerator. Let u_1 be the

# minimum of s*h^-1*u mod d as (h,s) ranges over the elements

# of hs_ls. We must find the smallest integer u_0 which is

# smaller than v_0, congruent to u_1 mod d, and coprime to

# v_0. Then u_0/v_0 is our minimal representative.

u_min = val_min

sign = None

for h_inv,s in hs_ls:

tmp = (h_inv * s * u)%d

while gcd(tmp, val_min) > 1 and tmp < u_min:

tmp += d

if tmp < u_min:

u_min = tmp

sign = s

return Cusps((u_min, val_min)), sign

def _find_cusps(self):

r"""

Return an ordered list of inequivalent cusps for self, i.e. a

set of representatives for the orbits of self on

`\mathbf{P}^1(\QQ)`. These are returned in a reduced

form; see self.reduce_cusp for the definition of reduced.

ALGORITHM:

Lemma 3.2 in Cremona's 1997 book shows that for the action

of Gamma1(N) on "signed projective space"

`\Q^2 / (\Q_{\geq 0}^+)`, we have `u_1/v_1 \sim u_2 / v_2`

if and only if `v_1 = v_2 \bmod N` and `u_1 = u_2 \bmod

gcd(v_1, N)`. It follows that every orbit has a

representative `u/v` with `v \le N` and `0 \le u \le

gcd(v, N)`. We iterate through all pairs `(u,v)`

satisfying this.

Having found a set containing at least one of every

equivalence class modulo Gamma1(N), we can be sure of

picking up every class modulo GammaH(N) since this

contains Gamma1(N); and the reduce_cusp call does the

checking to make sure we don't get any duplicates.

EXAMPLES::

sage: Gamma1(5)._find_cusps()

[0, 2/5, 1/2, Infinity]

sage: Gamma1(35)._find_cusps()

[0, 2/35, 1/17, 1/16, 1/15, 1/14, 1/13, 1/12, 3/35, 1/11, 1/10, 1/9, 4/35, 1/8, 2/15, 1/7, 1/6, 6/35, 1/5, 3/14, 8/35, 1/4, 9/35, 4/15, 2/7, 3/10, 11/35, 1/3, 12/35, 5/14, 13/35, 2/5, 3/7, 16/35, 17/35, 1/2, 8/15, 4/7, 3/5, 9/14, 7/10, 5/7, 11/14, 4/5, 6/7, 9/10, 13/14, Infinity]

sage: Gamma1(24)._find_cusps() == Gamma1(24).cusps(algorithm='modsym')

True

sage: GammaH(24, [13,17])._find_cusps() == GammaH(24,[13,17]).cusps(algorithm='modsym')

True

"""

s = []

hashes = []

N = self.level()

for d in range(1, 1+N):

w = N.gcd(d)

M = int(w) if w > 1 else 2

for a in range(1,M):

if gcd(a, w) != 1:

continue

while gcd(a, d) != 1:

a += w

c = self.reduce_cusp(Cusp(a,d))

h = hash(c)

if not h in hashes:

hashes.append(h)

s.append(c)

return sorted(s)

def _contains_sl2(self, a,b,c,d):

r"""

Test whether [a,b,c,d] is an element of this subgroup.

EXAMPLES::

sage: G = GammaH(10, [3])

sage: [1, 0, -10, 1] in G

True

sage: matrix(ZZ, 2, [7, 1, 20, 3]) in G

True

sage: SL2Z.0 in G

False

sage: GammaH(10, [9])([7, 1, 20, 3]) # indirect doctest

Traceback (most recent call last):

...

TypeError: matrix [ 7 1]

[20 3] is not an element of Congruence Subgroup Gamma_H(10) with H generated by [9]

"""

N = self.level()

return ( (c%N == 0) and (d%N in self._list_of_elements_in_H()))

def gamma0_coset_reps(self):

r"""

Return a set of coset representatives for self \\ Gamma0(N), where N is

the level of self.

EXAMPLES::

sage: GammaH(108, [1,-1]).gamma0_coset_reps()

[

[1 0] [-43 -45] [ 31 33] [-49 -54] [ 25 28] [-19 -22]

[0 1], [108 113], [108 115], [108 119], [108 121], [108 125],

[-17 -20] [ 47 57] [ 13 16] [ 41 52] [ 7 9] [-37 -49]

[108 127], [108 131], [108 133], [108 137], [108 139], [108 143],

[-35 -47] [ 29 40] [ -5 -7] [ 23 33] [-11 -16] [ 53 79]

[108 145], [108 149], [108 151], [108 155], [108 157], [108 161]

]

"""

from .all import SL2Z

N = self.level()

return [SL2Z(lift_to_sl2z(0, d.lift(), N)) for d in _GammaH_coset_helper(N, self._list_of_elements_in_H())]

def coset_reps(self):

r"""

Return a set of coset representatives for self \\ SL2Z.

EXAMPLES::

sage: list(Gamma1(3).coset_reps())

[

[1 0] [-1 -2] [ 0 -1] [-2 1] [1 0] [-3 -2] [ 0 -1] [-2 -3]

[0 1], [ 3 5], [ 1 0], [ 5 -3], [1 1], [ 8 5], [ 1 2], [ 5 7]

]

sage: len(list(Gamma1(31).coset_reps())) == 31**2 - 1

True

"""

from .all import Gamma0, SL2Z

reps1 = Gamma0(self.level()).coset_reps()

for r in reps1:

reps2 = self.gamma0_coset_reps()

for t in reps2:

yield SL2Z(t)*r

def is_subgroup(self, other):

r"""

Return True if self is a subgroup of right, and False

otherwise.

EXAMPLES::

sage: GammaH(24,[7]).is_subgroup(SL2Z)

True

sage: GammaH(24,[7]).is_subgroup(Gamma0(8))

True

sage: GammaH(24, []).is_subgroup(GammaH(24, [7]))

True

sage: GammaH(24, []).is_subgroup(Gamma1(24))

True

sage: GammaH(24, [17]).is_subgroup(GammaH(24, [7]))

False

sage: GammaH(1371, [169]).is_subgroup(GammaH(457, [169]))

True

"""

from .all import is_Gamma0, is_Gamma1

if not isinstance(other, GammaH_class):

raise NotImplementedError

# level of self should divide level of other

if self.level() % other.level():

return False

# easy cases

if is_Gamma0(other):

return True # recall self is a GammaH, so it's contained in Gamma0

if is_Gamma1(other) and len(self._generators_for_H()) > 0:

return False

else:

# difficult case

t = other._list_of_elements_in_H()

for x in self._generators_for_H():

if not (x in t):

return False

return True

def index(self):

r"""

Return the index of self in SL2Z.

EXAMPLES::

sage: [G.index() for G in Gamma0(40).gamma_h_subgroups()]

[72, 144, 144, 144, 144, 288, 288, 288, 288, 144, 288, 288, 576, 576, 144, 288, 288, 576, 576, 144, 288, 288, 576, 576, 288, 576, 1152]

"""

from .all import Gamma1

return Gamma1(self.level()).index() / len(self._list_of_elements_in_H())

def nu2(self):

r"""

Return the number of orbits of elliptic points of order 2 for this

group.

EXAMPLES::

sage: [H.nu2() for n in [1..10] for H in Gamma0(n).gamma_h_subgroups()]

[1, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0]

sage: GammaH(33,[2]).nu2()

sage: GammaH(5,[2]).nu2()

AUTHORS:

- Jordi Quer

"""

N = self.level()

H = self._list_of_elements_in_H()

if N % 4 == 0: return ZZ(0)

for p, r in N.factor():

if p % 4 == 3: return ZZ(0)

return (euler_phi(N) // len(H))*len([x for x in H if (x**2 + 1) % N == 0])

def nu3(self):

r"""

Return the number of orbits of elliptic points of order 3 for this

group.

EXAMPLES::

sage: [H.nu3() for n in [1..10] for H in Gamma0(n).gamma_h_subgroups()]

[1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

sage: GammaH(33,[2]).nu3()

sage: GammaH(7,[2]).nu3()

AUTHORS:

- Jordi Quer

"""

N = self.level()

H = self._list_of_elements_in_H()

if N % 9 == 0: return ZZ(0)

for p, r in N.factor():

if p % 3 == 2: return ZZ(0)

lenHpm = len(H)

if N - ZZ(1) not in H: lenHpm*=2

return (euler_phi(N)//lenHpm)*len([x for x in H if (x**2+x+1) % N == 0])

def ncusps(self):

r"""

Return the number of orbits of cusps (regular or otherwise) for this subgroup.

EXAMPLES::

sage: GammaH(33,[2]).ncusps()

sage: GammaH(32079, [21676]).ncusps()

28800

AUTHORS:

- Jordi Quer

"""

N = self.level()

H = self._list_of_elements_in_H()

c = ZZ(0)

for d in [d for d in N.divisors() if d**2 <= N]:

Nd = lcm(d,N//d)

Hd = set([x % Nd for x in H])

lenHd = len(Hd)

if Nd-1 not in Hd: lenHd *= 2

summand = euler_phi(d)*euler_phi(N//d)//lenHd

if d**2 == N:

c = c + summand

else:

c = c + 2*summand

return c

def nregcusps(self):

r"""

Return the number of orbits of regular cusps for this subgroup. A cusp is regular

if we may find a parabolic element generating the stabiliser of that

cusp whose eigenvalues are both +1 rather than -1. If G contains -1,

all cusps are regular.

EXAMPLES::

sage: GammaH(20, [17]).nregcusps()

sage: GammaH(20, [17]).nirregcusps()

sage: GammaH(3212, [2045, 2773]).nregcusps()

1440

sage: GammaH(3212, [2045, 2773]).nirregcusps()

720

AUTHOR:

- Jordi Quer

"""

if self.is_even():

return self.ncusps()

N = self.level()

H = self._list_of_elements_in_H()

c = ZZ(0)

for d in [d for d in divisors(N) if d**2 <= N]:

Nd = lcm(d,N//d)

Hd = set([x%Nd for x in H])

if Nd - 1 not in Hd:

summand = euler_phi(d)*euler_phi(N//d)//(2*len(Hd))

if d**2==N:

c = c + summand

else:

c = c + 2*summand

return c

def nirregcusps(self):

r"""

Return the number of irregular cusps for this subgroup.

EXAMPLES::

sage: GammaH(3212, [2045, 2773]).nirregcusps()

720

"""

return self.ncusps() - self.nregcusps()

def dimension_new_cusp_forms(self, k=2, p=0):

r"""

Return the dimension of the space of new (or `p`-new)

weight `k` cusp forms for this congruence subgroup.

INPUT:

- ``k`` - an integer (default: 2), the weight. Not fully implemented for k = 1.

- ``p`` - integer (default: 0); if nonzero, compute the `p`-new subspace.

OUTPUT: Integer

EXAMPLES::

sage: GammaH(33,[2]).dimension_new_cusp_forms()

sage: Gamma1(4*25).dimension_new_cusp_forms(2, p=5)

225

sage: Gamma1(33).dimension_new_cusp_forms(2)

sage: Gamma1(33).dimension_new_cusp_forms(2,p=11)

"""

N = self.level()

if p==0 or N % p != 0:

return sum([H.dimension_cusp_forms(k) * mumu(N // H.level()) \

for H in self.divisor_subgroups()])

else:

return self.dimension_cusp_forms(k) - \

2*self.restrict(N//p).dimension_new_cusp_forms(k)

def image_mod_n(self):

r"""

Return the image of this group in `SL(2, \ZZ / N\ZZ)`.

EXAMPLES::

sage: Gamma0(3).image_mod_n()

Matrix group over Ring of integers modulo 3 with 2 generators (

[2 0] [1 1]

[0 2], [0 1]

)

TESTS::

sage: for n in [2..20]:

....: for g in Gamma0(n).gamma_h_subgroups():

....: G = g.image_mod_n()

....: assert G.order() == Gamma(n).index() / g.index()

"""

N = self.level()

if N == 1:

raise NotImplementedError("Matrix groups over ring of integers modulo 1 not implemented")

gens = [matrix(Zmod(N), 2, 2, [x, 0, 0, Zmod(N)(1)/x]) for x in self._generators_for_H()]

gens += [matrix(Zmod(N),2,[1,1,0,1])]

return MatrixGroup(gens)

def _list_subgroup(N, gens):

r"""

Given an integer ``N`` and a list of integers ``gens``, return a list of

the elements of the subgroup of `(\ZZ / N\ZZ)^\times` generated by the

elements of ``gens``.

EXAMPLES::

sage: sage.modular.arithgroup.congroup_gammaH._list_subgroup(11, [3])

[1, 3, 4, 5, 9]

"""

H = set([1])

N = int(N)

for g in gens:

if gcd(g, N) != 1:

raise ValueError("gen (=%s) is not in (Z/%sZ)^*"%(g,N))

gk = int(g) % N

sbgrp = [gk]

while not (gk in H):

gk = (gk * g)%N

sbgrp.append(gk)

H = set([(x*h)%N for x in sbgrp for h in H])

H = sorted(H)

return H

def _GammaH_coset_helper(N, H):

r"""

Return a list of coset representatives for H in (Z / NZ)^*.

EXAMPLES::

sage: from sage.modular.arithgroup.congroup_gammaH import _GammaH_coset_helper

sage: _GammaH_coset_helper(108, [1, 107])

[1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53]

"""

t = [Zmod(N)(1)]

W = [Zmod(N)(h) for h in H]

HH = [Zmod(N)(h) for h in H]

k = euler_phi(N)

for i in range(1, N):

if gcd(i, N) != 1: continue

if not i in W:

t.append(t[0]*i)

W = W + [i*h for h in HH]

if len(W) == k: break

return t

def mumu(N):

"""

Return 0 if any cube divides `N`. Otherwise return

`(-2)^v` where `v` is the number of primes that

exactly divide `N`.

This is similar to the Möbius function.

INPUT:

- ``N`` - an integer at least 1

OUTPUT: Integer

EXAMPLES::

sage: from sage.modular.arithgroup.congroup_gammaH import mumu

sage: mumu(27)

sage: mumu(6*25)

sage: mumu(7*9*25)

-2

sage: mumu(9*25)

"""

if N < 1:

raise ValueError("N must be at least 1")

p = 1

for _,r in factor(N):

if r > 2:

return ZZ(0)

elif r == 1:

p *= -2

return ZZ(p)

Coverage for local/lib/python2.7/site-packages/sage/modular/arithgroup/congroup_gammaH.py : 83%

370 statements 307 run 63 missing 0 excluded