Kurt Foster on Fri, 28 Nov 2008 18:59:39 +0100

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Difficulty with binary quadratic equation solver

We were recently given the challenge of writing a GP script to solve the Diophantine binary quadratic equation

ax^2 + bxy + cy^2 + dx + ey + f = 0

where a, b, c, d, e, and f are integers.

Karim Belabas sketched out the procedure for the special cases, and Bill Allombert wrote a script for the "typical" case where b^2 - 4*a*c is not-a-square.

However, assuming gcd(a,b,c) = 1 and b^2 - 4*a*c = m^2*N > 0 where m > 1 and N is a fundamental discriminant, there is an additional complication. As in Bill's script, let

B = bnfinit(x^2 - b*x + a*c), and let U be the smallest power of B.fu with norm +1; that is,

U = B.fu if norm(B.fu) = 1, and U = (B.fu)^2 if norm(B.fu) = -1.

The difficulty is that in this case the binary quadratic form

x^2 + bxy + a*cy^2

describes norms of elements of the quadratic suborder O of index m in B.zk, and U might not be in O. Now Bill's script checks certain congruence conditions for


where the L[i] are elements of B.zk of desired norm, produced by bnfisntnorm(). But if U^k is the smallest positive power of U which lies in O, one has to check

(+/-)U^j*L[i], for 0 <= j <= k-1.

which the script doesn't do if k > 1.

Bill provides the example

[a,b,c,d,e,f] = [1,0,-5,1,1,2]

for which the field discriminant N = 5, the index m is 2, U = (B.fu)^2, the smallest value of k is 3, and plowing through the calculations by hand shows that there are two "inequivalent" solutions

[x,y] = [1,1] and [-5, -2]

For a given positive fundamental discriminant N and index m > 1, determining the exact smallest value of k for which U^k is in O has proven to be rather exasperating, although certain multiples of it are easy to find. I've dug into it a fair bit, but I'm sure this is a known calculation. Can someone provide a reference?

Once the correct value of k is in hand, one can turn to the problem of doing the additional checking indicated above. Unfortunately, my programming ability is practically nil...