In Number Theory, the study of the so-called Markov spectrum often relies upon the following classical fact relating continued fractions and the values of real indefinite binary quadratic forms at integral points:

and

coincide. (Here, stands for continued fraction expansions.)

Remark 1It is worth to note that the set concerns only the real binary quadratic forms with such that the quantity

isfinite. In particular, we areexcludingreal binary quadratic forms with .

In this post, we follow the books of Dickson and Cusick–Flahive in order to give a proof of this result via the classical reduction theory of binary quadratic forms.

**1. Generalities on binary quadratic forms**

A real *binary quadratic form* is with . From the point of view of linear algebra, a binary quadratic form is

where is the usual Euclidean inner product of , is the column vector , and is the matrix .

The *discriminant* of is .

Remark 2The values taken by are very easy to describe: in particular, in this context. Hence, by Remark 1, we can focus on with or . Moreover, by symmetry (i.e., exchanging the roles of the variables and ), we can assume that . So,from now on, we shall assume that .

Note that . Therefore, is *definite* (i.e., its values are all positive or all negative) whenever the discriminant is . Conversely, when , is *indefinite* (i.e., it takes both positive and negative values) whenever . In view of the definition of in the statement of Theorem 1 above, we will restrict ourselves **from now on** to the indefinite case .

are the *first* and *second roots* of . In particular, when or . So, by Remark 1, we will suppose **from now on** that .

In summary, **from now on**, our standing assumptions on are , and , .

Remark 3The first and second roots , and the discriminant determine the coefficients , , of the binary quadratic form . Indeed, the formula says that it suffices to determine . On one hand, the modulus is given by . On the other hand, the fact that is the 1st root and is the 2nd root determines the sign of : if we replace by in the formula , then we obtain the binary quadratic form whose 1st root is and 2nd root is ; hence, an ambiguity on the sign of could only occur when , i.e., , in contradiction with our assumption .

**2. Action of on binary quadratic forms**

A key idea (going back to Lagrange) to study the values of a *fixed* binary quadratic form is to investigate the *equivalent* problem of describing the values of a *family* of binary quadratic forms on a fixed vector.

More precisely, if a vector is obtained from a fixed vector via a matrix , i.e., , , then the value of at equals the value of at . By (1), the binary quadratic forms and are related by:

Observe that (3) implies that the discriminant of is . Thus, and have the *same* discriminant whenever .

**2.1. Action of on binary quadratic forms**

The quantity appearing in the definition of in the statement of Theorem 1 leads us to restrict our attention to the action of on . In fact, since , we have that

where is the set of *primitive* vectors of . So, it is natural to concentrate on because it acts transitively on .

Definition 2Two binary quadratic forms and areequivalentwhenever for some .

Note that two equivalent binary quadratic forms have the same discriminant. Furthermore, if is a factor of and , with , then is a factor of and, *a fortiori*, is a factor of . In particular, the roots of are related to the roots of via

In other words, and are related to each other via the action of by Möbius transformations. Actually, a direct calculation with the formulas for and in (4) and the fact that show that (6) respect the order of the roots, i.e.,

where and are the first roots, and and are the 2nd roots.

Remark 4Note that because and we are assuming that the roots of are irrational.

Lemma 3Under our standing assumptions, any binary quadratic form is equivalent to some with .

*Proof:* We will proceed in two steps: first, we apply certain elements of to ensure that , and, after that, we use a parabolic matrix to obtain .

By (4), the matrix converts into with .

If , the choice of with in the discussion above leads to with

In other terms, if , then is equivalent to with , i.e., .

By iterating this process, we find a sequence of binary quadratic forms equivalent to such that whenever . It follows that is equivalent to some with .

Finally, by (4), the matrix converts into with . Hence, the choice of with gives that is equivalent to with .

**2.2. Reduction theory (I)**

In general, the study of the dynamics of the action of a group on a certain space is greatly improved in the presence of nice *fundamental domain*, i.e., a portion with good geometrical properties capturing all orbits in the sense that the -orbit of any intersects .

In the setting of acting on binary quadratic forms, the role of fundamental domain is played by the notion of *reduced* binary quadratic form:

Definition 4We say that isreducedwhenever

