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).