Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a irreducible polynomial $f \in K[x]$ where $|K|=q$ is a finite field and $\deg(f)=n$. If $\alpha$ is a root of $f$ why are $\alpha, \alpha^q, \dots, \alpha^{q^{n-1}}$ the only possible candidates for the roots of $f$?

share|improve this question

3 Answers 3

up vote 5 down vote accepted

Amended in response to Arturo Magidin's comments.

$\beta^q = \beta$ for all $\beta \in \mathbb F_q$. Also, in any field that includes $\mathbb F_q$ as a subfield, $(a-b)^q = a^q - b^q$. Now suppose that $\alpha$ is an element in a field that contains $\mathbb F_q$ as a subfield, and that $f(\alpha)= 0$. Then, $$ 0 = [f(\alpha)]^q = \left[\sum_{i=0}^n f_i \alpha^i\right]^q = \sum_{i=0}^n (f_i)^q (\alpha^i)^q = \sum_{i=0}^n f_i (\alpha^q)^i = f(\alpha^q) $$ and so $f(\alpha) = 0 \Rightarrow f(\alpha^q) = 0$. It follows that the elements $\alpha, \alpha^q, \alpha^{q^2}, \alpha^{q^3}\cdots $ are roots of $f(x)$. How many of these are distinct? Suppose that $\alpha^{q^0}, \alpha^{q^1}, \cdots, \alpha^{q^{m-1}}$ are distinct elements but $\alpha^{q^m}$ is a repeat, that is, $\alpha^{q^m} = \alpha^{q^i}$ for some $i \in \{0, 1, \ldots, m-1\}$. If $i$ were greater than $0$, then we would have that $$\left(\alpha^{q^{i-1}}\right)^q = \alpha^{q^i} = \alpha^{q^m} = \left(\alpha^{q^{m-1}}\right)^q \Rightarrow \left(\alpha^{q^{i-1}}\right)^q - \left(\alpha^{q^{m-1}}\right)^q = 0 \Rightarrow \left(\alpha^{q^{i-1}} - \alpha^{q^{m-1}}\right)^q = 0$$ and so $\alpha^{q^{i-1}} = \alpha^{q^{m-1}}$ in contradiction to the hypothesis that $\alpha^{q^0}, \alpha^{q^1}, \cdots, \alpha^{q^{m-1}}$ are distinct elements. We conclude that $\alpha^{q^m} = \alpha$. Now consider the polynomial $g(x)$ defined as $$g(x) = \prod_{i=0}^{m-1}\left(x - \alpha^{q^i}\right) = \sum_{j=0}^m g_jx^j$$ whose roots are the $m$ distinct elements $\alpha^{q^0}, \alpha^{q^1}, \cdots, \alpha^{q^{m-1}}$. Then $$\begin{align*} [g(x)]^q &= \left[\prod_{i=0}^{m-1}\left(x - \alpha^{q^i}\right)\right]^q = \prod_{i=0}^{m-1}\left(x - \alpha^{q^i}\right)^q = \prod_{i=0}^{m-1}\left(x^q - \alpha^{q^{i+1}}\right)\\ &= \prod_{k=1}^{m}\left(x^q - \alpha^{q^{k}}\right) = \prod_{i=0}^{m-1}\left(x^q - \alpha^{q^i}\right) = g(x^q). \end{align*}$$ Thus, $\displaystyle [g(x)]^q = \left[ \sum_{j=0}^m g_jx^j\right]^q = \sum_{j=0}^m (g_j)^q(x^j)^q = \sum_{j=0}^m (g_j)^q(x^q)^j$ equals $\displaystyle g(x^q) = \sum_{j=0}^m g_j(x^q)^j$, that is, proving that $(g_j)^q = g_j$ for $0 \leq j \leq m$. Therefore, we see that $g(x) \in \mathbb F_q[x]$. But, $g(x)$ is a divisor of $f(x)$ which is given to be irreducible over $\mathbb F_q$. So it must be that $m = n$ and $f(x)$ is a scalar multiple of $g(x)$. Thus, $\alpha^{q^0}, \alpha^{q^1}, \cdots, \alpha^{q^{n-1}}$ are precisely the $n$ distinct roots of the degree-$n$ irreducible polynomial $f(x) \in \mathbb F_q[x]$.

share|improve this answer
    
@ArturoMagidin Yes, I should have been more careful in what I wrote. Comments on the revised version would be appreciated. –  Dilip Sarwate Jul 4 '12 at 4:46
1  
More than fine now, as far as I can tell. I'll delete the previous comment. –  Arturo Magidin Jul 4 '12 at 4:51
    
Why is $(a-b)^q = a^q-b^q$ in every field extension? –  joachim Jul 4 '12 at 16:12
    
@joachim: Because the field is of characteristic $p$, so $(a-b)^p = a^p-b^p$ (every other term has coefficient a multiple of $p$). Inductively, we obtain $(a-b)^{p^n} = a^{p^n} - b^{p^n}$ for all $n\geq 1$; and $q$ is a power of $p$. –  Arturo Magidin Jul 4 '12 at 16:35

They are all roots, at any rate.

Note that $K(\alpha)$ is an extension of degree $n$ of $K$. The Galois group is cyclic, generated by the Frobenius automorphism $a\longmapsto a^q$. As always, the image of a root $\alpha$ of a polynomial $f(x)\in K[x]$ under any element of $\mathrm{Gal}(E/K)$, where $E$ is a Galois extension of $K$, must also be a root of $f$. In particular, if $\alpha$ is a root, then so is $\alpha^q$, hence so is $\alpha^{q^2}$, and so on. The Galois group is of order $n$, so we end up with $\alpha$, $\alpha^q,\ldots,\alpha^{q^{(n-1)}}$ are all roots.

Now, there are $n$ of them. The questions is whether they are all distinct. If they are indeed all distinct, then that's it, they are all the roots and the only possible roots.

If $\alpha^{q^i} = \alpha^{q^j}$ with $0\leq i\leq j\leq n-1$, then that means that $\sigma^i(\alpha) = \sigma^j(\alpha)$ (where $\sigma$ is the Frobenius automorphisms); then $\alpha = \sigma^{j-i}(\alpha)$, which would mean that $\alpha$ lies in the fixed field of $\langle \sigma^{j-i}$. But since $K(\alpha)$ is generated by $\alpha$, $\alpha$ does not lie in any strictly intermediate field of $K(\alpha)/K$; that means that the fixed field of $\sigma^{j-i}$ must be $K(\alpha)$, hence $\sigma^{j-i} = \mathrm{id}$, so $j=i$. Therefore, they are all distinct, so they are in fact all the roots.

share|improve this answer

Let $E = K(\alpha) = K[x] / (f(x))$. For $\sigma \in \text{Gal}(E / K)$, $\sigma(\alpha)$ is a root of $f(x)$. The Galois group of finite extensions of finite fields is (cyclic) of order $n$. $\sigma_k(x) = x^{q^k}$ for $0 \leq k < n$ are $n$ of these automorphisms.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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