# Relation between indefinite quadratic forms and continued fractions

Let $D$ be a positive square free integer; for simplicity let's take $D$ to be $2$ or $3$ modulo $4$. Then ideal classes in $\mathbb{Z}[\sqrt{D}]$ are in bijection with matrices $\left( \begin{smallmatrix} a & b \\ b & c \end{smallmatrix} \right)$ such that $ac-b^2=-D$, module the action of $SL_2(\mathbb{Z})$. Given such a matrix, consider the element $\theta := \frac{b+\sqrt{D}}{a}$ in $\mathbb{Z}[\sqrt{D}]$. (Since $D$ is not a square, $a$ is not zero.) So matrices of the sort we are interested in are in bijection with numbers $\theta$ of the form $\frac{b+\sqrt{D}}{a}$ such that $a | (b^2-D)$.

When people discuss the continued fraction of $\sqrt{D}$, the set of such real numbers comes up, as it has the property that it is stable under translation by integers, and under inversion. (Which, now that I think about it, is just the $SL_2(\mathbb{Z})$ action. In fact, the relation between $\left( \begin{smallmatrix} a & b \\ b & c \end{smallmatrix} \right)$ and $\theta$ is that $(\theta \ 1)$ is isotropic for $\left( \begin{smallmatrix} a & b \\ b & c \end{smallmatrix} \right)$. So it makes sense that we have related $SL_2(\mathbb{Z})$ actions.)

This makes me think there should be some way to relate the continued fraction behavior of $\sqrt{D}$ to the class group of $\mathbb{Z}[\sqrt{D}]$. This is probably some standard thing that every number theorist knows. Where do I read about it?

-
Classically this is seen in terms of the relation between continued fractions and cycles of reduced indefinite quadratic forms. For a nice account see chapter 15 of Conway & Sloane's Sphere Packings, Lattices and Groups. – Robin Chapman Jul 9 '10 at 15:14
A better source could be Lachaud: iml.univ-mrs.fr/editions/biblio/files/lachaud/1988e.pdf See in particular the example on page 20 for $\sqrt{19}$. – Junkie Jul 9 '10 at 17:22

Recently, I got obsessed with working out this story, to the detriment of my mathematical work. Here is a quick crib sheet for relating properties of continued fractions to properties of real quadratic fields. Warning: I haven't checked this against a standard reference, so there may be errors.

Preliminary notation: Continued fractions

It is convenient to convert a continued fraction to a sequence of binary symbols; I've been using red and blue dots, which I'll represent here as $r$ and $b$. For example, $\sqrt{13}=[3,1,1,1,1,6,1,1,1,1,6,\cdots]$; I'll write this as $$r\ r\ r\ b\ r\ b\ r\ b\ b\ b\ b\ b\ b\ r\ b\ r\ b\ r\ r\ r\ r\ r\ r\ \cdots$$

This makes the continued fraction purely periodic instead of having that peculiar $3$ at the beginning; the period starts again in the middle of that last block of six $r$'s. Note also that the period of the fraction now appears to be twice what it was; when we get to the old period, we have switched colors. Finally, a sequence which starts with $b$'s should be thought of as a continued fraction for a number in $(0,1)$; the sequence starts with zero copies of $r$.

Let $K$ be a quadratic field and let $\Lambda$ be a rank $2$ sublattice of $K$, with $\mathbb{Q} \Lambda =K$. Let $\mathrm{End}(\Lambda)$ be the ring of $\theta \in K$ such that $\theta \Lambda \subseteq \Lambda$. This is an order in $\mathcal{O}_K$.

Let $K$ be a real quadratic field, with fixed embedding $K \to \mathbb{R}$, and write $z \mapsto \overline{z}$ for the Galois symetry of $K$. We'll say that two lattices $\Lambda_1$ and $\Lambda_2$ with CM are "strictly equivalent" if there is an element $\alpha \in K$ such that $\Lambda_1 = \alpha \Lambda_2$ with $\alpha$ and $\overline{\alpha}$ both positive.

Summary of results:

$\bullet$ Take any periodic sequence $a_i$ of $r$'s and $b$'s and turn it into a continued fraction. Let $z$ be the value of that continued fraction. Then $z$ is a quadratic irrational, with $z>0$ and $\overline{z}<0$. We have $a_0=r$ if $z>1$ and $a_0=b$ if $z<1$. Extending the periodicity to negative indices, $a_{-1}=r$ if $\overline{z} < -1$ and $a_{-1} =b$ if $\overline{z} > -1$.

