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

 Difficulty with binary quadratic equation solver

• To: Pari Users <pari-users@list.cr.yp.to>
• Subject: Difficulty with binary quadratic equation solver
• Date: Fri, 28 Nov 2008 09:36:47 -0700
• Delivery-date: Fri, 28 Nov 2008 18:59:39 +0100
• Mailing-list: contact pari-users-help@list.cr.yp.to; run by ezmlm

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
```
(+/-)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...
```
```