Reduction of an indefinite binary quadratic form
Given an indefinite binary quadratic form ax2+bxy+cy2, we use the PQa continued fraction algorithm to determine a reduced form and thence a cycle of reduced forms.
Our account is based on that in L.E. Dickson, Introduction to the theory of numbers pp. 99-105, Dover 1957, where the connection between a cycle of reduced forms and the periodic expansion of a reduced quadratic irrational is described. We generalise this, making use of the fact that the complete convergents of a quadratic irrational eventually become reduced.
There is another related algorithm (5.6.5) in Henri Cohen's book, A course in computational number theory, Edition 1, pp. 257-261.
Notation. d=b2-4ac > 0, d is not a perfect square, so ac ≠ 0. R = √d.
Dickson defines the first and second roots:
f = (R - b)/2a, σ(f) = (-R - b)/2a.
A form (a, b, c) is called reduced if
|f| < 1 < |σ(f)| and fσ(f) < 0.
Let τ = (R - b)/2|a| and η = (R + b)/2|c|. Then the following are equivalent:
Note. If (a, b, c) is reduced, then ac < 0 and f and a have the same sign.
- (a, b, c) is reduced;
- 0 < b < R and 0 < R - b < 2|a| < R + b;
- 0 < b < R and 0 < R - b < 2|c| < R + b;
- 0 < τ < 1 < -σ(τ);
- -1 < σ(1/τ) < 0 and 1 < 1/τ, ie. 1/τ is a reduced quadratic irrational.
- -1 < σ(η) < 0 and 1 < η, ie. η is a reduced quadratic irrational.
Also (c, b, a) is reduced.
We define a sequence of forms Φ0 = (a, b, c) and Φi = ((-1)iAi, Bi, (-1)i+1Ai+1) for i ≥ 0, as follows:
Expand F0 = η as a simple continued fraction: η = [g0,g1,...] and define Ai, Bi and Ai+1 by
Fi = (Bi + R)/2|Ai+1| = (Pi + R)/Qi, Bi2 + 4AiAi+1 = d,
where (Pi + R)/Qi is the i-th complete convergent to η.
Then with si = sgn(Ai+1),
Eventually Fi will be reduced for some i and
- Fi = (-1)isi/fi, where fi is the first root of Φi;
- Φi(x, y) is transformed into Φi+1(X, Y) by the unimodular substitution
x = Y, y = -X + (-1)isigiY.
(-1)isi/fi > 1, -1 < (-1)isi/σ(fi) < 0 .
Hence |fi| < 1 < |σ(fi)|, fiσ(fi) < 0 and Φi is a reduced form.
If n is the period-length of the continued fraction for Fi, then
will be a cycle of forms if n is even, whereas if n is odd,
will be a cycle of forms.
In the latter case, the Pell equation x2 - dy2 = -4 has a solution.
Last modified 8th December 2006
Return to main page