Positive Definite Binary Quadratic Forms and Reduction

Suppose $\mathrm{\Delta }$ is the discriminant of some integral form, say $\mathrm{\Delta }=b^2-4ac$. Then $\mathrm{\Delta }\equiv b^2(\mathrm{m}\mathrm{o}\mathrm{d}4)$.

If $\mathrm{\Delta }\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}4)$, then $(1,0,-\mathrm{\Delta }\mathrm{/}4)$ is an integral binary quadratic form and its discriminant is $0^2-4\cdot 1\cdot (-\mathrm{\Delta }\mathrm{/}4)=\mathrm{\Delta }$.

If $\mathrm{\Delta }\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)$, then $(1,1,(1-\mathrm{\Delta })\mathrm{/}4)$ is an integral binary quadratic form and its discriminant is $1^2-4\cdot 1\cdot ((1-\mathrm{\Delta })\mathrm{/}4)=\mathrm{\Delta }$.

If $b=2m$ is even, then $b^2=4m^2\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}4)$; if $b=2m+1$ is odd, then $b^2=4m(m+1)+1\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)$. Hence every discriminant is congruent to $0$ or $1$ modulo $4$.

Step 2.1 proves the forward implication, while steps 1.2 and 1.3 prove the converse in the two possible congruence classes.

If $I$ is the $2\times 2$ identity matrix, then $(f\mid I)(x,y)=f(1\cdot x+0\cdot y,0\cdot x+1\cdot y)=f(x,y)$ for all $x,y$, so $f\mid I=f$.

Write $M=\left(\begin{array}{cc}p& q\\ r& s\end{array}\right)$ and $N=\left(\begin{array}{cc}u& v\\ w& z\end{array}\right)$. Then $((f\mid M)\mid N)(x,y)=(f\mid M)(ux+vy,wx+zy)=f(p(ux+vy)+q(wx+zy),r(ux+vy)+s(wx+zy))$, which is exactly $(f\mid (MN))(x,y)$ by the definition of matrix multiplication.

The coefficients of $f\mid M$ are $a{p}^2+bpr+c{r}^2$, $2apq+b(ps+qr)+2crs$, and $a{q}^2+bqs+c{s}^2$, hence are integers. Therefore the substitutions stay inside the set of integral binary quadratic forms, and steps 1.1 and 1.2 are precisely the right-action axioms.

If $g(x,y)=n$, then $n=f(px+qy,rx+sy)$ by [F1], so every representation of $n$ by $g$ yields a representation of $n$ by $f$.

Since $ps-qr=1$, the inverse matrix is $M^{-1}=\left(\begin{array}{cc}s& -q\\ -r& p\end{array}\right)\in {\mathrm{S}\mathrm{L}}_2(\mathbb{Z})$. By [L1], $(f\mid M)\mid M^{-1}=f$, so $f=g\mid M^{-1}$. Applying step 1.1 to $g$ and $M^{-1}$ gives the converse implication. Therefore $f$ and $g$ represent exactly the same integers.

Let $u=px+qy$ and $v=rx+sy$. If $\gcd (x,y)=1$ and an integer $d$ divides both $u$ and $v$, then $d$ divides $su-qv=(ps-qr)x=x$ and $-ru+pv=(ps-qr)y=y$, so $\gcd (u,v)=1$. The same argument with $M^{-1}$ gives the converse, so the correspondence of steps 1.1 and 2.1 restricts to a bijection on primitive representations.

Expanding $g(x,y)=f(px+qy,rx+sy)$ gives $A=a{p}^2+bpr+c{r}^2$, $B=2apq+b(ps+qr)+2crs$, and $C=a{q}^2+bqs+c{s}^2$. A direct simplification yields $B^2-4AC=(ps-qr{)}^2(b^2-4ac)=b^2-4ac$, since $ps-qr=1$. Thus $f$ and $g$ have the same discriminant.