$\bullet$ Switching the colors changes $z$ to $1/z$. Reversing the sequence changes $z$ to $-\overline{z}$.

Strict ideal classes

$\bullet$ Let $K = \mathbb{Q}(z)$ and let $\Lambda = \langle 1, z \rangle$. Shifting the periodic sequence does not change the strict equivalence class of $\Lambda$.

$\bullet$ The above is a bijection between periodic sequences of $r$'s and $b$'s, up to shift, and strict equivalence classes of lattices in real quadratic fields.

$\bullet$ Switching the colors corresponds to multiplying by our lattice by an element of negative norm. So producing a lattice which is equivalent, but not strictly equivalent.

$\bullet$ Reversing the sequence sends $\Lambda$ to $\overline{\Lambda}$. If $\Lambda$ is a lattice in $K$, and $R = \mathrm{End}(\Lambda)$, then $\Lambda \overline{\Lambda}$ is a strictly principal fractional ideal for $R$. (This is a special property of quadratic fields, which I know of no generalization of in higher degree number fields.) So, with the understanding that we treat a fractional ideal as a fractional ideal for its full endomorphism ring, reversing the sequence sends $\Lambda$ to $\Lambda^{-1}$.

Units

$\bullet$ Let $R$ be the endomorphism ring of $\Lambda$. Let $p/q$ be the convergent obtained by truncating the continued fraction just before the first repetition of the block which contains $a_0$. Let $u=p-qz$. Then $u$ is a unit of $R$ with norm $1$, and is the fundamental generator of the group of such units.

For example, $\langle 1, \sqrt{13} \rangle$ has endomorphism ring $\mathbb{Z}[\sqrt{13}]$. We truncate the above sequence to $$r\ r\ r\ b\ r\ b\ r\ b\ b\ b\ b\ b\ b\ r\ b\ r\ b$$ or $$[3,1,1,1,1,6,1,1,1,1] = \frac{649}{180}$$ and $649-180 \sqrt{13}$ is the fundamental positive unit of $\mathbb{Z}[\sqrt{13}]$.

$\bullet$ The color reversal of our sequence is a shift of itself if and only if $R$ has units of norm $-1$. We can recover them by the same recipe, truncating before the color reversed copy of $a_0$.

For example, $$[3,1,1,1,1] = \frac{18}{5}$$ and $18-5 \sqrt{13}$ is the fundamental unit of norm $-1$ in $\mathbb{Z}[\sqrt{13}]$.

Note, by the way, that we have not yet seen the fundamental unit of $\mathbb{Q}(\sqrt{13})$, which is $(3-\sqrt{13})/2$. That's because $\langle 1, \sqrt{13} \rangle$ doesn't have CM by this unit.

We can obtain the same unit from two quite different looking continued fractions. For example $$\sqrt{10} = r\ r\ r\ b\ b\ b\ b\ b\ b\ r\ r\ r \cdots \quad \sqrt{10}/2 = r\ b\ r\ b\ b\ r\ b\ r \cdots$$ where I have given a full period for each fraction. Truncating to before the middle block gives $$r\ r\ r = \frac{3}{1} \quad r\ b\ r\ = \frac{3}{2}.$$ Both of these give the unit $3-\sqrt{10} = 3-2 \frac{\sqrt{10}}{2}$.

Fixing the endomorphism ring; working with triples $(a,b,c)$

$\bullet$ Let $R = \mathbb{Z}[\sqrt{D}]$, for $D>0$ and not square. The continued fractions which give rise to rings containing $R$ correspond to ordered triples $(a,b,c)$ of integers with $D=b^2+ac$ and $a$, $c>0$, by the recipe $(a,b,c) \mapsto (b+\sqrt{D})/a$.

The corresponding ring is exactly $\mathbb{Z}[\sqrt{D}]$ if and only if $(a,2b,c)$ have no common factor.

$\bullet$ Let $R = \mathbb{Z}[(1+\sqrt{D})/2]$ with $D \equiv 1 \mod 4$, positive and not square. The continued fractions which give rise to rings containing $R$ correspond to ordered triples $(a,b,c)$ with $D=b^2+ac$, $a$ and $c>0$, and the additional condition that $b$ is odd and $a$ and $c$ are even.

