Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)



Is it harder to factor a polynomial or to find a root?

Author: Russell Miller
Journal: Trans. Amer. Math. Soc. 362 (2010), 5261-5281
MSC (2010): Primary 12E05, 03D45; Secondary 03C57, 12L05
Published electronically: May 19, 2010
MathSciNet review: 2657679
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For a computable field $ F$, the splitting set $ S$ is the set of polynomials $ p(X)\in F[X]$ which factor over $ F$, and the root set $ R$ is the set of polynomials with roots in $ F$. Work by Frohlich and Shepherdson essentially showed these two sets to be Turing-equivalent, surprising many mathematicians since it is not obvious how to compute $ S$ from $ R$. We apply other standard reducibilities from computability theory, along with a healthy dose of Galois theory, to compare the complexity of these two sets. We show, in contrast to the Turing equivalence, that for algebraic fields the root set has slightly higher complexity: both are computably enumerable, and computable algebraic fields always have $ S\leq_1 R$, but it is possible to make $ R\not\leq_m S$. So the root set may be viewed as being more difficult than the splitting set to compute.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 12E05, 03D45, 03C57, 12L05

Retrieve articles in all journals with MSC (2010): 12E05, 03D45, 03C57, 12L05

Additional Information

Russell Miller
Affiliation: Department of Mathematics, Queens College – C.U.N.Y., 65-30 Kissena Blvd., Flushing, New York 11367 – and – Ph.D. Programs in Computer Science and Mathematics, The Graduate Center of C.U.N.Y., 365 Fifth Avenue, New York, New York 10016

Received by editor(s): June 11, 2008
Published electronically: May 19, 2010
Additional Notes: The author was partially supported by Grant # 13397 from the Templeton Foundation, and by Grants # PSCREG-38-967 and 61467-00 39 from The City University of New York PSC-CUNY Research Award Program
Article copyright: © Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.