Maximal Orders and Decomposition II
Radical Computation and the Ring of Multipliers
Computing the p-radical of an order as a kernel, and the ring of multipliers that enlarges the order.
Engineering / MathematicsMaximal Orders and Decomposition II2 min readKV-MATH-0614
The two linear algebra computations inside Round 2 are the p-radical and the ring of multipliers. Both reduce to kernels, which is what makes the algorithm practical.
The p-radical
The radical consists of elements whose image modulo p is nilpotent. Nilpotency is detected by raising to a sufficiently high power of p, which is a linear map because Frobenius is linear.
Computing the p-radical
- Build the quotientRepresent the order modulo p as a vector space over the field with p elements.
- Construct the mapCompute the matrix of the p-to-the-k power map on the basis.
- Take the kernelBy elimination over the field.
- LiftPull the kernel back to a module between pO and O.
The ring of multipliers
Given the radical, the ring of multipliers consists of field elements multiplying it into itself. This is again a kernel computation, on the map sending an element to the induced action on the quotient.
Computing the ring of multipliers
- Set up the actionFor each basis element of the order, compute its multiplication action on the radical modulo the radical.
- Assemble the matrixStack the actions into one matrix.
- Take the kernelElements acting trivially give the multipliers.
- Scale and normaliseDivide by p and combine with the original order; reduce to Hermite normal form.
Verification
The connection to decomposition
The radical is the intersection of the primes above p, so its quotient structure carries the decomposition data. Splitting that quotient is exactly what Buchmann-Lenstra does — see also algebra splitting.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 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.