Remote Access Transactions of the American Mathematical Society
Green Open Access

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

  • 1. H.M. Edwards, Galois Theory (New York: Springer-Verlag, 1984). MR 743418 (87i:12002)
  • 2. M.D. Fried & M. Jarden, Field Arithmetic (Berlin: Springer-Verlag, 1986). MR 868860 (89b:12010)
  • 3. R.M. Friedberg, Two recursively enumerable sets of incomparable degrees of unsolvability, Proc. Nat. Acad. Sci. (USA) 43 (1957), 236-238. MR 0084474 (18:867a)
  • 4. R.M. Friedberg & H. Rogers, Jr., Reducibility and completeness for sets of integers, Z. Math. Logik Grundlagen Math. 5 (1959), 117-125. MR 0112831 (22:3682)
  • 5. A. Frohlich & J.C. Shepherdson, Effective procedures in field theory, Phil. Trans. Royal Soc. London, Series A 248 (1956), 407-432. MR 0074349 (17:570d)
  • 6. N. Jacobson, Basic Algebra I (New York: W.H. Freeman & Co., 1985). MR 780184 (86d:00001)
  • 7. L. Kronecker, Grundzüge einer arithmetischen Theorie der algebraischen Größen, J. f. Math. 92 (1882), 1-122.
  • 8. G. Metakides & A. Nerode, Effective content of field theory, Annals of Mathematical Logic 17 (1979), 289-320. MR 556895 (82b:03082)
  • 9. R.G. Miller, Computable fields and Galois theory, Notices of the American Mathematical Society 55 (August 2008) no. 7, 798-807. MR 2436510
  • 10. R.G. Miller, Computability and differential fields: A tutorial, to appear in Differential Algebra and Related Topics: Proceedings of the Second International Workshop, eds. L. Guo & W. Sit, to appear. Also available at$ \tilde{~}$rmiller/research.html.
  • 11. R.G. Miller, $ \boldsymbol{d}$-Computable categoricity for algebraic fields, The Journal of Symbolic Logic 74 (2009), 1325-1351. MR 2583823
  • 12. A.A. Muchnik, On the unsolvability of the problem of reducibility in the theory of algorithms, Dokl. Akad. Nauk SSSR, N.S. 109 (1956), 194-197 (Russian). MR 0081859 (18:457a)
  • 13. M. Rabin, Computable algebra, general theory, and theory of computable fields, Transactions of the American Mathematical Society 95 (1960), 341-360. MR 0113807 (22:4639)
  • 14. H. Rogers, Jr., Theory of Recursive Functions and Effective Computability (New York: McGraw-Hill Book Co., 1967). MR 0224462 (37:61)
  • 15. R.I. Soare, Recursively Enumerable Sets and Degrees (New York: Springer-Verlag, 1987). MR 882921 (88m:03003)
  • 16. V. Stoltenberg-Hansen & J.V. Tucker, Computable Rings and Fields, in Handbook of Computability Theory, ed. E.R. Griffor (Amsterdam: Elsevier, 1999), 363-447. MR 1720739 (2000g:03100)
  • 17. B.L. van der Waerden, Algebra, volume I, trans. F. Blum & J.R. Schulenberger (New York: Springer-Verlag, 1970 hardcover, 2003 softcover). MR 1080172 (91h:00009a)
  • 18. H. Völklein, Groups as Galois Groups: An Introduction (Cambridge: Cambridge University Press, 1996). MR 1405612 (98b:12003)

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.

American Mathematical Society