Binary quadratic form

If f is a quadratic form, a matrix

${\displaystyle {\begin{pmatrix}\alpha &\beta \\\gamma &\delta \end{pmatrix}}}$

in ${\displaystyle \mathrm {SL} _{2}(\mathbb {Z} )}$ is an automorphism of f if ${\displaystyle f(\alpha x+\beta y,\gamma x+\delta y)=f(x,y)}$. For example, the matrix

${\displaystyle {\begin{pmatrix}3&-4\\-2&3\end{pmatrix}}}$

is an automorphism of the form ${\displaystyle f=x^{2}-2y^{2}}$. The automorphisms of a form form a subgroup of ${\displaystyle \mathrm {SL} _{2}(\mathbb {Z} )}$. When f is definite, the group is finite, and when f is indefinite, it is infinite and cyclic.

Diophantus considered whether, for an odd integer ${\displaystyle n}$, it is possible to find integers ${\displaystyle x}$ and ${\displaystyle y}$ for which ${\displaystyle n=x^{2}+y^{2}}$.[2] When ${\displaystyle n=65}$, we have

${\displaystyle {\begin{aligned}65&=1^{2}+8^{2},\\65&=4^{2}+7^{2},\end{aligned}}}$

so we find pairs ${\displaystyle (x,y)=(1,8){\text{ and }}(4,7)}$ that do the trick. We obtain more pairs that work by switching the values of ${\displaystyle x}$ and ${\displaystyle y}$ and/or by changing the sign of one or both of ${\displaystyle x}$ and ${\displaystyle y}$. In all, there are sixteen different solution pairs. On the other hand, when ${\displaystyle n=3}$, the equation

${\displaystyle 3=x^{2}+y^{2}}$

does not have integer solutions. To see why, we note that ${\displaystyle x^{2}\geq 4}$ unless ${\displaystyle x=-1,0}$ or ${\displaystyle 1}$. Thus, ${\displaystyle x^{2}+y^{2}}$ will exceed 3 unless ${\displaystyle (x,y)}$ is one of the nine pairs with ${\displaystyle x}$ and ${\displaystyle y}$ each equal to ${\displaystyle -1,0}$ or 1. We can check these nine pairs directly to see that none of them satisfies ${\displaystyle 3=x^{2}+y^{2}}$, so the equation does not have integer solutions.

A similar argument shows that for each ${\displaystyle n}$, the equation ${\displaystyle n=x^{2}+y^{2}}$ can have only a finite number of solutions since ${\displaystyle x^{2}+y^{2}}$ will exceed ${\displaystyle n}$ unless the absolute values ${\displaystyle |x|}$ and ${\displaystyle |y|}$ are both less than ${\displaystyle {\sqrt {n}}}$. There are only a finite number of pairs satisfying this constraint.

Another ancient problem involving quadratic forms asks us to solve Pell's equation. For instance, we may seek integers x and y so that ${\displaystyle 1=x^{2}-2y^{2}}$. Changing signs of x and y in a solution gives another solution, so it is enough to seek just solutions in positive integers. One solution is ${\displaystyle (x,y)=(3,2)}$, that is, there is an equality ${\displaystyle 1=3^{2}-2\cdot 2^{2}}$. If ${\displaystyle (x,y)}$ is any solution to ${\displaystyle 1=x^{2}-2y^{2}}$, then ${\displaystyle (3x+4y,2x+3y)}$ is another such pair. For instance, from the pair ${\displaystyle (3,2)}$, we compute

${\displaystyle (3\cdot 3+4\cdot 2,2\cdot 3+3\cdot 2)=(17,12)}$,

and we can check that this satisfies ${\displaystyle 1=17^{2}-2\cdot 12^{2}}$. Iterating this process, we find further pairs ${\displaystyle (x,y)}$ with ${\displaystyle 1=x^{2}-2y^{2}}$:

${\displaystyle {\begin{aligned}(3\cdot 17+4\cdot 12,2\cdot 17+3\cdot 12)&=(99,70),\\(3\cdot 99+4\cdot 70,2\cdot 99+3\cdot 70)&=(477,408),\\&\vdots \end{aligned}}}$

These values will keep growing in size, so we see there are infinitely many ways to represent 1 by the form ${\displaystyle x^{2}-2y^{2}}$. This recursive description was discussed in Theon of Smyrna's commentary on Euclid's Elements.

