# Explicit examples of infinitely many irreducible polynomials in k

My question is the following.

Is it possible to give examples of infinitely many irreducible polynomials in a polynomial ring $k[x]$ with $k$ a field?

I’m interested in this because I’m doing an exercise in which I’m asked to show that there are infinitely many maximal ideals in $k[x]$ by listing them explicitly. Now, I know that if $k$ is infinite then the ideals $I_a := (x – a)$ for $a \in k$ are maximal and this would do. But if the field is finite I really don’t know what to do.

I haven’t been able to find anything online or in books. I also know that we can prove that there are infinitely many irreducible monic polynomials in $k[x]$ by using Euclid’s argument for proving that there are infinitely many prime numbers. But this does not give me explicit maximal ideals, just the existence of infinitely many of them.

Thank you very much for any help.

#### Solutions Collecting From Web of "Explicit examples of infinitely many irreducible polynomials in k"

The best I can come up with for now is the following. If $\alpha$ is an element in some extension of the field $F_p, p$ prime, then its conjugates are well-known to be $\alpha^p$,
$\alpha^{p^2}$, $\alpha^{p^3}$, $\ldots$. So, if $\alpha$ happens to be a root of unity of a prime order $\ell$, and $p$ happens to be a generator of the multiplicative group $\mathbf{Z}_\ell^*$, then the minimal polynomial of $\alpha$ is
$$(x-\alpha)(x-\alpha^2)\cdots(x-\alpha^{\ell-1})=\phi_\ell(x)=\sum_{i=0}^{\ell-1}x^i,$$
so $\phi_\ell(x)$ is then irreducible in $F_p[x]$.
If Artin’s conjecture is true, then this happens for infinitely many rational primes $\ell$. This gives a little bit narrower set of polynomials that is likely to contain
an infinite number of irreducible ones. A variant of Artin’s conjecture may then also settle the case $k=GF(p^n)$.

No good: depends on the truth of an unknown conjecture, and not very explicit. Feel free to downvote.

==============================

Addendum: (Exercise 3.96 from Finite Fields, Lidl & Niederreiter) An explicit infinite family of irreducible polynomials in $F_2[x]$ is the following. Let $k$ be a positive integer. The polynomial
$$p_k(x)=x^{2\cdot3^k}+x^{3^k}+1\in F_2[x]$$
is irreducible.

My solution to this exercise. The proof of this fact is very similar to the previous construction. The ingredients are the observation that
$$p_k(x)=\frac{x^{3^{k+1}}+1}{x^{3^k}+1}$$
is the cyclotomic polynomial $\phi_{3^{k+1}}(x)$, and the fact that $2$ is a generator of the group of units $U_n$ of the residue class rings $\mathbf{Z}/3^n\mathbf{Z}$. The latter fact is equivalent to showing that the order of $2$ in $U$ is exactly $\phi(3^n)=2\cdot3^{n-1}$. This follows, if we can show that $\nu_3(2^{2\cdot3^{n-1}}-1)=n$, because it is known that a generator $x$ of $U_\ell$ is also a generator of $U_{\ell+1}$ unless it happens that $x^{|U_\ell|}=1$ in $U_{\ell+1}$ (see e.g. Jacobson, Basic Algebra I). But $(x^3-1)=(x-1)(x^2+x+1)$ implies that
$$2^{2\cdot 3^{n+1}}-1=(2^{2\cdot 3^n}-1)(2^{4\cdot 3^n}+2^{2\cdot 3^n}+1).$$
In the latter factor all three terms are congruent to $1\pmod 9$, so that factor is divisible by $3$ but not divisible by $9$. This is the inductive step.

If $\alpha$ is a primitive root of order $3^{k+1}$,
then $\alpha$ is a root of $p_k(x)$. Therefore so are its conjugates $\alpha^{2^j}, j\in\mathbf{N}.$ But we saw that $U_{k+1}=<2>$, so the conjugates are exactly the
powers $\alpha^t$, $(t,3)=1$. There are $2\cdot3^k=\deg p_k(x)$ of these, so $p_k(x)$
is the minimal polynomial of $\alpha$ and hence irreducible. Q.E.D.

If $k$ is infinite, it’s easy as you say.

Suppose that $k$ is finite. Then, for any positive integer $n\geq 2$, there exists an irreducible polynomial in $k[t]$ of degree $n$.

Consider the finite field $\mathbf{F}_p$, where $p$ is a prime number.

Edit: (might help a bit.)
The irreducible polynomials of degree less or equal to $n$ in $\mathbf{F}_p[x]$ are the irreducible factors of $X^{p^n}-X$. In fact, $$X^{p^n} – X = \prod_{f \textrm{ monic irreducible}, (\deg f) \vert n} f.$$ As a fun sidefact, this implies that the number of irreducible polynomials $x_n$ of degree $n$ satisfies $\sum_{d\vert n } dx_d = p^n$.

