Coverage for local/lib/python2.7/site-packages/sage/algebras/quatalg/quaternion

raise NotImplementedError("algorithm for computing local splittings not implemented in general (currently require the first invariant to be coprime to p)")

i2inv = 1/i2

a = None

for b in list(F):

if not b: continue

c = j2 + i2inv * b*b

if c.is_square():

a = -c.sqrt()

break

if a is None:

# do a fallback search, maybe needed in char 3 sometimes.

for J in M:

K = I*J

if J*J == j2 and K == -J*I:

return I, J, K

J = M([a,b,(j2-a*a)/b, -a])

K = I*J

assert K == -J*I, "bug in that I,J don't skew commute"

return I, J, K

def modp_splitting_map(self, p):

r"""

Return Python map from the (`p`-integral) quaternion algebra to

the set of `2\times 2` matrices over `\GF{p}`.

INPUT:

- `p` -- prime number

EXAMPLES::

sage: Q.<i,j,k> = QuaternionAlgebra(-1, -7)

sage: f = Q.modp_splitting_map(13)

sage: a = 2+i-j+3*k; b = 7+2*i-4*j+k

sage: f(a*b)

[12 3]

[10 5]

sage: f(a)*f(b)

[12 3]

[10 5]

"""

I, J, K = self.modp_splitting_data(p)

F = I.base_ring()

def phi(q):

v = [F(a) for a in q.coefficient_tuple()]

return v[0] + I*v[1] + J*v[2] + K*v[3]

return phi

############################################################

# Unpickling

############################################################

def unpickle_QuaternionAlgebra_v0(*key):

"""

The 0th version of pickling for quaternion algebras.

EXAMPLES::

sage: Q = QuaternionAlgebra(-5,-19)

sage: t = (QQ, -5, -19, ('i', 'j', 'k'))

sage: sage.algebras.quatalg.quaternion_algebra.unpickle_QuaternionAlgebra_v0(*t)

Quaternion Algebra (-5, -19) with base ring Rational Field

sage: loads(dumps(Q)) == Q

True

sage: loads(dumps(Q)) is Q

True

"""

return QuaternionAlgebra(*key)

class QuaternionOrder(Algebra):

"""

An order in a quaternion algebra.

EXAMPLES::

sage: QuaternionAlgebra(-1,-7).maximal_order()

Order of Quaternion Algebra (-1, -7) with base ring Rational Field with basis (1/2 + 1/2*j, 1/2*i + 1/2*k, j, k)

sage: type(QuaternionAlgebra(-1,-7).maximal_order())

"""

def __init__(self, A, basis, check=True):

"""

INPUT:

- ``A`` - a quaternion algebra

- ``basis`` - list of 4 integral quaternions in ``A``

- ``check`` - whether to do type and other consistency checks

.. WARNING::

Currently most methods silently assume that the ``A.base_ring()``

is ``QQ``.

EXAMPLES::

sage: A.<i,j,k> = QuaternionAlgebra(-3,-5)

sage: sage.algebras.quatalg.quaternion_algebra.QuaternionOrder(A, [1,i,j,k])

Order of Quaternion Algebra (-3, -5) with base ring Rational Field with basis (1, i, j, k)

sage: R = sage.algebras.quatalg.quaternion_algebra.QuaternionOrder(A, [1,2*i,2*j,2*k]); R

Order of Quaternion Algebra (-3, -5) with base ring Rational Field with basis (1, 2*i, 2*j, 2*k)

sage: type(R)

Over QQ and number fields it is checked whether the given

basis actually gives a an order (as a module over the maximal order):

sage: A.<i,j,k> = QuaternionAlgebra(-1,-1)

sage: A.quaternion_order([1,i,j,i-j])

Traceback (most recent call last):

...

ValueError: basis must have rank 4

sage: A.quaternion_order([2,i,j,k])

Traceback (most recent call last):

...

ValueError: lattice must contain 1

sage: A.quaternion_order([1,i/2,j/2,k/2])

Traceback (most recent call last):

...

ValueError: given lattice must be a ring

sage: K = QuadraticField(10)

sage: A.<i,j,k> = QuaternionAlgebra(K,-1,-1)

sage: A.quaternion_order([1,i,j,k])

Order of Quaternion Algebra (-1, -1) with base ring Number Field in a with defining polynomial x^2 - 10 with basis (1, i, j, k)

sage: A.quaternion_order([1,i/2,j,k])

Traceback (most recent call last):

...

ValueError: given lattice must be a ring

TESTS::

sage: TestSuite(R).run()

"""

if check:

# right data type

if not isinstance(basis, (list, tuple)):

raise TypeError("basis must be a list or tuple")

# right length

if len(basis) != 4:

raise ValueError("basis must have length 4")

# coerce to common parent

basis = tuple([A(x) for x in basis])

# has rank 4

V = A.base_ring()**4

if V.span([ V(x.coefficient_tuple()) for x in basis]).dimension() != 4:

raise ValueError("basis must have rank 4")

# The additional checks will work over QQ and over number fields,

# but we can't actually do much with an order defined over a number

# field

if A.base_ring() == QQ: # fast code over QQ

M = matrix(QQ, 4, 4, [ x.coefficient_tuple() for x in basis])

v = M.solve_left(V([1,0,0,0]))

if v.denominator() != 1:

raise ValueError("lattice must contain 1")

# check if multiplicatively closed

M1 = basis_for_quaternion_lattice(basis)

M2 = basis_for_quaternion_lattice(list(basis) + [ x*y for x in basis for y in basis])

if M1 != M2:

raise ValueError("given lattice must be a ring")

if A.base_ring() != QQ: # slow code over number fields (should eventually use PARI's nfhnf)

O = None

try:

O = A.base_ring().maximal_order()

except AttributeError:

pass

if O:

M = matrix(A.base_ring(), 4, 4, [ x.coefficient_tuple() for x in basis])

v = M.solve_left(V([1,0,0,0]))

if any([ not a in O for a in v]):

raise ValueError("lattice must contain 1")

# check if multiplicatively closed

Y = matrix(QQ, 16, 4, [ (x*y).coefficient_tuple() for x in basis for y in basis])

X = M.solve_left(Y)

if any([ not a in O for x in X for a in x ]):

raise ValueError("given lattice must be a ring")

self.__basis = basis

self.__quaternion_algebra = A

Parent.__init__(self, base=ZZ, facade=(A,), category=Algebras(ZZ))

def gens(self):

"""

Return generators for self.

EXAMPLES::

sage: QuaternionAlgebra(-1,-7).maximal_order().gens()

(1/2 + 1/2*j, 1/2*i + 1/2*k, j, k)

"""

return self.__basis

def ngens(self):

"""

Return the number of generators (which is 4).

EXAMPLES::

sage: QuaternionAlgebra(-1,-7).maximal_order().ngens()

"""

return 4

def gen(self, n):

"""

Return the n-th generator.

INPUT:

- ``n`` - an integer between 0 and 3, inclusive.

EXAMPLES::

sage: R = QuaternionAlgebra(-11,-1).maximal_order(); R

Order of Quaternion Algebra (-11, -1) with base ring Rational Field with basis (1/2 + 1/2*i, 1/2*j - 1/2*k, i, -k)

sage: R.gen(0)

1/2 + 1/2*i

sage: R.gen(1)

1/2*j - 1/2*k

sage: R.gen(2)

sage: R.gen(3)

-k

"""

return self.__basis[n]

def __eq__(self, R):

"""

Compare orders self and other. Two orders are equal if they

have the same basis and are in the same quaternion algebra.

EXAMPLES::

sage: R = QuaternionAlgebra(-11,-1).maximal_order()

sage: R == R # indirect doctest

True

sage: R == QuaternionAlgebra(-1,-1).maximal_order()

False

sage: R == 5

False

"""

if not isinstance(R, QuaternionOrder):

return False

