Algorithmic enumeration of ideal classes for quaternion orders

Markus Kirschmer; John Voight

Source-linked AI summary

Algorithmic enumeration of ideal classes for quaternion orders

Markus Kirschmer, John Voight

arXiv:0808.3833v4Aug 28, 2008math.NT

TL;DR

The paper addresses computation of class numbers and ideal-class representatives for Eichler orders over number fields, together with related order and ideal problems. It develops algorithms for these tasks, analyzes their running times, and concludes with a complete classification of definite Eichler orders of class number at most 2.

Problem
The paper studies how to compute class numbers and representatives of invertible right ideal classes for Eichler orders, alongside related problems such as principalization and order connectivity.
Method
The authors develop algorithms for definite and indefinite Eichler orders, including class-number computation, S-neighbor enumeration, and ideal principalization.
Results
The paper gives algorithms for counting and enumerating ideal classes, analyzes their running times, and reports exactly 74 definite Eichler-order classes with class number 1 and 172 with class number 2.
Takeaways & Limitations
The results provide computational access to ideal classes and related structures for Eichler orders, including a complete low-class-number list in the definite case.
Takeaways & Limitations
For indefinite orders, Algorithm 4.10 has no rigorous time bounds because principal ideal testing lacks proven complexity estimates.

Abstract

from arXiv · show

We provide algorithms to count and enumerate representatives of the (right) ideal classes of an Eichler order in a quaternion algebra defined over a number field. We analyze the run time of these algorithms and consider several related problems, including the computation of two-sided ideal classes, isomorphism classes of orders, connecting ideals for orders, and ideal principalization. We conclude by giving the complete list of definite Eichler orders with class number at most 2.

1. Quaternion algebras, orders, and ideals

The paper introduces quaternion algebras and orders over a number field, establishing the algebraic setting for subsequent algorithms.

The section defines quaternion algebras and orders over a number field F of degree n with ring of integers Z_F.It also fixes the absolute discriminant d_F as part of the standing notation.

Number rings.

This section formalizes computation of class groups and unit groups of number fields, emphasizing output representation and algorithmic complexity.

The central number-ring problem is to compute the class group and unit group of Z_F.
The output representation is nonunique, and unit generators may have exponential size in a usual integral-basis representation.
Straight-line programs can represent unit generators as products of field elements, potentially reducing representation size to subexponential.
Under GRH and a smoothness condition, the class-group algorithm has a stated subexponential running-time bound, while a deterministic variant requires factoring polynomials over finite fields.
The same class-group computations can support ideal principal testing and generator recovery, although no rigorous running-time bound is established for that procedure.

Quaternion algebras.

This section develops the definitions and computational representation of quaternion algebras, orders, discriminants, Eichler orders, and order isomorphism classes.

A quaternion algebra B over F is a central simple F-algebra of dimension 4, equivalently generated by elements satisfying quaternion relations.
The reduced trace and norm provide coordinate formulas for quaternion elements, including nrd(γ) = x^2 − ay^2 − bz^2 + abw^2.
A field extension K splits B when B_K is isomorphic to M_2(K), and quadratic extensions split B exactly when they embed into B over F.
Quaternion algebras are classified by their ramified places, whose finite and infinite behavior also determines whether the algebra is totally definite or indefinite.
An order is a Z_F-lattice subring of B, and computing a maximal order is probabilistic polynomial-time equivalent to integer factorization.
An Eichler order is an intersection of two maximal orders, with level N defined by d = DN; all Eichler orders arise from the local upper-triangular construction up to conjugation.
Eichler orders can be computed from maximal orders and local embeddings by intersecting the corresponding local orders as Z_F-lattices.
There are finitely many isomorphism classes of Eichler orders of any fixed level N.

Quaternion ideals.

This section defines quaternion ideals, invertibility, ideal classes, and connecting ideals, and records finiteness and order-independence properties of ideal classes.

The reduced norm of a Z_F-lattice I is the fractional ideal generated by the reduced norms of its elements.
Products, colon ideals, and left and right orders are Z_F-lattices, and the latter operations are computable deterministically in polynomial time.
A right fractional O-ideal is a Z_F-lattice whose right order is O, with left and right ideals related by conjugation.
A lattice is a fractional ideal for its left and right orders; when those orders coincide, it is a two-sided O-ideal.
Invertibility is equivalent to local principality, and every right fractional ideal is invertible exactly when the order is hereditary.
Right ideal classes identify invertible right ideals up to multiplication by an element of B*, equivalently up to isomorphism as right O-modules.
Connecting ideals define an equivalence relation on orders, and two Eichler orders are connected exactly when they have the same level.
The right ideal class set is finite, and its cardinality is independent of the Eichler order chosen at a fixed level; this cardinality is the class number h(O).

2. Algorithmic problems

The paper formulates interconnected computational problems for Eichler orders, covering class numbers, ideal classes, isomorphism, principalization, two-sided classes, conjugacy, and connecting ideals. It establishes reductions linking these problems, including equivalence between ideal isomorphism and principalization and a construction reducing ideal-class enumeration to conjugacy classes, connecting ideals, and two-sided classes.

