# Irreducible polynomials over $F_q$ with exponents of the form $q^k - 1$.

Let $q$ be some prime power. Is there an explicit family of irreducible polynomials in $F_q[X]$ of the form $\sum_j a_j X^{q^j - 1}$? Thanks!

-
I'm not sure the answer to this, but a related fact is that if you have a finite field $\mathbb{F}_{q^n}=\mathbb{F}_q(\alpha)$, any element of $\mathbb{F}_q(\alpha)$ can be expressed as $\sum_{j=0}^{n-1}a_j\alpha^{q^j}$. –  Alexander Gruber Nov 20 '12 at 18:09
@AlexanderGruber: Really?? The way I see it your claim only holds, when $\alpha$ generates a normal basis. Otherwise its conjugates don't form a basis. But that is largely irrelevant to the question. –  Jyrki Lahtonen Nov 21 '12 at 8:14

The question is about irreducible polynomials of the form $F(x)/x\in \mathbb{F}_q[x]$ such that $F(x)$ is a $q$-linearized polynomial, i.e. of the form $$F(x)=a_0x+a_1x^q+a_2x^{q^2}+\cdots a_kx^{q^k}.$$ Here the polynomial $$f(x)=a_0+a_1x+a_2x^2+\cdots a_kx^k$$ is known as the conventional $q$-associate of $F(x)$. Similarly $F(x)$ is called the linearized $q$-associate of $f(x)$.

I refer you to section 4 of Chapter 3 in Lidl & Niederreiter for a more comprehensive discussion on linearized polynomials and their algebra. The following two results from there seem to be relevant to this question.

1: For $F(x)/x$ to be irreducible, it is necessary that $f(x)$ is irreducible, for otherwise the linearized $q$-associate of a factor of $f(x)$ will be a factor of $F(x)$.

2: Theorem 3.63 [loc.cit.] says that when $f(x)$ is irreducible, then every irreducible factor of $F(x)/x$ is of degree $e$, where $e$ is the order of $f(x)$, i.e. the smallest integer $e$ with the property $f(x)\mid x^e-1$ (=the order of the coset of $x$ in the quotient field $\mathbb{F}_q[x]/\langle f(x)\rangle$.

From these two bits we immediately see $F(x)/x$ is irreducible, iff $f(x)$ has order $q^k-1$. In other words, iff $f(x)$ is a primitive polynomial (= the minimal polynomial of a generator of the multiplicative group of $\mathbb{F}_{q^k}$).

Unfortunately I do not know of any explicit families of primitive polynomials. May be somewhere there are some? I guess that is bad news for you :-(

When I need a primitive polynomial, I will look one up from a table. In my case we usually then have $q=2$, and this table comes in handy.