# 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. – T.... 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? – T.... 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

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  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.