Finding the minimum value of an indefinite binary quadratic form via Markov's transformations
Given an indefinite binary quadratic form g(x0,y0)=a0x02+b0x0y0+c0y02, we use the PQa continued fraction algorithm applied to the first root ρ = (-b0 + √d)/2a0.
At each stage, we perform the transformation xn=qnxn+1+yn+1, yn=xn+1 on the form anxn2+bnxnyn+cnyn2, where qn is the nth partial quotient of ρ.
If fn = (-bn + √d)/2a and sn = (-bn - √d)/2a, then the nth complete quotient of ρ is fn or sn, according as n is even or odd.
Eventually the nth complete quotient of ρ will be reduced. The resulting form g0=(an,bn,cn) will be Hermite reduced. i.e. one root θ1 is greater than one, while the other is between -1 and 0.
The process continues until gk-1=g0. The form period k is printed, along
with the minimum value μ taken by g0 over all pairs of integers, not both zero,together with a corresponding Sk/Tk, k ≥ 0, a convergent to θ1 such that g(Sk,Tk) = μ.
The partial quotients of this period are also printed.
Note that there is a slight difference between a Hermite reduced form and a Lagrange
reduced form, so the cycle of forms is reversed and differs in sign at times from Lagrange's.
Last modified 9th August 2017
Return to main page