2
$\begingroup$

Let $p\left( x\right) =% %TCIMACRO{\tprod \limits_{k=1}^{m}}% %BeginExpansion {\textstyle\prod\limits_{k=1}^{m}} %EndExpansion \left( x^{e_{k}}-\omega_{k}^{e_{k}}\right) $ be a polynomial with $\omega_{k}\in\mathbb{R}$ and $e_{k}\geq2$. Is there any procedure to determine the vector of exponents $\left( e_{1},\ldots,e_{m}\right) $ without knowning any factorization of $p$?

If an order $e_{1}\leq e_{2}\leq\cdots\leq e_{m}$ is stated, I know that there exists at least a factor $\left( x^{e_{1}}-\omega_{1}^{e_{1}}\right) $.

Improve this question
$\endgroup$
3
  • $\begingroup$ For uniqueness of such a factorization it's necessary to take $\omega_i \geq 0$ for all $i = 1, \cdots m$. ($x^2-1 = (x-1)(x+1) $) $\endgroup$
    – Mohammad Ghiasi
    Jun 8, 2015 at 12:54
  • $\begingroup$ Do we know $m$? $\endgroup$
    – Mohammad Ghiasi
    Jun 8, 2015 at 12:54
  • $\begingroup$ Are you interested if this can be implemented in practice? With what precision do you have the coefficients of p(x)? $\endgroup$
    – joro
    Jun 8, 2015 at 16:30

1 Answer 1

Reset to default
1
$\begingroup$

A rough idea is to compute $\gcd\left(p(x),p(\xi_n\cdot x)\right)$ for various prime $n$, where $\xi_n$ is a primitive $n$-th power root of unity, which will extract the factors with powers of $x$ divisible by $n$.

For example, $\gcd(p(x),p(-x))$ will give the product of factors with $x$ in even power (assuming that $e_k$ are maximized, e.g., we have $x^6-\omega_1^6$ instead of $(x^3-\omega_1^3)(x^3-(-\omega_1)^3)$). Then we replacing $x^2$ with $x$ in the resulting polynomial, and iterate.

If there are no even powers, we try $n=3$ etc.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Does this work in practice? gcd over the reals is not exact AFAICT, you have rounding errors. $\endgroup$
    – joro
    Jun 8, 2015 at 15:11
  • $\begingroup$ @joro: If the given polynomial has rational coefficients, one can avoid dealing with real numbers by working with polynomials in $\mathbb{Q}[x,y]$ modulo the cyclotomic polynomial $\Phi_n(y)$. Here the indeterminate $y$ represents an algebraic counterpart of the primitive $n$-th power root of unity. $\endgroup$
    – Max Alekseyev
    Jun 8, 2015 at 15:27
  • $\begingroup$ Agree, if it has rational coefficients this is true. But if the coefficients are reals, this appears complicated in practice. $\endgroup$
    – joro
    Jun 8, 2015 at 16:29
  • $\begingroup$ Not only is it complicated in practice, it is undecidable in general. See the wikipedia on Richardson's theorem. So, to answer the original post, there is no "procedure" to determine the vector of exponents, because there is not even a procedure to determine whether two real numbers $\alpha,\beta$ are equal. So you could consider the polynomial $f(x):=(x^3-\alpha^3)(x^3-(-\beta)^3)$ and be unable to tell (using a fixed algorithm which is independent of $\alpha,\beta$) whether $f(x)=x^6-\alpha^6$ or not. $\endgroup$
    – Pace Nielsen
    Aug 7, 2015 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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