Re: Numbers represented by indefinite binary quad. forms

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Tue, Jun 03, 2014 at 08:45:32PM -0400, Neil Sloane wrote:
> Given an indefinite binary quadratic form ax^2+bxy+cy^2 (with discriminant
> b^2-4ac>0 and not a square) and a number n, how to use PARI to see if
> ax^2+bxy+cy^2=n has a solution?
> 
> [Back in 2003 Bill Alombert said: I have added a new function qfbsolve.
>  qfbsolve(Q,p): Solve  the  equation  Q(x,y)  = p over the integers,  where
> Q is an imaginary binary quadratic form and p a prime number.  Return
>  [x,y]  as a two-components vector,  or zero if there is no solution.  Note
> that this functions return only one solution and not all the solutions.
>  This is a preliminary implementation. I plan to allow non prime p and real
> binary quadratic. Me: Does the "non-prme" version exist? - that would solve
> my problem!

Alas, I implemented the real case, but not the non-prime one.
The algorithm was not optimal in the real case anyway and the combinatoric
painful.

I see two way to do it:

-- you can use qfsolve (integrated in PARI 2.8, otherwise available
at <http://www.math.unicaen.fr/~simon/qfsolve.gp>)

qfbs(Q,n)=my([a,b,c]=Vec(Q));qfsolve([a,b/2,0;b/2,c,0;0,0,-n])
? qfbs(Qfb(1,2,3),123)
%13 = [-12,7,1]~ 
(so the answer is (-12:7:1) in projective coordinate)
This give you a single solution.

-- otherwise, you can use bnfisintnorm() if your discriminant is fundamental.

qfbs(Q,n)=
{
  my(V=Vec(Q),a=V[1],b=V[2],c=V[3],B=bnfinit(x^2+b*x+a*c));
  apply(x->Vecrev(x),bnfisintnorm(B,a*n))
}
? qfbs(Qfb(1,2,3),123)
%10 = [[12,1],[-12,-7],[-2,-7],[-10,1]]
(this give all solution modulo units)

if your discriminant is not fundamental, then it is harder.
I wrote a script in 2011 to take care of that:
<http://pari.math.u-bordeaux.fr/archives/pari-users-0811/msg00009.html>
(be careful, I am not sure it is 100% correct. Report bugs)

qfbs(Q,n)=my(V=Vec(Q),a=V[1],b=V[2],c=V[3]);qesolve([a,b,c,0,0,-n])
? qfbs(Qfb(1,2,3),123)
%7 = [[-10,-1],[10,1],[-2,7],[2,-7],[-12,7],[12,-7],[12,-1],[-12,1]]
(this give all solution modulo non-torsion units)

Cheers,
Bill.