Anyway, to get explicit examples you’ll have to factorize the above polynomial for each $n$. This is a hard, but possible in theory. For small $p$ and $n$ you can do this. For example, for $p=2$ and $n=2$, you have to factor $X^4-X = X(X^3-1)=X(X-1)(X^2+X+1)$ in $\mathbf{F}_2$.

Define $\phi(y) = 1/(y^p-y-1)$ and define $\phi^n(y) = \phi(\phi(\cdots\phi(y)\cdots))$. I claim that the denominator of $\phi^n(y)$ is irreducible of degree $p^n$ over $\mathbb{F}_p$. This is going to be a long one, but I had a lot of fun finding it so I hope some of you will read it.

The rational function $\phi$ defines a from map
$\overline{\mathbb{F}_p} \cup \{ \infty \}$ to itself. This map is $p \to 1$, except that the preimage of $0$ is the single element
$\infty$. The image of $0$ is the fixed point $-1$. So $0 \not \in (\phi^n)^{-1}(\infty)$ for any $n$, and thus
$(\phi^{n+1})^{-1}(\infty)$ always has $p$ times as many elements as
$(\phi^n)^{-1}(\infty)$. So $(\phi^n)^{-1}(\infty)$ has size $p^n$ and we see that the denominator of $\phi$ has degree $p^n$. We must now show that it is irreducible.
Let $y_n$ be a root of this denominator; we need to show that $y_n$ is in $GF(p^{p^n})$ and not in $GF(p^{p^{n-1}})$.

Set $\phi(y_n) = y_{n-1}$, $\phi(y_{n-1}) = y_{n-2}$, etcetera. We rewrite these relations as
$$y_1^p-y_1 = 1 \quad y_2^p-y_2 = \frac{y_1+1}{y_1} \quad y_3^p-y_3 = \frac{y_2+1}{y_2} \quad y_4^p-y_4 = \frac{y_3+1}{y_3} \cdots$$
Define $K_i=\mathbb{F}_p(y_1, y_2, \ldots, y_i)$. We will establish, below, the following claim:

Key Claim The polynomial $z^p-z = \frac{y_i+1}{y_i}$ is irreducible over $K_i$.

Thus $[K_{i+1}:K_{i}]=p$ for every $i$. So $y_n \in K_n = GF(p^{p^n})$ and $y_n \not\in K_{n-1} = GF(p^{p^{n-1}})$. This shows that the minimal polynomial of $y_n$ over $\mathbb{F}_p$ has degree $p^{p^n}$, so the denominator of $\phi$ must be irreducible.

Our goal now is to establish the claim. We first need some lemmas about polynomials of the form $x^p-x=a$. This is the subject of Artin-Schrier theory (see also here).

Let $k$ be a field of characteristic $p$ and let $a \in k$.

Lemma 1 Let $u$ be a root of $x^p-x=a$. Then the other roots are $u+1$, $u+2$, …, $u+p-1$.

Proof Straightforward. $\square$

Lemma 2 If $a$ is of the form $b^p-b$, for $b \in k$, then $x^p-x-a = \prod_{i=0}^{p-1} (x-b-i)$. If $a$ is not of the form $b^p-b$, for $b \in k$, then $x^p-x-a$ is irreducible.

Proof The first statement is obvious.

We prove the contrapositive of the second statement. Suppose that $f$ has a nontrivial factor $g(x)$; let $g(x) = x^e – g_1 x^{e-1} + \cdots$. Let $u$ be a root of $f(x)$ and let the roots of $g$ be $u+i_1$, $u+i_2$, …, $u+i_e$. Then $g_1 = \sum_{j=1}^e (u+i_j) =e u + \sum i_j$ is in $k$, so $u = (g_1 – \sum i_j)/e$ is in $k$. $\square$

Lemma 3 Let $x^p-x-a$ be irreducible and let $u$ be a root of $x^p-x=a$. Then
$$Tr_{k(u)/k} \frac{1}{u} = \frac{-1}{a}.$$

Proof Let $z=1/u$. Then $z^p + (1/a) z^{p-1} – (1/a)=0$. This polynomial is irreducible, so it is the minimal polynomial of $z$, so $Tr(z)$ is the coefficient of $z^{p-1}$. $\square$

Lemma 4 Let $x^p-x-a$ be irreducible and let $u$ be a root of $x^p-x=a$. Then
$$Tr_{k(u)/k} \frac{eu+f}{gu+h} = \frac{eh-fg}{g^2 a}.$$
for $e$, $f$, $g$, $h \in \mathbb{F}_p$, and $g \neq 0$.

Proof
$$Tr \left( \frac{eu+f}{gu+h} \right) = Tr \left( \frac{e}{g} \right) + \frac{fg-eh}{g^2} Tr\left( \frac{1}{u+h/g} \right).$$
Since $e/g \in k$, and $\deg k(u)/k=p$, we have $Tr(e/g) = 0$. Since
$h/g \in k$, the element $u+h/g$ is another root of $x^p-x=a$, so
$Tr(1/(u+h/g)) = Tr(1/u) = -1/a$ by Lemma 3. $\square$

