Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given rational numbers $a$ and $b$, what is the fastest way to determine whether there are any rational solutions to $a=x^2+by^2$?

I am interested in the case where the numerator and denominator of $a$ have about $4$ digits, and those of $b$ have about $8$ digits. I am willing to restrict attention to solutions where $x$ and $y$ also have numerators and denominators that are not too large, if that will help. I would like to solve a large number of problems of this type, perhaps tens of millions, so efficiency is important. Both $a$ and $b$ will be different for each problem. I would also be interested in heuristics for roughly how often rational solutions exist.

share|improve this question

1 Answer 1

up vote 6 down vote accepted

This is a conic, so factoring the discriminant is important, then you can check local solubility at all bad primes. This gives whether it is solvable. With a little extra work (maybe negligible compared to factoring), Simon's algorithm will give you a solution. http://www.ams.org/journals/mcom/2005-74-251/S0025-5718-05-01729-1/ or alternatively Cremona-Rusin http://www.ams.org/journals/mcom/2003-72-243/S0025-5718-02-01480-1/

I would guess that in your application, the main thing is to be able to factor numbers whose size is 12 digits quite efficiently.

As for heuristics, the local root number is probably $-1$ about the half the time at primes dividing the discriminant, and up to evenness of number of such primes I guess these are independent. So global solubility should depend on the number of prime factors. Doing a simple test (with small numbers) on 10000 random trials gave about 36% soluble with 3 prime factors, 20% with 4 prime factors, 10% with 5 prime factors, 5% with 6.

share|improve this answer
    
Now that I think about, the fact that you have a diagonal conic means that you would only have to factor $a$ and $b$, and 8 digits is small enough to have a look-up table. Cremona-Rusin might also be faster for conics like these, Simon is more for large coefficients with small discriminant. –  NAME_IN_CAPS Jun 24 at 23:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.