Is it harder to factor a polynomial or to find a root?
HTML articles powered by AMS MathViewer
- by Russell Miller PDF
- Trans. Amer. Math. Soc. 362 (2010), 5261-5281 Request permission
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
- Harold M. Edwards, Galois theory, Graduate Texts in Mathematics, vol. 101, Springer-Verlag, New York, 1984. MR 743418
- Michael D. Fried and Moshe Jarden, Field arithmetic, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 11, Springer-Verlag, Berlin, 1986. MR 868860, DOI 10.1007/978-3-662-07216-5
- Richard M. Friedberg, Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post’s problem, 1944), Proc. Nat. Acad. Sci. U.S.A. 43 (1957), 236–238. MR 84474, DOI 10.1073/pnas.43.2.236
- Richard M. Friedberg and Hartley Rogers Jr., Reducibility and completeness for sets of integers, Z. Math. Logik Grundlagen Math. 5 (1959), 117–125. MR 112831, DOI 10.1002/malq.19590050703
- A. Fröhlich and J. C. Shepherdson, Effective procedures in field theory, Philos. Trans. Roy. Soc. London Ser. A 248 (1956), 407–432. MR 74349, DOI 10.1098/rsta.1956.0003
- Nathan Jacobson, Basic algebra. I, 2nd ed., W. H. Freeman and Company, New York, 1985. MR 780184
- L. Kronecker, Grundzüge einer arithmetischen Theorie der algebraischen Größen, J. f. Math. 92 (1882), 1-122.
- G. Metakides and A. Nerode, Effective content of field theory, Ann. Math. Logic 17 (1979), no. 3, 289–320. MR 556895, DOI 10.1016/0003-4843(79)90011-1
- Russell Miller, Computable fields and Galois theory, Notices Amer. Math. Soc. 55 (2008), no. 7, 798–807. MR 2436510
- 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 qcpages.qc.cuny.edu/$\tilde {~}$rmiller/research.html.
- Russell Miller, $d$-computable categoricity for algebraic fields, J. Symbolic Logic 74 (2009), no. 4, 1325–1351. MR 2583823, DOI 10.2178/jsl/1254748694
- A. A. Mučnik, On the unsolvability of the problem of reducibility in the theory of algorithms, Dokl. Akad. Nauk SSSR (N.S.) 108 (1956), 194–197 (Russian). MR 0081859
- Michael O. Rabin, Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc. 95 (1960), 341–360. MR 113807, DOI 10.1090/S0002-9947-1960-0113807-4
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
- Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
- V. Stoltenberg-Hansen and J. V. Tucker, Computable rings and fields, Handbook of computability theory, Stud. Logic Found. Math., vol. 140, North-Holland, Amsterdam, 1999, pp. 363–447. MR 1720739, DOI 10.1016/S0049-237X(99)80028-7
- B. L. van der Waerden, Algebra. Vol. I, Springer-Verlag, New York, 1991. Based in part on lectures by E. Artin and E. Noether; Translated from the seventh German edition by Fred Blum and John R. Schulenberger. MR 1080172, DOI 10.1007/978-1-4612-4420-2
- Helmut Völklein, Groups as Galois groups, Cambridge Studies in Advanced Mathematics, vol. 53, Cambridge University Press, Cambridge, 1996. An introduction. MR 1405612, DOI 10.1017/CBO9780511471117
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
- MR Author ID: 679194
- Email: Russell.Miller@qc.cuny.edu
- 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
- © Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 362 (2010), 5261-5281
- MSC (2010): Primary 12E05, 03D45; Secondary 03C57, 12L05
- DOI: https://doi.org/10.1090/S0002-9947-2010-04918-9
- MathSciNet review: 2657679