The oldest problem in the theory of binary quadratic forms is the representation problem: describe the representations of a given number ${\displaystyle n}$ by a given quadratic form f. "Describe" can mean various things: give an algorithm to generate all representations, a closed formula for the number of representations, or even just determine whether any representations exist.

The examples above discuss the representation problem for the numbers 3 and 65 by the form ${\displaystyle x^{2}+y^{2}}$ and for the number 1 by the form ${\displaystyle x^{2}-2y^{2}}$. We see that 65 is represented by ${\displaystyle x^{2}+y^{2}}$ in sixteen different ways, while 1 is represented by ${\displaystyle x^{2}-2y^{2}}$ in infinitely many ways and 3 is not represented by ${\displaystyle x^{2}+y^{2}}$ at all. In the first case, the sixteen representations were explicitly described. It was also shown that the number of representations of an integer by ${\displaystyle x^{2}+y^{2}}$ is always finite. The sum of squares function ${\displaystyle r_{2}(n)}$ gives the number of representations of n by ${\displaystyle x^{2}+y^{2}}$ as a function of n. There is a closed formula[3]

${\displaystyle r_{2}(n)=4(d_{1}(n)-d_{3}(n)),}$

where ${\displaystyle d_{1}(n)}$ is the number of divisors of n that are congruent to 1 modulo 4 and ${\displaystyle d_{3}(n)}$ is the number of divisors of n that are congruent to 3 modulo 4.

There are several class invariants relevant to the representation problem:

• The set of integers represented by a class. If an integer n is represented by a form in a class, then it is represented by all other forms in a class.
• The minimum absolute value represented by a class. This is the smallest nonnegative value in the set of integers represented by a class.
• The congruence classes modulo the discriminant of a class represented by the class.

The minimum absolute value represented by a class is zero for degenerate classes and positive for definite and indefinite classes. All numbers represented by a definite form ${\displaystyle f=ax^{2}+bxy+cy^{2}}$ have the same sign: positive if ${\displaystyle a>0}$ and negative if ${\displaystyle a<0}$. For this reason, the former are called positive definite forms and the latter are negative definite.

The number of representations of an integer n by a form f is finite if f is definite and infinite if f is indefinite. We saw instances of this in the examples above: ${\displaystyle x^{2}+y^{2}}$ is positive definite and ${\displaystyle x^{2}-2y^{2}}$ is indefinite.

The notion of equivalence of forms can be extended to equivalent representations. Representations ${\displaystyle m=f(x_{1},y_{1})}$ and ${\displaystyle n=g(x_{2},y_{2})}$ are equivalent if there exists a matrix

${\displaystyle {\begin{pmatrix}\alpha &\beta \\\gamma &\delta \end{pmatrix}}}$

with integer entries and determinant 1 so that ${\displaystyle f(\alpha x+\beta y,\gamma x+\delta y)=g(x,y)}$ and

${\displaystyle {\begin{pmatrix}\delta &-\beta \\-\gamma &\alpha \end{pmatrix}}{\begin{pmatrix}x_{1}\\y_{1}\end{pmatrix}}={\begin{pmatrix}x_{2}\\y_{2}\end{pmatrix}}}$

The above conditions give a (right) action of the group ${\displaystyle \mathrm {SL} _{2}(\mathbb {Z} )}$ on the set of representations of integers by binary quadratic forms. It follows that equivalence defined this way is an equivalence relation and in particular that the forms in equivalent representations are equivalent forms.

As an example, let ${\displaystyle f=x^{2}-2y^{2}}$ and consider a representation ${\displaystyle 1=f(x_{1},y_{1})}$. Such a representation is a solution to the Pell equation described in the examples above. The matrix

${\displaystyle {\begin{pmatrix}3&-4\\-2&3\end{pmatrix}}}$

has determinant 1 and is an automorphism of f. Acting on the representation ${\displaystyle 1=f(x_{1},y_{1})}$ by this matrix yields the equivalent representation ${\displaystyle 1=f(3x_{1}+4y_{1},2x_{1}+3y_{1})}$. This is the recursion step in the process described above for generating infinitely many solutions to ${\displaystyle 1=x^{2}-2y^{2}}$. Iterating this matrix action, we find that the infinite set of representations of 1 by f that were determined above are all equivalent.

