Software, Tables and Sources
Implementation Pitfalls and Testing Strategy
The recurring implementation errors in this subject and the testing discipline that catches them.
Engineering / MathematicsSoftware, Tables and Sources2 min readKV-MATH-0681
The errors in this subject are characteristically silent. Wrong answers look plausible, and the algorithms rarely crash. Testing discipline is therefore not optional.
The recurring pitfalls
| Pitfall | Where it appears |
|---|---|
| Trailing zero coefficients left after cancellation | Polynomial representation |
| Denominators not reduced to lowest terms | Standard representation |
| Characteristic two or three assumed away | Squarefree factorisation, Weierstrass forms |
| Degree drop of more than one unhandled | Sub-resultant sequences |
| Non-maximal order used as if maximal | Orders |
| Index divisor decomposed by the simple method | Simple decomposition |
| Congruence case split omitted | Quadratic fields |
| Insufficient precision in logarithmic data | Regulators |
| Reduction omitted between multiplications | Ideal reduction |
Why they are silent
Cheap invariant checks
Most of these errors are caught by an invariant check costing far less than the computation that produced the result.
- The sum of ramification index times residue degree must equal the field degree — see the degree relation.
- Norms are multiplicative: the norm of a product equals the product of norms.
- The order discriminant equals the field discriminant times the index squared.
- The unit rank must equal the value given by the signature.
- Class number times regulator must match the analytic formula — see verification.
- Observed Frobenius cycle types must occur in the identified Galois group.
- A factorisation must multiply back to the input.
Test material
Building a test suite
- Use published tablesThe best source of verified answers across a wide range — see published tables.
- Cover the special cases deliberatelyCharacteristic two and three, wild ramification, essential discriminant divisors, defective remainder sequences.
- Cross-check between methodsWhere two independent algorithms compute the same quantity, run both.
- Cross-check between packagesAn independent implementation is the strongest available check.
- Keep every failure as a regression testBugs recur; fixed cases must stay fixed.
Precision as a first-class concern
Prefer libraries
Most of these pitfalls are already handled in mature software. See software packages.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — collection orientation material. 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.