return (self.__quaternion_algebra == R.__quaternion_algebra and

self.__basis == R.__basis)

def __ne__(self, other):

"""

Compare orders self and other. Two orders are equal if they

have the same basis and are in the same quaternion algebra.

EXAMPLES::

sage: R = QuaternionAlgebra(-11,-1).maximal_order()

sage: R != R # indirect doctest

False

sage: R != QuaternionAlgebra(-1,-1).maximal_order()

True

"""

return not self.__eq__(other)

def basis(self):

"""

Return fix choice of basis for this quaternion order.

EXAMPLES::

sage: QuaternionAlgebra(-11,-1).maximal_order().basis()

(1/2 + 1/2*i, 1/2*j - 1/2*k, i, -k)

"""

return self.__basis

def quaternion_algebra(self):

"""

Return ambient quaternion algebra that contains this quaternion order.

EXAMPLES::

sage: QuaternionAlgebra(-11,-1).maximal_order().quaternion_algebra()

Quaternion Algebra (-11, -1) with base ring Rational Field

"""

return self.__quaternion_algebra

def _repr_(self):

"""

Return string representation of this order.

EXAMPLES::

sage: QuaternionAlgebra(-11,-1).maximal_order()._repr_()

'Order of Quaternion Algebra (-11, -1) with base ring Rational Field with basis (1/2 + 1/2*i, 1/2*j - 1/2*k, i, -k)'

sage: QuaternionAlgebra(-11,-1).maximal_order()

Order of Quaternion Algebra (-11, -1) with base ring Rational Field with basis (1/2 + 1/2*i, 1/2*j - 1/2*k, i, -k)

"""

return 'Order of %s with basis %s'%(self.quaternion_algebra(), self.basis())

def random_element(self, *args, **kwds):

"""

Return a random element of this order.

The args and kwds are passed to the random_element method of

the integer ring, and we return an element of the form

.. MATH::

ae_1 + be_2 + ce_3 + de_4

where `e_1`, ..., `e_4` are the basis of this order and `a`,

`b`, `c`, `d` are random integers.

EXAMPLES::

sage: QuaternionAlgebra(-11,-1).maximal_order().random_element()

-4 - 4*i + j - k

sage: QuaternionAlgebra(-11,-1).maximal_order().random_element(-10,10)

-9/2 - 7/2*i - 7/2*j - 3/2*k

"""

return sum( (ZZ.random_element(*args, **kwds) * b for b in self.basis()) )

def intersection(self, other):

"""

Return the intersection of this order with other.

INPUT:

- ``other`` - a quaternion order in the same ambient quaternion algebra

OUTPUT: a quaternion order

EXAMPLES::

sage: R = QuaternionAlgebra(-11,-1).maximal_order()

sage: R.intersection(R)

Order of Quaternion Algebra (-11, -1) with base ring Rational Field with basis (1/2 + 1/2*i, i, 1/2*j + 1/2*k, k)

We intersect various orders in the quaternion algebra ramified at 11::

sage: B = BrandtModule(11,3)

sage: R = B.maximal_order(); S = B.order_of_level_N()

sage: R.intersection(S)

Order of Quaternion Algebra (-1, -11) with base ring Rational Field with basis (1/2 + 1/2*j, 1/2*i + 5/2*k, j, 3*k)

sage: R.intersection(S) == S

True

sage: B = BrandtModule(11,5)

sage: T = B.order_of_level_N()

sage: S.intersection(T)

Order of Quaternion Algebra (-1, -11) with base ring Rational Field with basis (1/2 + 1/2*j, 1/2*i + 23/2*k, j, 15*k)

"""

if not isinstance(other, QuaternionOrder):

raise TypeError("other must be a QuaternionOrder")

A = self.quaternion_algebra()

if other.quaternion_algebra() != A:

raise ValueError("self and other must be in the same ambient quaternion algebra")

V = A.base_ring()**4

B = V.span([V(list(g)) for g in self.basis()], ZZ)

C = V.span([V(list(g)) for g in other.basis()], ZZ)

# todo -- A(list(e)) could be A(e)

return QuaternionOrder(A, [A(list(e)) for e in B.intersection(C).basis()])

def free_module(self):

r"""

Return the free `\ZZ`-module that corresponds to this order

inside the vector space corresponding to the ambient

quaternion algebra.

OUTPUT:

A free `\ZZ`-module of rank 4.

EXAMPLES::

sage: R = QuaternionAlgebra(-11,-1).maximal_order()

sage: R.basis()

(1/2 + 1/2*i, 1/2*j - 1/2*k, i, -k)

sage: R.free_module()

Free module of degree 4 and rank 4 over Integer Ring

Echelon basis matrix:

[1/2 1/2 0 0]

[ 0 1 0 0]

[ 0 0 1/2 1/2]

[ 0 0 0 1]

"""

try: return self.__free_module

except AttributeError: pass

V = self.quaternion_algebra().base_ring()**4

M = V.span([V(list(g)) for g in self.basis()], ZZ)

self.__free_module = M

return M

def discriminant(self):

r"""

Return the discriminant of this order, which we define as

`\sqrt{ det ( Tr(e_i \bar{e}_j ) ) }`, where `\{e_i\}` is the

basis of the order.

OUTPUT: rational number

EXAMPLES::

sage: QuaternionAlgebra(-11,-1).maximal_order().discriminant()

sage: S = BrandtModule(11,5).order_of_level_N()

sage: S.discriminant()

sage: type(S.discriminant())

<... 'sage.rings.rational.Rational'>

"""

L = []

for d in self.basis():

MM = []

for e in self.basis():

MM.append( (d * e.conjugate()).reduced_trace() )

L.append(MM)

return (MatrixSpace(QQ, 4, 4)(L)).determinant().sqrt()

def left_ideal(self, gens, check=True):

r"""

Return the ideal with given gens over `\ZZ`.

INPUT:

- ``gens`` -- a list of elements of this quaternion order

- ``check`` -- bool (default: ``True``); if ``False``, then ``gens`` must

4-tuple that forms a Hermite basis for an ideal

EXAMPLES::

sage: R = QuaternionAlgebra(-11,-1).maximal_order()

sage: R.left_ideal([2*a for a in R.basis()])

Fractional ideal (1 + i, 2*i, j + k, 2*k)

"""

if self.base_ring() == ZZ:

return QuaternionFractionalIdeal_rational(gens, left_order=self, check=check)

else:

raise NotImplementedError("ideal only implemented for quaternion algebras over QQ")

def right_ideal(self, gens, check=True):

r"""

Return the ideal with given gens over `\ZZ`.

INPUT:

- ``gens`` -- a list of elements of this quaternion order

- ``check`` -- bool (default: ``True``); if ``False``, then ``gens`` must

4-tuple that forms a Hermite basis for an ideal

EXAMPLES::

sage: R = QuaternionAlgebra(-11,-1).maximal_order()

sage: R.right_ideal([2*a for a in R.basis()])

Fractional ideal (1 + i, 2*i, j + k, 2*k)

"""

if self.base_ring() == ZZ:

return QuaternionFractionalIdeal_rational(gens, right_order=self, check=check)

else:

raise NotImplementedError("ideal only implemented for quaternion algebras over QQ")

def unit_ideal(self):

"""

Return the unit ideal in this quaternion order.

EXAMPLES::

sage: R = QuaternionAlgebra(-11,-1).maximal_order()

sage: I = R.unit_ideal(); I

Fractional ideal (1/2 + 1/2*i, 1/2*j - 1/2*k, i, -k)

"""

if self.base_ring() == ZZ:

return QuaternionFractionalIdeal_rational(self.basis(), left_order=self, right_order=self, check=False)

else:

raise NotImplementedError("ideal only implemented for quaternion algebras over QQ")

def quadratic_form(self):