There are generally finitely many equivalence classes of representations of an integer n by forms of given nonzero discriminant ${\displaystyle \Delta }$. A complete set of representatives for these classes can be given in terms of reduced forms defined in the section below. When ${\displaystyle \Delta <0}$, every representation is equivalent to a unique representation by a reduced form, so a complete set of representatives is given by the finitely many representations of n by reduced forms of discriminant ${\displaystyle \Delta }$. When ${\displaystyle \Delta >0}$, Zagier proved that every representation of a positive integer n by a form of discriminant ${\displaystyle \Delta }$ is equivalent to a unique representation ${\displaystyle n=f(x,y)}$ in which f is reduced in Zagier's sense and ${\displaystyle x>0}$, ${\displaystyle y\geq 0}$.[4] The set of all such representations constitutes a complete set of representatives for equivalence classes of representations.

A variety of definitions of composition of forms has been given, often in an attempt to simplify the extremely technical and general definition of Gauss. We present here Arndt's method, because it remains rather general while being simple enough to be amenable to computations by hand. An alternative definition is described at Bhargava cubes.

Suppose we wish to compose forms ${\displaystyle f_{1}=A_{1}x^{2}+B_{1}xy+C_{1}y^{2}}$ and ${\displaystyle f_{2}=A_{2}x^{2}+B_{2}xy+C_{2}y^{2}}$, each primitive and of the same discriminant ${\displaystyle \Delta }$. We perform the following steps:

1. Compute ${\displaystyle B_{\mu }={\tfrac {B_{1}+B_{2}}{2}}}$ and ${\displaystyle e=\gcd(A_{1},A_{2},B_{\mu })}$, and ${\displaystyle A={\tfrac {A_{1}A_{2}}{e^{2}}}}$
2. Solve the system of congruences

   ${\displaystyle {\begin{aligned}x&\equiv B_{1}{\pmod {2{\tfrac {A_{1}}{e}}}}\\x&\equiv B_{2}{\pmod {2{\tfrac {A_{2}}{e}}}}\\{\tfrac {B_{\mu }}{e}}x&\equiv {\tfrac {\Delta +B_{1}B_{2}}{2e}}{\pmod {2A}}\end{aligned}}}$

   It can be shown that this system always has a unique integer solution modulo ${\displaystyle 2A}$. We arbitrarily choose such a solution and call it B.
3. Compute C such that ${\displaystyle \Delta =B^{2}-4AC}$. It can be shown that C is an integer.

The form ${\displaystyle Ax^{2}+Bxy+Cy^{2}}$ is "the" composition of ${\displaystyle f_{1}}$ and ${\displaystyle f_{2}}$. We see that its first coefficient is well-defined, but the other two depend on the choice of B and C. One way to make this a well-defined operation is to make an arbitrary convention for how to choose B—for instance, choose B to be the smallest positive solution to the system of congruences above. Alternatively, we may view the result of composition, not as a form, but as an equivalence class of forms modulo the action of the group of matrices of the form

${\displaystyle {\begin{pmatrix}1&n\\0&1\end{pmatrix}}}$,

where n is an integer. If we consider the class of ${\displaystyle Ax^{2}+Bxy+Cy^{2}}$ under this action, the middle coefficients of the forms in the class form a congruence class of integers modulo 2A. Thus, composition gives a well-defined function from pairs of binary quadratic forms to such classes.

It can be shown that if ${\displaystyle f_{1}}$ and ${\displaystyle f_{2}}$ are equivalent to ${\displaystyle g_{1}}$ and ${\displaystyle g_{2}}$ respectively, then the composition of ${\displaystyle f_{1}}$ and ${\displaystyle f_{2}}$ is equivalent to the composition of ${\displaystyle g_{1}}$ and ${\displaystyle g_{2}}$. It follows that composition induces a well-defined operation on primitive classes of discriminant ${\displaystyle \Delta }$, and as mentioned above, Gauss showed these classes form a finite abelian group. The identity class in the group is the unique class containing all forms ${\displaystyle x^{2}+Bxy+Cy^{2}}$, i.e., with first coefficient 1. (It can be shown that all such forms lie in a single class, and the restriction ${\displaystyle \Delta \equiv 0{\text{ or }}1{\pmod {4}}}$ implies that there exists such a form of every discriminant.) To invert a class, we take a representative ${\displaystyle Ax^{2}+Bxy+Cy^{2}}$ and form the class of ${\displaystyle Ax^{2}-Bxy+Cy^{2}}$. Alternatively, we can form the class of ${\displaystyle Cx^{2}+Bxy+Ay^{2}}$ since this and ${\displaystyle Ax^{2}-Bxy+Cy^{2}}$ are equivalent.