algebraic-number-theory
Primitive element theorem for finite fields
Can you explain $2$ points in the proof of the proposition below
$\bullet$ First $\alpha$ is the root of the polynomial $T^{p^s}-T$, because $\mathbb F_p(\alpha)$ is an extension field and in particular it is a group, so $\alpha^{p^s-1}=1$, for any nonzero $\alpha$, am I correct
$\bullet$ Second, Why do we sum up the number of roots, are they all distinct, I don't get the conclusion
A (base-$g$) discrete logarithm of a finite field $\Bbb{F}_q$, is a function $$ \log_g:\Bbb{F}_q^*\to\Bbb{Z}_{q-1} $$ defined via the equivalence $g^j=x\Leftrightarrow \log_g(x)=j$. For this to be well-defined it is imperative that $g$ is a primitive element, i.e. a generator of $\Bbb{F}_q^*$, and that the domain of $\log_g$ is the residue class ring of integer modulo $q-1$, as $g^{q-1}=g^0=1$.
It immediately follows that the discrete logarithm satisfies the familiar rules $$ \begin{aligned} \log_g(x\cdot y)&=\log_g(x)+\log_g(y),\\ \log_g(x^n)&=n\cdot\log_g(x) \end{aligned} $$ for all elements $x,y\in \Bbb{F}_q^*$ and all integers $n$. The arithmetic on the r.h.s. is that of the ring $\Bbb{Z}_{q-1}$.
It is known that when $q=8$, a zero $\alpha$ of $x^3+x+1$ generates $\Bbb{F}_8^*$. This is proven by the following calculation, where we repeatedly use the fact that we are working in characteristic two, and that we have the relation $\alpha^3=\alpha+1$. $$ \eqalign{ \alpha^0&=&&=1,\\ \alpha^1&=&&=\alpha,\\ \alpha^2&=&&=\alpha^2,\\ \alpha^3&=&&=1+\alpha,\\ \alpha^4&=&\alpha\cdot\alpha^3=\alpha(1+\alpha)&=\alpha+\alpha^2,\\ \alpha^5&=&\alpha\cdot\alpha^4=\alpha(\alpha+\alpha^2)=\alpha^2+\alpha^3=\alpha^2+(1+\alpha)&=1+\alpha+\alpha^2,\\ \alpha^6&=&\alpha\cdot\alpha^5=\alpha(1+\alpha+\alpha^2)=\alpha+\alpha^2+\alpha^3= \alpha+\alpha^2+(1+\alpha)&=1+\alpha^2,\\ \alpha^7&=&\alpha\cdot\alpha^6=\alpha(1+\alpha^2)=\alpha+\alpha^3=\alpha+(1+\alpha)&=1. }$$
We see from the end results in the last column that all the non-zero quadratic polynomials evaluated at $\alpha$ appear. This is yet another confirmation of the fact that $\alpha$ is a primitive element.
The discrete logarithm is used to replace the cumbersome multiplication (and raising to an integer power) of the field with more familiar integer arithmetic. Exactly like the old-timers used logarithm tables to replace the error-prone multiplication with the easier addition.
For example $$ (1+\alpha)(1+\alpha+\alpha^2)=\alpha^3\cdot\alpha^5=\alpha^8=\alpha^7\cdot\alpha=\alpha. $$ Note that both the base-$\alpha$ discrete logarithms and its inverse mapping are needed. I generate such a table as a part of the program initialization, whenever I carry out extensive computer-aided calculations involving a finite field. The above table gives the discrete logarithm when read from right to left, and the inverse mapping (that we actually produced above) when read from left to right.
Similarly with $q=16$ we use $\gamma$, a zero of $x^4+x+1$. This time the table looks like $$ \begin{aligned} \gamma^0&=&1\\ \gamma^1&=&\gamma\\ \gamma^2&=&\gamma^2\\ \gamma^3&=&\gamma^3\\ \gamma^4&=&\gamma+1\\ \gamma^5&=\gamma(\gamma+1)=&\gamma^2+\gamma\\ \gamma^6&=\gamma(\gamma^2+\gamma)=&\gamma^3+\gamma^2\\ \gamma^7&=\gamma^4+\gamma^3=&\gamma^3+\gamma+1\\ \gamma^8&=(\gamma^4)^2=&\gamma^2+1\\ \gamma^9&=\gamma(\gamma^2+1)=&\gamma^3+\gamma\\ \gamma^{10}&=\gamma^4+\gamma^2=&\gamma^2+\gamma+1\\ \gamma^{11}&=&\gamma^3+\gamma^2+\gamma\\ \gamma^{12}&=\gamma^4+\gamma^3+\gamma^2=&\gamma^3+\gamma^2+\gamma+1\\ \gamma^{13}&=\gamma^4+\gamma^3+\gamma^2+\gamma=&\gamma^3+\gamma^2+1\\ \gamma^{14}&=\gamma^4+\gamma^3+\gamma=&\gamma^3+1\\ (\gamma^{15}&=\gamma^4+\gamma=&1) \end{aligned} $$
Thus for example $$ (\gamma^3+1)(\gamma^2+1)=\gamma^{14}\cdot\gamma^8=\gamma^{22}=\gamma^7=\gamma^3+\gamma+1. $$
As another example of the use of this table I want to discuss the problem of factorizing $x^4+x+1$ over $\Bbb{F}_4$. To that end we need to first identify a copy of $\Bbb{F}_4$ as a subfield of $\Bbb{F}_{16}$. We just saw that $\gamma$ is of order fifteen. Therefore $\gamma^5=\gamma^2+\gamma$ and $\gamma^{10}=\gamma^2+\gamma+1$ are third roots of unity. It is then trivial to check that we have a homomorphism of fields $\sigma:\Bbb{F}_4\to\Bbb{F}_{16}$ given by $\sigma(\beta)=\gamma^5$. Note that composing this (from either end) by the Frobenius automorphism gives an alternative embedding $\beta\mapsto \gamma^{10}$.
Basic Galois theory tells us that $$ x^4+x+1=(x-\gamma)(x-\gamma^2)(x-\gamma^4)(x-\gamma^8) $$ as we get the other roots by repeatedly applying the Frobenius automorphism $F:x\mapsto x^2$. Here we see that the factor $$ (x-\gamma)(x-\gamma^4)=x^2+x(\gamma+\gamma^4)+\gamma^5=x^2+x+\gamma^5 $$ is stable under the automorphism $F^2$, and thus (as we also see directly!) has its coefficients in the subfield $\sigma(\Bbb{F}_4)$. The same holds for the remaining factor $$ (x-\gamma^2)(x-\gamma^8)=x^2+x(\gamma^2+\gamma^8)+\gamma^{10}=x^2+x+\gamma^{10}. $$ Pulling back the effect of $\sigma$ we get the desired factorization $$ x^4+x+1=(x^2+x+\beta)(x^2+x+\beta+1) $$ in $\Bbb{F}_4[x]$.
Here is a local version of similar tables for $\Bbb{F}_{256}$
The easiest way to do this is to note that
$$G=\operatorname{Gal}\left(\Bbb Q(\zeta_{27})/\Bbb Q\right)\cong \left(\Bbb Z/27\Bbb Z\right)^*$$
is a cyclic group of order $\phi(27)=27-9=18$. Then cyclic groups have unique subgroups of every order dividing the group order, that means there are exactly $6$ subgroups of $G=\langle x\rangle $, one for each divisor of $18$. They are $\{1\}, G, \langle x^2\rangle, \langle x^3\rangle, \langle x^6\rangle, \langle x^9\rangle$.
Here we can exploit the uniqueness to classify the fields. I give something of a more ad-hoc approach for each, because this one can be done with a quick-and-dirty approach, for the most part, and I think it's sometimes good to get your hands a bit dirty to explore the techniques you can employ. For $\{1\}$ and $G$, this is easy, as always we get $K^{\{1\}}=K$ and $K^G=\Bbb Q$. So let us turn to the others. $\Bbb Q(\zeta_3)$ is clearly a subfield, and has degree $\phi(3)=2$, so it corresponds to $\langle x^9\rangle$ which is the unique index $2$ subgroup of $G$. To see $\Bbb Q(\zeta_9)=K^{\langle x^3\rangle}$ (which is another obvious subfield) we check that it has degree $\phi(9)=6$ immediately giving the result.
For the others, we don't have the same low-hanging fruit, but we can note that $K\cap\Bbb R$ is the maximal real sub-field and is exactly the field fixed by complex conjugation--this is always how you can determine the maximal real subfield--which we know to have order $2$, hence index $9$. Ergo this must correspond to the group $\langle x^2\rangle$.
Finally we have $K^{\langle x^3\rangle}$. For this one I give an argument which is a flavor of the general case and in the spirit of the adjunction approach from your original question. We recall that the identification $G\cong \left(\Bbb Z/27\Bbb Z\right)^*$ comes from the fact that we can define the map $\sigma_r:\zeta_{27}\mapsto \zeta_{27}^r$. You can check that $\sigma_{2}$ generates $G$ by noting that $2^9=512=(19)(27)-1\equiv -1\mod{27}$. How can we use this to write out our field explicitly? Well, since $\sigma_2$ is a generator, we can just say our $x=\sigma_2$ without any loss of generality. We note that $x^3=\sigma_{2^3}=\sigma_8$. So to make our field fixed by this, we should just adjoin all points in the orbit of $\langle x^3\rangle$ somehow. We compute that
$$\begin{cases} 8^1\equiv 8 \\ 8^2\equiv 10 \\ 8^3\equiv -1\equiv 26 \\ 8^3\equiv -1\cdot 10 \equiv 17 \\ 8^5\equiv -1\cdot 8\equiv 15 \end{cases}\mod 27.$$
to get all the possibilities. We then guess that perhaps $K^{\langle x^3\rangle}=\Bbb Q(\alpha)$ with
$$\alpha=\zeta_{27}^8+\zeta_{27}^{10}+\zeta_{27}^{15}+\zeta_{27}^{17}+\zeta_{27}^{26}=\zeta_{27}^8(1+\zeta_{27}^2+\zeta_{27}^7+\underbrace{\zeta_{27}^{9}+\zeta_{27}^{18}}_{\zeta_3^2+\zeta_3=-1})=\zeta_{27}^{10}+\zeta_{27}^{15}.$$
And how can we see this is the case? We just check that this number, $\alpha$ is not fixed by a subgroup of $\langle x\rangle$ containing $\langle x^3\rangle$. Of course, this is only possible if $\alpha$ is fixed by all of $G$, which we can tell if we can demonstrate that some automorphism, say $\sigma_2$ for simplicity, doesn't fix $\alpha$. But this is simple: recall any $18$ consecutive powers of $\zeta_{27}$ will serve as a $\Bbb Q$-basis for $K$ treated as a vector space. Using the defining relationship $\zeta_{27}^{18}=-\zeta_{27}^9-1$ we note that
$$\begin{cases} \alpha = \zeta_{27}^{10}+\zeta_{27}^{18-3}=\zeta_{27}^{10}-\zeta_{27}^6-\zeta_{27}^{-3} \\ \sigma_2(\alpha)=\zeta_{27}^3+\zeta_{27}^{18+2}=\zeta_{27}^3-\zeta_{27}^{11}-\zeta_{27}^2 \end{cases}$$
Choose the basis to be $\zeta_{27}^{-3},\ldots , \zeta_{27}^{14}$. Then $\alpha$ and $\sigma_2(\alpha)$ are easily seen to be linearly independent over $\Bbb Q$, hence unequal, finishing the problem.
Addendum If you cannot see how any $18$ consecutive powers work, it's not hard to see: by degree considerations $1,\zeta_{27},\ldots, \zeta_{27}^{17}$ are a basis, but then multiplication by $\zeta_{27}^k$ is a linear transformation on the field with inverse give by multiplication by $\zeta_{27}^{-k}$, hence it sends a basis to a basis.
Best Answer
Your first point is correct. Expressing it as $T^{p^s}-T$ ensures that $0$ is also a root.
For the second part, the idea is as follows: if $\alpha\in K$ in not a primitive element, then $\mathbb F_p(\alpha)$ will be a proper subfield of $K$ - i.e. a finite field of order $p^s$ for some $s<r$ - and $\alpha$ will satisfy the polynomial $T^{p^s}-T$.
The proof then proceeds by a counting argument. Each $\alpha\in K$ that isn't a primitive element is the root of a polynomial $T^{p^s}-T$. And each such polynomial has at most $p^s$ roots. So the total number of elements of $K$ which are not primitive elements will be at most the total number of roots of polynomials of the form $T^{p^s}-T$, i.e. $$\#\{\alpha\in K:\alpha \text{ is not a primitive element}\} \le \sum_{s=1}^{r-1}p^s<p^r$$ So the number of non-primitive elements is less than $|K| = p^r$. Hence, there must be a primitive element.