Uncomputably Large Integral Points on Algebraic Plane Curves?
<|reference_start|>Uncomputably Large Integral Points on Algebraic Plane Curves?: We show that the decidability of an amplification of Hilbert's Tenth Problem in three variables implies the existence of uncomputably large integral points on certain algebraic curves. We obtain this as a corollary of a new positive complexity result: the Diophantine prefixes EAE and EEAE are generically decidable. This means, taking the former prefix as an example, that we give a precise geometric classification of those polynomials f in Z[v,x,y] for which the question...   ``Does there exists a v in N such that for all x in N, there exists a y in N with f(v,x,y)=0?''   ...may be undecidable, and we show that this set of polynomials is quite small in a rigourous sense. (The decidability of EAE was previously an open question.) The analogous result for the prefix EEAE is even stronger. We thus obtain a connection between the decidability of certain Diophantine problems, height bounds for points on curves, and the geometry of certain complex surfaces and 3-folds.<|reference_end|>
@article{rojas1998uncomputably,
    title={Uncomputably Large Integral Points on Algebraic Plane Curves?},
    author={J. Maurice Rojas},
    journal={arXiv preprint arXiv:math/9809009},
    year={1998},
    archivePrefix={arXiv},
    eprint={math/9809009},
    primaryClass={math.NT cs.CC cs.SC math.AG math.LO}
}