|
Is it harder to factor a polynomial or to find a root?
Author(s):
Russell
Miller
Journal:
Trans. Amer. Math. Soc.
362
(2010),
5261-5281.
MSC (2010):
Primary 12E05, 03D45;
Secondary 03C57, 12L05
Posted:
May 19, 2010
MathSciNet review:
2657679
Retrieve article in:
PDF
Abstract |
References |
Similar articles |
Additional information
Abstract:
For a computable field , the splitting set is the set of polynomials which factor over , and the root set is the set of polynomials with roots in . 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 from . 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 , but it is possible to make . So the root set may be viewed as being more difficult than the splitting set to compute.
References:
-
- 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 qcpages.qc.cuny.edu/
rmiller/research.html. - 11.
- R.G. Miller,
-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
Email:
Russell.Miller@qc.cuny.edu
DOI:
10.1090/S0002-9947-2010-04918-9
PII:
S 0002-9947(2010)04918-9
Received by editor(s):
June 11, 2008
Posted:
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 of article:
Copyright
2010,
American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.
|