DISCLAIMER: I'm primarily a graph theorist and am fairly inept when it comes to classical number theory.

Recently I have been looking at the possibility (or impossibility) of embedding various graphs as Euclidean distance graphs in $\mathbb{Q}^3$. Frequently, constructions I am considering lead to questions of the following form:

Given polynomials $p_1(n), p_2(n), p_3(n)$ with integer coefficients, does there exist $n \in \mathbb{Z}$ such that the equation

$p_1(n)x^2 + p_2(n)y^2 + p_3(n)z^2 = 0$

has a non-trivial rational solution?

I can sometimes show for specific polynomials that the answer is NO by using criteria given by Legendre in the 1700s along with repeated use of the Law of Quadratic Reciprocity. However, generalized methods for showing the existence of an $n$ leading to non-trivial rational solutions of the above equation are something I am not familiar with. If someone can point me in the right direction or even just shed a little light on the subject, I would be most appreciative.

If a much more tailored question is to your taste, consider this:

Let $r$ be a square-free positive integer and let $a, b, c \in \mathbb{Z}$ such that $a^2 + b^2 + c^2 = r$. Characterize the values of $r$ such that for some $n \in \mathbb{Z}^+$ the equation

$rx^2 + y^2 -(12n^2 - 1)(a^2 + b^2)z^2 = 0$

has a non-trivial rational solution.

  • 1
    $\begingroup$ Given $r$, there can be many $a,b,c$. Is the answer meant to depend on the choice of $a,b,c$ (which is to say, on the choice of $c$)? $\endgroup$ Sep 23, 2012 at 23:21
  • $\begingroup$ Yes, there are potentially many representations of a given $r$ as a sum of three integer squares, but for this question it shouldn't matter what representation we choose. $\endgroup$
    – Matt Noble
    Sep 24, 2012 at 14:48

2 Answers 2


Denoting $s = 12 n^2 - 1$ and using $a^2 + b^2 + c^2 = r$ your final equation can be rearranged as $ (\frac{y}{z})^2 + r (\frac{x}{z})^2 + s c^2 = r s$.

Denoting $d, e = (\frac{x}{z})^2, (\frac{y}{z})^2 $ respectively, this becomes $(r - c^2) (s - d^2) = c^2 d^2 + e^2$, and a homogenized version of the latter can have integer solutions only if the primes dividing the LHS factors satisfy the usual mod 4 conditions that determine the existence of sum-of-two-squares representations.

edit: That gives necessary conditions but is presumably only a starting point, in view of the extra constraint that $c$ and $d$ are present on both sides of the equation.


Let $m^2 = n^3+An^2 + Bn + C$ be any elliptic curve.

Your question includes the question: For which values of $n$ does $y^2 = (n^3+An^2 + Bn + C) x^2$ have a solution or, in other words, "find the integer points on $m^2 = n^3+An^2 + Bn + C$." There are excellent algorithms for this in practice, but none that are proved to work in all cases. So your question probably doesn't have an answer which is better than this.

  • 1
    $\begingroup$ @David Speyer: Actually there are unconditional algorithms for computing integral points on elliptic curves, they're just incredibly slow. You can get an upper bound the coordinates of integral points using Baker's theory but this doesn't help you much because the bounds are usually too large for a computer search. So the integral points commands in Magma and Sage use something a little faster at the expense of requiring the computation of a Mordell-Weil basis, for which there is no algorithm proved to work in all cases. $\endgroup$ Sep 24, 2012 at 22:59

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.