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

Question

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!

Answer 1

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.

Sorry that I can't help you more at this time.