State/Solving quadratic Diophantine equations in two variables

Logical Connections

This statement logically relies on the following definitions and statements: Def/Binary quadratic form, Def/Discriminant of a binary quadratic form, State/Existence of wells for definite forms, State/Climbing in topographs, Def/Perfect square, Def/Range topograph, State/Periodicity along the river

The following statements and definitions rely on the material of this page:

To visualize the logical connections between this statements and other items of mathematical knowledge, you can visit the following cluster(s), and click the "Visualize" tab: Clust/Binary quadratic forms

Given a binary quadratic form $Q$ and $n \in \ZZ$, we are interested in the set: $$S = \{ (x,y) \in \ZZ^2 \mbox{ such that } Q(x,y) = n \}.$$ The range topograph contains the values of $Q$, when primitive lax vectors are input. For this reason, consider the following subset of $S$: $$S_{prim}(n) = \{ (x,y) \in \ZZ^2 \mbox{ such that } GCD(x,y) = 1 \mbox{ and } Q(x,y) = n \}.$$ If $(x,y) \in S$, and $g = GCD(x,y) \neq 1$, then we may consider $x' = x/g$ and $y' = y/g$. Then, $GCD(x', y') = 1$, and we find that: $$Q(x,y) = g^2 Q(x', y') = n.$$ It follows that $g^2$ divides $n$, and: $$(x,y) \in S_{prim}(n/g^2).$$ In this way, we find that, if $n \neq 0$, then: $$S = \bigcup_{g^2 \vert n} S_{prim}(n/g^2),$$ the union, over all integers $g$ such that $g^2$ divides $n$, of the subsets $S_{prim}(n/g^2)$. When $n = 0$, one must also consider the "trivial solution" $(0,0) \in S$, in addition to the solutions described above.

In this way, finding the set of solutions $S$ to the equation $Q(x,y) = n$ reduces to finding primitive solutions of related equations $Q(x,y) = n/g^2$ for a finite number of integers $g$, which can be found on the topograph of $Q$.

Let $\Delta$ be the discriminant of $Q$. If $\Delta < 0$, then $Q$ is positive definite or $Q$ is negative definite. In other words, one of the following two conditions holds:

• Every value of $Q$ on the range topograph is positive.
• Every value of $Q$ on the range topograph is negative.

Observe that $Q(x,y) = n$ if and only if $-Q(x,y) = -n$; hence, by replacing $Q$ by $-Q$ if necessary, it suffices to consider the positive definite case. In this case, the range topograph of $Q$ contains a unique well or double-well. Thus, it follows, by the climbing property of topographs, that if $n$ occurs in the range topograph, then $n$ occurs at a distance at most $n$ from the well (where distance is measured by travelling along edges). Since there are only finitely many regions within distance $n$ of the well or double-well, it follows that primitive solutions to $Q(x,y) = n$ can be found by algorithm.

Let $\Delta$ be the discriminant of $Q$. If $\Delta > 0$, and $\Delta$ is not a Def/Perfect square, then $Q$ is indefinite. It follows that the range topograph of $Q$ contains an "endless river". By periodicity along the river, we may consider a "fundamental domain" or "representative section" of the river. By periodicity, we find that if $n$ occurs in the topograph of $Q$, then $n$ occurs in a region of the topograph whose closest river segment lies in the chosen representative section. Furthermore, by periodicity, if $n$ occurs in the topograph of $Q$, then $n$ occurs infinitely many times.

It follows that if the set $S_{prim}(n)$ is nonempty, then $S_{prim}(n)$ is infinite, i.e., there are infinitely many primitive solutions to the Diophantine equation $Q(x,y) = n$. In order to find a solution algorithmically, observe that the climbing principle implies that an integer $n$ must be found (if it can be found) within a distance at most $\vert n \vert $ from the river. Since it suffices to consider a finite, representative section of the river, this area of the topograph can be searched in a finite amount of time.

Let $\Delta$ be the discriminant of $Q$. If $\Delta > 0$, and $\Delta$ is a perfect square, then $Q$ is indefinite, and there are two lakes in the range topograph of $Q$. These form either a double-lake, or the two lakes are joined by a river.

In particular, the positive and negative values of $Q$ are separated by a finite number of regions and/or edges of water. A primitive vector $(x,y)$, such that $Q(x,y) = n$, must be found within a distance $\vert n \vert$ from water, by the climbing principle. This allows us to find $n$ by searching a finite area of the topograph.

Suppose that $Q$ has discriminant $0$. Then, it can be shown that there exists an integer $z$, such that the values of $Q$ are precisely the integers of the form $z k^2$ for $k \in \ZZ$. Each of these values (except zero) occurs infinitely many times on the topograph of $Q$.