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

Miller, Russell

doi:10.1090/S0002-9947-2010-04918-9

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