Proof that there exists irreducible polynomial of degree $n$

Question

I do not really understand how they arrived the argument in the box. Can I get any hint or explanation about it?

Also, why in the first paragraph, they associate each polynomial to weight $x^n$?

Answer 1

You associate the weight $x^n$ because the above is a nice relation. Treat it like black magic for what it's worth - it was probably chosen so that the generating function becomes a geometric series.

Let $\mathbb{F}_p^m[X]$ denote the monic polynomials.\ Now, the result is $$ \frac{1}{1-px}=\sum_{n=1}^{\infty} p^n x^n=\sum_{f\in \mathbb{F}^m_p[X]} x^{deg(f)}, $$ that's simply going backwards in the first line. Now, what they say is (pardon the terrible notation)

$$ \sum_{f\in \mathbb{F}^m_p[X]} x^{deg(f)}=\sum_{f\in \mathbb{F}^m_p[X]} x^{\sum_{\substack{g\in \mathbb{F}_p[X]}\\g|f, \; g \; irr} deg(g)}=\sum_{f\in \mathbb{F}^m_p[X]}\prod_{\substack{g\in \mathbb{F}^m_p[X]}\\g|f, \; g \; irr} x^{deg(g)}, $$ since the degree of $f$ is the sum of the degrees of the irreducible factors of $f$ (we're counting the $g$'s with multiplicity in the above product). Now, really, what your author is looking at is, given an irreducible polynomial $g$, what sort of terms does it appear in? Well, we actually the sum of all finite products, which should, intuitively, be the product of power series.

Let's try to see this. Let $\mathbb{F}_p^i[X]$ denote the monic, irreducible polynomials. Then what are the finite products? $$ \prod_{\substack{g\in \mathbb{F}^i_p[X] \\ deg(g)\leq n}} \sum_{k=0}^n x^{k deg(g)} $$

Well, we know that whenever we expand one element of the sum, it's gonna give us the degree of a unique polynomial $f=g_1^{j_1}g_2^{j_2}...g_m^{j_m},$ where $j_m\leq n$ and $\deg(g_k)\leq n$. In fact, since the only irreducible polynomials omitted have degree greater than $n$, and any polynomial admits a decomposition into irreducible polynomials, we get that

$$ \prod_{\substack{g\in \mathbb{F}^i_p[X] \\ deg(g)\leq n}} \sum_{k=0}^n x^{k deg(g)}=\sum_{\substack{f\in \mathbb{F}^m_p[X] \\ deg(f)\leq n}} x^{deg(f)}+R(n), $$ where $R(n)$ is some positive remainder term, consisting of sums of the form $x^{deg(h)}$ for some polynomials $h$. In conclusion, we get that

$$ \sum_{\substack{f\in \mathbb{F}^m_p[X] \\ deg(f)\leq n}} x^{deg(f)}\leq \prod_{\substack{g\in \mathbb{F}^i_p[X] \\ deg(g)\leq n}} \sum_{k=0}^n x^{k deg(g)}\leq \sum_{f\in \mathbb{F}^m_p[X]} x^{deg(f)}, $$ and thus, taking $n\to\infty$ yields the first equality that your proof states.

The rest of the proof is just using the geometric series again and counting appropriately.