Is every element of GF(p^k) whose degree is k a generator?

Question

I'm reading notes on minimal polynomials and finite fields taken from Jim Belk's webpage

Proposition 7 goes:

It seems to me there exists a counterexample to this statement:

• The number of elements of order $p^k - 1$ in $\mathbb{F}_{p^k}$ (i.e. generators) is $$\varphi(p^k - 1)$$
• The number of elements of degree $k$ is the number of irreducible polynomials of degree $k$ over $\mathbb{F}_p$ times $k$ (each yields polynomial yields $k$ unique algebraic numerbs of degree $k$), which is $$k \cdot \frac{1}{k}\sum\limits_{d \mid k} \ \mu(k/d) \cdot p^{d} = \sum\limits_{d \mid k} \ \mu(k/d) \cdot p^{d}$$
• Taking $p = 2, k = 4$, we get: $$\varphi(2^4 - 1) = \varphi(15) = 2 * 4 = 8$$ $$ \sum\limits_{d \mid 4} \ \mu(4/d) \cdot 2^{d} = 2^1 * \mu(4) + 2^2 * \mu(2) + 2^4 * \mu(1) = 0 -4 + 16 = 12 $$
• And indeed, $x^{16} - x$ factorizes over $\mathbb{F}_2$ as $x (x + 1) (x^2 + x + 1) (x^4 + x + 1) (x^4 + x^3 + 1) (x^4 + x^3 + x^2 + x + 1)$, containing 3 polynomials of degree 4, each of which yields 4 unique algebraic numbers [of degree 4].
• Also, there is this python code which backs up this discrepancy.

Let's take a look at the proof in the notes:

It seems like this proof is incomplete: what implies that all the $[x]$, $[x^2]$, ..., $[x^{p^k - 1}]$ residues yield different results when applied to $a$?

Still, this looks fishy. Am I wrong? Is there a mistake in the counter-argument?

Answer 1

The Proposition 7 is OK. Here are some comments.

The linked text gives a definition for a "generator" as follows:

Generators for Fields

There is a notion of a generator for a field. This is similar to, but distinct from, the notion of a primitive element.

Definition: Generator for a Field

Let $\Bbb F$ be a finite field of characteristic $p$. An element $a\in\Bbb F$ is called a generator for $\Bbb F$ if the set $$ \{\ f(a)\ | \ f(x) ∈ \Bbb Z_p[x]\ \} $$ is equal to $\Bbb F$.

So such a generator is a generator for $\Bbb F$ in its field structure. In other words, $a$ is a generator iff starting from $1$ and $a$ and using all field operations (plus, minus, times, divided by something non-zero) we get all elements of $\Bbb F$.

Your counterexample works with "generators" for the underlying group structure of the group of non-zero field elements. The operation being multiplication. Yes, this is a cyclic group of order $q:=p^k$, it is isomorphic to the additive group $(\Bbb Z/q,+)$ - which is generated by $1$ - and this and any other generator is relatively prime to $q$, when lifted to the integers. (Or use the ring structure that can be added to
$(\Bbb Z/q,+)$ in a natural way.)

---

Then the proof is complete. Assume that for two polynomials $f$ and $g$ with coefficients in the prime field (not only those in the list $1,x,x^2,...$) we have - when applied to $a\in\Bbb F$ - the relation $f(a)=f(g)$. Then $f-g$ is zero when applied on $a$, so the minimal polynomial $m$ of $a$ divides this difference. We have the same class in $\Bbb Z_p[x]/(m(x))$ for $f(x)$ and $g(x)$.

---

Which is the connection of the polynomial factorization $$ x^{16}-x = x (x + 1) (x^2 + x + 1) (x^4 + x + 1) (x^4 + x^3 + 1) (x^4 + x^3 + x^2 + x + 1) $$ with the two structures above? Consider the tower of fields: $$\require{AMScd} \begin{CD} \Bbb F_{16}\\ @AAA\\ \Bbb F_4\\ @AAA\\ \Bbb F_2\\ \end{CD} $$ And there is no other field in between.