Suppose an integer $d$ divides $a$, $b$, and $c$. Then the formulas of step 1.1 show that $d$ also divides $A$, $B$, and $C$.

Since $ps-qr=1$, the inverse matrix $M^{-1}=\left(\begin{array}{cc}s& -q\\ -r& p\end{array}\right)$ is integral and lies in ${\mathrm{S}\mathrm{L}}_2(\mathbb{Z})$. By [L1], $f=g\mid M^{-1}$, so the same argument as in step 2.1 with $M^{-1}$ shows that every common divisor of $A$, $B$, and $C$ also divides $a$, $b$, and $c$.

Steps 2.1 and 3.1 show that $(a,b,c)$ and $(A,B,C)$ have exactly the same common divisors. Therefore one form is primitive exactly when the other is, by [F3].

Suppose a form $f=(a,b,c)$ of discriminant $\mathrm{\Delta }$ primitively represents $n$, say $n=f(r,s)$ with $\gcd (r,s)=1$. By [L1] choose integers $t,u$ with $ru-st=1$, and put $M=\left(\begin{array}{cc}r& t\\ s& u\end{array}\right)\in {\mathrm{S}\mathrm{L}}_2(\mathbb{Z})$.

Conversely, suppose $\mathrm{\Delta }\equiv b^2(\mathrm{m}\mathrm{o}\mathrm{d}4n)$ for some integer $b$. Then $4n$ divides $b^2-\mathrm{\Delta }$, so $c:=(b^2-\mathrm{\Delta })\mathrm{/}(4n)$ is an integer. The form $f=(n,b,c)$ has discriminant $\mathrm{\Delta }$, and $f(1,0)=n$ with $\gcd (1,0)=1$, so it primitively represents $n$.

The properly equivalent form $g=f\mid M$ has leading coefficient $g(1,0)=f(r,s)=n$, so $g=(n,b^{\mathrm{\prime }},c^{\mathrm{\prime }})$ for some integers $b^{\mathrm{\prime }},c^{\mathrm{\prime }}$. By [F3], $g$ has the same discriminant $\mathrm{\Delta }$, hence $\mathrm{\Delta }=b^{\mathrm{\prime }2}-4n{c}^{\mathrm{\prime }}$, which says exactly that $\mathrm{\Delta }\equiv b^{\mathrm{\prime }2}(\mathrm{m}\mathrm{o}\mathrm{d}4n)$.

Step 2.1 proves that primitive representation implies the square congruence, and step 1.2 proves the converse.

Suppose $f$ is positive definite. Then $a=f(1,0)>0$ by [F1].

Conversely, suppose $a>0$ and $\mathrm{\Delta }<0$. For every real $(x,y)$ one has $4af(x,y)=(2ax+by{)}^2-\mathrm{\Delta }{y}^2$ by direct expansion.

If $(x,y)\mathrm{\ne }(0,0)$ and $y=0$, then $x\mathrm{\ne }0$ and $f(x,0)=a{x}^2>0$ because $a>0$.

Also $(-\frac{b}{2a},1)\mathrm{\ne }(0,0)$, so [F1] gives $f(-\frac{b}{2a},1)>0$. Multiplying by $4a>0$ from step 1.1 yields $-\mathrm{\Delta }=(2a(-b\mathrm{/}(2a))+b{)}^2-\mathrm{\Delta }>0$, hence $\mathrm{\Delta }<0$.

If $(x,y)\mathrm{\ne }(0,0)$ and $y\mathrm{\ne }0$, then step 1.2 gives $4af(x,y)=(2ax+by{)}^2+(-\mathrm{\Delta })y^2>0$ because both summands are nonnegative and the second is positive.

Steps 2.2 and 1.3 cover every nonzero real pair, so $f$ is positive definite by [F1]. Together with steps 1.1 and 2.1, this proves the criterion.

Since $f$ is positive definite, [F3] gives $a>0$ and $\mathrm{\Delta }:=b^2-4ac<0$.

