PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (197)
Orphanage
Unclass'd
Unproven (498)
Corrections (22)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
integral binary quadratic forms (Topic)

This article develops the theory of integral binary quadratic forms invented by Gauss and developed by Gauss, Lagrange, and Legendre. The principal results are Theorem 8, which states that each positive integral binary quadratic form is properly equivalent to a unique reduced form, and Corollary 10, which states that for any given (negative) discriminant, there are a finite number of reduced forms of that discriminant. We also give a computational method for determining all reduced forms of a given discriminant.

An integral binary quadratic form is a quadratic form in two variables whose coefficients are integral, i.e. a polynomial

% latex2html id marker 1376 $\displaystyle F(x,y)=ax^2+bxy+cy^2, a,c\neq 0, a,b,c\in\mathbb{Z}$

Such a form is said to represent an integer $ n$ if there are $ r,s\in\mathbb{Z}$ such that $ F(r,s)=n$. If $ \gcd(r,s)=1$, $ F$ is said to represent $ n$ properly. The form is said to be primitive if its coefficients are relatively prime (i.e. $ \gcd(a,b,c)=1$).

We will use the terms “integral form”, “binary quadratic form”, and simply “form” interchangeably in what follows.

Using the definition of form equivalence given in the article on quadratic forms, we se that two forms $ F(x,y)$ and $ G(x,y)$ are equivalent if there is an invertible matrix $ M\in GL(2,\mathbb{Z})$ such that

$\displaystyle G(x,y)=F(M(x,y)^T)$
Invertible matrics in $ GL(2,\mathbb{Z})$ are matrices with determinant $ \pm 1$. So if $ \alpha,\beta,\gamma, \delta\in\mathbb{Z}$ and
$\displaystyle det\left( \begin{array}{cc} \alpha & \gamma \ \beta & \delta \end{array}\right) = \pm 1 $
then if
$\displaystyle G(x,y)=F(\alpha x + \beta y, \gamma x+\delta y)$
it follows that $ G$ is equivalent to $ F$.

An equivalence is a proper equivalence if the determinant of $ M$ is $ +1$, and an improper equivalence otherwise. If $ F$ is properly equivalent to $ G$, we write $ F\sim G$.

Note that while both equivalence and proper equivalence are equivalence relations, improper equivalence is not. For if $ F$ is improperly equivalent to $ G$ and $ G$ is improperly equivalent to $ H$, then the product of the transformation matrices has determinant $ 1$, so that $ F$ is properly equivalent to $ H$.

Since proper equivalence is an equivalence relation, we will say that two forms are in the same class if they are properly equivalent.

$ GL(2,\mathbb{Z})$ is generated as a multiplicative group by the two matrices

$\displaystyle \begin{pmatrix}1&0\\ 1&1\end{pmatrix},\quad\begin{pmatrix}0&1\\ 1&0\end{pmatrix}$
so in particular we see that we can construct all equivalence transformations by composing the following three transformations:
Transformation Matrix Determinant
$ (x,y)\mapsto(y,x)$ $ \left(\begin{array}{cc}0&1\\ 1&0\end{array}\right)$ $ -1$
$ (x,y)\mapsto(y,-x)$ $ \left(\begin{array}{cc}0&-1\\ 1&0\end{array}\right)$ $ 1$
$ (x,y)\mapsto(x+dy,y)$ $ \left(\begin{array}{cc}1&0\\ d&1\end{array}\right)$ $ 1$

Example: Let $ F(x,y)=x^2+xy+6y^2$, $ G(x,y)=82x^2+51xy+8y^2$. Then

$\displaystyle G(x,y)=F(\alpha x + \beta y, \gamma x+\delta y)=F(4x+y,3x+y)$
so
$\displaystyle \left( \begin{array}{cc} \alpha & \gamma \ \beta & \delta \end{array}\right) = \left( \begin{array}{cc} 4 & 3 \ 1 & 1 \end{array}\right) $
The transformations to map $ F$ into $ G$ are
$\displaystyle x^2+xy+6y^2$   $\displaystyle (x,y)\mapsto(x+y,y)$  
$\displaystyle x^2+3xy+8y^2$   $\displaystyle (x,y)\mapsto(y,x)$  
$\displaystyle 8x^2+3xy+y^2$   $\displaystyle (x,y)\mapsto(x+3y,y)$  
$\displaystyle 8x^2+51xy+82y^2$   $\displaystyle (x,y)\mapsto(y,x)$  
$\displaystyle 82x^2+51xy+8y^2$      