• There are $2$ elements in $\Bbb F_2$, those from the roots of the two factors of degree one in the factorization,
• There are $4$ elements in $\Bbb F_4$, two new ones, those from the roots of the one factor of degree two in the factorization,
• There are $16$ elements in $\Bbb F_4$, twelve new one, those from the roots of the three factors of degree four in the factorization.

This is the information on the degree of elements.

How to address the question about the multiplicative orders? Let us take an example.

We realize explicitly $\Bbb F$ as $\Bbb F_2[Y]/(Y^4+Y+1)$, and let $y$ be the class of $y$. Let us consider now some special element $b$ in this realization: $$ b := y^3\ . $$ Which is the degree of $b$, the degree of a minimal polynomial annihilating $b$. Well, let us show that the last polynomial in the factorization list above is the minimal polynomial: $$ b^4 + b^3 + b^2 + b + 1 = \frac{b^5-1}{b-1} = \frac{y^{15}-1}{y^3-1} = \frac{y^{16}-y}{y(y^3-1)} = 0 \ , $$ since each element in the field is annihilated by $x\to x^{16}-x$. Of course, $b\ne 0,1$. OK, the degree of $b=y^3$ is four. However, it is not a generator of the unit group for the "same reason". Its multiplicative order is $5$, not $15=2^4-1$, since: $$ b^5=y^{15}=1\ . $$

---

---

Programming support:

Python-like code to investigate the above situation and similar ones - this is relevant for the OP - as mentioned in the comments. The following code is written in sage, a CAS (computer algebra system) collecting features of free and less free CAS for most mathematical (computational) purposes. Note that sage is preparsing objects, in some cases preparsing is doing (un)wanted operations. Here is also some quick step-in-introduction.

I will work below also with the field $\Bbb F_{16}$ with $q=16$ elements. A generator of it - chosen by sage - will be denoted by $y$. We initialize this field, and in the same time the polynomial ring in the new transcendental variable $X$ over this field:

q = 2^4
F.<y> = GF(q)
R.<X> = PolynomialRing(GF(2))    # also R.<X> = GF(2)[] for short possible

We copy+paste this into the sage interpreter, which is an ipython3 code eater, so we also have a handy completion to get the methods of some objects, also their doc strings using question mark(s).

sage: q = 2^4
....: F.<y> = GF(q)
....: R.<X> = PolynomialRing(GF(2))
sage: F
Finite Field in y of size 2^4
sage: R
Univariate Polynomial Ring in X over Finite Field of size 2 (using GF2X)
sage: y.minpoly()
x^4 + x + 1
sage: factor(X^q - X)
X * (X + 1) * (X^2 + X + 1) * (X^4 + X + 1)
  * (X^4 + X^3 + 1) * (X^4 + X^3 + X^2 + X + 1)

(Factorization was manually adjusted to fit in page.)

sage: for f in F:
....:     mp = f.minpoly()
....:     print('Element {!s:18} has minpoly {!s:23} of degree {} and multiplicative order {}'
....:           .format(f, mp, mp.degree(), f.multiplicative_order() if f else 'UNDEFINED' ))
....: 
Element 0                  has minpoly x                       of degree 1 and multiplicative order UNDEFINED
Element y                  has minpoly x^4 + x + 1             of degree 4 and multiplicative order 15
Element y^2                has minpoly x^4 + x + 1             of degree 4 and multiplicative order 15
Element y^3                has minpoly x^4 + x^3 + x^2 + x + 1 of degree 4 and multiplicative order 5
Element y + 1              has minpoly x^4 + x + 1             of degree 4 and multiplicative order 15
Element y^2 + y            has minpoly x^2 + x + 1             of degree 2 and multiplicative order 3
Element y^3 + y^2          has minpoly x^4 + x^3 + x^2 + x + 1 of degree 4 and multiplicative order 5
Element y^3 + y + 1        has minpoly x^4 + x^3 + 1           of degree 4 and multiplicative order 15
Element y^2 + 1            has minpoly x^4 + x + 1             of degree 4 and multiplicative order 15
Element y^3 + y            has minpoly x^4 + x^3 + x^2 + x + 1 of degree 4 and multiplicative order 5
Element y^2 + y + 1        has minpoly x^2 + x + 1             of degree 2 and multiplicative order 3
Element y^3 + y^2 + y      has minpoly x^4 + x^3 + 1           of degree 4 and multiplicative order 15
Element y^3 + y^2 + y + 1  has minpoly x^4 + x^3 + x^2 + x + 1 of degree 4 and multiplicative order 5
Element y^3 + y^2 + 1      has minpoly x^4 + x^3 + 1           of degree 4 and multiplicative order 15
Element y^3 + 1            has minpoly x^4 + x^3 + 1           of degree 4 and multiplicative order 15
Element 1                  has minpoly x + 1                   of degree 1 and multiplicative order 1

