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$
  • $\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 '12 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 '12 at 12:23
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$
  • $\begingroup$ The characteristic might not be irreducible. Simply consider x = sqrt(2). Now, the characteristic polynomial has degree 2, but the solution is x^2 = 2, needing only degree 1. $\endgroup$ – WorldSEnder Nov 4 at 4:45

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.