Equivalence and Reduction of Binary Forms

Reduction of positive definite binary quadratic forms is the concrete engine behind computing the class number $h(D)$ of the imaginary quadratic field $\mathbb{Q}(\sqrt{D})$, since the class group of that field is isomorphic to the group of $SL_2(\mathbb{Z})$-classes of primitive forms of discriminant $D$ under Gauss composition — a bridge that turns purely elementary coefficient inequalities into deep statements about factorization of ideals in Quadratic Fields. The same reduction algorithm, run in reverse for indefinite forms, becomes the continued fraction algorithm for computing fundamental solutions of the Pell equation, the subject taken up next in Pell's Equation and Continued Fractions. In computational number theory and cryptography, reduced binary forms of large negative discriminant give a concrete, efficiently manipulable model of class groups used in cryptographic protocols (form-class-group based schemes, analogous in spirit to elliptic curve groups), while in the geometry of numbers, reduction generalizes to Minkowski-reduced bases of lattices in higher dimensions, feeding into lattice-based cryptography and the LLL algorithm. Finally, the reduced representative realizing the minimal value $a\le\sqrt{|D|/3}$ gives explicit, sharp bounds used whenever one needs to bound the smallest integer represented by a given quadratic form, a recurring lemma throughout the theory built on Binary Quadratic Forms: Introduction.

Ask the tutor: Can you walk through Gauss composition of two reduced forms of the same discriminant to see how the class set becomes a group?