Lemma 5 Let $k$ be a finite field. If $Tr_{k/\mathbb{F}_p}(a) \neq 0$, then $a$ is not of the form $b^p-b$.

Proof Again, we prove the contrapositive. If $a=b^p-b$, then $$Tr_{k/\mathbb{F}_p}(a) = Tr_{k/\mathbb{F}_p}(b^p)-Tr_{k/\mathbb{F}_p}(b)= Tr_{k/\mathbb{F}_p}(b)^p-Tr_{k/\mathbb{F}_p}(b)= 0. \quad \square$$

We now move to the main claim. We want to show that $z^p-z=\frac{y_i+1}{y_i}$ is irreducible. So, by Lemmas 2 and 5, we must show that $Tr_{K_{i}/\mathbb{F}_p}\left( \frac{y_{i}+1}{y_i} \right) \neq 0$. We compute this trace as the
composite of traces $K_{i} \to K_{i-1} \to \cdots \to K_2 \to K_1 \to \mathbb{F}_p$. By our inductive hypotheses, each of these
individual field extensions is a degree $p$ Artin-Schrier extension,
so Lemma 4 is relevant. Using Lemma 4 repeatedly:
$$Tr_{K_{i}/K_{i-1}} \left( \frac{y_{i}+1}{y_{i}} \right) = \frac{- y_{i-1}}{y_{i-1}+1}$$
$$Tr_{K_{i-1}/K_{i-2}} \left(\frac{- y_{i-1}}{y_{i-1}+1}\right) = \frac{y_{i-2}}{y_{i-2}+1}$$
$$Tr_{K_{i-2}/K_{i-3}} \left(\frac{ y_{i-2}}{y_{i-2}+1}\right) = \frac{- y_{i-3}}{y_{i-3}+1}$$
etcetera. At the end of the day, we get $Tr_{K_{i}/\mathbb{F}_p}\left( \frac{y_{i}+1}{y_i} \right) = \pm 1 \neq 0$ as desired.
By Lemmas 2 and 5, this proves the claim.

Another, easier, way. Let $\ell$ be a prime dividing $p-1$ and, if $\ell=2$, assume that $p \equiv 1 \bmod 4$. Such an $\ell$ exists for every $p \geq 5$. Let $Q \in \mathbb{F}_p$ not be an $\ell$-th power. I claim that $x^{\ell^n}-Q$ is irreducible for every $n$.

Lemma Let $\ell$ be prime, let $k$ be a field which contains the $\ell$-th roots of unity, and let $a \in k$. Then $x^{\ell} -a$ is either irreducible or splits into linear factors.

Proof Let $b$ be an $\ell$-th root of $a$ in the algebraic closure of $k$. So the roots of $x^{\ell}-a$ are $b$, $b \zeta$, $b \zeta^2$, …, $b \zeta^{\ell-1}$. Suppose that $g(x)$ is a nontrivial factor of $x^{\ell}-a$, with $g(x) = x^d + \cdots + (-1)^d g_0$. Then $g_0 = \pm \zeta^j b^d$ for some $j$ and we deduce that $b^d \in k$. Since $\ell$ is prime and $0 < d < \ell$, we can find $f$ and $g$ such that $df-g \ell =1$. So $(b^d)^f a^{-g} = b$ is in $k$. We have showed that, if $x^{\ell}-a$ has a nontrivial factor then $a$ has an $\ell$-th root in $k$ and, since $k$ contains the $\ell$-th roots of unity, this shows that $x^{\ell}-a$ splits in $k$. $\square$.

Let
$$x_1^{\ell} = Q \quad x_2^{\ell}=x_1 \quad x_3^{\ell} = x_2 \quad \cdots.$$
Let $K_i = \mathbb{F}_p(x_1, x_2, \ldots, x_i)$. We show by induction on $i$ that $[K_i:K_{i-1}] = \ell$. So $K_n = GF(p^{\ell^n})$ and $x_n$ is in $GF(p^{\ell^n})$ and not $GF(p^{\ell^{n-1}})$. So the minimal polynomial of $x_n$ has degree $\ell^n$ and must be $x^{\ell^n}-Q$, showing that $x^{\ell^n}-Q$ is irreducible as desired.

So, we want to show that $[K_i:K_{i-1}]=\ell$. By the lemma, $[K_i:K_{i-1}]$ is either $1$ or $\ell$. To rule out the latter case, we must show that $x_i$ is not an $\ell$-th power in $K_i$. Suppose, for the sake of contradiction that $b^{\ell} = x_i$. Then $N_{K_i/\mathbb{F}_p}(b)^{\ell} = N(x_i)$. Since, inductively, the minimal polynomial of $x_i$ is $z^{\ell^i} – Q$ and (also inductively) $K_i = GF(p^{\ell^i})$, we get $N(x_i) = (-1)^{\ell-1} Q$.

By hypothesis, $Q$ is not an $\ell$-th power in $\mathbb{F}_p$ and (using that $p \equiv 1 \bmod 4$ for $\ell=2$) neither is $(-1)^{\ell-1} Q$. So we have a contradiction. QED