reduced integral binary quadratic forms

Definition 1.

A positive binary form is one where $F\mathit{}\mathrm{(}x\mathrm{,}y\mathrm{)}\mathrm{\ge }\mathrm{0}\mathit{}\mathrm{\forall }x\mathrm{,}y\mathrm{\in }\mathrm{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\mathrm{>}\mathrm{0}$. If and either $a\mathrm{>}\mathrm{0}$ or $c\mathrm{>}\mathrm{0}$, then $F$ is positive.

Proof.

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

Definition 2.

A primitive positive form $a\mathit{}{x}^{\mathrm{2}}\mathrm{+}b\mathit{}x\mathit{}y\mathrm{+}c\mathit{}{y}^{\mathrm{2}}$ is reduced if

$$|b|\le a\le c\mathit{\text{, and }}b\ge 0\mathit{\text{ if either }}|b|=a\mathit{\text{ or }}a=c$$

This is equivalent to saying that $\mathrm{-}a\mathrm{\le }b\mathrm{\le }a\mathrm{\le }c$ and that $b$ can be negative only if or . Thus $\mathrm{(}\mathrm{3}\mathrm{,}\mathrm{-}\mathrm{2}\mathrm{,}\mathrm{4}\mathrm{)}$ is reduced, but $\mathrm{(}\mathrm{3}\mathrm{,}\mathrm{-}\mathrm{2}\mathrm{,}\mathrm{3}\mathrm{)}$ 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 $\mathrm{\Delta }\mathrm{\ne }\mathrm{-}\mathrm{3}$, $F\mathit{}\mathrm{(}x\mathrm{,}y\mathrm{)}\mathrm{=}a\mathit{}{x}^{\mathrm{2}}\mathrm{+}b\mathit{}x\mathit{}y\mathrm{+}c\mathit{}{y}^{\mathrm{2}}$, then the minimum value assumed by $F$ if $x\mathrm{,}y$ are not both zero is $a$. If , then this value is assumed only for $\mathrm{(}x\mathrm{,}y\mathrm{)}\mathrm{=}\mathrm{(}\mathrm{\pm }\mathrm{1}\mathrm{,}\mathrm{0}\mathrm{)}$; if $a\mathrm{=}c$; it is assumed for $\mathrm{(}x\mathrm{,}y\mathrm{)}\mathrm{=}\mathrm{(}\mathrm{\pm }\mathrm{1}\mathrm{,}\mathrm{0}\mathrm{)}$ and $\mathrm{(}x\mathrm{,}y\mathrm{)}\mathrm{=}\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{\pm }\mathrm{1}\mathrm{)}$.

Proof.

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

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

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

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

If $a=c$, then $|b|\ne 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\ne 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\mathrm{,}G$ are primitive positive reduced forms with $F\mathrm{\sim }G$, then $F\mathrm{=}G$.

Proof.

We take the cases $\mathrm{\Delta }\ne -3$ and $\mathrm{\Delta }=-3$ separately.

First assume $\mathrm{\Delta }\ne -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=a{x}^2+bxy+c{y}^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 , 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 }\ge 0$. So $b=b^{\prime }=0$ and we are done.

Finally, in the case $\mathrm{\Delta }=-3$, we see that for any such reduced form, $3=4ac-b^2\ge 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|\le a\le c$. Among all forms properly equivalent to the given one, choose $F(x,y)=a{x}^2+bxy+c{y}^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)=a{x}^2+(2am+b)xy+c^{\prime }{y}^2$$

is properly equivalent to $F$, and we can choose $m$ so that , contradicting our choice of minimal $|b|$. So $|b|\le a$; similarly, $|b|\le 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)=a{x}^2+bxy+c{y}^2$, where $|b|\le a\le c$, then $F$ is properly equivalent to a reduced form. The form is already reduced unless and either $a=-b$ or $a=c$. But in these cases, the form $G(x,y)=a{x}^2-bxy+c{y}^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 $a{x}^2-axy+c{y}^2$ to $a{x}^2+axy+c{y}^2$, while if $a=c$, then $(x,y)\mapsto (-y,x)$ takes $a{x}^2+bxy+a{y}^2$ to $a{x}^2-bxy+a{y}^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\mathit{}\mathrm{(}x\mathrm{,}y\mathrm{)}\mathrm{=}a\mathit{}{x}^{\mathrm{2}}\mathrm{+}b\mathit{}x\mathit{}y\mathrm{+}c\mathit{}{y}^{\mathrm{2}}$ is a positive reduced form with , then $a\mathrm{\le }\sqrt{\frac{\mathrm{|}\mathrm{\Delta }\mathrm{|}}{\mathrm{3}}}$.

Proof.

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

Definition 3.

If , then $h\mathrm{}\mathrm{(}\mathrm{\Delta }\mathrm{)}$ is the number of classes of primitive positive forms of discriminant $\mathrm{\Delta }$.

Corollary 6.

If , then $h\mathit{}\mathrm{(}\mathrm{\Delta }\mathrm{)}$ is finite, and $h\mathit{}\mathrm{(}\mathrm{\Delta }\mathrm{)}$ is equal to the number of primitive positive reduced forms of discriminant $\mathrm{\Delta }$.

Proof.

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

Examples: $\mathrm{\Delta }=-4$: $b^2-4ac=-4\Rightarrow b$ even, $|b|\le |a|\le \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(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.

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

$(1,1,6)$
$(1,-1,6)$	not reduced since ; properly equivalent to $(1,1,6)$ via $(x,y)\mapsto (x+y,y)$
$(2,1,3)$
$(2,-1,3)$	reduced since $b|\ne a,a\ne c$

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

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

$(1,1,14)$
$(1,-1,14)$	not reduced since , properly equivalent to $(1,1,14)$ via $(x,y)\mapsto (x+y,y)$
$(2,1,7)$
$(2,-1,7)$	reduced since $|b|\ne a,a\ne c$
$(4,3,4)$
$(4,-3,4)$	not reduced since , equivalent to $(4,3,4)$ via $(x,y)\mapsto (-y,x)$

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

$\mathrm{\Delta }=-163$: $b^2-4ac=-163\Rightarrow b$ odd, $|b|\le |a|\le \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 , 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
Canonical name	ReducedIntegralBinaryQuadraticForms
Date of creation	2013-03-22 19:18:52
Last modified on	2013-03-22 19:18:52
Owner	rm50 (10146)
Last modified by	rm50 (10146)
Numerical id	4
Author	rm50 (10146)
Entry type	Definition
Classification	msc 11E12
Classification	msc 11E16
Related topic	integralbinaryquadraticforms