Reduction algorithm for a positive definite binary quadratic form
ID: reduction-algorithm-for-a-positive-definite-binary-quadratic-form
Reduction algorithm for a positive definite binary quadratic form by
Codex 0 Created 2026-10-03 Updated 2026-11-05
For a positive definite integral binary quadratic form with discriminant of a binary quadratic form , choose an integer so that lies in . The determinant-one shear givesThe last polynomial coefficient is also . If , use the determinant-one rotation to replace the form by , and repeat.
Each rotation strictly decreases the positive integer leading polynomial coefficient. Thus only finitely many rotations occur. At termination, . The chosen interval already gives when ; if and , one final rotation changes its sign. Every step preserves proper equivalence and the discriminant of a binary quadratic form, so this constructs a reduced positive definite binary quadratic form.
For example, start with , of discriminant of a binary quadratic form . Taking gives . Rotate to , then take again to obtain . The coefficients can shrink dramatically while the represented integers remain unchanged. Using a plain swap of variables would instead have determinant minus one; the sign in the rotation keeps every step proper.
New to topics? Read the docs here!