# reduced integral binary quadratic forms

###### Definition 1.

A positive binary form is one where $F(x,y)\geq 0\ \forall x,y\in\mathbb{Z}$.

This article deals only with positive integral binary quadratic forms (i.e. those with negative discriminant and with $a>0$). Some but not all of this theory applies to forms with positive discriminant.

###### Proposition 1.

If $F$ is positive, then $a>0$. If $\Delta(F)<0$ and either $a>0$ or $c>0$, then $F$ is positive.

###### Proof.

If $F$ is positive, then $F(1,0)=a$, so $a>0$.
If $\Delta(F)<0$, then $4aF(x,y)=(2ax+by)^{2}-\Delta y^{2}\geq 0$. Thus if $a>0$, then $F(x,y)\geq 0$. The proof for the case $c>0$ is identical. ∎

###### Definition 2.

A primitive positive form $ax^{2}+bxy+cy^{2}$ is reduced if

 $|b|\leq a\leq c\text{, and }b\geq 0\text{ if either }|b|=a\text{ or }a=c$

This is equivalent to saying that $-a\leq b\leq a\leq c$ and that $b$ can be negative only if $a or $-a. Thus $(3,-2,4)$ is reduced, but $(3,-2,3)$ is not.

It turns out that each proper equivalence class of primitive positive forms contains a single reduced form, and thus we can understand how many classes there are of a given discriminant by studying only the reduced forms.

###### Theorem 2.

If $F$ is a primitive positive reduced form with discriminant $\Delta\neq-3$, $F(x,y)=ax^{2}+bxy+cy^{2}$, then the minimum value assumed by $F$ if $x,y$ are not both zero is $a$. If $a, then this value is assumed only for $(x,y)=(\pm 1,0)$; if $a=c$; it is assumed for $(x,y)=(\pm 1,0)$ and $(x,y)=(0,\pm 1)$.

###### Proof.

Since $|b|\leq a\leq c$, it follows that

 $F(x,y)\geq(a-|b|+c)\min(x^{2},y^{2})$

Thus, $F(x,y)\geq a-|b|+c$ whenever $xy\neq 0$, while if $x$ or $y$ is zero, then $F(x,y)\geq a$. So $a$ is clearly the smallest nonzero value of $F$.

If $a, then $F(x,y)\geq a+(c-|b|)>a$ if $xy\neq 0$, and $F(0,y)\geq c>a$ for $y\neq 0$, so $F$ achieves its minimum only at $(x,y)=(\pm 1,0)$.

If $a=c$, then $|b|\neq a$ since otherwise $F$ is not reduced (we cannot have $a=c=1,b=\pm 1$ else we have a form of discriminant $-3$). Thus again $c-|b|>0$ and thus $F(x,y)>a$ if $xy\neq 0$, so in this case the result follows as well. ∎

Note that the reduced form of discriminant $-3$, $x^{2}+xy+y^{2}$, also achieves its minimum value at $(1,-1),(-1,1)$.

###### Theorem 3.

If $F,G$ are primitive positive reduced forms with $F\sim G$, then $F=G$.

###### Proof.

We take the cases $\Delta\neq-3$ and $\Delta=-3$ separately.

First assume $\Delta\neq-3$ so we can apply the above theorem.

Since $F\sim G$, we can write $G(x,y)=F(\alpha x+\beta y,\gamma x+\delta y)$ with $\alpha\delta-\beta\gamma=1$. Suppose $F=ax^{2}+bxy+cy^{2},G=a^{\prime}x^{2}+b^{\prime}xy+c^{\prime}y^{2}$. Now, $F$ and $G$ have the same minimum value, so $a=a^{\prime}$.

If $a, then $F$ achieves its minimum only at $(pm1,0)$, so $a=a^{\prime}=G(1,0)=F(\alpha,\gamma)$ and thus $\alpha=\pm 1,\gamma=0$. So $G(x,y)=F(\pm x+ry,\pm y)$ and thus $b^{\prime}=b+2ra$. Since $G$ is also reduced, $b=b^{\prime}$ and thus $c=c^{\prime}$ and $F=G$.

If instead $a=c$, then instead of concluding that $\alpha=\pm 1$ we can only conclude that $\alpha=\pm 1$ or $\gamma=\pm 1$. If $\alpha=\pm 1$, the argument carries through as above. If $\gamma=\pm 1$, then $\alpha=0,\beta=\mp 1$, so $G(x,y)=F(\mp y,\pm x+ry)$ and thus $b^{\prime}=\pm 2cr-b$. Thus $b^{\prime}=-b$. But then $c=c^{\prime}$ since the discriminants are equal, and thus both $b,b^{\prime}\geq 0$. So $b=b^{\prime}=0$ and we are done.

Finally, in the case $\Delta=-3$, we see that for any such reduced form, $3=4ac-b^{2}\geq 4a^{2}-a^{2}=3a^{2}$, so $a=1,b=\pm 1,c=1$. Thus $b=1$ since otherwise the form is not reduced. So the only reduced form of discriminant $-3$ is in fact $x^{2}+xy+y^{2}$. ∎

###### Theorem 4.

Every primitive positive form is properly equivalent to a unique reduced form.

###### Proof.

We just proved uniqueness, so we must show existence. Note that I used a different method of proof in class that relied on “infinite descent” to get the result in the first paragraph below; the method here is just as good but provides less insight into how to actually reduce a form.

We first show that any such form is properly equivalent to some form satisfying $|b|\leq a\leq c$. Among all forms properly equivalent to the given one, choose $F(x,y)=ax^{2}+bxy+cy^{2}$ such that $|b|$ is as small as possible (there may be multiple such forms; choose one of them). If $|b|>a$, then

 $G(x,y)=F(x+my,y)=ax^{2}+(2am+b)xy+c^{\prime}y^{2}$

is properly equivalent to $F$, and we can choose $m$ so that $|2am+b|<|b|$, contradicting our choice of minimal $|b|$. So $|b|\leq a$; similarly, $|b|\leq c$. Finally, if $a>c$, simply interchange $a$ and $c$ (by applying the proper equivalence $(x,y)\mapsto(-y,x)$) to get the required form.

To finish the proof, we show that if $F(x,y)=ax^{2}+bxy+cy^{2}$, where $|b|\leq a\leq c$, then $F$ is properly equivalent to a reduced form. The form is already reduced unless $b<0$ and either $a=-b$ or $a=c$. But in these cases, the form $G(x,y)=ax^{2}-bxy+cy^{2}$ is reduced, so it suffices to show that $F$ and $G$ are properly equivalent. If $a=-b$, then $(x,y)\mapsto(x+y,y)$ takes $ax^{2}-axy+cy^{2}$ to $ax^{2}+axy+cy^{2}$, while if $a=c$, then $(x,y)\mapsto(-y,x)$ takes $ax^{2}+bxy+ay^{2}$ to $ax^{2}-bxy+ay^{2}$. ∎

Let’s see how to reduce $82x^{2}+51xy+8y^{2}$ to $x^{2}+xy+6y^{2}$:

Form Transformation Result
$82x^{2}+51xy+8y^{2}$ $(x,y)\mapsto(-y,x)$ $8x^{2}-51xy+82y^{2}$
$8x^{2}-51xy+82y^{2}$ $(x,y)\mapsto(x+3y,y)$ $8(x+3y)^{2}-51(x+3y)y+82y^{2}=$
$8x^{2}+48xy+72y^{2}-51xy-153y^{2}+82y^{2}=$
$8x^{2}-3xy+y^{2}$
$8x^{2}-3xy+y^{2}$ $(x,y)\mapsto(-y,x)$ $x^{2}+3xy+8y^{2}$
$x^{2}+3xy+8y^{2}$ $(x,y)\mapsto(x-y,y)$ $(x-y)^{2}+3(x-y)y+8y^{2}=x^{2}+xy+6y^{2}$
$x^{2}+xy+6y^{2}$
###### Theorem 5.

