April 20, 2024
On Monic Square-Free Polynomials over a Finite Field
COL863
Show that for a prime power $q$ and a positive integer $n\geq 2$, the probability for a random polynomial in $\mathbb{F}_q[x]$ of degree $n$ to be squarefree is $1-1/q$. Let $s_n$ denote the number of monic squarefree polynomials of degree $n$ in $\mathbb{F}_q[x]$. Then $s_0 = 1$ and $s_1= q$.
(a) Prove the recursive formula $\sum_{0\leq 2k\leq n} q^{k}s_{n-2k} = q^n$.
(b) Conclude that $s_n = q^n - q^{n-1}$ if $n\geq 2$.
We start by defining two sets:
\[\mathcal{P}(\mathbb{F}_q, n,r) := \{(p(X))^r\in \mathbb{F}_q[X] : \deg{p}=n, \text{$p$ is monic}\}\] \[\mathcal{Q}(\mathbb{F}_q,n) := \{p(X) \in \mathbb{F}_q[X] : \deg{p}=n, \text{$p$ is monic and square free}\}\]Note that for the given problem we have:
\[\operatorname{card}(\mathcal{P}(\mathbb{F}_q, n,1))=q^n, \quad \operatorname{card}(\mathcal{Q}(\mathbb{F}_q,n)) = s_n.\]Part (a)
Let $p(X)\in \mathbb{F}_q[X]$ be a generic monic polynomial of degree $n$. Since $\mathbb{F}_q[X]$ is a UFD, we can uniquely factorize:
\[p(X) = \prod_{i=1}^{\eta} g_{i}(X)^{\nu(i)}\]where $g_i$ are irreducible polynomials over $\mathbb{F}_q[X]$.
We can further decompose this as follows:
\[p(X) = \prod_{i : 2\mid\nu(i)} g_i(X)^{\nu(i)} \prod_{i : 2\nmid\nu(i)} g_i(X)^{\nu(i)}.\]The second product can be rewritten as:
\[p(X) = \color{teal}{\left( \prod_{i : 2\mid\nu(i)} g_i(X)^{\nu(i)/2} \prod_{i : 2\nmid\nu(i)} g_i(X)^{(\nu(i)-1)/2} \right)^2} \color{orange}{\prod_{i : 2\nmid\nu(i)} g_i(X)}.\]If the $\color{teal}{\text{teal}}$ product has degree $2k$, then the $\color{orange}{\text{orange}}$ product has degree $n - 2k$.
We define the following map:
\[\Psi : \mathcal{P}(\mathbb{F}_q, n,1) \to \coprod_{0\leq 2k\leq n} \mathcal{P}(\mathbb{F}_q, k,2)\times \mathcal{Q}(\mathbb{F}_q, n-2k)\] \[p(X) \mapsto \left( \left( \prod_{i : 2\mid\nu(i)} g_i(X)^{\nu(i)/2} \prod_{i : 2\nmid\nu(i)} g_i(X)^{(\nu(i)-1)/2} \right)^2, \prod_{i : 2\nmid\nu(i)} g_i(X) \right).\]This map is clearly well defined. If $\Psi(p(X)) = (p_1(X), p_2(X))$, then $p(X) = p_1(X)p_2(X)$. Since $\Psi$ is both injective and surjective, it is a bijection.
Thus, the cardinalities of the domain and range must be equal:
\[q^n = \sum_{0\leq 2k\leq n} \operatorname{card}(\mathcal{P}(\mathbb{F}_q, k,2)) \cdot \operatorname{card}(\mathcal{Q}(\mathbb{F}_q, n-2k)).\]Since $\operatorname{card}(\mathcal{P}(\mathbb{F}_q, k,2)) = \operatorname{card}(\mathcal{P}(\mathbb{F}_q, k,1)) = q^k$, we get:
\[q^n = \sum_{0\leq 2k\leq n} q^k \cdot s_{n-2k}.\]Part (b)
From Part (a), we have:
\[q^n = \sum_{0\leq 2k\leq n} q^k \cdot s_{n-2k}.\]Taking the generating function:
\[\sum_{n=0}^{\infty} q^n t^n = \sum_{n=0}^{\infty} \sum_{0\leq 2k\leq n} q^k s_{n-2k}t^n.\]Rewriting as:
\[\sum_{n=0}^{\infty} q^n t^n = \left( \sum_{n=0}^{\infty} (qt^2)^n \right) \left( \sum_{n=0}^{\infty} t^n s_n \right).\]Thus,
\[\sum_{n=0}^{\infty} t^n s_n = (1 - qt^2) \sum_{n=0}^{\infty} q^n t^n = 1 + qt + \sum_{n\geq 2} (q^n - q^{n-1}) t^n.\]Comparing coefficients:
\[s_n = \begin{cases} q^n, & n=0,1 \\ q^n - q^{n-1}, & n\geq 2. \end{cases}\]The probability that a random polynomial in $\mathbb{F}_q[X]$ of degree $n$ is square-free is:
\[\Pr[p(X)\in \mathcal{Q}(\mathbb{F}_q,n) | p(X) \in \mathcal{P}(\mathbb{F}_q, n,1)] = \frac{\operatorname{card}(\mathcal{Q}(\mathbb{F}_q,n))}{\operatorname{card}(\mathcal{P}(\mathbb{F}_q, n,1))} = \frac{s_n}{q^n}.\]Thus,
\[\Pr = \begin{cases} 1, & n=0,1 \\ 1-\frac{1}{q}, & n\geq 2. \end{cases}\]