"""

Return the normalized quadratic form associated to this quaternion order.

OUTPUT: quadratic form

EXAMPLES::

sage: R = BrandtModule(11,13).order_of_level_N()

sage: Q = R.quadratic_form(); Q

Quadratic form in 4 variables over Rational Field with coefficients:

[ 14 253 55 286 ]

[ * 1455 506 3289 ]

[ * * 55 572 ]

[ * * * 1859 ]

sage: Q.theta_series(10)

1 + 2*q + 2*q^4 + 4*q^6 + 4*q^8 + 2*q^9 + O(q^10)

"""

return self.unit_ideal().quadratic_form()

def ternary_quadratic_form(self, include_basis=False):

"""

Return the ternary quadratic form associated to this order.

INPUT:

- ``include_basis`` -- bool (default: False), if True also

return a basis for the dimension 3 subspace `G`

OUTPUT:

- QuadraticForm

- optional basis for dimension 3 subspace

This function computes the positive definition quadratic form

obtained by letting G be the trace zero subspace of `\ZZ` +

2* ``self``, which has rank 3, and restricting the pairing::

(x,y) = (x.conjugate()*y).reduced_trace()

to `G`.

APPLICATIONS: Ternary quadratic forms associated to an order

in a rational quaternion algebra are useful in computing with

Gross points, in decided whether quaternion orders have

embeddings from orders in quadratic imaginary fields, and in

computing elements of the Kohnen plus subspace of modular

forms of weight 3/2.

EXAMPLES::

sage: R = BrandtModule(11,13).order_of_level_N()

sage: Q = R.ternary_quadratic_form(); Q

Quadratic form in 3 variables over Rational Field with coefficients:

[ 5820 1012 13156 ]

[ * 55 1144 ]

[ * * 7436 ]

sage: factor(Q.disc())

2^4 * 11^2 * 13^2

The following theta series is a modular form of weight 3/2 and level 4*11*13::

sage: Q.theta_series(100)

1 + 2*q^23 + 2*q^55 + 2*q^56 + 2*q^75 + 4*q^92 + O(q^100)

"""

if self.base_ring() != ZZ:

raise NotImplementedError("ternary quadratic form of order only implemented for quaternion algebras over QQ")

Q = self.quaternion_algebra()

# 2*R + ZZ

twoR = self.free_module().scale(2)

A = twoR.ambient_module()

Z = twoR.span( [Q(1).coefficient_tuple()], ZZ)

S = twoR + Z

# Now we intersect with the trace 0 submodule

v = [b.reduced_trace() for b in Q.basis()]

M = matrix(QQ,4,1,v)

tr0 = M.kernel()

G = tr0.intersection(S)

B = [Q(a) for a in G.basis()]

m = matrix(QQ,[[x.pair(y) for x in B] for y in B])

from sage.quadratic_forms.quadratic_form import QuadraticForm

Q = QuadraticForm(m)

if include_basis:

return Q, B

else:

return Q

class QuaternionFractionalIdeal(Ideal_fractional):

def __hash__(self):

r"""

Stupid constant hash function!

TESTS::

sage: R = QuaternionAlgebra(-11,-1).maximal_order()

sage: hash(R.right_ideal(R.basis()))

"""

return 0

class QuaternionFractionalIdeal_rational(QuaternionFractionalIdeal):

"""

A fractional ideal in a rational quaternion algebra.

INPUT:

- ``left_order`` -- a quaternion order or ``None``

- ``right_order`` -- a quaternion order or ``None``

- ``basis`` -- tuple of length 4 of elements in of ambient

quaternion algebra whose `\\ZZ`-span is an ideal

- ``check`` -- bool (default: ``True``); if ``False``, do no type

checking, and the input basis *must* be in Hermite form.

"""

def __init__(self, basis, left_order=None, right_order=None, check=True):

"""

EXAMPLES::

sage: R = QuaternionAlgebra(-11,-1).maximal_order()

sage: R.right_ideal(R.basis())

Fractional ideal (1/2 + 1/2*i, i, 1/2*j + 1/2*k, k)

sage: R.right_ideal(tuple(R.basis()), check=False)

Fractional ideal (1/2 + 1/2*i, 1/2*j - 1/2*k, i, -k)

"""

if check:

if left_order is not None and not isinstance(left_order, QuaternionOrder):

raise TypeError("left_order must be a quaternion order or None")

if right_order is not None and not isinstance(right_order, QuaternionOrder):

raise TypeError("right_order must be a quaternion order or None")

if not isinstance(basis, (list, tuple)):

raise TypeError("basis must be a list or tuple")

self.__left_order = left_order

self.__right_order = right_order

if check:

try:

Q = self.quaternion_order().quaternion_algebra()

except RuntimeError:

Q = basis[0].parent()

basis = tuple([Q(v) for v in

(QQ**4).span([Q(v).coefficient_tuple() for v in basis], ZZ).basis()])

self.__basis = basis

def scale(self, alpha, left=False):

r"""

Scale the fractional ideal ``self`` by multiplying the basis

by ``alpha``.

INPUT:

- `\alpha` -- element of quaternion algebra

- ``left`` -- bool (default: False); if true multiply

`\alpha` on the left, otherwise multiply `\alpha` on the right

OUTPUT:

- a new fractional ideal

EXAMPLES::

sage: B = BrandtModule(5,37); I = B.right_ideals()[0]; i,j,k = B.quaternion_algebra().gens(); I

Fractional ideal (2 + 2*j + 106*k, i + 2*j + 105*k, 4*j + 64*k, 148*k)

sage: I.scale(i)

Fractional ideal [2*i + 212*j - 2*k, -2 + 210*j - 2*k, 128*j - 4*k, 296*j]

sage: I.scale(i, left=True)

Fractional ideal [2*i - 212*j + 2*k, -2 - 210*j + 2*k, -128*j + 4*k, -296*j]

sage: I.scale(i, left=False)

Fractional ideal [2*i + 212*j - 2*k, -2 + 210*j - 2*k, 128*j - 4*k, 296*j]

sage: i * I.gens()[0]

2*i - 212*j + 2*k

sage: I.gens()[0] * i

2*i + 212*j - 2*k

"""

Q = self.quaternion_algebra()

alpha = Q(alpha)

if left:

gens = [alpha*b for b in self.basis()]

else:

gens = [b*alpha for b in self.basis()]

return Q.ideal(gens, left_order = self.__left_order,

right_order = self.__right_order, check=False)

def quaternion_algebra(self):

"""

Return the ambient quaternion algebra that contains this fractional ideal.

OUTPUT: a quaternion algebra

EXAMPLES::

sage: I = BrandtModule(3,5).right_ideals()[1]; I

Fractional ideal (2 + 6*j + 4*k, 2*i + 4*j + 34*k, 8*j + 32*k, 40*k)

sage: I.quaternion_algebra()

Quaternion Algebra (-1, -3) with base ring Rational Field

"""

try: return self.__quaternion_algebra

except AttributeError: pass

A = self.__basis[0].parent()

self.__quaternion_algebra = A

return A

def _compute_order(self, side='left'):

r"""

Used internally to compute either the left or right order

associated to an ideal in a quaternion algebra. If

action='right', compute the left order, and if action='left'

compute the right order.

INPUT:

- ``side`` -- 'left' or 'right'

EXAMPLES::

sage: R.<i,j,k> = QuaternionAlgebra(-1,-11)

sage: I = R.ideal([2 + 2*j + 140*k, 2*i + 4*j + 150*k, 8*j + 104*k, 152*k])

sage: Ol = I._compute_order('left'); Ol

Order of Quaternion Algebra (-1, -11) with base ring Rational Field with basis (1/2 + 1/2*j + 35*k, 1/4*i + 1/2*j + 75/4*k, j + 32*k, 38*k)

sage: Or = I._compute_order('right'); Or

Order of Quaternion Algebra (-1, -11) with base ring Rational Field with basis (1/2 + 1/2*j + 16*k, 1/2*i + 11/2*k, j + 13*k, 19*k)

sage: Ol.discriminant()

209

sage: Or.discriminant()

209

sage: I.left_order() == Ol

True

sage: I.right_order() == Or

True

ALGORITHM: Let `b_1, b_2, b_3, b_3` be a basis for this

fractional ideal `I`, and assume we want to compute the left

order of `I` in the quaternion algebra `Q`. Then

multiplication by `b_i` on the right defines a map `B_i:Q \to

Q`. We have

.. MATH::

R = B_1^{-1}(I) \cap B_2^{-1}(I) \cap B_3^{-1}(I)\cap B_4^{-1}(I).

This is because

.. MATH::

B_n^{-1}(I) = \{\alpha \in Q : \alpha b_n \in I \},

and

.. MATH::

R = \{\alpha \in Q : \alpha b_n \in I, n=1,2,3,4\}.

"""

if side == 'left':

action = 'right'

elif side == 'right':

action = 'left'

else:

raise ValueError("side must be 'left' or 'right'")

Q = self.quaternion_algebra()

if Q.base_ring() != QQ:

raise NotImplementedError("computation of left and right orders only implemented over QQ")

M = [(~b).matrix(action=action) for b in self.basis()]

B = self.basis_matrix()

invs = [B*m for m in M]

# Now intersect the row spans of each matrix in invs

ISB = [Q(v) for v in intersection_of_row_modules_over_ZZ(invs).row_module(ZZ).basis()]

return Q.quaternion_order(ISB)

def left_order(self):

"""

Return the left order associated to this fractional ideal.

OUTPUT: an order in a quaternion algebra

EXAMPLES::

sage: B = BrandtModule(11)

sage: R = B.maximal_order()

sage: I = R.unit_ideal()

sage: I.left_order()

Order of Quaternion Algebra (-1, -11) with base ring Rational Field with basis (1/2 + 1/2*j, 1/2*i + 1/2*k, j, k)

We do a consistency check::

sage: B = BrandtModule(11,19); R = B.right_ideals()

sage: [r.left_order().discriminant() for r in R]

[209, 209, 209, 209, 209, 209, 209, 209, 209, 209, 209, 209, 209, 209, 209, 209, 209, 209]

"""

if self.__left_order is None:

self.__left_order = self._compute_order(side='left')

return self.__left_order

def right_order(self):

"""

Return the right order associated to this fractional ideal.

OUTPUT: an order in a quaternion algebra

EXAMPLES::

sage: I = BrandtModule(389).right_ideals()[1]; I

Fractional ideal (2 + 6*j + 2*k, i + 2*j + k, 8*j, 8*k)

sage: I.right_order()

Order of Quaternion Algebra (-2, -389) with base ring Rational Field with basis (1/2 + 1/2*j + 1/2*k, 1/4*i + 1/2*j + 1/4*k, j, k)

sage: I.left_order()

Order of Quaternion Algebra (-2, -389) with base ring Rational Field with basis (1/2 + 1/2*j + 3/2*k, 1/8*i + 1/4*j + 9/8*k, j + k, 2*k)

The following is a big consistency check. We take reps for

all the right ideal classes of a certain order, take the

corresponding left orders, then take ideals in the left orders

and from those compute the right order again::

sage: B = BrandtModule(11,19); R = B.right_ideals()

sage: O = [r.left_order() for r in R]

sage: J = [O[i].left_ideal(R[i].basis()) for i in range(len(R))]

sage: len(set(J))

sage: len(set([I.right_order() for I in J]))

sage: J[0].right_order() == B.order_of_level_N()

True

"""

if self.__right_order is None:

self.__right_order = self._compute_order(side='right')

return self.__right_order

def __repr__(self):

"""

Return string representation of this quaternion fractional ideal.

EXAMPLES::

sage: I = BrandtModule(11).right_ideals()[1]

sage: type(I)

sage: I.__repr__()

'Fractional ideal (2 + 6*j + 4*k, 2*i + 4*j + 2*k, 8*j, 8*k)'

"""

return 'Fractional ideal %s'%(self.gens(),)

def quaternion_order(self):

"""

Return the order for which this ideal is a left or right

fractional ideal. If this ideal has both a left and right

ideal structure, then the left order is returned. If it has

neither structure, then an error is raised.

OUTPUT: QuaternionOrder

EXAMPLES::

sage: R = QuaternionAlgebra(-11,-1).maximal_order()

sage: R.unit_ideal().quaternion_order() is R

True

"""

try: return self.__quaternion_order

except AttributeError: pass

if self.__left_order is not None:

A = self.__left_order

elif self.__right_order is not None:

A = self.__right_order

else:

raise RuntimeError("unable to determine quaternion order of ideal without known order")

self.__quaternion_order = A

return A

def ring(self):

"""

Return ring that this is a fractional ideal for.

EXAMPLES::

sage: R = QuaternionAlgebra(-11,-1).maximal_order()

sage: R.unit_ideal().ring() is R

True

"""

return self.quaternion_order()

def basis(self):

"""

Return basis for this fractional ideal. The basis is in Hermite form.

OUTPUT: tuple

EXAMPLES::

sage: QuaternionAlgebra(-11,-1).maximal_order().unit_ideal().basis()

(1/2 + 1/2*i, 1/2*j - 1/2*k, i, -k)

"""

return self.__basis

def gens(self):

"""

Return the generators for this ideal, which are the same as

the `\\ZZ`-basis for this ideal.

EXAMPLES::

sage: QuaternionAlgebra(-11,-1).maximal_order().unit_ideal().gens()

(1/2 + 1/2*i, 1/2*j - 1/2*k, i, -k)

"""

return self.__basis

def __eq__(self, right):

"""

Compare this fractional quaternion ideal to ``right``.

If ``right`` is not a fractional quaternion ideal, return ``False``.

If the fractional ideals are in different ambient

quaternion algebras, then the quaternion algebras themselves

are compared.

INPUT:

- ``right`` - another fractional quaternion ideal

EXAMPLES::

sage: I = QuaternionAlgebra(-11,-1).maximal_order().unit_ideal()

sage: I == I # indirect doctest

True

sage: I == 5

False

"""

if not isinstance(right, QuaternionFractionalIdeal_rational):

return False

return self.__basis == right.__basis

def __ne__(self, other):

"""

Compare this fractional quaternion ideal to ``right``.

INPUT:

- ``right`` - another fractional quaternion ideal

EXAMPLES::

sage: I = QuaternionAlgebra(-11,-1).maximal_order().unit_ideal()

sage: I != I # indirect doctest

False

"""

return not self.__eq__(other)

def basis_matrix(self):

r"""

Return basis matrix `M` in Hermite normal form for self as a

matrix with rational entries.

If `Q` is the ambient quaternion algebra, then the `\ZZ`-span of

the rows of `M` viewed as linear combinations of Q.basis() =

`[1,i,j,k]` is the fractional ideal self. Also,

``M * M.denominator()`` is an integer matrix in Hermite normal form.

OUTPUT: matrix over `\QQ`

EXAMPLES::

sage: QuaternionAlgebra(-11,-1).maximal_order().unit_ideal().basis_matrix()

[ 1/2 1/2 0 0]

[ 0 0 1/2 -1/2]

[ 0 1 0 0]

[ 0 0 0 -1]

"""

try: return self.__hermite_basis_matrix

except AttributeError: pass

B = quaternion_algebra_cython.rational_matrix_from_rational_quaternions(self.__basis)

self.__hermite_basis_matrix = B

return B

def free_module(self):

r"""

Return the free module associated to this quaternionic

fractional ideal, viewed as a submodule of

``Q.free_module()``, where ``Q`` is the ambient quaternion

algebra.

OUTPUT:

Free `\ZZ`-module of rank 4 embedded in an ambient `\QQ^4`.

EXAMPLES::

sage: QuaternionAlgebra(-11,-1).maximal_order().unit_ideal().basis_matrix()

[ 1/2 1/2 0 0]

[ 0 0 1/2 -1/2]

[ 0 1 0 0]

[ 0 0 0 -1]

This shows that the issue at :trac:`6760` is fixed::

sage: R.<i,j,k> = QuaternionAlgebra(-1, -13)

sage: I = R.ideal([2+i, 3*i, 5*j, j+k]); I

Fractional ideal (2 + i, 3*i, j + k, 5*k)

sage: I.free_module()

Free module of degree 4 and rank 4 over Integer Ring

Echelon basis matrix:

[2 1 0 0]

[0 3 0 0]

[0 0 1 1]

[0 0 0 5]

"""

try: return self.__free_module

except AttributeError:

M = self.basis_matrix().row_module(ZZ)

self.__free_module = M

return M

def theta_series_vector(self, B):

r"""

Return theta series coefficients of ``self``, as a vector

of ``B`` integers.

INPUT:

- ``B`` -- positive integer

OUTPUT:

Vector over `\ZZ` with ``B`` entries.

EXAMPLES::

sage: I = BrandtModule(37).right_ideals()[1]; I

Fractional ideal (2 + 6*j + 2*k, i + 2*j + k, 8*j, 8*k)

sage: I.theta_series_vector(5)

(1, 0, 2, 2, 6)

sage: I.theta_series_vector(10)

(1, 0, 2, 2, 6, 4, 8, 6, 10, 10)

sage: I.theta_series_vector(5)

(1, 0, 2, 2, 6)

"""

B = Integer(B)

try:

if len(self.__theta_series_vector)>= B: return self.__theta_series_vector[:B]

except AttributeError: pass

V = FreeModule(ZZ, B)

Q = self.quadratic_form()

v = V(Q.representation_number_list(B))

self.__theta_series_vector = v

return v

def quadratic_form(self):

"""

Return the normalized quadratic form associated to this quaternion ideal.

OUTPUT: quadratic form

EXAMPLES::

sage: I = BrandtModule(11).right_ideals()[1]

sage: Q = I.quadratic_form(); Q

Quadratic form in 4 variables over Rational Field with coefficients:

[ 18 22 33 22 ]

[ * 7 22 11 ]

[ * * 22 0 ]

[ * * * 22 ]

sage: Q.theta_series(10)

1 + 12*q^2 + 12*q^3 + 12*q^4 + 12*q^5 + 24*q^6 + 24*q^7 + 36*q^8 + 36*q^9 + O(q^10)

sage: I.theta_series(10)

1 + 12*q^2 + 12*q^3 + 12*q^4 + 12*q^5 + 24*q^6 + 24*q^7 + 36*q^8 + 36*q^9 + O(q^10)

"""

try: return self.__quadratic_form

except AttributeError: pass

from sage.quadratic_forms.quadratic_form import QuadraticForm

# first get the gram matrix

gram_matrix = self.gram_matrix()

# rescale so that there are no denominators

gram_matrix, _ = gram_matrix._clear_denom()

# Make sure gcd of all entries is 1.

g = gram_matrix.gcd()

if g != 1:

gram_matrix = gram_matrix / g

# now get the quadratic form

Q = QuadraticForm(gram_matrix)

self.__quadratic_form = Q

return Q

def theta_series(self, B, var='q'):

r"""

Return normalized theta series of self, as a power series over

`\ZZ` in the variable ``var``, which is 'q' by default.

The normalized theta series is by definition

.. MATH::

\theta_I(q) = \sum_{x \in I} q^{\frac{N(x)}{N(I)}}.

INPUT:

- ``B`` -- positive integer

- ``var`` -- string (default: 'q')

OUTPUT: power series

EXAMPLES::

sage: I = BrandtModule(11).right_ideals()[1]; I

Fractional ideal (2 + 6*j + 4*k, 2*i + 4*j + 2*k, 8*j, 8*k)

sage: I.norm()

sage: I.theta_series(5)

1 + 12*q^2 + 12*q^3 + 12*q^4 + O(q^5)

sage: I.theta_series(5,'T')

1 + 12*T^2 + 12*T^3 + 12*T^4 + O(T^5)

sage: I.theta_series(3)

1 + 12*q^2 + O(q^3)

"""

try:

if self.__theta_series.prec() >= B:

if var == self.__theta_series.variable():

return self.__theta_series.add_bigoh(B)

else:

ZZ[[var]](self.__theta_series.list()[:B+1])

except AttributeError: pass

v = self.theta_series_vector(B)

theta = ZZ[[var]](v.list()).add_bigoh(B)

self.__theta_series = theta

return theta

def gram_matrix(self):

r"""

Return the Gram matrix of this fractional ideal.

OUTPUT: `4 \times 4` matrix over `\QQ`.

EXAMPLES::

sage: I = BrandtModule(3,5).right_ideals()[1]; I

Fractional ideal (2 + 6*j + 4*k, 2*i + 4*j + 34*k, 8*j + 32*k, 40*k)

sage: I.gram_matrix()

[ 640 1920 2112 1920]

[ 1920 14080 13440 16320]

[ 2112 13440 13056 15360]

[ 1920 16320 15360 19200]

"""

try: return self.__gram_matrix

except AttributeError: pass

M = []

A = self.__basis

B = [z.conjugate() for z in self.__basis]

two = QQ(2)

m = [two*(a*b).reduced_trace() for b in B for a in A]

M44 = MatrixSpace(QQ, 4)

G = M44(m,coerce=False)

self.__gram_matrix = G

return G

def norm(self):

"""

Return the reduced norm of this fractional ideal.

OUTPUT: rational number

EXAMPLES::

sage: M = BrandtModule(37)

sage: C = M.right_ideals()

sage: [I.norm() for I in C]

[16, 32, 32]

sage: (a,b) = M.quaternion_algebra().invariants() # optional - magma

sage: magma.eval('A<i,j,k> := QuaternionAlgebra<Rationals() | %s, %s>' % (a,b)) # optional - magma

sage: magma.eval('O := QuaternionOrder(%s)' % str(list(C[0].right_order().basis()))) # optional - magma

sage: [ magma('rideal<O | %s>' % str(list(I.basis()))).Norm() for I in C] # optional - magma

[16, 32, 32]

sage: A.<i,j,k> = QuaternionAlgebra(-1,-1)

sage: R = A.ideal([i,j,k,1/2 + 1/2*i + 1/2*j + 1/2*k]) # this is actually an order, so has reduced norm 1

sage: R.norm()

sage: [ J.norm() for J in R.cyclic_right_subideals(3) ] # enumerate maximal right R-ideals of reduced norm 3, verify their norms

[3, 3, 3, 3]

"""

G = self.gram_matrix() / QQ(2)

r = G.det().abs()

assert r.is_square(), "first is bad!"

r = r.sqrt()

# If we know either the left- or the right order, use that one to compute the norm.

# Otherwise quaternion_order() will raise a RuntimeError and we compute the left order

try:

R = self.quaternion_order()

except RuntimeError:

R = self.left_order()

r/= R.discriminant()

assert r.is_square(), "second is bad!"

return r.sqrt()

def conjugate(self):

"""

Return the ideal with generators the conjugates of the generators for self.

OUTPUT: a quaternionic fractional ideal

EXAMPLES::

sage: I = BrandtModule(3,5).right_ideals()[1]; I

Fractional ideal (2 + 6*j + 4*k, 2*i + 4*j + 34*k, 8*j + 32*k, 40*k)

sage: I.conjugate()

Fractional ideal (2 + 2*j + 28*k, 2*i + 4*j + 34*k, 8*j + 32*k, 40*k)

"""

return self.quaternion_algebra().ideal([b.conjugate() for b in self.basis()],

left_order=self.__right_order,

right_order=self.__left_order)

def __mul__(self, right):