The paper asks for the class number and a complete set of invertible right ideal-class representatives for an Eichler order.
Isomorphism testing for invertible right ideals and principalization are computationally equivalent.Both problems ask for an explicit element of the quaternion algebra when the relevant equivalence or principality holds.
The paper also formulates problems for two-sided ideal classes, order isomorphism and conjugacy classes, and connecting ideals between Eichler orders.
The representatives {J_i,j I_i} form a complete set of right ideal-class representatives, using connecting ideals and two-sided ideal-class representatives.
Solving ConjClassSet reduces to ClassSet with ConnectingIdeal and TwoSidedClassSet, while the converse uses IsConjugate.

3. Two-sided ideal classes and connecting ideals

The section introduces two-sided ideal classes and connecting ideals as central algorithmic subproblems. It begins by describing two-sided ideals locally at primes of the number field.

The paper studies TwoSidedClassSet and ConnectingIdeal for an Eichler order.
Two-sided ideals of an Eichler order are analyzed through their local descriptions at prime completions.

Two-sided ideal classes.

Invertible two-sided ideal classes form a finitely generated abelian group whose generators arise from local behavior at ramified and level primes. The paper gives a polynomial-time reduction for computing these classes when the discriminant is factored.

At a ramified prime, the local two-sided ideal group is cyclic exactly when the local exponent is odd or zero.
The invertible fractional two-sided ideals form an abelian group generated by specified two-sided ideals.
An integral two-sided ideal can be reduced inductively by dividing by a maximal two-sided ideal, yielding the generator description.
If B is indefinite, generators with even exponent can be omitted because they share a reduced norm with a principal ideal.
Problem TwoSidedClassSet is probabilistic polynomial-time reducible to ClassUnitGroup(Z_F) and O(h(Z_F)^2 N d^2) instances of IsIsomorphic when d is factored.

Eichler orders and connecting ideals.

The paper tests whether an order is Eichler using local computations at prime powers and constructs connecting ideals between same-level Eichler orders. These constructions also reduce conjugacy testing to two-sided class computation and ideal isomorphism.

Algorithm 3.4 determines whether an order is Eichler and, when it is, computes a conjugating element to the standard local model.
For each prime power dividing the level, the algorithm tests for a common eigenvector modulo that prime power.
The Chinese remainder theorem combines the local data to produce the global conjugating element.
Algorithm 3.5 constructs an invertible fractional O′,O-ideal connecting two Eichler orders of the same level.
The construction scales an element into O′, uses its reduced norm, and returns I = μO + nO′O.
IsConjugate reduces probabilistic polynomial-time to TwoSidedClassSet and IsIsomorphic for Eichler orders with factored discriminant.

4. Ideal classes in indefinite orders

For indefinite Eichler orders, Eichler’s theorem reduces ideal-class enumeration to reduced norms and ray class data, yielding polynomial-time algorithms over a fixed field. The section also develops principalization methods, while noting that rigorous runtime bounds remain unavailable for the practical principalization algorithm.

Structural reduction: Eichler’s theorem relates the reduced norm map to the ray class group, providing the structural basis for enumerating ideal classes in indefinite orders.The quotient ClS∞ZF / Cl ZF is an elementary 2-group, and the reduced norm map supplies the relevant norm classes.
Ideal construction: Algorithm 4.3 constructs an invertible right O-ideal of prescribed norm by local norm equations, lifting, and the Chinese remainder theorem.It factors the target ideal, finds local elements with prescribed reduced norms, combines them, and returns βO + aO.
Ideal-class enumeration: Algorithm 4.4 enumerates representatives of Cl O from ray-class representatives modulo 2 and ideals produced by Algorithm 4.3.The construction yields all representatives through the set {cIa} indexed by the relevant ray-class data.
Complexity: For a fixed field F, ClassSet for indefinite orders is solvable in probabilistic polynomial time, while ClassNumber is reducible in deterministic polynomial time to ClassUnitGroup(ZF).The probabilistic bound uses square-root extraction modulo prime ideals; the class-number reduction follows from Eichler’s theorem and Corollary 4.2.
Principalization: Principalization tests whether nrd(I) is trivial in the ray class group and then seeks a generator using a positive definite auxiliary form and LLL reduction.The auxiliary form turns I into a definite lattice, allowing enumeration of short elements whose reduced norm can produce a generator.
Limitations: The practical principalization algorithm improves naive enumeration, but the authors provide no rigorous time bounds for it.The unresolved bounds include principal ideal testing, even when the number-field class group has already been computed.

5. Computing the class number for definite orders

For definite Eichler orders, the class number is computed from the Eichler mass formula plus torsion corrections, with embedding numbers obtained from local data. The resulting algorithm is probabilistic polynomial time when the discriminant is factored, and for fixed F the problem reduces to discriminant factorization.

