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 |
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^2describes 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
(+/-)L[i]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...