Can you write 67 in the form $$x^2 + 7 y^2$$? By brute force, we find $$67 = 2^2 + 7 \times 3^2$$, so the answer is yes. But what if I ask the same question about a larger prime like 1234577?

We’ll soon learn $$1234577 = x^2 + 7 y^2$$ only if 7 is quadratic residue modulo 1234577. Using quadratic reciprocity, we find that $$(7|1234577) = -(1|7) = -1$$, so this time there are no solutions.

A binary quadratic form is written $$[a, b, c]$$ and refers to the expression $$a x^2 + b x y + c y^2$$. We are interested in what numbers can be represented in a given quadratic form.

The divisor of a quadratic form $$[a, b, c]$$ is $$\gcd(a, b, c)$$.

Representations $$x, y$$ with $$\gcd(x, y) = 1$$ are primitive representations.

If the divisor of a form is 1 then it is a primitive form, but we can forget this. For our purposes, primitive representations matter, and primitive forms don’t.

Completing the square, we find:

$4a(a x^2 + b x y + c y^2) = (2a x + b y)^2 - d y^2$

where $$d = b^2 - 4a c$$. We call $$d$$ the discriminant.

If $$d = 0$$, then the quadratic form is a perfect square. This case is trivial.

If $$d < 0$$ then $$a c > 0$$, so $$a, c$$ have the same sign. From the above equality we see if $$a > 0$$ then the form is nonnegative for any $$x, y$$. We call such a form positive definite. Similarly, if $$a < 0$$ then the form is negative definite.

If $$d > 0$$ then a little experimentation shows the form takes negative and positive values. Such a form is termed indefinite.

Equivalent forms

Given a form, if we swap $$x$$ and $$y$$ then the resulting form represents the same numbers. We consider them equivalent. There are less trivial ways to change a form so it represents the same numbers. If we replace $$x$$ with $$x+y$$, then $$x = u - v, y = v$$ represents the same number that $$x = u, y = v$$ did in the original form.

More generally, let $$T$$ be a 2x2 matrix with integer entries of determinant $$\pm 1$$, that is, an integral unimodular matrix. We state facts that are easy but tedious to prove.

The quadratic form $$[a, b, c]$$ can be written as the matrix:

$A = \begin{pmatrix} a & b/2 \\ b/2 & c \end{pmatrix}$

Why? Evaluate $$\begin{pmatrix}x & y\end{pmatrix}A\begin{pmatrix}x \\ y \end{pmatrix}.$$

We have $$\det A = -4 d$$; some authors define $$d$$ to be $$\det A$$ instead of the discriminant, which generalizes nicely beyond the quadratic case.

Then let:

$A' = T^T A T = \begin{pmatrix} a' & b'/2 \\ b'/2 & c' \end{pmatrix}$

for some $$a', b', c'$$. We write $$[a, b, c] \sim [a', b', c']$$; this relation is an equivalence relation.

If $$\begin{pmatrix}u \\ v\end{pmatrix} = T \begin{pmatrix}u' \\ v'\end{pmatrix}$$ then $$u, v$$ represents the same integer under $$A$$ as $$u', v'$$ does under $$A'$$, and we call these equivalent representations. Equivalent representations have the same divisor.

Equivalent forms represent the same integers, have the same divisor and discriminant.

[If two forms represent the same integers, are they necessarily equivalent? I don’t know.]

Principal forms

The principal form of a discriminant $$d$$ is $$[1, 0, -k]$$ when $$d = 4k$$ and $$[1, 1, k]$$ when $$d = 4k + 1$$. Its equivalence class is the 'principal class of forms of discriminant $$d$$'.

Reduced forms

By applying transformations judiciously, we can reduce any definite form to $$[a, b, c]$$ such that $$-|a| < b \le |a| < |c|$$ or $$0 \le b \le |a| = |c|$$.

Reduction is like Euclid’s algorithm. There exist $$q, r$$ such that $$-b = 2|c|q + r$$ with $$-|c| < r \le |c|$$, so we apply the integral uniform matrix:

$\begin{pmatrix} 0 & 1 \\ -1 & \text{sgn}(c)q \end{pmatrix}$

to transform an unreduced form $$[a, b, c]$$ to $$[c, r, d]$$ for some $$d$$. Repeating eventually leads to $$|c| \le |d|$$.