If $c<a$ or if $c=a$ and $b<0$, let $g=f\mid \left(\begin{array}{cc}0& -1\\ 1& 0\end{array}\right)=(c,-b,a)$. This matrix lies in ${\mathrm{S}\mathrm{L}}_2(\mathbb{Z})$, so $g$ is properly equivalent to $f$; by [F2] and [F3] it is again positive definite because its leading coefficient is $c>0$ and its discriminant is still $\mathrm{\Delta }<0$. Its measure satisfies $\mu (g)=3c+a+\epsilon (g)<3a+c+\epsilon (f)=\mu (f)$ because $c<a$ gives a drop of at least $1$, and when $c=a$ with $b<0$ the boundary defect disappears so $\epsilon (g)=0<1=\epsilon (f)$.

Assume now that step 2.1 does not apply. Then $a\le c$ and, because $f$ is not reduced, one must have $b\mathrm{\notin }(-a,a]$. Choose the unique integer $k$ for which $b^{\mathrm{\prime }}:=b+2ak$ lies in $(-a,a]$, and let $g=f\mid \left(\begin{array}{cc}1& k\\ 0& 1\end{array}\right)=(a,b^{\mathrm{\prime }},c^{\mathrm{\prime }})$, where $c^{\mathrm{\prime }}=a{k}^2+bk+c$.

The new form $g$ is properly equivalent to $f$, so it has the same discriminant $\mathrm{\Delta }<0$ by [F2]; its leading coefficient is still $a>0$, so [F3] makes it positive definite. Also $4a(c^{\mathrm{\prime }}-c)=b^{\mathrm{\prime }2}-b^2$, hence $c^{\mathrm{\prime }}\le c$, with strict inequality when $\mathrm{\mid }{b}^{\mathrm{\prime }}\mathrm{\mid }<\mathrm{\mid }b\mathrm{\mid }$.

If $\mathrm{\mid }b\mathrm{\mid }>a$, then $\mathrm{\mid }{b}^{\mathrm{\prime }}\mathrm{\mid }<\mathrm{\mid }b\mathrm{\mid }$, so step 4.1 gives $c^{\mathrm{\prime }}<c$. In this case $\epsilon (f)=0$: if $a<c$ there is no boundary defect, while if $a=c$ then step 2.1 was excluded and therefore $b>0$.

If $\mathrm{\mid }b\mathrm{\mid }=a$, then step 2.1 is excluded, so $a<c$ and the only way $b\mathrm{\notin }(-a,a]$ can occur is $b=-a$. Then the chosen residue is $b^{\mathrm{\prime }}=a$, so $c^{\mathrm{\prime }}=c$ and the boundary defect disappears: $\epsilon (g)=0<1=\epsilon (f)$. Hence again $\mu (g)<\mu (f)$.

If $\mathrm{\mid }b\mathrm{\mid }>a$ and $c^{\mathrm{\prime }}>a$, then $-a<b^{\mathrm{\prime }}\le a<c^{\mathrm{\prime }}$, so $g$ already satisfies the reduced-form boundary sign conditions and $\epsilon (g)=0$. Therefore $\mu (g)=3a+c^{\mathrm{\prime }}<3a+c=\mu (f)\mathrm{.}$

If $\mathrm{\mid }b\mathrm{\mid }>a$ and $c^{\mathrm{\prime }}=a$, then step 5.1 gives $c>a$ because otherwise $c=a$ and $c^{\mathrm{\prime }}=c$ would force $\mathrm{\mid }{b}^{\mathrm{\prime }}\mathrm{\mid }=\mathrm{\mid }b\mathrm{\mid }$, contradicting $\mathrm{\mid }{b}^{\mathrm{\prime }}\mathrm{\mid }<\mathrm{\mid }b\mathrm{\mid }$. If $b^{\mathrm{\prime }}\ge 0$, then $\epsilon (g)=0$ and $\mu (g)=4a<3a+c=\mu (f)\mathrm{.}$ If instead $b^{\mathrm{\prime }}<0$, let $h=g\mid \left(\begin{array}{cc}0& -1\\ 1& 0\end{array}\right)=(a,-b^{\mathrm{\prime }},a)$. Then $h$ is properly equivalent to $f$, still positive definite, and $\epsilon (h)=0$, so again $\mu (h)=4a<3a+c=\mu (f)\mathrm{.}$