(Please scroll to the right to see the rows.) Alternatively, we may ask for the same information to be inserted in some latex array block:

sage: F_list.sort(key=lambda f: f.minpoly().degree())
sage: 
sage: F_list = list(F)
sage: F_list.sort(key=lambda f: f.minpoly().degree())
sage: for f in F_list:
....:     mp = f.minpoly()
....:     print('{!s:18} & {!s:23} & {} & {}\\\\\\hline'
....:           .format(f, mp, mp.degree(), f.multiplicative_order() if f else '' ))
....: 

$$ \begin{array}{|l|l|r|r|} \hline f & \text{ Minimal polynomial} & \deg & \text{order in }\Bbb F^\times\\\hline\hline 0 & x & 1 & \\\hline 1 & x + 1 & 1 & 1\\\hline y^2 + y & x^2 + x + 1 & 2 & 3\\\hline y^2 + y + 1 & x^2 + x + 1 & 2 & 3\\\hline y & x^4 + x + 1 & 4 & 15\\\hline y^2 & x^4 + x + 1 & 4 & 15\\\hline y^3 & x^4 + x^3 + x^2 + x + 1 & 4 & 5\\\hline y + 1 & x^4 + x + 1 & 4 & 15\\\hline y^3 + y^2 & x^4 + x^3 + x^2 + x + 1 & 4 & 5\\\hline y^3 + y + 1 & x^4 + x^3 + 1 & 4 & 15\\\hline y^2 + 1 & x^4 + x + 1 & 4 & 15\\\hline y^3 + y & x^4 + x^3 + x^2 + x + 1 & 4 & 5\\\hline y^3 + y^2 + y & x^4 + x^3 + 1 & 4 & 15\\\hline y^3 + y^2 + y + 1 & x^4 + x^3 + x^2 + x + 1 & 4 & 5\\\hline y^3 + y^2 + 1 & x^4 + x^3 + 1 & 4 & 15\\\hline y^3 + 1 & x^4 + x^3 + 1 & 4 & 15\\\hline \end{array} $$

Note that it is possible to use instead of the above $y$, chosen by sage to have the minpoly $X^4+X+1$, some other generator. It must be one of the three irreducible polynomials of degree four however, of course. To initialize $F$ so, use the wanted modulus, which must be a polynomial over some already known polynomial ring over GF(2) - i have it, the X was introduced with this purpose also:

F.<y> = GF(q, modulus=X^4 + X^3 + X^2 + X + 1)
F
y.minpoly()

After a copy+paste into the interpreter:

sage:     F.<y> = GF(q, modulus=X^4 + X^3 + X^2 + X + 1)
....:     F
....:     y.minpoly()
....: 
Finite Field in y of size 2^4
x^4 + x^3 + x^2 + x + 1
sage: y.multiplicative_order()
5
sage: 

So here is an example of an element of maximal degree $4$, which has multiplicative order strictly smaller then $q-1=15$, thus not maximal.

But conversely, all elements of $F$ of maximal multiplicative degree $q-1=15$ must have maximal degree four.

sage: [f.minpoly().degree() for f in F if f and f.multiplicative_order() == 15]
[4, 4, 4, 4, 4, 4, 4, 4]

(See also the table above for the same information.)

---

Many experimental lines along these lines can be dropped down into the interpreter, it makes it easier to test properties of the structure of finite fields. Enjoy!