Thus we have a form $$[a, b, c]$$ satisfying $$-|a| < b \le |a| \le |c|$$, and we are done unless $$|a| = |c|$$ and $$b < 0$$. In this last case, we apply the above procedure one more time (we’ll find $$q = 0$$ and $$r = -b$$) to get the reduced form $$[c, -b, a]$$.

-- | Matrix multiplication.
mmul a b = [[sum $zipWith (*) r c | c <- transpose b] | r <- a] tat t m = mmul (transpose t)$ mmul m t

reduce (a, b, c)
| b^2 - 4*a*c >= 0 = error "indefinite form"
| -abs a < b, b <= abs a, abs a <  abs c = (a, b, c)
|     0 <= b, b <= abs a, abs a == abs c = (a, b, c)
| otherwise = reduce (div a' 2, b', div c' 2)
where
c2       = 2 * abs c
(q0, r0) = (-b) divMod c2
(q , r) | r0 * 2 > c2 = (q0 + 1, r0 - c2)
| otherwise   = (q0    , r0)
[[a', b'],[_, c']] = tat
[[0, 1], [-1, signum c * q]]
[[2*a, b], [b, 2*c]]

Our reduction algorithm works for indefinite forms with nonzero $$a$$ and $$c$$. However, it turns out we need to refine our definition of "reduced" to get useful results in the indefinite case. We’ll skip this part of the theory.

Principal forms are reduced forms.

The above conditions imply $$b^2 \le |a c| \le |d|/3$$ when $$ac /= 0$$. This suggests a brute force algorithm to find all reduced forms of a given discriminant $$d$$.

The following function returns all positive definite forms for a given discriminant. The negative definite forms are the same with $$a$$ and $$c$$ negated.

pos d
| d >= 0        = error "d must be negative"
| d mod 4 > 1 = error "d must be 0 or 1 mod 4"
| otherwise     = posBs ++ negBs
where
upFrom n = takeWhile (\x -> x^2 <= abs d div 3) [n..]
posBs = [(a, b, c) | b <- upFrom 0, a <- upFrom b, a /= 0,
let (c, r) = divMod (b^2 - d) (4*a), r == 0, c >= a]
negBs = [(a, -b, c) | (a, b, c) <- posBs, a /= c, b > 0, a > b]

For example:

> pos (-39)
[(1,1,10),(2,1,5),(3,3,4),(2,-1,5)]

Since there are only finitely many reduced forms of discriminant $$d$$ and every form is equivalent to some reduced form, the number of equivalence classes of forms with discriminant $$d$$ is finite. We call this number the class number of the discriminant $$d$$.

At least that’s what I understood from Number Theory by John Hunter. I think the class number is actually the number of equivalence classes of positive definite forms when $$d < 0$$, as there’s no point doubling the total by also counting the negative definite forms.

Theorem: The equivalence class of a positive definite binary quadratic contains exactly one reduced form.

Proof. Let $$f = [a, b, c]$$ be a reduced positive definite binary quadratic form. Again, we complete the square:

$4a f(x,y) = (2a x + b y)^2 - d y^2$

Both $$a$$ and $$c$$ are positive so $$-a < b \le a < c$$ or $$0 \le b \le a = c$$.

Then if $$|y| \ge 2$$ then $$- d y^2 \ge 12 a c$$ thus

$f(x,y) \ge 3c > a + c .$

And if $$|x| \ge 2$$ and $$|y| = 1$$ we find

$f(x,y) \ge ax^2 - a|x| + c \ge 2a + c > a + c .$

Among the remaining the cases, we find the four smallest integers primitively represented are $$a, c, a+b+c, a-b+c$$, corresponding to $$(x,y) = (1,0), (0,1), (1,1), (1,-1)$$. The smallest three are $$a, c, a + c - |b|$$ and since these are each smaller than $$a + c$$, they are the smallest three integers (possibly non-distinct) primitvely represented by $$[a, b, c]$$. Observe $$a \le c \le a + c - |b|$$.

If $$[a', b', c']$$ is a reduced form equivalent to $$[a, b, c]$$, the same reasoning implies the smallest three integers it primitively represents are $$a', c', a'+c'-|b'|$$ and $$a' \le c' \le a' + c' - |b'|$$.

Thus $$a = a'$$, $$c = c'$$ and $$|b| = |b'|$$. When $$a = c$$, both $$b$$ and $$b'$$ are nonnegative, implying $$b = b'$$. It remains to prove this holds when $$a < c$$, which is the least pleasant part of the proof.

Suppose $$b = -b'$$. Since $$[a,b,c] \sim [a,-b,c]$$ there exists a 2x2 integer matrix

$\begin{pmatrix} p & q \\ r & s \end{pmatrix}$

with $$p s - q r = 1$$ that transforms one to the other, that is,

\begin{aligned} a & = a p^2 + b p r + c r^2 \\ -b & = 2apq + b(ps+qr) + 2crs \end{aligned}

Then:

$a = a p^2 + b p r + c r^2 > a p^2 - a|pr| + a^2 \ge 2a|pr|-a|pr| = a|pr|$

Thus we must have $$pr = 0$$. If $$p = 0$$ then $$r /= 0$$, whence $$a = a p^2 + b p r + c r^2 > c$$, a contradiction. So $$r = 0$$, which means $$ps = 1$$.

Then:

$-b = 2apq + b(ps+qr) + 2crs = 2a pq + b$

We deduce $$|b| = a|pq|$$, which implies $$b = 0$$ or $$b = a$$. Since $$[a, -a, c]$$ is not reduced, we must have $$b = 0$$. ∎

Theorem: An integer $$n$$ is primitively representable by a quadratic form $$[a, b, c]$$ if and only if $$[a, b, c] \sim [n, b', c']$$ for some $$b', c'$$.

Proof. If $$n = a x^2 + b x y + c^2$$ and $$\gcd(x, y) = 1$$ then the extended Euclid’s algorithm can find $$p, q$$ so that $$p x - q y = 1$$. Then the integral unimodular transformation:

$\begin{pmatrix} x & q \\ y & p \end{pmatrix}$

to $$[a, b, c]$$ gives $$[n, b', c']$$ for some $$b', c'$$.

Conversely, $$(1, 0)$$ primitively represents $$n$$ for $$[n, b', c']$$, so transforms to a primitive representation of $$n$$ for $$[a, b, c]$$.∎

Theorem: A nonzero integer $$n$$ is primitively representable by a form of discriminant $$d$$ if and only if

$x^2 = d \bmod 4 |n|$

for some $$x$$.

Proof. If $$n$$ is primitive representable, by the previous theorem there exists a form $$[n, b', c']$$ that primitively represents $$n$$. The condition follows immediately from $$d = b'^2 - 4 n c'$$.

Conversely, the condition implies $$b'^2 - 4 n c' = d$$ for some integers $$b', c'$$, and 1, 0 is a primitive representation of $$n$$ by the form $$[n, b', c']$$.∎

Example: The form $$x^2 + 3y^2$$ of discriminant $$-12$$ cannot represent $$2$$, yet $$2^2 = -12 \pmod{8}$$. The above theorem simplies there must exist some form of discriminant $$-12$$ in another equivalence class, and indeed we find $$[2, 2, 2]$$ has the desired discriminant and can represent $$2$$.

Sum of two squares

The quadratic form $$[1, 0, 1]$$ has discriminant $$-4$$. From the previous theorem, a nonnegative integer $$n$$ is primitively represented by some form of discriminant $$-4$$ if and only there exists $$x$$ satisfying $$x^2 = -4 \bmod 4n$$, which is the same as $$x^2 = -1 \bmod n$$.

A brief search confirms $$[1, 0, 1]$$ is only reduced positive definite form of discriminant $$-4$$. Therefore, $$n$$ is primitively represented by some form of discriminant $$-4$$ if and only if $$n$$ is primitively represented by $$[1, 0, 1]$$, namely, $$n$$ is the sum of two squares.

Factorize $$n$$:

$n = \prod 2^s p_i^{k_i}$

where the $$p_i$$ are distinct odd primes. By the Chinese Remainder Theorem, and considering quadratic residues for prime powers, $$n$$ is primitively represented by $$x^2 + y^2$$ if and only if each $$p_i = 1 \bmod 4$$ and $$s \le 1$$.

If we allow non-primitive representations, then $$n$$ is a sum of two squares provided $$k_i = 0 \bmod 2$$ whenever $$p_i = 3 \bmod 4$$.

Ben Lynn blynn@cs.stanford.edu 💡