Generating function identity from number of irreducible monic polynomials in $\mathbf{GF}(q)$.

I denote by $m_n(q)$ the number of irreducible monic polynomials with degree $n$ over the finite field of order $q$. So the number of monic polynomials with degree is just $q^n$.

From this, how does it follow that $$\prod_{n\geq 1}\frac{1}{(1-x^n)^{m_n(q)}}=\frac{1}{1-qx}.$$ I know $$\frac{1}{1-qx}=1+qx+q^2x^2+\cdots$$ but I don't see an obvious relation between the coefficients of one to the other.

Thanks,

2nd try: Based on the help, I try to write this out in form $$(1+x+x^2+\cdots)^{m_1(q)}(1+x^2+x^4+c\dots)^{m_2(q)}\cdots=\sum_{f\text{ monic}}x^{\deg f}.$$

Due to unique factorization, distinct products of monic irreducibles of determine unique monic polynomials. So the coefficient of $x^{\deg f}$ is the number of monic polynomials of degree $\deg f$, But I'm having a hard time picturing how the expanded left hand side would count them for the identity to hold. Would someone be willing to explain this subtlety?

-

1
Hint: Imagine expanding each term on the left, just like you did for $1/(1-qx)$. Then imagine multiplying out the expanded versions. For every $N$, you get a term in $x^N$ precisely for every product of monic irreducibles that have sum of degrees equal to $N$. It is a close analogue of the corresponding formula for the integers, and as for integers it uses unique factorization. – André Nicolas Jan 25 '12 at 19:25
Thanks @AndréNicolas. I tried to get a little further based on your hint. If you find the time, do you mind explaining how your method works? So far I'm not able to imagine how the expanded version multiply out correctly to get the identity. – Hailie Jan 29 '12 at 8:52

1 Answer

$q^n$ is the number of monic polynomials of degree $n$ over $\mathbb{F}_q$, so we can write $\frac{1}{1 - qx}$ as $$\sum_{f \text{ a monic polynomial}} x^{\deg f}.$$

Now, monic polynomials can be uniquely factored into a product of irreducible polynomials, and $\deg$ satisfies $\deg fg = \deg f + \deg g$. What does that tell you about how the above generating function can be factored? (This is closely analogous to how we derive the Euler product for the Riemann zeta function.)

-

Thank you for answering Qiaochu Yuan. I tried to write down my thoughts based on your hint. If you find the time, could you expand on what you're getting at? If not, that's fine, thanks. – Hailie Jan 29 '12 at 7:00
@Hailie: are you familiar with the Euler product for the Riemann zeta function? It is very similar. – Qiaochu Yuan Jan 29 '12 at 7:14
– Hailie Jan 29 '12 at 7:26
@Hailie: you can't exactly identify them. The point is that $n \mapsto \frac{1}{n^s}$ maps is a multiplicative function in the same way that $f \mapsto x^{\deg f}$ is. Does that give you any ideas? – Qiaochu Yuan Jan 29 '12 at 7:34
Well, I see that $gf\mapsto x^{\deg fg}=x^{\deg f}x^{\deg g}$, but I don't see how this argument works. To me, $\sum_{f\text{ monic}}x^{\deg f}$ seems like it would just have form $1+x+x^2+x^3+\cdots$. I don't see any coefficients for the $x^{\deg f}$ monomials in the sum. – Hailie Jan 29 '12 at 7:49
show 3 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 23, "mathjax_display_tex": 4, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9253811836242676, "perplexity_flag": "head"}