3
$\begingroup$

The undecidability of Hilbert's tenth problem implies the following (there is a stronger statement here, Theorem 9):

For any computable function $f$, there is a family of integer polynomials (where some coefficients are allowed to vary) which have integer solutions, but the growth of the least integer solution (in absolute value) with respect to the varying coefficients is not bounded by $f$.

Hilbert's tenth problem over the rationals is not known to be undecidable. However, even if it were, the equivalent rational statement would not follow, since one could grow the denominator to get "inaccessible" solutions rather than the absolute value.

Nevertheless, I'm curious whether some kind of superpolynomial growth (e.g. exponential) is known to be achievable (or unachievable). So, for example, is there a system of equations of the form $$P(x_1,\ldots,x_n,\beta_1,\ldots,\beta_m)$$ such that for every rational $\vec\beta$ there is a rational $\vec x$ satisfying them, but the length of the smallest rational solution vector for a given fixed $\vec \beta$ is not bounded by a polynomial in the $|\beta_i|$? Or, conversely, is there some reason that this would be impossible?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

I'm not sure what is currently provable, but here is a conjectural answer. Normally one measures the "size" of a rational number by taking the larger of the numerator and the denominator. This is called the height, $$ H(a/b) = \max\{|a|,|b|\},\quad\text{where $\gcd(a,b)=1$.} $$ And for a list of rationals, take the max of the heights. Then it is conjectured that for "most" elliptic curves $y^2=x^3+Ax+B$ with $A,B\in\mathbb Q$ and $4A^3+27B^2\ne0$, if there is any rational solution, thenthe smallest solutions $(x_0,y_0)$ has height that is exponential in the height of $A$ and $B$. Here "most" would mean a set of density 1, where we compute density by ordering the set of elliptic curves by the height of their coefficients (and for precision, normalize by changing variables $(x,y)\to(u^2x,u^3y)$ so that $A,B\in\mathbb Z$ and $|4A^3+27B^2|$ is minimized).

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is certainly interesting! Is the exponential growth known for specific examples? Is there anything known about growth of the absolute value rather than height? $\endgroup$
    – Fedya
    Commented Nov 5, 2017 at 10:04
  • $\begingroup$ I don't know of a specific family for which what i wrote is proven. Further, you may be asking for too much. Even for the elliptic curve conjecture, there are likely to be a some equations in the family with a small solution. By analogy, it is expected that for many squarefree $D$, the smallest solution of the Pell eqn $X^2-DY^2=1$ is exponential in $D$, but there are $D$ for which this is not the case. For your second equation, it seems unlikely if you just use absolute value, since there are infinitely many rational numbers with bounded absolute value. $\endgroup$
    – Joe Silverman
    Commented Nov 5, 2017 at 11:57
  • $\begingroup$ Yes, I'm not asking for anything to be bounded below -- just not bounded above. $\endgroup$
    – Fedya
    Commented Nov 5, 2017 at 12:52

You must log in to answer this question.

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