Binary Quadratic Forms

note

This is Lab 16 from Clint by Hugh Montgomery, edited by Elad Zelingher. All rights reserved to Hugh Montgomery.

Whether a number $n$ can be expressed as a sum of two squares can be elegantly characterized in terms of the canonical factorization of $n$ into prime powers (recall Theorem 2.15 of NZM). It is therefore natural to ask whether something similar happens with other binary quadratic forms. The answer, as discussed in $\S 3.4-3.7$ of NZM, is generally less satisfactory.

Problem 1

What is the discriminant of the form $f(x, y)=3508 x^{2}+11259 x y+9034 y^{2}$ ? Is this form definite or indefinite (Recall Theorem 3.11 of NZM.)? Use Reduce to find a reduced form that is equivalent to $f(x, y)$. Use the program QFormTab to view a list of all the reduced quadratic forms of this discriminant. Describe, in terms of the arithmetic progressions that they fall in, the primes represented by this form. (Suggestion: Use Corollary 3.14 and Theorem 3.17 of NZM.)

Problem 2

What is the discriminant of the form $f(x, y)=1039 x^{2}+11223 x y+30307 y^{2}$ ? Is this form definite or indefinite? Using the program QFormTab, construct a list of all the reduced quadratic forms of this discriminant. Describe, in terms of arithmetic progressions that they fall in, the primes represented by this form. Use Reduce to find a reduced form $g(x, y)$ that is equivalent to the given form. From the information displayed, find values of $x$ and $y$ such that $g(x, y)=1039$. If you check the checkbox then the bottom form in the table is reduced, the steps of the reduction are displayed, with the matrix that takes $f$ to $g$. To view the inverse matrix, that takes $g$ to $f$, say $M: g \rightarrow f$, compute the inverse (recall that for matrices in $\mathrm{SL}(2, \mathbb{Z})$ we have

$$\begin{pmatrix} a & b \\ c & d \end{pmatrix} ^{-1} = \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}.$$

). To express the original first coefficient 1039 properly by $g$, one takes $x=m_{11}, y=m_{12}$ where

$$M = \begin{pmatrix} m_{11} & m_{12} \\ m_{21} & m_{22} \end{pmatrix}.$$

In Reduce enter

$$\begin{align} a & =123456789876543401, \\ b & =31971493083730684, \\ c & =2069907153395965, \end{align}$$

and reduce this form. In this way, discover a representation of the prime $a$ as a sum of two squares.

The prime $p=123456757$ is $\equiv 1(\bmod 4)$, and hence can be written as a sum of two squares. In order to find such a representation, we first construct a quadratic form $f(x, y)=a x^{2}+b x y+c y^{2}$ with $a=p$ and discriminant $d=-4$. That is, we must find $b$ and $c$ so that $b^{2}-4 p c=-4$. By using SqrtModP, we find that $x^{2} \equiv-4 (\bmod p)$ where $x=51035038$. We need $b$ to satisfy $b^{2} \equiv-4 (\bmod 4 p)$. Thus we may take $b \equiv x$ $(\bmod p)$. We also need $b$ to be even, so that $b^{2} \equiv-4(\bmod 4)$. Since $x$ is even, it suffices to take $b=x$. Then $c=\frac{b^{2}+4}{4 p}=5274266$ (You can use WolframAlpha for this). Next we use the program Reduce to reduce this quadratic form. The only reduced form of discriminant $-4$ is $x^{2}+y^{2}$, and hence not only is $f(x, y)$ equivalent to this form, but we find the value of $x$ and $y$ that we should take to give a proper representation of $a$. From the values displayed, we find that $123456757=10281^{2}+4214^{2}$.

Problem 3

Use the programs SqrtModP and Reduce, as described above, to find a proper representation of the prime 987654337 as a sum of two squares (This is similar to Example 3 in $\S 3.6$ of NZM.).

Problem 4

