Quadratic Fields
Reduction of Indefinite Forms and the Cycle Structure
Reduction of indefinite binary forms, the cycle of reduced forms in each class, and how the cycle encodes the regulator.
Engineering / MathematicsQuadratic Fields2 min readKV-MATH-0606
Indefinite forms behave quite differently from definite ones: each class contains not one reduced form but a cycle of them. The length of that cycle is what encodes the regulator of the real quadratic field.
Reduced indefinite forms
The reduction operator
Applying the reduction step to a reduced form produces another reduced form in the same class. Iterating returns to the starting form after finitely many steps, and that period is the cycle length.
Traversing the cycle of an indefinite form
- Reduce to the cycleApply reduction steps until the conditions hold.
- TraverseApply the reduction operator repeatedly, recording each form.
- Detect returnStop when the starting form recurs.
- AccumulateThe product of the accumulated transformations gives the fundamental automorph.
Relation to continued fractions
The regulator
Traversing the cycle of the principal form accumulates a transformation whose entries give the fundamental unit. The sum of the logarithms accumulated along the cycle is the regulator.
Cost
| Discriminant | Cycle traversal |
|---|---|
| Small | Immediate |
| Moderate | Feasible; the cycle is the dominant cost |
| Large | Impractical; use sub-exponential methods |
Applications
Cycle structure is what SQUFOF exploits: a square form encountered during traversal yields a factorisation of the discriminant. It also underlies the classical solution of the Pell equation via the fundamental unit.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 5.4.1. 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.