= Reduction algorithm for a positive definite binary quadratic form
For a positive definite integral <binary quadratic form> $[a,b,c]$ with <discriminant of a binary quadratic form> $D<0$, choose an <integer> $q$ so that $b'=b+2aq$ lies in $-a<b'\leq a$. The determinant-one shear $(x,y)\mapsto(x+qy,y)$ gives
$$
[a,b,c]\longmapsto[a,b+2aq,aq^2+bq+c].
$$
The last <polynomial coefficient> is also $c'=(b'^2-D)/(4a)$. If $c'<a$, use the determinant-one rotation $(x,y)\mapsto(-y,x)$ to replace the form by $[c',-b',a]$, and repeat.
Each rotation strictly decreases the positive <integer> leading <polynomial coefficient>. Thus only finitely many rotations occur. At termination, $|b'|\leq a\leq c'$. The chosen interval already gives $b'\geq0$ when $|b'|=a$; if $a=c'$ and $b'<0$, 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 $[5,16,13]$, of <discriminant of a binary quadratic form> $-4$. Taking $q=-2$ gives $[5,-4,1]$. Rotate to $[1,4,5]$, then take $q=-2$ again to obtain $[1,0,1]$. 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.
Back to article page