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

It is well-known that the number of monic $n$-degree polynomials over a finite field of size $q$ is $q^n$. How many such degree-$n$ polynomials can be completely factored into only irreducible polynomials of odd degree? Does anyone know of any related literature?

share|cite|improve this question
I think you could use… – xavierm02 Aug 13 '13 at 19:58

I'm not sure what type of answer is desired (estimating the number of such polynomials, or giving a formula for this number, or...). I just want to remark here that one can approach this question via generating functions. Write $O_n$ for the number of monic degree-$n$ polynomials in $\mathbf{F}_q[x]$ which have only odd-degree irreducible factors, and $I_n$ for the number of monic degree-$n$ irreducible polynomials in $\mathbf{F}_q[x]$. Then $O_n$ is the sum, over all partitions $1\le a_1\le a_2\le...$ of $n$ into odd parts, of the product $I_{a_1} \cdot I_{a_2} \cdot ...$. Now write $$ I(t) = \sum_{\substack{i>0 \\ i \text{ odd}}} I_i t^i \quad\text{ and }\quad O(t) = \sum_{i=1}^{\infty} O_i t^i $$ where $t$ is a formal variable. Then the above identity for $O_n$ becomes $$ O(t) = \sum_{k=1}^{\infty} I(t)^k = -1 + \frac{1}{1-I(t)}. $$ This formulation has the advantage of compactly recording the known information. In some sense, since we know the coefficients of $I(t)$, we also know $O(t)$... although whether this helps resolve a specific question about $O(t)$ will depend on the question.

share|cite|improve this answer

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.