# Equal degree factoring of homogeneous polynomials over $\Bbb Q[x_1,\dots,x_n]$?

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.

• 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$. – Fan Zheng Sep 10 '17 at 2:17
• @FanZheng right and so for $n=2$ we know it. – Turbo Sep 10 '17 at 5:13
• 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$. – Emil Jeřábek Sep 10 '17 at 8:32
• @EmilJeřábek I assume the natural way. So may be there is hope now? – Turbo Sep 10 '17 at 9:52
• The factors may have exponentially many monomials, even if the original polynomial is sparse. – Emil Jeřábek Sep 10 '17 at 12:20

## 1 Answer

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.