8
$\begingroup$

Given $a,b\in\Bbb Q_+$, is there an easy way to decide if $$S_{a,b}=\{(x,y)\in\Bbb Z^2:ax^2 + by^2=1\}=\emptyset?$$

I am more interested in seeing if there is a quick way to test for case when solutions do not exist.

$\endgroup$
12
  • $\begingroup$ This is an interesting problem. As Silverman points out, the natural approach is to check solubility in all $\mathbb{Z}_p$ first. A priori there is no guarantee however that this will imply there is a solution $\mathbb{Z}$ (note that the Hasse principle can fail here when you have 3 variables instead of 2: see the paper by Colliot-Thélène and Xu on the Brauer-Manin obstruction for integral points). $\endgroup$ Apr 5, 2015 at 13:54
  • $\begingroup$ My naive guess however is that for $2$ variables, the Hasse principle for integral points holds. One approach to this would be to notice that the equation is a torsor for some norm one torus. Once one has this structure, its make studying the problem much easier as there are many tools for the Hasse principle for torsors under algebraic groups. I would not be surprised if it was already known that the Brauer-Manin obstruction is the only one to the existence of integral points; one then just has to show that the Brauer group is trivial to deduce that the Hasse principle holds. $\endgroup$ Apr 5, 2015 at 13:57
  • 1
    $\begingroup$ @DanielLoughran The Hasse principle certainly does not hold for $2$ variables: for $x^2+dy^2=q$ with $d,q$ positive integers, the local conditions amounts to looking at the splitting of primes dividing $q$ in $\mathbb{Q}(\sqrt{-d})$ and there is a class group obstruction. $\endgroup$
    – Aurel
    Apr 5, 2015 at 14:46
  • 1
    $\begingroup$ For such a case $ax^2+bxy+cy^2=jz^2$ you can write such a formula. math.stackexchange.com/questions/738446/… channeled in dividing. $\endgroup$
    – individ
    Apr 5, 2015 at 17:28
  • 2
    $\begingroup$ @Aurel could you post your suggested answer? $\endgroup$
    – Turbo
    Apr 5, 2015 at 19:19

3 Answers 3

6
$\begingroup$

It's better to write it as $ax^2+by^2=c$ with $a,b,c\in\mathbb{Z}$. Your assumption that $a$ and $b$ are positive implies that there is a real solution. So now you can use Legendre's theorem (criterion), which says that $ax^2+by^2+cz^2=0$ (with $a,b,c$ nonzero integers, squarefree, pairwise relatively prime, and not all positive or negative) has a non-trivial solution in integers if and only if $$ \left({-ab\atop c}\right)=1 \quad\hbox{and}\quad \left({-ac\atop b}\right)=1 \quad\hbox{and}\quad \left({-bc\atop a}\right)=1. $$ So it just comes down to checking these three quadratic residue symbols. What's really going on is that a quadratic polynomial equation has a solution in integers if and only if it has a real solution and a $p$-adic solution for all $p$.

For a proof of Legendre's theorem, see for example A Classical Introduction to Modern Number Theory, Ireland and Rosen, Chapter 17, Section 3.

$\endgroup$
8
  • 2
    $\begingroup$ Thank you. Checking these three qr symbols will yield a solution $(x,y,z)\in\Bbb Z^3$. It could be that there is a solution with $z\neq\pm1$. Still the three qr symbols could yield $1$ on evaluation. Am I missing some detail here? $\endgroup$
    – Turbo
    Apr 5, 2015 at 11:29
  • 1
    $\begingroup$ No, you're right. Legendre's theorem is really about rational solutions to $ax^2+by^2=c$, not integer solutions. So Legendre's theorem is a good first step in looking for integer solutions. Once you have one rational solution $(x_0,y_0)$, you can parametrize all rational solutions, and then search within those for integer solutions. $\endgroup$ Apr 5, 2015 at 12:06
  • $\begingroup$ Conics either have none or infinitely many. So your suggestion is to check these symbols. If these are valid, find a solution and try to see if you could get one with $z=\pm 1$. right? Is there a general procedure for this type of descent for conics? $\endgroup$
    – Turbo
    Apr 5, 2015 at 12:12
  • $\begingroup$ It seems if $a^{-1}c \bmod b$ or $b^{-1}c \bmod a$ is a quadratic non-residue, then we will not have a solution? $\endgroup$
    – Turbo
    Apr 6, 2015 at 3:49
  • 1
    $\begingroup$ The criterion should read that $-ab$ is a square modulo $c$, $-ac$ a square modulo $b$, and $-bc$ a square modulo $a$. The statement with Legendre/Jacobi symbols is not in general equivalent to this unless $a,b,c$ are primes. Already in the simplest case $a=b=1$, it’s not true that a square-free $c$ is a sum of two rational squares iff it is $\equiv1\pmod4$. $\endgroup$ Aug 14, 2015 at 12:16
3
$\begingroup$

I think it is best to write the equation $ax^2+by^2=c$ with $a,b,c$ positive integers with $gcd(a,b,c)=1$.

Let me first give you a slow algorithm: since $a,b$ are positive a solution must satisfy $x^2\le c/a$ and $y^2\le c/b$, so you can enumerate these possible $x$ and $y$ and see whether you find a solution. Slightly better, only enumerate the $y$'s (or $x$'s) and check whether $c-by^2$ is divisible by $a$ and the quotient is a square.