Think of a positive definite form as an ellipse: $f(x,y)=n$ traces an ellipse in the plane for each $n>0$, and the values represented by $f$ are exactly the levels at which some lattice point $(x,y)\in\mathbb{Z}^2$ lies on that ellipse. Changing variables by $\gamma \in SL_2(\mathbb{Z})$ does not change the lattice $\mathbb{Z}^2$ at all — it only relabels which pair of integers we call "$(x,y)$" — so it cannot change which values are hit. Equivalence of forms is thus the statement that the same quadratic shape, viewed through two different integer bases of the same lattice, produces two algebraically different-looking formulas $(a,b,c)$ and $(a',b',c')$. Reduction picks out, among all bases of that lattice, the one made from the two shortest linearly independent vectors, ordered and oriented in a fixed way. Concretely, $a=f(1,0)$ is the squared length (in the metric defined by $f$) of the first basis vector, $c=f(0,1)$ of the second, and $b$ measures their "angle." The condition $a \le c$ says the first vector is at least as short as the second; $|b|\le a$ says the angle between them is at least $60^\circ$-ish (no shorter vector can be built by adding/subtracting one basis vector from the other); the sign convention on $b$ removes the last two-fold ambiguity (reflection). This is exactly Gauss's reduction of positive definite quadratic forms, the two-dimensional case of Minkowski reduction of lattices.

Example 1 — Reducing an asymmetric form. Take $f=(a,b,c)=(7,6,4)$, i.e. $f(x,y)=7x^2+6xy+4y^2$. First compute the discriminant:

Check positive definiteness: $a=7>0$ and $D<0$, so yes. We follow the descent algorithm. Currently $a=7 > c=4$, so the coefficient is not yet minimal in position; apply $S=\begin{pmatrix}0&-1\\1&0\end{pmatrix}$, which sends $(a,b,c)\mapsto(c,-b,a)$:

Check: this should have the same discriminant. $(-6)^2 - 4(4)(7) = 36-112=-76$. Good, matches $D=-76$. Now $(a,b,c)=(4,-6,7)$: we need $|b|\le a$, but $|-6|=6>4=a$. Apply $T_n$ with $n$ chosen so $b+2an=-6+8n$ has smallest absolute value; try $n=1$: $-6+8=2$, and $|2|\le 4$. Good, take $n=1$.

Check discriminant: $2^2-4(4)(5)=4-80=-76$. Correct. Now $(a,b,c)=(4,2,5)$: check reduced conditions. $|b|=2 \le a=4 \le c=5$. Since $|b|=2 \neq a=4$ and $a=4\ne c=5$, the boundary sign condition is vacuous. This form is reduced.

Verification of equivalence directly: the composite matrix is $T_1 S$. Compute

determinant $1\cdot0-(-1)\cdot1=1$, confirming $T_1S\in SL_2(\mathbb{Z})$. Direct check: with $\gamma=\begin{pmatrix}1&-1\\1&0\end{pmatrix}$, $(\gamma\cdot f)(x,y) = f(x-y,x)$. Compute

This does not match $(4,2,5)$ — because the correct composition order for iterated substitution is $\gamma = \gamma_1 \circ \gamma_2$ applied as $g = \gamma_2\cdot(\gamma_1\cdot f)$ corresponds to the matrix product $\gamma_1\gamma_2$ acting via $f(\gamma_1\gamma_2 \mathbf{v})$; let us redo this carefully with the correct order $S$ first, then $T_1$: the composite substitution is $\mathbf{v}\mapsto T_1(S\mathbf v)$, i.e. matrix $T_1 S$ as above, but the action convention $(\gamma\cdot f)(\mathbf v)=f(\gamma\mathbf v)$ means we apply $S$ then $T_1$ reading right to left on vectors, matching $\gamma=T_1S$. Let's just verify numerically instead: with $\gamma=T_1S=\begin{pmatrix}1&-1\\1&0\end{pmatrix}$, so $p=1,q=-1,r=1,s=0$, we get $(\gamma\cdot f)(x,y)=f(x-y,x)$ exactly as above, giving $17x^2-20xy+7y^2$ — discriminant $(-20)^2-4(17)(7)=400-476=-76$, consistent, but not equal to $(4,2,5)$. The resolution is that composition of the form action reverses matrix order: if $g=\gamma_1\cdot f$ and $h=\gamma_2\cdot g$, then $h(\mathbf v)=g(\gamma_2\mathbf v)=f(\gamma_1\gamma_2\mathbf v)$, so $h=(\gamma_1\gamma_2)\cdot f$. We performed $S$ first ($g=S\cdot f$) and then $T_1$ ($h=T_1\cdot g$), so $h = (S T_1)\cdot f$, matrix product $ST_1$, not $T_1S$. Recompute:

With $\gamma=\begin{pmatrix}0&-1\\1&1\end{pmatrix}$: $(\gamma\cdot f)(x,y) = f(-y, x+y) = 7y^2 + 6(-y)(x+y)+4(x+y)^2$

This matches $(4,2,5)$ exactly. So indeed $(7,6,4)\sim(4,2,5)$ via $\gamma=\begin{pmatrix}0&-1\\1&1\end{pmatrix}\in SL_2(\mathbb Z)$, and $(4,2,5)$ is the reduced form of this class.

Example 2 — A discriminant with two classes. Let $D=-20$. By the corollary, any reduced form $(a,b,c)$ satisfies $a\le\sqrt{20/3}\approx2.58$, so $a\in\{1,2\}$. Case $a=1$: then $|b|\le1$ so $b\in\{-1,0,1\}$; reducedness requires $b\ge0$ when $|b|=a=1$, so $b=-1$ is excluded, leaving $b\in\{0,1\}$. From $b^2-4c=-20$: if $b=0$, $c=5$, giving $(1,0,5)$, and $a=1\le c=5$, valid, reduced (boundary conditions: $|b|=0\ne a=1$, and $a=1\ne c=5$, vacuous). If $b=1$: $1-4c=-20\Rightarrow c=21/4\notin\mathbb Z$, discard. Case $a=2$: $|b|\le2$, $b\in\{-2,-1,0,1,2\}$; reduced requires $b\ge0$ when $|b|=a=2$, excluding $b=-2$; and when $a=c$ requires $b\geq 0$ (relevant if $c=2$). From $b^2-4(2)c=-20$, i.e. $8c=b^2+20$:

• $b=0$: $8c=20$, not integer.
• $b=1$: $8c=21$, not integer.
• $b=2$: $8c=24\Rightarrow c=3$. Check $a=2\le c=3$: valid. Form $(2,2,3)$, reduced (since $|b|=a=2$ we needed $b\ge0$: satisfied).
• $b=-1$: $8c=21$, not integer.

So the reduced forms of discriminant $-20$ are exactly $(1,0,5)$ and $(2,2,3)$, giving

As a sanity check on distinctness: $(1,0,5)$ represents $1=f(1,0)$, but the minimum nonzero value of $(2,2,3)$ is $a=2$ (by the Corollary), so $(2,2,3)$ can never represent $1$; since represented sets are equivalence invariants (Lemma), the two forms are genuinely inequivalent, confirming $h(-20)=2$ is correct and not an artifact of the coefficient search.