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.

$\endgroup$
  • 1
    $\begingroup$ Doesn't it follow from Matiyasevich's result that there is no recursive upper bound? $\endgroup$ – Mark Sapir Nov 10 '16 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 '16 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 '16 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 '16 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 '16 at 17:43
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.

$\endgroup$
  • $\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 '17 at 22:10
  • $\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 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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