Now here is what you can do in the special case $a=1$: $x^2+by^2$ is the norm form of the imaginary quadratic order $\mathbb{Z}[\sqrt{-b}]$. After factoring $c$, you can write down the list of ideals of norm $c$. Solvability of the equation is then equivalent to the principality of one of these ideals. This can be tested by computing the shortest vectors of the ideal for the norm quadratic form, which you can do in polynomial time. I suspect that there is a similar algorithm in the general case $a\neq 1$ but I have not worked it out.


Edit: Your second equation $ax^2+by=c$ ($a,b,c$ integers) is simpler. If $x$ is given, there is a solution $y$ if and only if $ax^2=c \pmod{b}$. So you should factor $b$, then test whether $ca^{-1}$ is a square modulo $b$ and find all the possible square roots, and finally all the solutions are given by taking all lifts of those roots and the corresponding $y$.

$\endgroup$
17
  • $\begingroup$ So all you have to do for case $a = 1$ is factorize see and test for non-principality of any of the ideals to test for non-solvability of $x^2 + by^2 = c$? There should be something similar for $a\neq1$. $\endgroup$
    – Turbo
    Apr 6, 2015 at 2:30
  • $\begingroup$ are you thinking about this for principality of ideals m-hikari.com/ams/ams-2014/ams-141-144-2014/…? It says polynomial algorithm is known. $\endgroup$
    – Turbo
    Apr 6, 2015 at 2:38
  • $\begingroup$ It seems if $a^{-1}c \bmod b$ or $b^{-1}c \bmod a$ is a quadratic non-residue, then we will not have a solution? $\endgroup$
    – Turbo
    Apr 6, 2015 at 3:49
  • $\begingroup$ @Turbo No, I was thinking of the algorithm of Hafner and McCurley (generalized by Buchmann for non-quadratic fields). The condition you write here is that of Joe Silverman's post : if there are no rational solutions, then there are no integral solutions! $\endgroup$
    – Aurel
    Apr 6, 2015 at 14:52
  • 1
    $\begingroup$ (And it remains NP-complete even the factorization of $b$ is known.) Note that this all holds for solvability in nonnegative integers, as requested in Turbo’s comment. Solvability in $\mathbb Z$ is easier (reducible to factoring, hence in $\mathrm{NP}\cap\mathrm{coNP}$). $\endgroup$ Apr 7, 2015 at 13:02
2
$\begingroup$

I thinks pari/gp can solve this via bnfisintnorm.

For integers, $a,b,c$, you are solving $ax^2+by^2=c$ with $ab$>0.

Solving symbolically:

$$ x= \pm {\frac {\sqrt {-a \left( b{y}^{2}-c \right) }}{a}} $$.

The denominator is integer, so the numerator must be integer divisble by $a$.

Squaring the numerator we get:

$$ X^2+aby^2=ac \qquad(1) $$

Since $ab>0$, (1) has finitely many solutions and it is Pell-like since it is monic in $X$.

There are no units in the the number field with defining polynomial $X^2+ab$, so pari's bnfisintnorm(K,ac) will give solutions and you must find those $X$ divisible by $a$.


Prototype pari implementation

 {
 solveabc(a,b,c)=
 /*
 pari/gp implementation for solving
 ax^2+by^2=c

 https://mathoverflow.net/questions/202037/deciding-a-quadratic-diophantine-equation

 sample usage:

 ? \r solveabc.gp

 ? a=7;b=5;T=solveabc(a,b,a*2^2+b*3^2)
 %64 = [[2, 3], [2, -3]]

 */
 if(!issquarefree(a*b),print("ab is not squarefree, likely will fail"););
 K=bnfinit('x^2+a*b,1);
 no=bnfisintnorm(K,a*c);
 if(no==[],print(" a is not norm, no solutions");return([]));
 r=[];
 for(i=1,#no,
 v=lift(no[i]);
 X=polcoeff(v,0)/a;
 Y=polcoeff(v,1);
 r=concat(r,[[X,Y]]);
 );
 return(r);
 }
$\endgroup$
5
  • 1
    $\begingroup$ Since you compute a bnfinit, you compute the class group of the field, which is costly and can be avoided. Also the algorithm as you wrote it is correct only under GRH. $\endgroup$
    – Aurel
    Apr 7, 2015 at 13:29
  • $\begingroup$ @Aurel maybe bnfinit can be avoided indeed, but this is more convenient for writing. I believe bnfcertify solves the case for GRH. $\endgroup$
    – joro
    Apr 7, 2015 at 13:32
  • 1
    $\begingroup$ It does, but in exponential time. $\endgroup$
    – Aurel
    Apr 7, 2015 at 13:42
  • $\begingroup$ @Aurel I strongly doubt you can avoid factorization, which is considered costly by current standards. $\endgroup$
    – joro
    Apr 7, 2015 at 13:57
  • $\begingroup$ Indeed you cannot, but factorization is subexponential and is faster than obtaining a proved class group. My point was that you could avoid computing a class group, not that you could avoid factorization. $\endgroup$
    – Aurel
    Apr 7, 2015 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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