"""

Return the product of the fractional ideals ``self`` and ``right``.

.. note::

We do not keep track of left or right order structure.

EXAMPLES::

sage: I = BrandtModule(3,5).right_ideals()[1]; I

Fractional ideal (2 + 6*j + 4*k, 2*i + 4*j + 34*k, 8*j + 32*k, 40*k)

sage: I*I

Fractional ideal (8 + 24*j + 16*k, 8*i + 16*j + 136*k, 32*j + 128*k, 160*k)

sage: I*I.conjugate()

Fractional ideal (16 + 16*j + 224*k, 8*i + 16*j + 136*k, 32*j + 128*k, 320*k)

sage: I.multiply_by_conjugate(I)

Fractional ideal (16 + 16*j + 224*k, 8*i + 16*j + 136*k, 32*j + 128*k, 320*k)

"""

if not isinstance(right, QuaternionFractionalIdeal_rational):

return self._scale(right, left=False)

gens = [a*b for a in self.basis() for b in right.basis()]

#if self.__right_order == right.__left_order:

# left_order = self.__left_order

# right_order = right.__right_order

basis = tuple(basis_for_quaternion_lattice(gens))

A = self.quaternion_algebra()

return A.ideal(basis, check=False)

@cached_method

def free_module(self):

r"""

Return the underlying free `\ZZ`-module corresponding to this ideal.

EXAMPLES::

sage: X = BrandtModule(3,5).right_ideals()

sage: X[0]

Fractional ideal (2 + 2*j + 8*k, 2*i + 18*k, 4*j + 16*k, 20*k)

sage: X[0].free_module()

Free module of degree 4 and rank 4 over Integer Ring

Echelon basis matrix:

[ 2 0 2 8]

[ 0 2 0 18]

[ 0 0 4 16]

[ 0 0 0 20]

sage: X[0].scale(1/7).free_module()

Free module of degree 4 and rank 4 over Integer Ring

Echelon basis matrix:

[ 2/7 0 2/7 8/7]

[ 0 2/7 0 18/7]

[ 0 0 4/7 16/7]

[ 0 0 0 20/7]

The free module method is also useful since it allows for checking if

one ideal is contained in another, computing quotients `I/J`, etc.::

sage: X = BrandtModule(3,17).right_ideals()

sage: I = X[0].intersection(X[2]); I

Fractional ideal (2 + 2*j + 164*k, 2*i + 4*j + 46*k, 16*j + 224*k, 272*k)

sage: I.free_module().is_submodule(X[3].free_module())

False

sage: I.free_module().is_submodule(X[1].free_module())

True

sage: X[0].free_module() / I.free_module()

Finitely generated module V/W over Integer Ring with invariants (4, 4)

"""

return self.basis_matrix().row_module(ZZ)

def intersection(self, J):

"""

Return the intersection of the ideals self and `J`.

EXAMPLES::

sage: X = BrandtModule(3,5).right_ideals()

sage: I = X[0].intersection(X[1]); I

Fractional ideal (2 + 6*j + 4*k, 2*i + 4*j + 34*k, 8*j + 32*k, 40*k)

"""

V = self.free_module().intersection(J.free_module())

H,d = V.basis_matrix()._clear_denom()

A = self.quaternion_algebra()

gens = quaternion_algebra_cython.rational_quaternions_from_integral_matrix_and_denom(A, H, d)

return A.ideal(gens)

def multiply_by_conjugate(self, J):

"""

Return product of self and the conjugate Jbar of `J`.

INPUT:

- ``J`` -- a quaternion ideal.

OUTPUT: a quaternionic fractional ideal.

EXAMPLES::

sage: R = BrandtModule(3,5).right_ideals()

sage: R[0].multiply_by_conjugate(R[1])

Fractional ideal (8 + 8*j + 112*k, 8*i + 16*j + 136*k, 32*j + 128*k, 160*k)

sage: R[0]*R[1].conjugate()

Fractional ideal (8 + 8*j + 112*k, 8*i + 16*j + 136*k, 32*j + 128*k, 160*k)

"""

Jbar = [b.conjugate() for b in J.basis()]

gens = [a*b for a in self.basis() for b in Jbar]

basis = tuple(basis_for_quaternion_lattice(gens))

R = self.quaternion_algebra()

return R.ideal(basis, check=False)

def is_equivalent(I, J, B=10):

"""

Return ``True`` if ``I`` and ``J`` are equivalent as right ideals.

INPUT:

- ``I`` -- a fractional quaternion ideal (self)

- ``J`` -- a fractional quaternion ideal with same order as ``I``

- ``B`` -- a bound to compute and compare theta series before

doing the full equivalence test

OUTPUT: bool

EXAMPLES::

sage: R = BrandtModule(3,5).right_ideals(); len(R)

sage: R[0].is_equivalent(R[1])

False

sage: R[0].is_equivalent(R[0])

True

sage: OO = R[0].quaternion_order()

sage: S = OO.right_ideal([3*a for a in R[0].basis()])

sage: R[0].is_equivalent(S)

True

"""

if not isinstance(I, QuaternionFractionalIdeal_rational):

return False

if I.right_order() != J.right_order():

raise ValueError("I and J must be right ideals")

# Just test theta series first. If the theta series are

# different, the ideals are definitely not equivalent.

if B > 0 and I.theta_series_vector(B) != J.theta_series_vector(B):

return False

# The theta series are the same, so perhaps the ideals are

# equivalent. We use Prop 1.18 of [Pizer, 1980] to decide.

# 1. Compute I * Jbar

# see Prop. 1.17 in Pizer. Note that we use IJbar instead of

# JbarI since we work with right ideals

IJbar = I.multiply_by_conjugate(J)

# 2. Determine if there is alpha in K such

# that N(alpha) = N(I)*N(J) as explained by Pizer.

c = IJbar.theta_series_vector(2)[1]

return c != 0

def __contains__(self, x):

"""

Returns whether x is in self.

EXAMPLES::

sage: R.<i,j,k> = QuaternionAlgebra(-3, -13)

sage: I = R.ideal([2+i, 3*i, 5*j, j+k])

sage: 2+i in I

True

sage: 2+i+j+k in I

True

sage: 1+i in I

False

sage: 101*j + k in I

True

"""

try:

x = self.quaternion_algebra()(x)

return self.basis_matrix().transpose().solve_right(vector(x)) in ZZ**4

except (ValueError, TypeError):

return False

@cached_method

def cyclic_right_subideals(self, p, alpha=None):