Remark 5Suppose that is reduced. Then, thanks to the condition . In particular, , so that . Hence, thanks to the condition . Note that the inequality says that . In other words, reduced implies ( and) .Conversely, the inequality implies that ( and) is reduced.Therefore, is reduced

if and only ifFurthermore, the identity implies that is reduced

if and only if

In particular, is reduced if and only is reduced where is the matrix inducing the change of variables , .Moreover, if is reduced, then and , i.e., the sign of is opposite to the signs of and .

The next result says that reduced forms are a fundamental domain for the action on binary quadratic forms:

Theorem 5Under our standing assumptions, any binary quadratic form is equivalent to some reduced binary quadratic form.

*Proof:* By Lemma 3, we can assume that with , so that . Thus, . By performing the change of variables , (i.e., applying the matrix ) if necessary, we can suppose that .

Since we are assuming that , it is possible to choose such that . So, if we apply the matrix (i.e., , ) to , then we get the equivalent binary quadratic form with .

We affirm that is reduced. In fact, by Remark 5, our task is to show that we have strict inequalities

However, or or would imply that or is a root of , a contradiction with our assumption that none of its roots is rational. Hence, is reduced.

**2.3. Reduction theory (II)**

In this subsection, we use the matrices inducing the change of variables , (similar to an Euclidean division) to navigate through the set of reduced binary quadratic forms (cf. Lemma 6 below).

Before explaining this fact, let us introduce the following definition: we say that the binary quadratic forms , resp. , , are the *right*, resp. *left neighbors* of the binary quadratic form .

The notion of neighbors is adapted to the investigation of reduced binary quadratic forms because of the following result:

Lemma 6Under our standing assumptions, a reduced binary quadratic form has an unique reduced right neighbor and an unique reduced left neighbor.

*Proof:* Let us first show the existence and uniqueness of the reduced right neighbor of a reduced binary quadratic form .

Consider the 1st and 2nd roots and of . Since is reduced, i.e., and , the largest integer is not zero. We take with the same sign as and and, hence, opposite to (cf. Remark 5).

By (4) and (7), the right neighbor is with and the roots of satisfy and .

Thus, our choice of implies that and has opposite sign to and . Since , has opposite sign to ( and) , we have that has the same sign of and . In summary, the right neighbor of is reduced.

Moreover, this reduced right neighbor is unique because and imply that must be the unique integer with the same sign of and .

Finally, let us establish the existence and the uniqueness of the reduced left neighbor of . Consider the matrix (with determinant ) inducing the change of variables and . By Remark 5, the fact that is reduced implies that is also reduced. In particular, has an unique reduced right neighbor . In particular, is reduced. Since

we conclude that is the unique left neighbor of .

This lemma allows us to organize the reduced binary quadratic forms into *chains*:

Definition 7Achainis a sequence of reduced binary quadratic forms such that is the right neighbor for all .

**2.4. Reduction theory (III)**

The proof of Lemma 6 hints to a connection between chains and continued fraction expansions. More concretely, let be a chain, say and the change of variables , converts into (i.e., ). Note that for all . By Remark 5, since is reduced, it follows that the sign of is opposite to the sign of . In particular, up to replacing each by its right neighbor , we can assume that .

In this context, we write with for all . Since , we have

where . As (because is reduced) and for all , the previous equation implies that

for all . Moreover, means that the roots of satisfy

In particular, and where describe the entries of the continued fraction expansions of

Moreover, the fact that and (where is the common discriminant of ), we have

**2.5. Reduction theory (IV)**

Coming back to our study of binary quadratic forms, we saw that, under our standing assumption, any binary quadratic form is equivalent to *some* chain of reduced forms.

The next *fundamental* result says that any equivalence class of binary quadratic forms contains an *unique* chain.

Theorem 8Two equivalent reduced binary quadratic forms belong to the same chain.

As it turns out, one can deduce Theorem 1 *directly* from (11) and this theorem. For this reason, let us *postpone* the proof of Theorem 8 to the last portion of this section in order to complete the proof of Theorem 1.

**2.6. End of proof of Theorem 1 (modulo Theorem 8)**

Lagrange used Theorem 8 to obtain the following result:

Theorem 9Let be a chain of reduced binary quadratic forms with discriminant . Then,

*Proof:* Fix and such that verifies