The number $20193797$ is a product of two primes $\equiv 1(\bmod 4)$. Hence $20193797$ can be expressed as a sum of two squares. Use the program Factor to find these prime factors, say $20193797=p_{1} p_{2}$. Use SqrtModP to find $x_{i}$ such that $x_{i}^{2} \equiv-4\left(\bmod p_{i}\right)$, for $i=1,2$. Then use CRT to find numbers $b$ such that $b \equiv \pm x_{1}\left(\bmod p_{1}\right), b \equiv \pm x_{2}$ $\left(\bmod p_{2}\right)$, and $b \equiv 0(\bmod 2)$. Note that because of the various possible choices of the signs, there are 4 such numbers $b$. For each such $b$, put $c=\frac{b^{2}+4}{4 a}$. Reduce the $4$ quadratic forms to obtain representations of $20193797$ as a sum of two squares. How many distinct ordered pairs $(x, y)$ of positive integers do you obtain? Compare your findings with Theorem 3.22 of NZM.

Problem 5

Use the program QFormTab to view the reduced quadratic forms of discriminant -20 . How many such forms are there? The prime number 666666667 is properly represented by the form $666666667 x^{2}+200000 x y+15 y^{2}$, whose discriminant is -20 . Reduce this form, to determine a representation of 666666667 by one of the reduced forms. (Problems 5 and 10 at the end of $\S 3.6$ of NZM are relevant here.)

Problem 6

The program ClaNoTab generates a table of the class numbers of binary quadratic forms of negative discriminant (Recall Theorem 3.25 of NZM.). This program operates by the straightforward approach of noting the value of $b^{2}-4 a c$ whenever $-a<b \leq a \leq c$ or $0 \leq b \leq a=c$, for each $0 \le a \le \sqrt{\frac{\left|\Delta\right|}{3}}$. Scroll down through the table, looking for $d$ for which the class number $h(d)$ is 1. How many such $d$ do you find? Gauss found these $d$, and conjectured that there are no more. In 1934 it was proved that there could be at most one more such $d$. Finally in 1952, Heegner solved the Gauss class number problem by showing that there are no further $d<0$ for which the class number is 1 . (There are lots of $d>0$ for which the class number is 1 , and it is conjectured that there are infinitely many, though this has not yet been proved.) When $d<0$, the numbers $h(d)$ grow irregularly with $|d|$. How does $h(d)$ compare with $\sqrt{-d}$ ?

It is known that if $d<0$ then $h(d)=O(\sqrt{-d} \log -d)$, and also that if $\epsilon>0$ then there is a $D_{0}(\epsilon)<0$ such that if $d<D_{0}(\epsilon)$ then $h(d)>d^{1 / 2-\epsilon}$. Moreover, it is known that if the Generalized Riemann Hypothesis is true then $h(d) / \sqrt{-d}$ lies between $c / \log \log -d$ and $c \log \log -d$.

Problem 7

If $a, b$, and $c$ are large (in absolute value), how likely is it that $d=b^{2}-4 a c$ is small? Try some triples in the environment of the program Reduce. Suppose that $a=111111222222333333$ and that $c=333333222222111111$. How many $b$'s are there for which $|d|<10^{18}$ ?

Problem 8

Each form of negative discriminant is equivalent to a unique reduced form. (Recall Theorem 3.25 of NZM.) In particular, the reduced forms of given negative discriminant $d$ are mutually inequivalent. Hence the number $H(d)$ of equivalence classes of positive definite binary quadratic forms of discriminant $d, d<0$, is equal to the number of reduced positive definite forms of discriminant $d$. For $d>0$ our reduction process is incomplete, and reduced forms may be equivalent. Thus for $d>0$ the number of reduced forms is only an upper bound for the number $H(d)$ of equivalence classes.

Using the program QFormTab, construct a list of the reduced quadratic forms of discriminant $5$. Show that each of these two forms are equivalent. Hence $H(5)=1$. Give matrices that takes the first one to the others. Complete the following statement: "A prime $p$ is represented by the form $x^{2}+x y-y^{2}$ if and only if $\ldots$." (This is similar to Example 2 in $\S 3.5$ of NZM.)

Problem 9

Use the program QFormTab to construct a list of reduced forms of discriminant 12 . Show that $x^{2}-3 y^{2}=-1$ has no solution because it has no solution as a congruence modulo 3. Deduce that the two reduced forms are inequivalent, and hence that $H(12)=2$.

Problem 10

The form $f(x, y)=17 x^{2}+8 x y+y^{2}$ has discriminant -4 , and hence is equivalent to $g(x, y)=x^{2}+y^{2}$. Using Reduce, find a matrix that takes $g$ to $f$.