Norm Spaces and Basis Reduction

For definite quaternion orders or ideals one can compute reduced bases and Gram matrices.

If the base ring of the order or ideal is \({\mathbb{Z}}\) or \({\mathbb{F}}_q[X]\) with \(q\) odd, the Gram matrices can be made unique up to isomorphism. In fact, in these cases, the isomorphism testing of ideals and orders is based on this reduction.

NormSpace(A): AlgQuat -> ModTupFld, Map: Given a quaternion algebra \(A\) over any field \(F\) not of characteristic \(2\), this function returns the underlying \(F\)-space with inner product the norm form. A map from \(A\) into the structure is returned as second value.

NormSpace(S): AlgQuatOrd -> ModTupRng, Map
NormModule(S): AlgQuatOrd -> ModTupRng, Map: Given a quaternion order \(S\) over \({\mathbb{Z}}\) or \({\mathbb{F}}_q[X]\) (with \(q\) odd), this function returns the underlying module over its base ring, with inner product respect to the norm. A map from \(O\) into the structure is returned as second value.

GramMatrix(S): AlgQuatOrd -> AlgMatElt
GramMatrix(I): AlgQuatOrdIdl -> AlgMatElt: The Gram matrix of the quaternion order \(S\) or ideal \(I\) over \({\mathbb{Z}}\) or \({\mathbb{F}}_q[X]\) with respect to the norm on the basis for \(S\).

ReducedGramMatrix(S): AlgQuatOrd[RngInt] -> AlgMatElt

ReducedGramMatrix(S): AlgQuatOrdIdl[RngInt] -> AlgMatElt

Given an order or ideal \(S\) over \({\mathbb{Z}}\) in a definite quaternion algebra, this function returns the Gram matrix \(G\) of the corresponding lattice.

The quaternion ideal machinery makes use of a Minkowski basis reduction algorithm which returns a unique normalized reduced Gram matrix \(G\) for any definite quaternion ideal. This forms the core of the isomorphism testing for quaternion ideals.

ReducedBasis(S): AlgQuatOrd[RngInt] -> SeqEnum
ReducedBasis(S): AlgQuatOrdIdl[RngInt] -> SeqEnum: Given an order or ideal \(S\) over \({\mathbb{Z}}\) in a definite quaternion algebra, this function returns some basis \(B\) of \(S\) the Gram matrix \(G\) of the corresponding lattice associated with \(S\). Note that while there exists a unique Minkowski-reduced Gram matrix \(G\), the basis \(B\) is not unique.

Example: Minkowski Reduction of Quaternion Ideals (ex-dbe93f)

Run in calculator (opens in a new tab)

Recall that Minkowski basis reduction is used which returns a unique normalized reduced Gram matrix \(G\) for any definite quaternion ideal. This forms the core of the isomorphism testing for quaternion ideals. We illustrate this by applying it to representatives of the set of left ideal classes of an order.

> A := QuaternionOrder(19,2);
> ideals := LeftIdealClasses(A);
> #ideals;
5
> [ (1/Norm(I))*ReducedGramMatrix(I) : I in ideals ];
[
    [ 2  0  1  1]
    [ 0  2  1  1]
    [ 1  1 20  1]
    [ 1  1  1 20],

    [6 0 1 3]
    [0 6 3 1]
    [1 3 8 1]
    [3 1 1 8],

    [6 0 1 3]
    [0 6 3 1]
    [1 3 8 1]
    [3 1 1 8],

    [ 4  0  1 -1]
    [ 0  4  1  1]
    [ 1  1 10  0]
    [-1  1  0 10],

    [ 4  0  1 -1]
    [ 0  4  1  1]
    [ 1  1 10  0]
    [-1  1  0 10]
]

Run in calculator (opens in a new tab)

ReducedGramMatrix(S): AlgQuatOrd[RngUPol] -> AlgMatElt, SeqEnum

ReducedGramMatrix(S): AlgQuatOrdIdl[RngUPol] -> AlgMatElt, SeqEnum

ReducedBasis(S): AlgQuatOrd[RngUPol] -> SeqEnum

ReducedBasis(S): AlgQuatOrdIdl[RngUPol] -> SeqEnum

Canonical: BoolElt                    Default: false

Given an order or ideal \(S\) over \({\mathbb{F}}_q[X]\) in a quaternion algebra \(A\), this function returns a Gram matrix and/or a basis of \(S\) whose Gram matrix is in dominant diagonal form (see the function DominantDiagonalForm in Section Automorphism Group and Isometry Testing over \({\mathbb{F}}_q[t]\)). The Gram matrix will not be unique unless \(A\) is definite and Canonical is set to true.

ReducedBasis(O): AlgAssVOrd[RngOrd] -> [AlgAssVElt]
ReducedBasis(I): AlgAssVOrdIdl[RngOrd] -> [AlgAssVOrdElt]: Returns a “reduced” basis for the order \(O\) or the ideal \(I\) over some number ring. If \(O\) or \(I\) arise from a definite quaternion algebra, then this basis is LLL-reduced with respect to the norm form; otherwise, the basis is reduced with respect to a Minkowski-like embedding (see [KV10, Section 4]).

OptimizedRepresentation(O): AlgAssVOrd -> AlgQuat, Map
OptimisedRepresentation(O): AlgAssVOrd -> AlgQuat, Map: Given an order \(O\) contained in a quaternion algebra \(A\) over \({\mathbb{Q}}\) or a number field \(F\), this function returns a new quaternion algebra \(A'\) such that \(A' = ((a, b)/F)\) where \(a\) and \(b\) are small (with respect to \(O\)), and, as second return value, an isomorphism \(A \to A'\).

OptimizedRepresentation(A): AlgQuat -> AlgQuat, Map
OptimisedRepresentation(A): AlgQuat -> AlgQuat, Map: Given a quaternion algebra \(A\) over \({\mathbb{Q}}\) or a number field \(F\), this function returns a new quaternion algebra \(A'\) such that \(A' = ((a, b)/F)\) where \(a\) and \(b\) are small. An isomorphism \(A \to A'\) is returned as second value.

Enumerate(O, A, B): AlgQuatOrd[RngInt], RngIntElt, RngIntElt -> [AlgQuatOrdElt]
Enumerate(O, B): AlgQuatOrd[RngInt], RngIntElt -> [AlgQuatOrdElt]
Enumerate(O, A, B): AlgQuatOrdIdl[RngInt], RngElt, RngElt -> [AlgQuatElt]
Enumerate(O, B): AlgQuatOrd[RngInt], RngElt -> [AlgQuatElt]: The sequence of all elements \(x\) (up to sign) in the definite quaternion order \(O\) or ideal \(I\) over \({\mathbb{Z}}\) such that the reduced norm of \(x\) lies in the interval \([A, \ldots B]\) or \([0, \ldots B]\), respectively.

Enumerate(O, A, B): AlgAssVOrd[RngOrd], RngElt, RngElt -> [AlgAssVOrdElt]
Enumerate(O, B): AlgAssVOrd[RngOrd], RngElt -> [AlgAssVOrdElt]
Enumerate(O, B): AlgAssVOrd[RngOrd], [RngElt] -> [AlgAssVOrdElt]
Enumerate(I, B): AlgAssVOrdIdl[RngOrd], [RngElt] -> [AlgAssVOrdElt]: The sequence of elements \(x\) (up to sign) in the definite quaternion order \(O\) or ideal \(I\) over a number ring such that the absolute trace of the norm of \(x\) lies in the interval \([A, \ldots B]\) or \([0, \ldots B]\), respectively.

Norm Spaces and Basis Reduction#

Norm Spaces and Basis Reduction