1
$\begingroup$

Consider the following problem. Given a quadratic equation

$$ \sum_{i,j=1}^n a_{i,j} x_ix_j + \sum_{k=1}^n d_{k} x_k + e = 0, \qquad a_{i,j},d_k,e\in\mathbb{Z}$$

if it exists, find (at least) a integer solution to the problem ($x_1,...,x_n\in\mathbb{Z}$). This is indeed a quadratic Diophantine equation on $n$ variables. Researching on the internet I could find the following:

  • an implementation of solvers for the case of two variables (here)
  • a paper by Grunewald and Segal on the topic that essentially says that the problem is decidable, but it does not provide an implementation of their method and it does not give (as far as I understood) a complexity estimation of the approach (here).
  • I solved with WolframAlpha problems with 5 variables (then I reach the limit of the input characters allowed by the online tool), but it does not say what method uses.

Does anyone have an idea on how to implement a solver for the general case of $n$ variables that does not do trivial bruteforce? Any source where a more algorithmic description of the Grunewald and Segal approach is provided? Or any open source implementation for this?

Improve this question
$\endgroup$
1
  • $\begingroup$ There is one idea for such an equation. The application of the ideas of holistic algebra leads to the fact that finding out the solvability of any Diophantine equation of the 2nd degree can be reduced to finding out the solvability of some equivalent Pell equation. For example, for the case $e=0$, it is easy to show that there are always solutions. The formulas are extremely cumbersome. For example, such. math.stackexchange.com/questions/794510/… $\endgroup$
    – individ
    Commented Mar 16, 2023 at 5:35

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .