# Independence of Roots

Let $f \in F_p[x]$ be an irreducible polynomial of degree $n$, where $p$ is prime. Prove that its roots are independent over $F_p$.

EDIT: It was pointed in the answers that this claim is true only for some irreducible polynomials. My question can be changed to: prove that for any $n$, such irreducible polynomial of degree $n$ exists.

Remarks:

1. This is false in characteristic zero: take $x^2+1 \in \mathbb{R}[x]$.
2. I think it's true for any finite field (i.e., $p$ can be a prime power)

Let $\theta$ be some root of $f$.

1. $F_p[\theta] = F_{p^n}$, and $\{\theta^i\}_{i=0}^{n-1}$ is a basis.
2. By Frobenius Automorphism and by the identity $x^{p^i}-x = \prod_{a \in F_{p^i}} (x-a)$, one can show that $\{\theta^{p^i}\}_{i=0}^{n-1}$ are all the roots of $f$. It also shows that all of $f$'s roots are in the extension - they are powers of $\theta$.
3. Since $F_p[\theta]$ contains all $f$'s roots, the claim is equivalent to: $Span \{\theta^{p^i}\} = Span \{ \theta^i\}$

The motivation is that I saw this fact used in a cool combinatorics proof, where the bijection $$\vec{a} \to \sum a_i \theta^{p^i}$$ from $(F_p)^n$ to $F_{p^n}$ was used, and I didn't understand why it is a bijection. (For the curious: if we restrict this bijection to Lyndon words of length $n$ with alphabet $F_p$, and send $\sum a_i \theta^{p^i}$ to $\text{minimal polynomial of} \sum a_i \theta^{p^i}$, it becomes a bijection of Lyndon words of length $n$ to irreudcible polynomials of degree $n$)

-
What does it mean for a root to be irreducible? –  Qiaochu Yuan Jul 23 '11 at 14:54
Do you mean a bijection between $(\mathbf{F}_p)^n$ and $\mathbf{F}_{p^n}$? –  Dylan Moreland Jul 23 '11 at 14:59
Judging from the rest of the OP's thinking he means "linearly independent over the prime field". –  Jyrki Lahtonen Jul 23 '11 at 14:59
Dylan and Jyrki - you are correct, I've fixed my typos. –  Ofir Jul 23 '11 at 15:04

For example the roots of the irreducible polynomial $p(x)=x^3+x+1\in\mathbf{Z}_2[x]$ sum up to zero: $$p(x)=(x-\alpha)(x-\alpha^2)(x-\alpha^4)=x^3+(\alpha+\alpha^2+\alpha^4)x^2+x+1,$$ so $\alpha+\alpha^2+\alpha^4=0$ is a non-trivial linear dependency relation.
Edit: OTOH it is not too difficult to show that $\theta$ can be chosen in such a way that we get linear independence. Look up normal basis. An argument that I happen to remember goes as follows. Let us view $F_{p^n}$ as a module $M$ over the polynomial ring $R=F_p[T]$, where we let the indeterminate $T$ act via the Frobenius automorphism: $T\cdot x=x^p$ for all $x\in M$. As $M$ is finite dimensional over $F_p$, it is obviously a torsion module, and as $R$ is a PID, we can write it as a direct sum cyclic $R$-modules in terms of the invariant factors: $$M=\bigoplus\sum_{i=1}^rR/p_i(T)R,$$ where always $p_i(T)|p_{i+1}(T)$. I claim that here actually $r=1$ and $p_r(T)=q(T)=T^n-1.$ Anyway $p_r(T)=a_0+a_1T+\cdots+a_kT^k$ annihilates all of $M$ (here $a_i\in F_P for i=0,1,\ldots,k$ at least one non-zero). It is well known that $q(T)$ annihilates $M$, so $k\le n$, because $p_r(T)$ is the lowest degree polynomial in $ann(M)$. But for all $x\in F_{p^n}$ $$a_0x+a_1x^p+\cdots+a_kx^{p^k}=0,$$ and this polynomial cannot have $p^n$ zeros unless $k=n$. Therefore $p_r(T)=q(T)$. But $\dim_{F_p}(R/p_i(T)R)=\deg p_i(T)$, so $n=\sum_i\deg p_i(T)$, and there is no room for any other invariant factor. Therefore $$M\cong_R R/q(T)R,$$ and $M$ is a cyclic $R$-module. Now we can let $\theta$ be any generator of $M$ as an $R$-module. The elements $T^i\cdot\theta=\theta^{p^i},i=0,1,\ldots,n-1$ are then a basis. QED
Oh, you are right. That's sad. I now realize that in the combinatorics problem it is enough to choose a root $\theta$ of a polynomial whose roots are independent, and that indeed it is not necessary that this property is always true. I will look up that term, "normal basis". –  Ofir Jul 23 '11 at 15:07