Maximal Orders and Decomposition II
The Round 2 Maximal Order Algorithm
The Round 2 algorithm: computing the maximal order prime by prime via radicals and rings of multipliers.
Engineering / MathematicsMaximal Orders and Decomposition II2 min readKV-MATH-0613
Round 2 is the standard algorithm for computing the maximal order. It handles each candidate prime independently and combines the results, and its correctness rests on the Pohst-Zassenhaus theorem.
The structure
The Round 2 algorithm
- Start from the equation orderGenerated by powers of the root of the defining polynomial.
- Compute the discriminantAnd find its square divisors.
- For each candidate prime, testApply the Dedekind criterion.
- Enlarge if neededCompute the p-radical, then the ring of multipliers — see radical computation.
- Iterate at that primeRepeat until the order stops growing.
- Combine across primesTake the sum of the p-maximal orders as modules; normalise by Hermite normal form.
- VerifyThe field discriminant equals the polynomial discriminant divided by the index squared.
Why per-prime work combines
The verification step
Cost
| Stage | Cost driver |
|---|---|
| Discriminant computation | Resultant of degree n polynomials |
| Factoring the discriminant | The dominant and potentially prohibitive cost |
| Per-prime enlargement | Linear algebra over the field with p elements, size n |
| Combination | Hermite normal form on n by n matrices |
Round 4
Output
The output is an integral basis in Hermite normal form with a denominator, plus the field discriminant. Both are needed downstream — see discriminants and integral bases.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 6.1.3-6.1.4. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.