Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
Thanks Jyrki! This characterization seems extremely useful! – Henry Yuen Nov 21 '12 at 16:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.