### Finding the minimum value of an indefinite binary quadratic form via Markov's transformations

Given an indefinite binary quadratic form g(x_{0},y_{0})=a_{0}x_{0}^{2}+b_{0}x_{0}y_{0}+c_{0}y_{0}^{2}, we use the PQa continued fraction algorithm applied to the first root ρ = (-b_{0} + √d)/2a_{0}.

At each stage, we perform the transformation x_{n}=q_{n}x_{n+1}+y_{n+1}, y_{n}=x_{n+1} on the form a_{n}x_{n}^{2}+b_{n}x_{n}y_{n}+c_{n}y_{n}^{2}, where q_{n} is the nth partial quotient of ρ.

If f_{n} = (-b_{n} + √d)/2a and s_{n} = (-b_{n} - √d)/2a, then the nth complete quotient of ρ is f_{n} or s_{n}, according as n is even or odd.

Eventually the nth complete quotient of ρ will be reduced. The resulting form g_{0}=(a_{n},b_{n},c_{n}) 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 g_{k-1}=g_{0}. The form period k is printed, along
with the minimum value μ taken by g_{0} over all pairs of integers, not both zero,together with a corresponding S_{k}/T_{k}, k ≥ 0, a convergent to θ_{1} such that g(S_{k},T_{k}) = μ.

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