Denis Simon on Wed, 04 Jun 2014 14:53:58 +0200


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

Re: Numbers represented by indefinite binary quad. forms


Dear Neil,

When using qfsolve, be careful that it is not supposed
to find integral solutions but only rational solutions.

When integral solutions exist, it might happen that
qfsolve finds one (like in Bill's example), and in practice
it quite often does. However I have no proof that it is always
the case, and I suspect that counterexamples are not difficult
to find.

Denis SIMON.

----- Mail original -----
> De: "Bill Allombert" <Bill.Allombert@math.u-bordeaux.fr>
> À: pari-users@pari.math.u-bordeaux.fr
> Envoyé: Mercredi 4 Juin 2014 13:17:51
> Objet: Re: Numbers represented by indefinite binary quad. forms
> 
> 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.
> 
>