Uncomputably large integral points on algebraic plane curves?

DOI10.1016/S0304-3975(99)00188-7MaRDI QIDQ1978704zbMATH OpenOpenAlexFDO

Authors J. Maurice Rojas

Publication date 4 June 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9809009

zbMATH Keywords

decidabilitypolynomialsHilbert's Tenth Problemheight boundsdiophantine prefixgeometry of complex surfaces and 3-foldsuncomputably large integral points on algebraic curves

Mathematics Subject Classification ID

[https://portal.mardi4nfdi.de/w/index.php?search=%2211G30%22&title=Special%3ASearch&profile=advanced&fulltext=1&ns120=1 Curves of arbitrary genus or genus ( e 1) over global fields (11G30)] Rational and ruled surfaces (14J26) Decidability of theories and sets of sentences (03B25) Diophantine equations in many variables (11D72) Undecidability and degrees of sets of sentences (03D35) Decidability (number-theoretic aspects) (11U05) Curves in algebraic geometry (14H99) Arithmetic problems in algebraic geometry; Diophantine geometry (14G99)

Abstract: 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.

Recommendations

• Large Integral Points on Elliptic Curves
• On the number of integral points on algebraic curves
• On Certain Plane Curves with Many Integral Points
• Integer points on a curve and the plane Jacobian problem
• CHARACTERIZING ALGEBRAIC CURVES WITH INFINITELY MANY INTEGRAL POINTS
• scientific article; zbMATH DE number 2149958
• Real algebraic curves with large finite number of real points
• scientific article; zbMATH DE number 1129318
• Integral points on hyperelliptic curves
• scientific article; zbMATH DE number 7024806

Cites work

• scientific article; zbMATH DE number 435565 (Why is no real title available?)
• scientific article; zbMATH DE number 4189884 (Why is no real title available?)
• scientific article; zbMATH DE number 3838204 (Why is no real title available?)
• scientific article; zbMATH DE number 3765914 (Why is no real title available?)
• scientific article; zbMATH DE number 34788 (Why is no real title available?)
• scientific article; zbMATH DE number 42574 (Why is no real title available?)
• scientific article; zbMATH DE number 3465382 (Why is no real title available?)
• scientific article; zbMATH DE number 3572315 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1113847 (Why is no real title available?)
• scientific article; zbMATH DE number 747049 (Why is no real title available?)
• scientific article; zbMATH DE number 916043 (Why is no real title available?)
• scientific article; zbMATH DE number 3278404 (Why is no real title available?)
• scientific article; zbMATH DE number 3308501 (Why is no real title available?)
• Algebraic Geometry. I: Complex projective varieties.
• An algorithm for computing an integral basis in an algebraic function field
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Classification of Quantifier Prefixes Over Diophantine Equations
• Computational complexities of diophantine equations with parameters
• Contributions to the theory of diophantine equations I. On the representation of integers by binary forms
• Diophantine approximations and value distribution theory
• Integer Points on Curves of Genus 2 and their Jacobians
• Mathematical problems for the next century
• On S-integral solutions of the equation y^ m=f(x)
• On the complexity of Diophantine geometry in low dimensions (extended abstract)
• On the distribution of integer points on curves of genus zero
• Points entiers sur les courbes de genre 0
• Solving degenerate sparse polynomial systems faster
• Sur le théorème de Runge
• Universal diophantine equation

Cited in

(3)

• Mixed quantifier prefixes over Diophantine equations with integer variables
• On the distribution of integer points on curves of genus zero
• Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy

This page was built for publication: Uncomputably large integral points on algebraic plane curves?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1978704)