If $F(x,y)=ax^{2}+bxy+cy^{2}$ is a positive reduced form with $\Delta<0$, then $a\leq\sqrt{\frac{|\Delta|}{3}}$.

###### Proof.

$-\Delta=4ac-b^{2}\geq 4a^{2}-a^{2}$ since the form is reduced. So $-\Delta\geq 3a^{2}$, and the result follows. ∎

###### Definition 3.

If $\Delta<0$, then $h(\Delta)$ is the number of classes of primitive positive forms of discriminant $\Delta$.

###### Corollary 6.

If $\Delta<0$, then $h(\Delta)$ is finite, and $h(\Delta)$ is equal to the number of primitive positive reduced forms of discriminant $\Delta$.

###### Proof.

Essentially obvious. Since every positive form is properly equivalent to a (unique) reduced form, $h(\Delta)$ is clearly equal to the number of positive reduced forms of discriminant $\Delta$. But given a reduced form of discriminant $\Delta$, there are only finitely many choices for $a>0$, by the proposition. This constrains us to finitely many choices for $b$, since $-a. $a$ and $b$ determine $c$ since $\Delta$ is fixed. ∎

Examples: $\Delta=-4$: $b^{2}-4ac=-4\Rightarrow b$ even, $|b|\leq|a|\leq\sqrt{\frac{4}{3}}\Rightarrow b=0$. So $(1,0,1)$, corresponding to $x^{2}+y^{2}$, is the only reduced form of discriminant $-4$. Note that this provides another proof that primes $\equiv 1\pod{4}$ are representable as the sum of two squares, since all such primes have $\left(\frac{-4}{p}\right)=\left(\frac{-1}{p}\right)=1$ and thus are representable by this quadratic form.

$\Delta=-23$: $b^{2}-4ac=-23\Rightarrow b$ odd, $|b|\leq a\leq\sqrt{\frac{23}{3}}\Rightarrow b=\pm 1$. So $ac=6,a. This gives us

$(1,\phantom{-}1,6)$ not reduced since $|b|=a,b<0$; properly equivalent to $(1,1,6)$ via $(x,y)\mapsto(x+y,y)$ reduced since $b|\neq a,a\neq c$

There are three equivalence classes of positive reduced forms with discriminant $-23$.

$\Delta=-55$: $4ac-b^{2}=55$, so $b$ is odd, $|b|\leq\sqrt{\frac{55}{3}}\Rightarrow|b|=1,\pm 3$. So $ac=14\text{ or }16,a\leq c$. So the forms are

$(1,\phantom{-}1,14)$ not reduced since $|b|=a,b<0$, properly equivalent to $(1,1,14)$ via $(x,y)\mapsto(x+y,y)$ reduced since $|b|\neq a,a\neq c$ not reduced since $a=c,b<0$, equivalent to $(4,3,4)$ via $(x,y)\mapsto(-y,x)$

There are four classes of forms of discriminant $-55$.

$\Delta=-163$: $b^{2}-4ac=-163\Rightarrow b$ odd, $|b|\leq|a|\leq\sqrt{\frac{163}{3}}\cong\sqrt{55}$. So $b=\pm 1,\pm 3,\pm 5,\pm 7$, and $ac=\frac{b^{2}+163}{4}$, so $ac=41,43,45,47$. Since $a, we must have $a=1$; thus $b=\pm 1$ and thus we get only $(1,\pm 1,41)$. But $(1,-1,41)$ is properly equivalent to $(1,1,41)$ via $(x,y)\mapsto(x+y,y)$, so there is only one equivalence class of positive reduced forms with discriminant $-163$.

Title reduced integral binary quadratic forms ReducedIntegralBinaryQuadraticForms 2013-03-22 19:18:52 2013-03-22 19:18:52 rm50 (10146) rm50 (10146) 4 rm50 (10146) Definition msc 11E12 msc 11E16 integralbinaryquadraticforms