COMPUTATIONAL ARITHMETIC GEOMETRY

I've always loved the algorithmic side of number theory and have begun to look at certain problems which are on the verge of intractability.

In particular, I've explored the complexity of certain Diophantine equations, and have found an unusual result on the computability of height bounds for integral points on curves. In a recent paper:

  • ``Uncomputably Large Integral Points on Algebraic Plane Curves?,'' submitted for publication
    ...I show that the decidability of a class of Diophantine problems in four variables implies that there are uncomputably large integral points on certain algebraic plane curves.

    As for rational points, it is interesting to note that the corresponding analogue of Hilbert's Tenth Problem is still open. For instance, we don't even have an algorithm for deciding whether an arbitrary input elliptic curve has a rational point. (That would be the special case of 1 polynomial, 2 variables, degree 3.)

    So it is natural to focus on invariants that could simplify the problem. For instance, what if one restricts to equations whose underlying set of complex zeroes is finite? Suprisingly, this still leads to subtle questions. For, while one can use results of the 1980's to get a complexity upper bound of PSPACE to find all the rational points, can one decide their mere existence faster? The first evidence that the answer is yes appears in the following paper:

  • J. Maurice Rojas, Computational Arithmetic Geometry I: Sentences Nearly in the Polynomial Hierarchy, invited paper (journal version of an earlier extended abstract that appeared in the Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC '99, May 1-4, 1999, Atlanta, Georgia)), Journal of Computer and Systems Science, vol. 62 (2001), no. 2, march, pp. 216-235.

    On the more geometric end of arithmetic geometry, there is the problem of semi-stable reduction, which is a deepening of resolution of singularities. A special case of the semi-stable reduction problem can actually be reduced to questions on certain polyhedral subdivisions. This is covered in:

  • Dan Abramovich and J. Maurice Rojas, ``Extending Triangulations and Semistable Reduction,'' Proceedings of FoCM 2000, special meeting in honor of Steve Smale's 70th birthday (July 2000, City University of Hong Kong, Hong Kong), World Scientific (2002), pp. 1-13.

    More recently, I am working on a deep connection between algebraic sets over finite fields and algebraic sets over the complex numbers. In particular, extending earlier work of Koiran, I gave a new number-theoretic algorithm for the old Hilbert's Nullstellensatz problem:

  • J. Maurice Rojas, ``Dedekind Zeta Functions and the Complexity of Hilbert's Nullstellensatz,'' paper corresponding to semi-plenary talk at FoCM 2002 (August 5-14, 2002, University of Minnesota, Minneapolis), Journal of Complexity, submitted for publication.
    The underlying algorithm is the fastest current method for deciding whether an input system of multivariate equations has a complex root, but relies on a (so far) unproven number-theoretic hypothesis called RIPIT. Nevertheless, RIPIT is significantly weaker than the famous Generalized Riemann Hypothesis (which most experts believe), so one of my current interests is exploring analytic number theory estimates in the hopes of proving RIPIT. The end goal is to prove (unconditionally) the following characterization of the P=NP problem: Let DIM denote the problem of deciding where an input system of equations has a complex zero set of dimension greater than some input integer d. Then DIM in P implies that P differs from NP.

    It is worth noting that the above implication is new, and currently known only under the assumption of RIPIT (see my paper above).