Take sending to . By definition, . In other terms, is equivalent to . Similarly to the proof of Theorem 5, we can take such that satisfies , so that the matrix converts into the equivalent binary quadratic form . Note that is reduced because and .

In summary, and are equivalent reduced binary quadratic forms. By Theorem 8, and belong to the same chain, i.e., there exists such that . By definition, this means that .

This result yields the following fact about the values of binary quadratic forms:

Proposition 10Let be a binary quadratic form satisfying our standing assumptions. Denote by the unique chain in the equivalence class of (coming from Theorems 5 and 8). Then,

*Proof:* Since for all , there is no loss of generality in applying Theorem 5 in order to assume that is reduced, say . In this situation, , so that , i.e., . Hence,

The desired conclusion now follows from Theorem 9.

The proof of Theorem 1 is now very easy to complete: indeed, it suffices to put together (5), Proposition 10 and (11).

At this stage, it remains only to prove Theorem 8. This matter is the purpose of the remainder of this section.

**2.7. Four basic properties of continued fractions**

Before starting our discussion of Theorem 8, we need to recall the following four basic properties of continued fractions:

Proposition 11Given a sequence , , let be the th convergent of . Then:

- one has the recurrence relation with the convention that ;
- ;
- and .
- ;

The reader can prove this elementary proposition along the following lines. An induction argument based on the fact that gives the recurrence relations and implying the first three items of the proposition. Finally, the third item is a consequence of the first item because the matrix has determinant . For more details, the reader is invited to consult the book of Cusick–Flahive and/or Dickson.

**2.8. Reduction theory (IV) bis: proof of Theorem 8**

Let and be two equivalent reduced binary quadratic forms. By replacing and/or by their right neighbors if necessary, we can assume that . In this case, the 1st and 2nd roots of satisfy and .

Denote by the matrix realizing the equivalence between and , so that and (cf. (7)).

Since there is nothing to prove when is the identity matrix (i.e., ), we will assume that . Up to replacing by if necessary, we can further assume that either or and .

*Proof:* Indeed, and would imply that (because ). Therefore, and , i.e.,

a contradiction.

Proposition 13If is not the identity matrix, then .

*Proof:* If , then (because and Proposition 12 ensures that ). This would imply that , i.e.,

Since , one would get , i.e., , so that would be the identity matrix. Similarly, if , then one would have , so that . Since , this would force , i.e., , so that would be the identity matrix.

*Proof:* By the previous proposition, our task is to prove that .

If , then (as and Proposition 12 says that ). By (12), it follows that . Since , one gets that

that is, .

Similarly, if , then . By (12), one gets that . Thus, (as and ). This completes the argument.

The previous propositions allow us to suppose that and . Since (as ), we also have . Moreover, up to exchanging the roles of and , i.e., replacing by its inverse if necessary, we can assume that , . Finally, the proof of Proposition 14 also tells us that , . In particular, the fact that says that , .

In summary, we can (and do) assume from now on that

Therefore, and is a solution of the equation

with and .

Proposition 15The equation has an unique solution with and .

*Proof:* Since any solution of this equation satisfies and we have that (as ), there exists with

On the other hand, if and , then and . It follows that and, *a fortiori*, . This completes the proof. We affirm that and are determined by a continued fraction expansion of .

In fact, let us write with *even* and for all : this is always possible because if is odd, then we replace the term in the continued fraction expansion by , resp. when , resp. . Denoting by

we have from Proposition 11 that and , . By Proposition 15, this implies that and , i.e.,

Moreover, Proposition 11 also tells us that

Since , we have that , , are the first entries of the continued fraction expansion of . Furthermore, (10) says that where is the first root of the th element of the chain containing . In other words, and have the same discriminant and the same first root .

At this point, we are ready to complete the proof of Theorem 8. For this sake, it suffices to establish the following fact:

Proposition 16One has . In particular, and belong to the same chain.

*Proof:* We saw that and share the same discriminant and 1st root. Since a binary quadratic form is determined by its discriminant and its 1st and 2nd roots (cf. Remark 3), our task is simply to show that and have the same 2nd root .

By Proposition 11, the fact that and implies , and, hence,

Since , it follows from (10) that , i.e., .

## Leave a Reply