Example: If we want to get the ring $\mathbb{Z}[(1+\sqrt{13})/2]$, we need to pick $z$ so that $\langle 1, z \rangle$ has CM by this ring. An obvious choice is $z=(1+\sqrt{13})/2$, with $(a,b,c) = (2,1,6)$. The continued fraction is $$r\ r\ b\ b\ b\ r\ r\ r\ b\ b\ b\ r\ r\ r\ b\ b\ b\$$ or $[2, 3,3,3,3,\ldots]$ in conventional notation.

$\bullet$ The corresponding ring is exactly $\mathbb{Z}[(1+\sqrt{D})/2]$ if and only if $(a,b,c)$ have no common factor.

$\bullet$ There are only finitely many $(a,b,c)$ for any $R$.

$\bullet$ Adding an $r$ at the beginning of the sequence changes $(a,b,c)$ to $(a,a+b,c-a-2b)$. Adding a $b$ at the beginning changes $(a,b,c)$ to $(a-c-2b,b+c,c)$. Reversing the sequence changes $(a,b,c)$ to $(a,-b,c)$; color switching the sequence sends $(a,b,c)$ to $(c,-b,a)$.

Continued fractions with special symmetry

$\bullet$ A continued fraction is a shift of its color switch if and only if $R$ contains a unit with norm $-1$; we have already described how to find this unit.

$\bullet$ A continued fraction is a shift of its reversal if and only if it is a $2$-torsion class in the strict ideal class group.

Consider continued fractions which equal their reversal, so the periodic sequence starts at the middle of an even block of $r$'s or $b$'s, like the sequence for $\sqrt{13}$ above. These correspond to $z = \sqrt{D}/a$ for some divisor $a$ of $D$.

Consider continued fractions which are off from one by a shift of their reversal, so the periodic sequence starts in the middle of an odd block of $r$'s or $b$'s. These correspond to $z = (b+\sqrt{D})/(2b)$. If $D$ is odd, then we can take $b$ to be any divisor of $D$. If $D$ is $2 \mod 4$, then there are no solutions to $b^2+2bc=D$. If $D$ is $0 \mod 4$, then we can take $b$ of the form $2 b'$, where $b'$ is a divisor of $D/4$.

$\bullet$ Let $(-)$ denote the strict ideal class of principal $\Lambda$ ideals generated by elements of negative norm. A continued fraction is a shift of its color switched reversal if and only if $\Lambda^2 = (-)$ in the strict ideal class group.

A continued fraction actually equals its color switched reversal if and only if $a=c$. In other words, such continued fractions for $R = \mathbb{Z}[\sqrt{D}]$ are in bijection with solutions to $a^2+b^2=D$ with $a$ and $b>0$, and $GCD(a,2b)=1$. Such continued fractions for $R=\mathbb{Z}[(1+\sqrt{D})/2]$ are in bijection with solutions to $a^2+b^2=D$ with $a$, $b>0$, such that $a$ even and $b$ odd.

Example: We have $34=3^2+5^2$. So take $z=(3+\sqrt{34})/5$. Take $\Lambda$ to be the lattice $\langle 1, (3+\sqrt{34})/5 \rangle$, which is strictly equivalent to the ideal $I=\langle 5, 3+\sqrt{34} \rangle$ in $\mathbb{Z}[\sqrt{34}]$. This is a non-principal prime ideal dividing $5$. We have $I^2 = \langle 3+\sqrt{34} \rangle$, which is principal, but not strictly principal.

The corresponding continued fraction is $$r\ b\ r\ r\ r\ b\ b\ b\ r\ b\ r\ b\ r\ r\ r\ b\ b\ b\ r\ b\ r\ b\ \cdots$$ or $[1,1,3,3,1,1,1,1,3,3,1,1,1,1,\cdots]$ in conventional notation. This sequence is its own color switched reversal, reflecting that $I^2=(-)$. However, it is not a shift of its own reversal, reflecting that $I^2$ is not strictly principal, and it is not a shift of its color switch, reflecting that $\mathbb{Z}[\sqrt{34}]$ does not have a unit of norm $-1$.

-

The continued fraction is actually related to the principle cycle, which in turn is related to the class group. For example, it is an easy exercise to prove that the period length for $\sqrt{D}$ is at most a logarithmic factor away from the regulator of $\mathbb{Z}[\sqrt{D}]$ (this need not be a maximal order).