and
$\displaystyle \left( \begin{array}{cc} 4 & 3 \ 1 & 1 \end{array}\right)= \lef... ...\end{array}\right) \left( \begin{array}{cc} 1 & 0 \ 1 & 1 \end{array}\right) $

Example: % latex2html id marker 1505 $ F(x,y)=ax^2+bxy+cy^2$ and % latex2html id marker 1507 $ G(x,y)=ax^2-bxy+cy^2$ are always improperly equivalent via the transformation $ (x,y)\mapsto (x,-y)$. They are sometimes properly equivalent, and sometimes not (we will see this later).

Theorem 1   If $ F, G$ are equivalent integral quadratic forms, then $ F$ and $ G$ represent the same set of integers.
Proof. Write $ G(x,y)=F(\alpha x+\beta y, \gamma x+\delta y)$ where
$\displaystyle det\left( \begin{array}{cc} \alpha & \gamma \ \beta & \delta \end{array}\right) = \pm 1 $
Then $ m=G(r,s) \Rightarrow m=F(\alpha r+\beta s,\gamma r+\delta s)$, so if $ G$ represents $ m$, so does $ F$. Since the matrix has determinant 1, it is invertible and its inverse is another integer matrix, so the reverse statement follows as well. $ \qedsymbol$
Lemma 2   $ F$ properly represents an integer $ m$ if and only if $ F$ is properly equivalent to a form $ mx^2+Bxy+Cy^2$.
Proof. $ \Leftarrow$: It is obvious by the above that $ F$ represents $ m$; the problem is to show that it represents $ m$ properly. Write $ G(x,y)=mx^2+Bxy+Cy^2$; then $ G(x,y)=F(\alpha x+\beta y,\gamma x+\delta y)$, where $ \alpha\delta-\beta\gamma=1$. Then $ m=G(1,0)=F(\alpha,\gamma)$. But clearly $ (\alpha,\gamma)=1$ since otherwise we cannot have $ \alpha\delta-\beta\gamma=1$. So $ F$ represents $ m$ properly.
$ \Rightarrow$: Write $ F(p,q)=m$, where $ (p,q)=1$. Since $ (p,q)=1$, we can find integers $ r,s$ such that $ ps-qr=1$, and then
\begin{multline*} F(px+ry,qx+sy)=a(px+ry)^2+b(px+ry)(qx+sy)+c(qx+sy)^2\ =(ap^2... ...=F(p,q)x^2+(2apr+bps+bqr+2cqs)xy+F(r,s)y^2=mx^2+Bxy+Cy^2\qedhere \end{multline*}

$ \qedsymbol$
Definition 1   If $ F$ is a binary quadratic form, its discriminant, $ \Delta(F)$ is $ b^2-4ac$.

Note that $ \Delta(F)$ is always either congruent to 0 or $ 1$ mod 4, and that $ b$ is even (odd) exactly when $ \Delta(F)\equiv 0 (1) \pmod 4$.

Theorem 3   If $ F, G$ are equivalent integral quadratic forms, then $ \Delta(F)=\Delta(G)$.
Proof. For any form $ F$, define
$\displaystyle M_F=\left( \begin{array}{cc} 2a & b \ b & 2c \end{array}\right) $
Then
$\displaystyle 2F(x,y)=(x$ $\displaystyle y)M_F\left(\begin{array}{c} x \ y\end{array}\right) $
Note further that $ \Delta(F)=-det(M_F)$.

Now in our particular case, if $ G(x,y)=F(\alpha x + \beta y, \gamma x+\delta y)$, then

$\displaystyle 2G(x,y) = (\alpha x + \beta y$  $\displaystyle \gamma x+\delta y)M_F\left(\begin{array}{c} \alpha x + \beta y \ \gamma x+\delta y\end{array}\right)=(x$ $\displaystyle y)\left( \begin{array}{cc} \alpha & \gamma \ \beta & \delta \en... ...ma & \delta \end{array}\right)\left(\begin{array}{c} x \ y\end{array}\right) $
Hence
$\displaystyle M_G = \left( \begin{array}{cc} \alpha & \gamma \ \beta & \delta... ...\left( \begin{array}{cc} \alpha & \beta \ \gamma & \delta \end{array}\right) $
But $ \Delta(F) = -det(M_F)$, so since $ det\left( \begin{array}{cc} \alpha & \gamma \ \beta & \delta \end{array}\rig... ...t( \begin{array}{cc} \alpha & \beta \ \gamma & \delta \end{array}\right)=\pm1$,
$\displaystyle \Delta(G)=-det(M_G)=-det\left( \begin{array}{cc} \alpha & \gamma ... ...pha & \beta \ \gamma & \delta \end{array}\right)=-det(M_F)=\Delta(F)\qedhere $
$ \qedsymbol$

Note that this proof shows that applying a set of transformations amount to multiplying by the transform matrix on the left and its transpose on the right.

Example: In the previous example, note that $ \Delta(F) = 1-4\cdot 1\cdot 6=-23$, and $ \Delta(G)=51^2-4\cdot 82\cdot 8 = 2601-2624=-23$.

The converse of this theorem is not true - that is, there are forms of the same discriminant that represent different numbers. For example, $ x^2+5y^2$ and $ 2x^2+2xy+3y^2$ both have discriminant $ -20$, yet the second form represents $ 2$ while the first clearly does not.

A natural question is whether we can classify forms of a given discriminant based on the numbers they represent; this investigation begins with the following theorem:

Theorem 4   Let $ p$ be an odd prime. Suppose $ F,G$ both represent $ p$ and $ \Delta(F)=\Delta(G)$. Then $ F\sim G$.
Proof. Since $ p$ is prime, $ F$ obviously represents $ p$ properly. So $ F\sim px^2+bxy+cy^2$. Note that the transformation $ (x,y)\mapsto(x+dy,y)$ results in a form whose middle term is $ 2pd+b$, so by an appropriate choice of $ d$ we can arrange that $ -p< b\leq p$. Similarly, $ G\sim px^2+b'xy+c'y^2$ with $ -p< b'\leq p$. Note also that since $ b^2-4pc=b'^2-4pc'$, it follows that $ b\equiv b'\pod 2$ (i.e. $ b,b'$ have the same parity).

Since $ \Delta(F)=\Delta(G)$, we see that $ b^2-4pc=b'^2-4pc'\Leftrightarrow b^2\equiv b'^2\pod p\Leftrightarrow b\equiv \pm b'\pod p$, so $ b=b'+kp$ for some $ k$. Since $ b,b'$ have the same parity and $ p$ is odd, $ k$ is even; since $ -p<b,b'\leq p$, $ k=0$ (since otherwise $ b,b'$ would be separated by at least $ 2p$, which is impossible).

Thus $ b=b'$, so $ c=c'$ and hence $ F\sim G$. $ \qedsymbol$

In summary, we have proved the following:

$\displaystyle F,G$ equivalent $\displaystyle \Rightarrow F,G$    represent the same set of integers     
$\displaystyle F,G$ equivalent $\displaystyle \Rightarrow \Delta(F)=\Delta(G)$    
$\displaystyle \Delta(F)=\Delta(G), F,G$ both represent some odd prime $\displaystyle p\Rightarrow F\sim G$    

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

From this point on, we will deal only with positive 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 5   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 % latex2html id marker 1772 $ 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. $ \qedsymbol$
Definition 3   A primitive positive form % latex2html id marker 1785 $ ax^2+bxy+cy^2$ is reduced if
$\displaystyle \vert b\vert\leq a\leq c$, and $\displaystyle b\geq 0$ if either $\displaystyle \vert b\vert=a$ or $\displaystyle a=c $
This is equivalent to saying that $ -a\leq b\leq a\leq c$ and that $ b$ can be negative only if $ a<c$ or $ -a<b$. 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 6   If $ F$ is a primitive positive reduced form with discriminant $ \Delta\neq -3$, % latex2html id marker 1813 $ 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<c$, then this value is assumed only for $ (x,y)=(\pm1,0)$; if $ a=c$; it is assumed for $ (x,y)=(\pm 1,0)$ and $ (x,y)=(0,\pm 1)$.
Proof. Since $ \vert b\vert\leq a\leq c$, it follows that
$\displaystyle F(x,y)\geq (a-\vert b\vert+c)\min(x^2,y^2)$
Thus, $ F(x,y)\geq a-\vert b\vert+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<c$, then $ F(x,y)\geq a+(c-\vert b\vert)>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 $ \vert b\vert\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-\vert b\vert>0$ and thus $ F(x,y)>a$ if $ xy\neq 0$, so in this case the result follows as well. $ \qedsymbol$

Note that the reduced form of discriminant $ -3$, $ x^2+xy+y^2$, also achieves its minimum value at $ (1,-1),(-1,1)$.
Theorem 7   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 % latex2html id marker 1914 $ F=ax^2+bxy+cy^2, G=a'x^2+b'xy+c'y^2$. Now, $ F$ and $ G$ have the same minimum value, so $ a=a'$.

If $ a<c$, then $ F$ achieves its minimum only at $ (pm 1,0)$, so $ a=a'=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'=b+2ra$. Since $ G$ is also reduced, $ b=b'$ and thus $ c=c'$ 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'=\pm 2cr-b$. Thus $ b'=-b$. But then $ c=c'$ since the discriminants are equal, and thus both $ b,b'\geq 0$. So $ b=b'=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$. $ \qedsymbol$

Theorem 8   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 $ \vert b\vert\leq a\leq c$. Among all forms properly equivalent to the given one, choose % latex2html id marker 1992 $ F(x,y)=ax^2+bxy+cy^2$ such that $ \vert b\vert$ is as small as possible (there may be multiple such forms; choose one of them). If $ \vert b\vert>a$, then

% latex2html id marker 1998 $\displaystyle G(x,y)=F(x+my,y)=ax^2+(2am+b)xy+c' y^2 $
is properly equivalent to $ F$, and we can choose $ m$ so that $ \vert 2am+b\vert<\vert b\vert$, contradicting our choice of minimal $ \vert b\vert$. So $ \vert b\vert\leq a$; similarly, $ \vert b\vert\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 % latex2html id marker 2020 $ F(x,y)=ax^2+bxy+cy^2$, where $ \vert b\vert\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 % latex2html id marker 2032 $ 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 % latex2html id marker 2042 $ ax^2-axy+cy^2$ to % latex2html id marker 2044 $ ax^2+axy+cy^2$, while if $ a=c$, then $ (x,y)\mapsto(-y,x)$ takes % latex2html id marker 2050 $ ax^2+bxy+ay^2$ to % latex2html id marker 2052 $ ax^2-bxy+ay^2$. $ \qedsymbol$

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 9   If % latex2html id marker 2117 $ F(x,y)=ax^2+bxy+cy^2$ is a positive reduced form with $ \Delta<0$, then $ a\leq \sqrt{\frac{\vert\Delta\vert}{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. $ \qedsymbol$
Corollary 10   If $ \Delta<0$, then the number of primitive positive reduced forms of discriminant $ \Delta$ (which, by the foregoing, is equal to the number of classes of primitive positive forms of discriminant $ \Delta$) is finite.
Proof. Essentially obvious. 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<b\leq a$. $ a$ and $ b$ determine $ c$ since $ \Delta$ is fixed. $ \qedsymbol$

Examples: $ \Delta=-4$: $ b^2-4ac=-4 \Rightarrow b$ even, $ \vert b\vert\leq \vert a\vert\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$.

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

$ (1,1,6)$  
$ (1,-1,6)$ not reduced since $ \vert b\vert=a,b<0$, properly equivalent to $ (1,1,6)$ via $ (x,y)\mapsto (x+y,y)$
$ (2,1,3)$  
$ (2,-1,3)$ reduced since $ b\vert\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, $ \vert b\vert\leq \sqrt{\frac{55}{3}} \Rightarrow \vert b\vert=1,\pm 3$. So $ ac=14$ or $ 16, a\leq c$. So the forms are

$ (1,1,14)$  
$ (1,-1,14)$ not reduced since $ \vert b\vert=a,b<0$, properly equivalent to $ (1,1,14)$ via $ (x,y)\mapsto (x+y,y)$
$ (2,1,7)$  
$ (2,-1,7)$ reduced since $ \vert b\vert\neq a, a\neq c$
$ (4,3,4)$  
$ (4,-3,4)$ 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, $ \vert b\vert\leq \vert a\vert\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<c$, 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$.



"integral binary quadratic forms" is owned by rm50.
(view preamble)

View style:

Log in to rate this entry.
(view current ratings)

Cross-references: fixed, proposition, minimal, multiple, argument, contains, equivalence class, reduced, point, separated, parity, prime, converse, right, transpose, Transform, proof, odd, even, congruent, binary, obvious, inverse, map, multiplicative group, class, transformation, product, equivalence relations, determinant, matrix, invertible, equivalence, terms, relatively prime, primitive, integer, represent, polynomial, integral, coefficients, variables, quadratic form, number, finite, discriminant, negative, reduced form, equivalent, positive, Gauss, theory
There are 2 references to this entry.

This is version