Reducing an indefinite binary quadratic form using an algorithm of Don Zagier
Reducing an indefinite binary quadratic form using an algorithm of Don Zagier
Given an indefinite binary quadratic form ax2+bxy+cy2, we follow pages 120-132 of
Zetafunktionen und quadratische Körper, Eine Einführung in die höhere Zahlentheorie, Don Zagier, Springer 1981 and define (a,b,c) to be reduced if a > 0, c > 0 and b > a+c, or equivalently,
0 < (√d - b)/2a < 1 < (√d + b)/2a.
The transformation x=nx'+y', y=-x', where n > (b + √d)/2a > n - 1, converts ax2+bxy+cy2 to (an2-bn+c)x'2+(2an-b)x'y'+ay'2 and on repeated application, will eventually reach a reduced form, and this gives a cycle of reduced forms.
Note: d=b2-4ac > 0, d is not a perfect square.
See the corresponding BC program.
Last modified 31st December 2011
Return to main page