r"""

Let `I` = ``self``. This function returns the right subideals

`J` of `I` such that `I/J` is an `\GF{p}`-vector space of

dimension 2.

INPUT:

- ``p`` -- prime number (see below)

- ``alpha`` -- (default: ``None``) element of quaternion algebra,

which can be used to parameterize the order of the

ideals `J`. More precisely the `J`'s are the right annihilators

of `(1,0) \alpha^i` for `i=0,1,2,...,p`

OUTPUT:

- list of right ideals

.. NOTE::

Currently, `p` must satisfy a bunch of conditions, or a

``NotImplementedError`` is raised. In particular, `p` must be

odd and unramified in the quaternion algebra, must be

coprime to the index of the right order in the maximal

order, and also coprime to the normal of self. (The Brandt

modules code has a more general algorithm in some cases.)

EXAMPLES::

sage: B = BrandtModule(2,37); I = B.right_ideals()[0]

sage: I.cyclic_right_subideals(3)

[Fractional ideal (2 + 2*i + 10*j + 90*k, 4*i + 4*j + 152*k, 12*j + 132*k, 444*k), Fractional ideal (2 + 2*i + 2*j + 150*k, 4*i + 8*j + 196*k, 12*j + 132*k, 444*k), Fractional ideal (2 + 2*i + 6*j + 194*k, 4*i + 8*j + 344*k, 12*j + 132*k, 444*k), Fractional ideal (2 + 2*i + 6*j + 46*k, 4*i + 4*j + 4*k, 12*j + 132*k, 444*k)]

sage: B = BrandtModule(5,389); I = B.right_ideals()[0]

sage: C = I.cyclic_right_subideals(3); C

[Fractional ideal (2 + 10*j + 546*k, i + 6*j + 133*k, 12*j + 3456*k, 4668*k), Fractional ideal (2 + 2*j + 2910*k, i + 6*j + 3245*k, 12*j + 3456*k, 4668*k), Fractional ideal (2 + i + 2295*k, 3*i + 2*j + 3571*k, 4*j + 2708*k, 4668*k), Fractional ideal (2 + 2*i + 2*j + 4388*k, 3*i + 2*j + 2015*k, 4*j + 4264*k, 4668*k)]

sage: [(I.free_module()/J.free_module()).invariants() for J in C]

[(3, 3), (3, 3), (3, 3), (3, 3)]

sage: I.scale(3).cyclic_right_subideals(3)

[Fractional ideal (6 + 30*j + 1638*k, 3*i + 18*j + 399*k, 36*j + 10368*k, 14004*k), Fractional ideal (6 + 6*j + 8730*k, 3*i + 18*j + 9735*k, 36*j + 10368*k, 14004*k), Fractional ideal (6 + 3*i + 6885*k, 9*i + 6*j + 10713*k, 12*j + 8124*k, 14004*k), Fractional ideal (6 + 6*i + 6*j + 13164*k, 9*i + 6*j + 6045*k, 12*j + 12792*k, 14004*k)]

sage: C = I.scale(1/9).cyclic_right_subideals(3); C

[Fractional ideal (2/9 + 10/9*j + 182/3*k, 1/9*i + 2/3*j + 133/9*k, 4/3*j + 384*k, 1556/3*k), Fractional ideal (2/9 + 2/9*j + 970/3*k, 1/9*i + 2/3*j + 3245/9*k, 4/3*j + 384*k, 1556/3*k), Fractional ideal (2/9 + 1/9*i + 255*k, 1/3*i + 2/9*j + 3571/9*k, 4/9*j + 2708/9*k, 1556/3*k), Fractional ideal (2/9 + 2/9*i + 2/9*j + 4388/9*k, 1/3*i + 2/9*j + 2015/9*k, 4/9*j + 4264/9*k, 1556/3*k)]

sage: [(I.scale(1/9).free_module()/J.free_module()).invariants() for J in C]

[(3, 3), (3, 3), (3, 3), (3, 3)]

sage: Q.<i,j,k> = QuaternionAlgebra(-2,-5)

sage: I = Q.ideal([Q(1),i,j,k])

sage: I.cyclic_right_subideals(3)

[Fractional ideal (1 + 2*j, i + k, 3*j, 3*k), Fractional ideal (1 + j, i + 2*k, 3*j, 3*k), Fractional ideal (1 + 2*i, 3*i, j + 2*k, 3*k), Fractional ideal (1 + i, 3*i, j + k, 3*k)]

The general algorithm is not yet implemented here::

sage: I.cyclic_right_subideals(3)[0].cyclic_right_subideals(3)

Traceback (most recent call last):

...

NotImplementedError: general algorithm not implemented (The given basis vectors must be linearly independent.)

"""

R = self.right_order()

Q = self.quaternion_algebra()

f = Q.modp_splitting_map(p)

if alpha is not None:

alpha = f(alpha)

W = GF(p)**4

try:

A = W.span_of_basis([W(f(a).list()) for a in self.basis()])

scale = 1

IB = self.basis_matrix()

except (ValueError, ZeroDivisionError):

# try rescaling the ideal.

B, d = self.basis_matrix()._clear_denom()

g = gcd(B.list())

IB = B/g

scale = g/d

try:

A = W.span_of_basis([W(f(Q(a.list())).list()) for a in IB.rows()])

except (ValueError, ZeroDivisionError) as msg:

# Here we could replace the ideal by an *equivalent*

# ideal that works. This is always possible.

# However, I haven't implemented that algorithm yet.

raise NotImplementedError("general algorithm not implemented (%s)"%msg)

Ai = A.basis_matrix()**(-1)

AiB = Ai.change_ring(QQ) * IB

# Do not care about the denominator since we're really working in I/p*I.

AiB, _ = AiB._clear_denom()

pB = p*IB

pB, d = pB._clear_denom()

ans = []

Z = matrix(ZZ,2,4)

P1 = P1List(p)

if alpha is None:

lines = P1

else:

x = alpha

lines = []

for i in range(p+1):

lines.append(P1.normalize(x[0,0], x[0,1]))

x *= alpha

for u,v in lines:

# The following does:

# z = matrix(QQ,2,4,[0,-v,0,u, -v,0,u,0],check=False) * AiB

Z[0,1]=-v; Z[0,3]=u; Z[1,0]=-v; Z[1,2]=u

z = Z * AiB

# Now construct submodule of the ideal I spanned by the

# linear combinations given by z of the basis for J along

# with p*I.

G = (d*z).stack(pB) # have to multiply by d since we divide by it below in the "gens = " line.

H = G._hnf_pari(0, include_zero_rows=False)

gens = tuple(quaternion_algebra_cython.rational_quaternions_from_integral_matrix_and_denom(Q, H, d))

if scale != 1:

gens = tuple([scale*g for g in gens])

J = R.right_ideal(gens, check=False)

ans.append(J)

return ans

#######################################################################

# Some utility functions that are needed here and are too

# specialized to go elsewhere.

#######################################################################

def basis_for_quaternion_lattice(gens, reverse = False):

r"""

Return a basis for the `\ZZ`-lattice in a quaternion algebra

spanned by the given gens.

INPUT:

- ``gens`` -- list of elements of a single quaternion algebra

- ``reverse`` -- when computing the HNF do it on the basis

`(k,j,i,1)` instead of `(1,i,j,k)`; this ensures

that if ``gens`` are the generators for an order,

the first returned basis vector is 1

EXAMPLES::

sage: from sage.algebras.quatalg.quaternion_algebra import basis_for_quaternion_lattice

sage: A.<i,j,k> = QuaternionAlgebra(-1,-7)

sage: basis_for_quaternion_lattice([i+j, i-j, 2*k, A(1/3)])

[1/3, i + j, 2*j, 2*k]

sage: basis_for_quaternion_lattice([A(1),i,j,k])

[1, i, j, k]

"""

if len(gens) == 0: return []

Z, d = quaternion_algebra_cython.integral_matrix_and_denom_from_rational_quaternions(gens, reverse)

H = Z._hnf_pari(0, include_zero_rows=False)

A = gens[0].parent()

return quaternion_algebra_cython.rational_quaternions_from_integral_matrix_and_denom(A, H, d, reverse)

def intersection_of_row_modules_over_ZZ(v):

r"""

Intersects the `\ZZ`-modules with basis matrices the full rank `4 \times 4`

`\QQ`-matrices in the list v. The returned intersection is

represented by a `4 \times 4` matrix over `\QQ`. This can also be done

using modules and intersection, but that would take over twice as long

because of overhead, hence this function.

EXAMPLES::

sage: a = matrix(QQ,4,[-2, 0, 0, 0, 0, -1, -1, 1, 2, -1/2, 0, 0, 1, 1, -1, 0])

sage: b = matrix(QQ,4,[0, -1/2, 0, -1/2, 2, 1/2, -1, -1/2, 1, 2, 1, -2, 0, -1/2, -2, 0])

sage: c = matrix(QQ,4,[0, 1, 0, -1/2, 0, 0, 2, 2, 0, -1/2, 1/2, -1, 1, -1, -1/2, 0])

sage: v = [a,b,c]

sage: from sage.algebras.quatalg.quaternion_algebra import intersection_of_row_modules_over_ZZ

sage: M = intersection_of_row_modules_over_ZZ(v); M

[ 2 0 -1 -1]

[ -4 1 1 -3]

[ 3 -19/2 1 4]

[ 2 -3 -8 4]

sage: M2 = a.row_module(ZZ).intersection(b.row_module(ZZ)).intersection(c.row_module(ZZ))

sage: M.row_module(ZZ) == M2

True

"""

