6
$\begingroup$

First off, I know that there's no general algorithm for determining if there's a solution to a general Diophantine equation, much less a system.

However, I'm wondering if there is an algorithm for solving a Diophantine system of linear and quadratic equations? In fact, I have a system which is "sparse" in some sense (the linear equations are all the sum of three variables equals a number, and all the same number, and the quadratics aren't much worse).

If so, then can it be extended to the case of countably many variables?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Mathematica implements quite a few algorithms, documented (to some extent) here [for V5]: reference.wolfram.com/legacy/v5_2/functions/… They do not always cite published papers for their algorithms; perhaps some are proprietary. But they are pretty clear on which they can solve, e.g., "Mathematica can solve arbitrary quadratic Diophantine equations in two variables." $\endgroup$
    – Joseph O'Rourke
    Commented Sep 3, 2010 at 16:44
  • $\begingroup$ If there exists a small enough solution a variant of Coppersmith's method might find it, even rigorously (this doesn't contradict David's answer, and should always be kept in mind). Though, note that sparse systems are harder to solve this way because there aren't many monomial overlappings between equations. $\endgroup$
    – Dror Speiser
    Commented Sep 3, 2010 at 19:38

1 Answer 1

Reset to default
14
$\begingroup$

No. Given any set of diophantine equations $f_1(z_1, \ldots, z_n) = \ldots = f_m(z_1, \ldots, z_n)=0$, we can rewrite in terms of linear equations and quadratics. Create a new variable $w_{k_1 \cdots k_n}$ for each monomial $z_1^{k_1} \cdots z_n^{k_n}$ which occurs in the $f$'s, or which divides any monomial which occurs in the $f$'s. Turn each $f$ into a linear equation: For example, $x^3 y^2 + 7 x^2 y=5$ becomes $w_{32} + 7 w_{21} = 5$. Then create quadratic equations $z_i w_{k_1 \cdots k_i \cdots k_n} = w_{k_1 \cdots (k_i +1) \cdots k_n}$. For example, $x w_{22} = w_{32}.$ This shows that the solvability of Diophantine equations is equivalent to that of Diophantine equations of degree $\leq 2$.

I'll also mention a very concrete case. The intersection of two quadrics in $\mathbb{P}^3$ is a genus $1$ curve. To my knowledge, no algorithm is known to test for the existence of rational points even in this case. (But my knowledge is not very large.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Your argument seems to also answer this question: mathoverflow.net/questions/11488/varieties-cut-by-quadrics am I understanding correctly? $\endgroup$
    – Charles Siegel
    Commented Sep 3, 2010 at 17:07
  • 1
    $\begingroup$ Correct, there are no algorithms, but there are very good conjectural algorithms for genus 1 curves, i.e. computer programs that will be able to decide if there is a solution (and find them all). If it can't then some conjecture is wrong (BSD). Of course larger examples, say an intersection of 196 quadrics in $\mathhb{P}^{379}$ won't even have that. $\endgroup$
    – Chris Wuthrich
    Commented Sep 3, 2010 at 17:08
  • 1
    $\begingroup$ Chris: Of course you're right and you understand these matters far better than I do. But it seems to me worth emphasizing occasionally that all one needs for the algorithm to work is not even close to the full BSD, but just the finitness of, say, the 2-primary part of the Tate-Shafarevich group. $\endgroup$
    – Minhyong Kim
    Commented Sep 4, 2010 at 2:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .