Efficiently Detecting Torsion Points and Subtori

Details Efficiently Detecting Torsion Points and Subtori Efficiently Detecting Torsion Points and Subtori

2005-01-23

arxiv.org/abs/math/0501388v4

Mathematics

Algebraic Geometry

21 pages, no figures. Final version, with additional commentary and references. Also fixes a gap in Theorems 2 (now Theorem 1.

Scientific paper

Suppose X is the complex zero set of a finite collection of polynomials in Z[x_1,...,x_n]. We show that deciding whether X contains a point all of whose coordinates are d_th roots of unity can be done within NP^NP (relative to the sparse encoding), under a plausible assumption on primes in arithmetic progression. In particular, our hypothesis can still hold even under certain failures of the Generalized Riemann Hypothesis, such as the presence of Siegel-Landau zeroes. Furthermore, we give a similar (but UNconditional) complexity upper bound for n=1. Finally, letting T be any algebraic subgroup of (C^*)^n we show that deciding whether X contains T is coNP-complete (relative to an even more efficient encoding),unconditionally. We thus obtain new non-trivial families of multivariate polynomial systems where deciding the existence of complex roots can be done unconditionally in the polynomial hierarchy -- a family of complexity classes lying between PSPACE and P, intimately connected with the P=?NP Problem. We also discuss a connection to Laurent's solution of Chabauty's Conjecture from arithmetic geometry.

Affiliated with

Also associated with

No associations

Rating

Efficiently Detecting Torsion Points and Subtori does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficiently Detecting Torsion Points and Subtori, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficiently Detecting Torsion Points and Subtori will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-473425