Efficiently Detecting Torsion Points and Subtori
<|reference_start|>Efficiently Detecting Torsion Points and Subtori: 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.<|reference_end|>
@article{rojas2005efficiently,
    title={Efficiently Detecting Torsion Points and Subtori},
    author={J. Maurice Rojas},
    journal={arXiv preprint arXiv:math/0501388},
    year={2005},
    archivePrefix={arXiv},
    eprint={math/0501388},
    primaryClass={math.AG cs.CC math.NT}
}