The first place I recall that contains a bit on the correspondence with classes, the relation to the regulator, and computational applications is chpater 5.6 and 5.7 in Cohen's "A Course in Computational Algebraic Number Theory".

The second being "Quadratics" by Mollin, chapter 2.

-
Sorry, I am confused: the regulator is related to units (by definition), whose link with continued fractions is more familiar. How are class groups (or class numbers) related to the topic in this answer? – BCnrd Jul 9 '10 at 15:21
Maybe my wording isn't clear - both references answer exactly the question, and more, if one wants to read more. The bit about the regulator is not familiar to all, and in my experience, except the correspondence with reduced ideals, the continued fraction doesn't have much more to do with the class group directly. The relation between regulator and class number is deeper than the class number formula, especially when looking at non-fundamental discriminants. That is a whole other discussion not fit for comments. – Dror Speiser Jul 9 '10 at 16:10

Dror is right about the cycles.

For definite forms($\Delta < 0$), there is only one reduced form per class but for indefinite forms($\Delta > 0$), there is actually a cycle of reduced forms. Consider for example, the cycle of indefinite reduced forms

(a, b, c) $\rightarrow$ (-a, b, -c)$\rightarrow$ (c, b, a) $\rightarrow$ (-c, -b, -a).

The cycle of the equivalent reduced indefinite forms corresponds to the convergents of the periodic continued fraction. The quadratic forms also correspond to the ideal classes of the quadratic field

Mollin's book on Quadratics that Dror mentioned has worked examples. Also see the paper "Computing in Quadratic Orders" on John Robertson's site

-

Your question is the subject of Shanks' "infrastructure" of a quadratic field. See http://en.wikipedia.org/wiki/Infrastructure_(number_theory) .

This has been generalized by Hendrik Lenstra and Rene Schoof (among others). See the very nice paper by Schoof "Computing Arakelov Class Groups" http://www.msri.org/people/staff/levy/files/Book44/14schoof.pdf

-
I think that this answer is a little bit misleading. The connection between reduction theory of indefinite binary quadratic forms and the theory of continued fractions is indeed classical. Shanks infrastructure, on the other hand, gives some kind of an "almost group structure" on the principal cycle, i.e., the unit element of the class group. In addition to the references already given I'd suggest Jacobson & Williams, Solving the Pell Equation. – Franz Lemmermeyer Jul 10 '10 at 8:56

Hi, David. This is roughly Robin's comment, just with longer discussions, and, I am afraid, links to my own answers. That's life.

I think you would probably enjoy J.H. Conway, "The Sensual Quadratic Form," especially PSL_2(Z) on pages 27-33.

I always like "The Markoff and Lagrange Spectra" by Thomas W. Cusick and Mary E. Flahive and "Binary Quadratic Forms" by Duncan A. Buell.

On particular issues I think you are raising, answers by me and by Dror in:

Reasons for switching from simple continued fractions for $\sqrt D$ to reduced forms: Upper bound of period length of continued fraction representation of very composite number square root

Numbers (here primes) occurring as "diagonal" coefficients: Primes as the first coefficient of a reduced indefinite quadratic form

In my language, I think you are asking mostly about small numbers occurring as diagonal coefficients, just not necessarily prime. For me, such numbers need also to be primitively represented by the forms in the cycle (for you I guess it is by $x^2 - D y^2 ,$ using $a_0 = \lfloor \sqrt D \rfloor$ your quadratic form is equivalent to the reduced form $\langle 1,\; 2 a_0, \; a_0^2 - D \rangle.$ )

phoebus:~/Cplusplus> ./Pell
Input n for Pell
67

0  form   1 16 -3   delta  -5
1  form   -3 14 6   delta  2
2  form   6 10 -7   delta  -1
3  form   -7 4 9   delta  1
4  form   9 14 -2   delta  -7
5  form   -2 14 9   delta  1
6  form   9 4 -7   delta  -1
7  form   -7 10 6   delta  2
8  form   6 14 -3   delta  -5
9  form   -3 16 1   delta  16
10  form   1 16 -3

disc   268
Automorph, written on right of Gram matrix:
-1106  -17901
-5967  -96578

Pell automorph
-48842  -399789
-5967  -48842

Pell unit
-48842^2 - 67 * -5967^2 = 1

=========================================
phoebus:~/Cplusplus>


Anyway, let me know if you want to see any more worked examples. Or the computer program. It is C++ so the numbers are bounded. Easy enough in other languages, of course.

-