Factoring polynomials and finding roots
Russell Miller
City University of New York
We will use computability theory to investigate the difficulty of two standard questions from algebra. First, given a field F and a polynomial p∈ F[X], does the equation p=0 have a solution in F? And second, is p(X) irreducible in F[X]? Obviously these two questions are related, but it is not immediately clear which one is more difficult to answer. Indeed, it is not clear how one should measure the “difficulty” of answering these questions.
To address this problem, we will consider computable fields, which are countable fields in which we have algorithms for listing all the field elements and for the basic field operations. It has been known since 1960 that in this context, the two questions are equivalent under the standard notion of Turing reducibility: an algorithm for answering either question can be used to give an algorithm for answering the other one. However, computability theory also provides more precise measures of difficulty, and using one of these measures, known as 1-reducibility, we will show that one of the two questions can definitively be said to be more difficult in general than the other. To find out which is which, come to the talk!
Russell Miller is professor of mathematics at Queens College of CUNY and also at the CUNY Graduate Center. He conducts research in mathematical logic, especially computability theory and its interaction with other areas of mathematics, as in computable model theory. He received his doctorate from the University of Chicago in 2000, as a student of Robert Soare, and subsequently held a postdoctoral position at Cornell University until 2003, when he came to CUNY.