6
$\begingroup$

Consider any algebraic number $\alpha$ which is given by its minimal polynomial $f$. How can I compute the minimal polynomial of $\alpha^m$ for some natural number $m$? How efficient the algorithm is?

I assume that this problem is well-studied, but can anyone give me a reference, or some short description of the algorithm?

Thanks a lot!

$\endgroup$
2
  • $\begingroup$ I think the minimal polynomial of $\alpha$ and the minimal polynomial of $\alpha^m$ are not strongly related. (Except of course in some special cases.) $\endgroup$
    – rschwieb
    Oct 19, 2012 at 12:09
  • $\begingroup$ thanks. Somehow this question can be formulated as given $\alpha$, how to compute (symbolically) $\alpha^m$. I guess there must be some algorithm to do so. $\endgroup$
    – user29271
    Oct 19, 2012 at 12:23

2 Answers 2

6
$\begingroup$

Here's one way --- I don't know how efficient it is.

You know the polynomial for $\alpha$. Say it has degree $d$. That means you can express any power of $\alpha$ as a rational linear combination of $1,\alpha,\dots,\alpha^{d-1}$. In particular, you can express any power of $\alpha^m$ as such a linear combination. Then you can test, for various $r$, whether $1,\alpha^m,\alpha^{2m},\dots,\alpha^{rm}$ is a linearly independent set over the rationals. As soon as you get a set that isn't, you have your minimal polynomial for $\alpha^m$.

EDIT: For example, suppose $\alpha$ is a zero of $x^3-x-1$, and find a polynomial for $\beta=\alpha^2$. Well, $\alpha^3=\alpha+1$; $\alpha^4=\alpha^2+\alpha$; $\alpha^5=\alpha^3+\alpha^2=\alpha^2+\alpha+1$; $\alpha^6=\alpha^3+\alpha^2+\alpha=\alpha^2+2\alpha+1$. We find that $1,\beta,\beta^2,\beta^3$ are linearly dependent: $2\beta^2-\beta^3=\beta-1$. So our polynomial is $x^3-2x^2+x-1$.

$\endgroup$
1
$\begingroup$

(This is a question I wanted to ask; and doing a search before asking led me to this post. This should explain why a 5-year old question is getting an answer now).

I have one way and I am not sure it is efficient. I think there is no loss of generality assuming $\alpha$ to be an algebraic integer. Take the matrix $A$ for which $f(x)$ is the companion matrix.

Now computer the matrix power $A^m$. Then factors of characteristic polynomial of $A^m$ will lead to minimal polynomial of $\alpha^m$.

(I am curious when the characteristic polynomial of $A^m$ would itself be irreducible.)

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .