# Explicit examples of infinitely many irreducible polynomials in k[x]

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.

-
I took the liberty of adding the finite-fields tag. I think that the turn this question has taken warrants such an edition. Do roll it back, if you disagree :-) –  Jyrki Lahtonen Oct 6 '11 at 6:01
See also this question for some useful links and discussion of the case $k=GF(2)$. I think that we can safely conclude that a literal interpretation of this exercise was not intended :-) –  Jyrki Lahtonen Oct 9 '11 at 7:42
@JyrkiLahtonen Yes it seems that way. That's a nice link with a lot of references. Thank you very much for all your effort and interest in this question =) –  Adrián Barquero Oct 9 '11 at 15:44

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.

-
@Adrián I added an explicit infinite family of irreducible polynomials over the field $F_2$. I think that this is a very tough exercise, when taken this literally :-) –  Jyrki Lahtonen Oct 6 '11 at 5:57
Mind you, it should be possible to generalize this approach to other suitable finite fields also. –  Jyrki Lahtonen Oct 6 '11 at 6:05
Thank you very much Jyrki. This is all very interesting. I now believe that the wording of the exercise I was doing may be somehow misleading after seeing these answers. There's just no way on Earth that I could have come up with such a family of irreducible polynomials and just for $\mathbb{F}_2$. But I'm really glad I asked this. Thank you for this very nice answer. –  Adrián Barquero Oct 6 '11 at 15:02
@AdriánBarquero I agree. They probably don't want quite this explicit an answer. OTOH we may have overlooked a simple family. I will still think about this, and you should probably wait for a while. I'm not at all confident that a simple answer would not exist :-( –  Jyrki Lahtonen Oct 6 '11 at 20:02
Jyrki, I will accept your answer since you provided an example of an infinite family of irreducible polynomials for $\mathbb{F}_2[x]$. Thank you =) –  Adrián Barquero Oct 9 '11 at 15:47

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$.

-
Ok maybe I just don't understand, but how does this give me an explicit example? –  Adrián Barquero Oct 5 '11 at 18:54
By the way I didn't downvote your answer. I really appreciate that you're trying to help. –  Adrián Barquero Oct 5 '11 at 18:58
Ow you need it to be explicit. Didn't get that. I edited my answer. I'm not sure if it'll give you what you want though.... –  shaye Oct 5 '11 at 19:22

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

-