Mass formula: The class number of a definite Eichler order is governed by the Eichler mass formula and differs from the mass by torsion corrections.The correction term is expressed through elliptic subgroups and embedding numbers.
Embedding corrections: Global embedding numbers eq(D, N) are computed by comparing local embedding numbers m(Rp, Op), which equal 1 for almost all primes.The relevant quadratic orders are organized by their elliptic unit structure, including fully elliptic and half elliptic cases.
Algorithm: The algorithm computes the mass, Dedekind-zeta contribution, and torsion correction using factored discriminant and level data together with class-unit-group computations.The zeta value ζF(-1) is approximated from a truncated Euler product and recovered using its rational denominator bound.
Complexity: Theorem 5.6 gives a probabilistic algorithm for ClassNumber of definite orders with factored discriminant, with runtime depending on field and order-discriminant parameters.The runtime statement includes terms involving dF, N, and d, together with the cost of solving O(2^n) class-unit-group instances.
Complexity: For a fixed number field F, ClassNumber for definite orders is probabilistic polynomial-time reducible to factoring the order discriminant.This is the stated consequence of Theorem 5.6 and the preceding computations.
Related consequence: Computing ClassNumber for definite quaternion algebras over Q can factor integers with O(log log a) prime factors in probabilistic polynomial time.The reduction recovers a prime factor from class-number values, with repeated attempts succeeding with probability at least 1/2.

6. Ideal principalization for definite orders

For totally definite quaternion orders, the paper reduces ideal principalization to shortest-vector searches over finitely many unit-scaled lattices, yielding a deterministic polynomial-time algorithm over a fixed totally real field.

Algorithm 6.3: Algorithm 6.3 solves principalization for a right fractional ideal I whose reduced norm is cZF.It tests sign conditions, enumerates totally positive units, and searches shortest vectors in the corresponding lattice.
Correctness: Principalization is reduced to finding ξ ∈ I with reduced norm ucz, characterized by equality in a norm bound.Equality holds exactly when the auxiliary element α equals 1, making ξ a shortest vector for the relevant quadratic form.
Runtime analysis: Shortest vectors can be found deterministically in O(log^3 A) time for fixed dimension when lattice basis vectors have squared norm at most A.The bound follows from the LLL algorithm; a floating-point variant might improve the exponent to 2, but the paper does not use that refinement.
Auxiliary algorithms: Uniformly random ideals in a fixed ideal class with bounded norm can be generated in probabilistic polynomial time over a fixed totally real field.The construction samples lattice elements, filters by norm, and uses shortest-vector computation to obtain a uniformly distributed ideal.
Runtime analysis: Algorithm 6.3 runs in deterministic polynomial time in the input size over a fixed totally real field.The proof bounds the unit enumeration and applies fixed-dimension shortest-vector computation to lattices with polynomial-size bases.

7. Computing the class set for definite orders

For totally definite Eichler orders, the paper enumerates right ideal classes using primitive-ideal neighbors, class-group representatives, isomorphism testing, and a class-number stopping criterion. The resulting algorithm is probabilistic polynomial time in the output size when the discriminant is factored.

Ideal decomposition: The enumeration separates primitive right ideals from two-sided ideals of the form aO and then reconstructs all right ideals as products JI.Primitivity excludes containment in nontrivial two-sided ideals, while the class group acts by ideal multiplication.
Algorithmic framework: Primitive right invertible O-ideals of norm a correspond bijectively to P1(ZF /a), providing the local enumeration step.The construction uses a splitting and an explicitly defined map to projective-line points.
Algorithmic framework: Strong approximation permits choosing representatives whose reduced norms are supported on S, so enumerating those ideals finds every ideal class.The algorithm tests newly generated ideals for isomorphism and stops once the computed class number H is reached.
Algorithmic framework: The S-neighbors algorithm solves ClassSet by enumerating right invertible ideal classes for an Eichler order using a suitable finite prime set S.S must generate the relevant ideal class group and be coprime to the quaternion discriminant and order level.
Complexity: Theorem 7.9 gives probabilistic polynomial time in the output size for ClassSet over a fixed field when definite orders have factored discriminant.The runtime analysis uses bounds on the neighbor process and polynomially many principalness or isomorphism tests.

8. Definite Eichler orders with class number at most two

The paper classifies definite Eichler orders with class number at most two by bounding candidate fields and order data, computing class numbers, and checking them by explicit ideal-class enumeration. It finds 74 equivalence classes with class number 1 and 172 with class number 2.

Enumeration: 279 totally real fields satisfy the relevant Odlyzko bound: 1, 39, 47, 108, 37, 40, 4, and 3 fields in degrees 1 through 8.No field of degree n ≥9 satisfies the bound.
Enumeration: The computation uses the mass formula to produce a finite list of possible discriminants D and levels N for each field.Candidate orders are then assigned class numbers using the Eichler mass formula.
Verification: Explicit enumeration of ideal classes independently checks the mass-formula computations, and the two methods agree in all cases.The check uses Algorithm 7.10 together with the alternate mass formula.
Equivalence: The classification identifies orders up to field isomorphisms carrying the discriminant and level ideals to their counterparts.Equivalent Eichler orders have the same class number by the mass formula.
Results: There are exactly 74 equivalence classes of definite Eichler orders with class number 1 and 172 with class number 2.The classes are listed in Tables 8.2–8.3 using field degree, field discriminant, and norms of D and N.