<p>Let an <em>explicit</em> 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.</p>

<p>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 <em>dense representation</em> of the polynomial, that is the list of all its coefficients.</p>

<blockquote>
  <p>Is there an explicit field for which</p>
  
  <ul>
  <li>either the best known algorithm has an exponential running time,</li>
  <li>or (better) there exists an exponential lower bound for irreducibility testing?</li>
  </ul>
</blockquote>

<p><strong>Quick clarification:</strong> There may be very different <em>explicit fields</em>, 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.</p>

<p><strong>References.</strong></p>

<p>[1] A. Fröhlich et J. C. Shepherdson (1955): <a href="http://dx.doi.org/10.1007/BF01180640">On the factorisation of polynomials in a finite number of steps</a>.<br>
[2] A. K. Lenstra, H. W. Lenstra Jr., L. Lovász (1982): <a href="http://dx.doi.org/10.1007/BF01457454">Factoring polynomials with rational coefficients</a>.<br>
[3] E.R. Berlekamp (1967): <a href="http://www3.alcatel-lucent.com/bstj/vol46-1967/articles/bstj46-8-1853.pdf">Factoring Polynomials Over Finite Fields</a>.</p>

CC BY-SA 3.0
2013-07-30T10:25:05.283Z
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.
minar
CC BY-SA 3.0
2013-07-30T12:16:29.977Z
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.
Bruno
CC BY-SA 3.0
2013-07-30T17:53:07.070Z
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: http://www.ams.org/mathscinet-getitem?mr=1512605
Joshua Grochow
CC BY-SA 3.0
2013-07-31T07:19:42.163Z
Thanks @JoshuaGrochow! I found the paper incredibly easy to read, even though my German lessons are quite old now...
Bruno
<algebraic-complexity><polynomials><exp-time-algorithms>
Exponential-time factorization of polynomials
Bruno
# Exponential-time factorization of polynomials

(Asked by: username_0 on 2013-07-30)

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](http://dx.doi.org/10.1007/BF01180640).  
[2] A. K. Lenstra, H. W. Lenstra Jr., L. Lovász (1982): [Factoring polynomials with rational coefficients](http://dx.doi.org/10.1007/BF01457454).  
[3] E.R. Berlekamp (1967): [Factoring Polynomials Over Finite Fields](http://www3.alcatel-lucent.com/bstj/vol46-1967/articles/bstj46-8-1853.pdf).

**Tags:** algebraic-complexity, polynomials, exp-time-algorithms

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: 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: http://www.ams.org/mathscinet-getitem?mr=1512605  
> **username_0**: Thanks @JoshuaGrochow! I found the paper incredibly easy to read, even though my German lessons are quite old now...  

---

## 0 answers

