1
$\begingroup$

Let $F(x_1,\ldots,x_n)$ be polynomial with integer coefficients and $x_i$ integers.

System of Diophantine equations can be brought in this form via sum of squares.

Assume $F=0$ has finitely many integer solutions.

Let $M$ be the largest solution: $M=\max\{|a| : F(\ldots,a,\ldots)=0\}$.

Q1 Is there (conjectural) upper bound on $M$ in terms of the coefficients of $F$,$\deg(F)$ and $n$?

Or is it known $M$ can't be bounded this way?

For Thue equations, there is enormous upper bound (probably far from sharp).

If I remember correctly, there was Arxiv paper with many revisions giving upper bound in different notation.

Improve this question
$\endgroup$
15
  • 1
    $\begingroup$ Doesn't it follow from Matiyasevich's result that there is no recursive upper bound? $\endgroup$
    – user6976
    Nov 10, 2016 at 15:21
  • 2
    $\begingroup$ @MarkSapir “One can assume that every value is attained at most finite number of times”: certainly not without further conditions; for example, this is always false if the recursively enumerable set in question is finite. I would be extremely surprised if something like that were known to hold for a wide class of sets. You can assume without loss of generality that every value is attained infinitely many times, and since usual proofs of the MRDP theorem proceed by throwing in auxiliary variables all along the way, it’s almost inevitable they end up like that even without asking. $\endgroup$
    – Emil Jeřábek
    Nov 10, 2016 at 15:48
  • 1
    $\begingroup$ @joro: Baker's method usually gives bounds which look completely useless for practical purposes, however, using e.g. continued fractions it is often quite easy to search for solutions up to $10^{500}$, say. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Nov 10, 2016 at 16:02
  • 1
    $\begingroup$ You should explain what you mean by "in terms of the coefficients of $F$, $\deg(F)$ and $n$". If you allow any function of these data, then trivially you can bound $M$ by $M$, since $M$ itself is a function of these data. $\endgroup$
    – GH from MO
    Nov 10, 2016 at 16:58
  • 2
    $\begingroup$ "Explicit" is a subjective term. Your $M$ depends only on $F$, hence (trivially) it is a function of the coefficients, degree and $n$. If you allow a subjective answer: Falting's theorem (en.wikipedia.org/wiki/Faltings%27s_theorem) is not known effectively, so the (subjective) answer is no. $\endgroup$
    – GH from MO
    Nov 10, 2016 at 17:43

1 Answer 1

Reset to default
2
$\begingroup$

Please read the article:

A. Tyszka, A hypothetical way to compute an upper bound for the heights of solutions of a Diophantine equation with a finite number of solutions, Proceedings of the 2015 Federated Conference on Computer Science and Information Systems (eds. M. Ganzha, L. Maciaszek, M. Paprzycki); Annals of Computer Science and Information Systems, vol. 5, 709-716, IEEE Computer Society Press, 2015,

http://dx.doi.org/10.15439/2015F41

Please read the preprint (updated on January 2017):

A. Tyszka, A conjecture which implies that there exists a computable upper bound for the heights of solutions of a Diophantine equation with a finite number of solutions,

https://arxiv.org/abs/1109.3826

Let $f(1)=2$, $f(2)=4$, and $f(n+1)=f(n)!$ for every integer $n \geq 2$. We conjecture that if a system $S \subseteq \{x_i \cdot x_j=x_k, x_i+1=x_k: i,j,k \in \{1,...,n\}\}$ has only finitely many solutions in positive integers $x_1,...,x_n$, then each such solution $(x_1,...,x_n)$ satisfies $x_1,...,x_n \leq f(2n)$.

The conjecture implies that there exists an algorithm which takes as input a Diophantine equation, returns an integer, and this integer is greater than the heights of integer (non-negative integer, positive integer, rational) solutions, if the solution set is finite.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I did some formatting, but I wasn't sure whether you wanted $x_i+1=x_k$, or $x_{i+1}=x_k$. Maybe you can fix it if I got it wrong. $\endgroup$
    – Gerry Myerson
    Jan 16, 2017 at 22:10
  • 1
    $\begingroup$ Please read the article, A. Tyszka, A hypothetical upper bound on the heights of the solutions of a Diophantine equation with a finite number of solutions, Open Computer Science 8 (2018), no.1, 109-114, dx.doi.org/10.1515/comp-2018-0012 $\endgroup$
    – Apoloniusz Tyszka
    Jan 28, 2019 at 21:00
  • $\begingroup$ The Hilbert's $10$th problem is undecidable. $\endgroup$
    – user178594
    Mar 1 at 19:42

You must log in to answer this question.

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