If $\mathrm{\mid }b\mathrm{\mid }>a$ and $c^{\mathrm{\prime }}<a$, let $h=g\mid \left(\begin{array}{cc}0& -1\\ 1& 0\end{array}\right)=(c^{\mathrm{\prime }},-b^{\mathrm{\prime }},a)$. Then $h$ is properly equivalent to $f$ and positive definite. Since $c^{\mathrm{\prime }}\le a-1$ and $\epsilon (h)\le 1$, $\mu (h)=3c^{\mathrm{\prime }}+a+\epsilon (h)\le 3(a-1)+a+1=4a-2<4a\le 3a+c=\mu (f)\mathrm{.}$

Step 2.1 covers the case $c<a$ or $c=a$ with $b<0$; steps 6.1, 6.2, and 6.3 cover the remaining case $\mathrm{\mid }b\mathrm{\mid }>a$; and step 5.2 covers the case $\mathrm{\mid }b\mathrm{\mid }=a$ with $b<0$. Therefore every non-reduced positive-definite form is properly equivalent to a positive-definite form of smaller reduction measure.

Let $S$ be the set of reduction measures of the positive-definite forms properly equivalent to $f$. The set $S$ is nonempty because it contains the measure of $f$, and $S\subseteq \mathbb{N}$.

By [L2], the set $S$ has a least element. Choose a positive-definite form $g$ properly equivalent to $f$ whose reduction measure is that least element.

If $g$ were not reduced, [L1] would produce a properly equivalent positive-definite form $h$ with strictly smaller reduction measure. Since $h$ is properly equivalent to $g$ and $g$ is properly equivalent to $f$, the form $h$ is also properly equivalent to $f$, so its measure lies in $S$, contradicting the choice of $g$.

Therefore $g$ is reduced, and it is properly equivalent to $f$ by construction.

Since $f$ is positive definite, $a=f(1,0)>0$. Also the leading coefficient of $g$ is $g(1,0)=f(p,r)=a{p}^2+bpr+c{r}^2$.

Because $ps-qr=1$, every common divisor of $p$ and $r$ divides $1$, so $\gcd (p,r)=1$. Thus the integer $f(p,r)$ is primitively represented by $f$.

Using $\mathrm{\mid }b\mathrm{\mid }\le a\le c$ from [F1], we have $f(p,r)\ge a{p}^2-a\mathrm{\mid }pr\mathrm{\mid }+a{r}^2=a(p^2-\mathrm{\mid }pr\mathrm{\mid }+r^2)$.

If $r=0$, then $p\mathrm{\ne }0$ because $ps-qr=1$, so $p^2-\mathrm{\mid }pr\mathrm{\mid }+r^2=p^2\ge 1$. If $r\mathrm{\ne }0$, then $p^2-\mathrm{\mid }pr\mathrm{\mid }+r^2=(\mathrm{\mid }p\mathrm{\mid }-\mathrm{\mid }r\mathrm{\mid }{)}^2+\mathrm{\mid }pr\mathrm{\mid }\ge 1$. Hence in all cases $p^2-\mathrm{\mid }pr\mathrm{\mid }+r^2\ge 1$.

Combining steps 1.1, 2.1, and 3.1 gives $g(1,0)=f(p,r)\ge a$. So the leading coefficient of $g$ is at least $a$.

The leading coefficient of $g$ is $g(1,0)=f(p,r)=a{p}^2+bpr+c{r}^2$, and because $\mathrm{\mid }b\mathrm{\mid }\le a\le c$ one has $g(1,0)\ge a(p^2-\mathrm{\mid }pr\mathrm{\mid }+r^2)\ge a$. Since $g$ has leading coefficient exactly $a$, equality holds throughout.

Equality in step 1.1 forces $p^2-\mathrm{\mid }pr\mathrm{\mid }+r^2=1$, so $(\mathrm{\mid }p\mathrm{\mid },\mathrm{\mid }r\mathrm{\mid })$ is one of $(1,0)$, $(0,1)$, or $(1,1)$.

If $(\mathrm{\mid }p\mathrm{\mid },\mathrm{\mid }r\mathrm{\mid })=(1,0)$, then $r=0$ and $p=\pm 1$. The determinant condition gives $s=p$ and $M=\left(\begin{array}{cc}p& q\\ 0& p\end{array}\right)$. The transformed middle coefficient is $b^{\mathrm{\prime }}=b+2aq$ when $p=1$ and $b^{\mathrm{\prime }}=b-2aq$ when $p=-1$, so $\mathrm{\mid }{b}^{\mathrm{\prime }}\mathrm{\mid }\le a$ and $\mathrm{\mid }b\mathrm{\mid }\le a$ force $q=0$ unless $\mathrm{\mid }b\mathrm{\mid }=a$ and $b^{\mathrm{\prime }}=-b$. But the boundary rule in [F2] forbids $b^{\mathrm{\prime }}=-a$ for a reduced form, so $q=0$, hence $b^{\mathrm{\prime }}=b$ and $c^{\mathrm{\prime }}=c$.

If $(\mathrm{\mid }p\mathrm{\mid },\mathrm{\mid }r\mathrm{\mid })=(0,1)$, then $p=0$ and $r=\pm 1$. Equality in step 1.1 gives $c=a$, so reducedness of $f$ yields $0\le b\le a$. The determinant condition gives $q=-r$, so $M=\left(\begin{array}{cc}0& -r\\ r& s\end{array}\right)$, and direct substitution gives $g=(a,-b+2ars,a-brs+a{s}^2)$. Since $g$ is reduced, $\mathrm{\mid }-b+2ars\mathrm{\mid }\le a$. If $s=0$, then $g=(a,-b,a)$, and reducedness of $g$ with $a=c^{\mathrm{\prime }}=a$ forces $-b\ge 0$; together with $b\ge 0$ this gives $b=0$, hence $g=f$. If $s\mathrm{\ne }0$, then the same bound implies $2a\mathrm{\mid }s\mathrm{\mid }-b\le a$, so $\mathrm{\mid }s\mathrm{\mid }=1$ and $b=a$; because $0\le b\le a$, this means $b=a$, and the sign of $-b+2ars$ shows $rs=1$. Then $g=(a,a,a)=f$.

If $(\mathrm{\mid }p\mathrm{\mid },\mathrm{\mid }r\mathrm{\mid })=(1,1)$, equality in step 1.1 forces $c=a$ and $\mathrm{\mid }b\mathrm{\mid }=a$. By reducedness, $b=a$. Replacing $M$ by $-M$ if necessary does not change the substitution, so we may assume $(p,r)=(1,-1)$. Then $s+q=1$, and the transformed middle coefficient is $b^{\mathrm{\prime }}=a(2q-1)$. Since $\mathrm{\mid }{b}^{\mathrm{\prime }}\mathrm{\mid }\le a$, one has $q=0$ or $q=1$; reducedness excludes $b^{\mathrm{\prime }}=-a$, so $q=1$ and $b^{\mathrm{\prime }}=a$. The discriminant identity $b^{\mathrm{\prime }2}-4a{c}^{\mathrm{\prime }}=b^2-4ac$ then gives $c^{\mathrm{\prime }}=a=c$, so again $g=f$.