Quadratic Fields
Reduction of Positive Definite Binary Forms
Reducing a positive definite binary quadratic form to the unique reduced form in its class, and the resulting class number algorithm.
Engineering / MathematicsQuadratic Fields2 min readKV-MATH-0602
Every positive definite binary form is equivalent to exactly one reduced form. Uniqueness makes reduction a canonical form computation, and it turns class number computation into enumeration.
The reduction conditions
The algorithm
Gauss reduction of a positive definite form
- Normalise the middle coefficientTranslate so that the middle coefficient lies in the interval determined by the first.
- Swap if neededIf the first coefficient exceeds the last, swap them and negate the middle one.
- RepeatContinue until both conditions hold.
- Break tiesApply the final sign convention.
Class number by enumeration
Reduced forms of a given discriminant satisfy explicit bounds on their coefficients. Enumerating all triples within those bounds and keeping the reduced ones counts the classes exactly.
Counting class number by enumeration
- Bound the first coefficientBy the square root of a third of the absolute discriminant.
- Loop over the middle coefficientWithin the reduction bounds and the correct parity.
- Solve for the lastFrom the discriminant relation; discard non-integer results.
- Test reduction and countKeep only reduced forms, applying the tie-break convention.
Relation to lattice reduction
A positive definite binary form is a rank two lattice, and reduction is exactly finding its shortest basis. This is the two-dimensional case of LLL, where the shortest vector can be found exactly rather than approximately — see short vector search.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 5.2. 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.