if len(v) <= 0:

raise ValueError("v must have positive length")

if len(v) == 1:

return v[0]

elif len(v) == 2:

# real work - the base case

a, b = v

s,_ = a.stack(b)._clear_denom()

s = s.transpose()

K = s.right_kernel_matrix(algorithm='pari', basis='computed')

n = a.nrows()

return K.matrix_from_columns(range(n)) * a

else:

# induct

w = intersection_of_row_modules_over_ZZ(v[:2])

return intersection_of_row_modules_over_ZZ([w] + v[2:])

def normalize_basis_at_p(e, p, B = lambda x,y: (x*y.conjugate()).reduced_trace()):

r"""

Computes a (at ``p``) normalized basis from the given basis ``e``

of a `\ZZ`-module.

The returned basis is (at ``p``) a `\ZZ_p` basis for the same

module, and has the property that with respect to it the quadratic

form induced by the bilinear form B is represented as a orthogonal

sum of atomic forms multiplied by p-powers.

If `p \neq 2` this means that the form is diagonal with respect to

this basis.

If `p = 2` there may be additional 2-dimensional subspaces on which

the form is represented as `2^e (ax^2 + bxy + cx^2)` with

`0 = v_2(b) = v_2(a) \leq v_2(c)`.

INPUT:

- ``e`` -- list; basis of a `\ZZ` module.

WARNING: will be modified!

- ``p`` -- prime for at which the basis should be normalized

- ``B`` -- (default:

``lambda x,y: ((x*y).conjugate()).reduced_trace()``)

a bilinear form with respect to which to normalize

OUTPUT:

- A list containing two-element tuples: The first element of

each tuple is a basis element, the second the valuation of

the orthogonal summand to which it belongs. The list is sorted

by ascending valuation.

EXAMPLES::

sage: from sage.algebras.quatalg.quaternion_algebra import normalize_basis_at_p

sage: A.<i,j,k> = QuaternionAlgebra(-1, -1)

sage: e = [A(1), i, j, k]

sage: normalize_basis_at_p(e, 2)

[(1, 0), (i, 0), (j, 0), (k, 0)]

sage: A.<i,j,k> = QuaternionAlgebra(210)

sage: e = [A(1), i, j, k]

sage: normalize_basis_at_p(e, 2)

[(1, 0), (i, 1), (j, 1), (k, 2)]

sage: A.<i,j,k> = QuaternionAlgebra(286)

sage: e = [A(1), k, 1/2*j + 1/2*k, 1/2 + 1/2*i + 1/2*k]

sage: normalize_basis_at_p(e, 5)

[(1, 0), (1/2*j + 1/2*k, 0), (-5/6*j + 1/6*k, 1), (1/2*i, 1)]

sage: A.<i,j,k> = QuaternionAlgebra(-1,-7)

sage: e = [A(1), k, j, 1/2 + 1/2*i + 1/2*j + 1/2*k]

sage: normalize_basis_at_p(e, 2)

[(1, 0), (1/2 + 1/2*i + 1/2*j + 1/2*k, 0), (-34/105*i - 463/735*j + 71/105*k, 1), (-34/105*i - 463/735*j + 71/105*k, 1)]

"""

N = len(e)

if N == 0:

return []

else:

min_m, min_n, min_v = 0, 0, infinity

# Find two basis vector on which the bilinear form has minimal

# p-valuation. If there is more than one such pair, always

# prefer diagonal entries over any other and (secondary) take

# min_m and then min_n as small as possible

for m in range(N):

for n in range(m, N):

v = B(e[m], e[n]).valuation(p)

if v < min_v or (v == min_v and (min_m != min_n) and (m == n)):

min_m, min_n, min_v = m, n, v

if (min_m == min_n) or p != 2: # In this case we can diagonalize

if min_m == min_n: # Diagonal entry has minimal valuation

f0 = e[min_m]

else:

f0 = e[min_m] + e[min_n] # Only off-diagonal entries have min. val., but p!=2

# Swap with first vector

e[0], e[min_m] = e[min_m], e[0]

# Orthogonalize remaining vectors with respect to f

c = B(f0, f0)

for l in range(1, N):

e[l] = e[l] - B(e[l],f0)/c * f0

# Recursively normalize remaining vectors

f = normalize_basis_at_p(e[1:], p)

f.insert(0, (f0, min_v - valuation(p, 2)))

return f

else: # p = 2 and only off-diagonal entries have min. val., gives 2-dim. block

# first diagonal entry should have smaller valuation

if B(e[min_m],e[min_m]).valuation(p) > B(e[min_n],e[min_n]).valuation(p):

e[min_m], e[min_n] = e[min_n], e[min_m]

f0 = p**min_v / B(e[min_m],e[min_n]) * e[min_m]

f1 = e[min_n]

# Ensures that (B(f0,f0)/2).valuation(p) <= B(f0,f1).valuation(p)

if B(f0,f1).valuation(p) + 1 < B(f0,f0).valuation(p):

f0 = f0 + f1

f1 = f0

# Make remaining vectors orthogonal to span of f0, f1

e[min_m] = e[0]

e[min_n] = e[1]

B00 = B(f0,f0)

B11 = B(f1,f1)

B01 = B(f0,f1)

d = B00*B11 - B01**2

tu = [ (B01 * B(f1,e[l]) - B11 * B(f0,e[l]),

B01 * B(f0,e[l]) - B00 * B(f1,e[l])) for l in range(2,N) ]

e[2:n] = [ e[l] + tu[l-2][0]/d * f0 + tu[l-2][1]/d * f1 for l in range(2,N) ]

# Recursively normalize remaining vectors

f = normalize_basis_at_p(e[2:N], p)

return [(f0, min_v), (f1, min_v)] + f

def maxord_solve_aux_eq(a, b, p):

r"""

Given ``a`` and ``b`` and an even prime ideal ``p`` find

(y,z,w) with y a unit mod `p^{2e}` such that

.. MATH::

1 - ay^2 - bz^2 + abw^2 \equiv 0 mod p^{2e},

where `e` is the ramification index of `p`.

Currently only `p=2` is implemented by hardcoding solutions.

INPUT:

- ``a`` -- integer with `v_p(a) = 0`

- ``b`` -- integer with `v_p(b) \in \{0,1\}`

- ``p`` -- even prime ideal (actually only ``p=ZZ(2)`` is implemented)

OUTPUT:

- A tuple `(y, z, w)`

EXAMPLES::

sage: from sage.algebras.quatalg.quaternion_algebra import maxord_solve_aux_eq

sage: for a in [1,3]:

....: for b in [1,2,3]:

....: (y,z,w) = maxord_solve_aux_eq(a, b, 2)

....: assert mod(y, 4) == 1 or mod(y, 4) == 3

....: assert mod(1 - a*y^2 - b*z^2 + a*b*w^2, 4) == 0

"""

if p != ZZ(2):

raise NotImplementedError("Algorithm only implemented over ZZ at the moment")

v_a = a.valuation(p)

v_b = b.valuation(p)

if v_a != 0:

raise RuntimeError("a must have v_p(a)=0")

if v_b != 0 and v_b != 1:

raise RuntimeError("b must have v_p(b) in {0,1}")

R = ZZ.quo(ZZ(4))

lut = {

(R(1), R(1)) : (1,1,1),

(R(1), R(2)) : (1,0,0),

(R(1), R(3)) : (1,0,0),

(R(3), R(1)) : (1,1,1),

(R(3), R(2)) : (1,0,1),

(R(3), R(3)) : (1,1,1), }

return lut[ (R(a), R(b)) ]

Coverage for local/lib/python2.7/site-packages/sage/algebras/quatalg/quaternion_algebra.py : 76%

729 statements 554 run 175 missing 0 excluded