14
$\begingroup$

Let an explicit field be a field for which equality is decidable (in some standard model of computation). I am interested in the factorization of univariate polynomials over an explicit field.

It is known that over some explicit fields, testing irreducibility of polynomials is undecidable [1]. Though, over many fields, the irreducible factorization of polynomials is known to be computable in polynomial time, either deterministically (over $\mathbb Q$ [2] or any number field) or probabilistically (over finite fields [3]). Here the size of the input is the size of the dense representation of the polynomial, that is the list of all its coefficients.

Is there an explicit field for which

  • either the best known algorithm has an exponential running time,
  • or (better) there exists an exponential lower bound for irreducibility testing?

Quick clarification: There may be very different explicit fields, depending on the complexity (for instance) on the equality test or of the standard operations (addition, multiplication). Actually, I am not aware of any result about polynomial factorization which is not a polynomial time upper bound, or undecidability. So I am interested in any kind of different result (exponential time is just an example). Conditional lower bounds are of interest too.

References.

[1] A. Fröhlich et J. C. Shepherdson (1955): On the factorisation of polynomials in a finite number of steps.
[2] A. K. Lenstra, H. W. Lenstra Jr., L. Lovász (1982): Factoring polynomials with rational coefficients.
[3] E.R. Berlekamp (1967): Factoring Polynomials Over Finite Fields.

Improve this question
$\endgroup$
4
  • $\begingroup$ What do you mean by "explicit field" ? Are the operations is the field given by oracles or by algorithms ? I am asking because if the field's operations are given by efficient algorithms proving an exponential lower bound for factoring seems to imply of proof of ETH. $\endgroup$ – minar Jul 30 '13 at 10:25
  • $\begingroup$ I was aware while writing my question that some this question should be addressed. Actually, I am interested in both cases. I would be very much interested by the implication to ETH you mention. In other words, I am also interested in conditional lower bounds. $\endgroup$ – Bruno Jul 30 '13 at 12:16
  • $\begingroup$ Depending on your definition of "explicit field", the result you cite as [1] was also proven by van der Waerden much earlier (1930). Amazingly, he proved this before the notion of computability had been formally defined! See: ams.org/mathscinet-getitem?mr=1512605 $\endgroup$ – Joshua Grochow Jul 30 '13 at 17:53
  • $\begingroup$ Thanks @JoshuaGrochow! I found the paper incredibly easy to read, even though my German lessons are quite old now... $\endgroup$ – Bruno Jul 31 '13 at 7:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.