Given $f(x_1,\dots,x_n)\in\Bbb Q[x_1,\dots,x_n]$ of form $\prod_{i=1}^df_i(x_1,\dots,x_n)$ where each of $f,f_i$ are homogeneous and each $f_i$ are irreducible and of equal degree what is the best technique to factor such polynomials?

Assume $GCD$ of coefficients is $1$ after removing denominator.

  1. Is there a deterministic or a randomized algorithm that is polynomial time in complexity in total degree ($d$), variables ($n$) and number of bits in coefficients ($L$)?

  2. Is there an algorithm that is at least in $O(2^{c\cdot n}(d\cdot L)^c)$ for a fixed real $c$?

Assume that the polynomial and its factors have at most $\max(2^{2d},2^{2n})$ coefficients.

  • 2
    $\begingroup$ Presumably by setting $x_n=1$ it's the same as factoring general (inhomogeneous) polynomials over $\mathbb Q$, up to some powers of $x_n$. $\endgroup$ – Fan Zheng Sep 10 '17 at 2:17
  • $\begingroup$ @FanZheng right and so for $n=2$ we know it. $\endgroup$ – 1.. Sep 10 '17 at 5:13
  • $\begingroup$ For 1, how do you represent the polynomials? A polynomial with degree $d$ and $n$ variables may have as many $\binom{n+d}n$ monomials, which is exponential if $n\approx d$. $\endgroup$ – Emil Jeřábek Sep 10 '17 at 8:32
  • $\begingroup$ @EmilJeřábek I assume the natural way. So may be there is hope now? $\endgroup$ – 1.. Sep 10 '17 at 9:52
  • $\begingroup$ The factors may have exponentially many monomials, even if the original polynomial is sparse. $\endgroup$ – Emil Jeřábek Sep 10 '17 at 12:20

Note that a polynomial of degree $d$ with $n$ variables may have $\binom{n+d}n$ monomials, hence both input and output may have size exponential in $n$ and $d$, if the polynomials are represented by lists of monomials and coefficients, as the OP seems to assume. (The additional assumption at the end of the question is completely unhelpful, as $\binom{n+d}n\le\max\{2^{2d},2^{2n}\}$ anyway.)

Having said that, von zur Gathen and Kaltofen [1] prove that there exist randomized factoring algorithms for multivariate polynomials over $\mathbb Q$ (and certain other fields) that work in time polynomial in the size of the input and output: i.e., $d$, $n$, $L$, and the number of nonzero coefficients.

[1] Joachim von zur Gathen and Erich Kaltofen: Factoring sparse multivariate polynomials, Journal of Computer and System Sciences 31 (1985), no. 2, pp. 265–287, doi: 10.1016/0022-0000(85)90044-3.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.