4
$\begingroup$

Let $M(n)(q)$, where $q$ is a prime power and $n$ a natural number, stand for the number of irreducible monic polynomials of degree $n$ in the polynomial ring $\mathbf{F}_{q}[X]$ over the finite field $\mathbf{F}_{q}$. Since \begin{equation*} M(n) = \frac{1}{n} \sum_{d \mid n} \mu(d) q^{n/d} \end{equation*} we have that $M(1)=q$, $M(2) = \frac{1}{2}(q^2-q)$, etc. Also, let $P(n)$ be the set of partitions $[n_1^{e_1},\ldots, n_s^{e_s}]$ of $n = n_1e_1 + \cdots + n_se_s$. Consider the sum of polynomials in $\mathbf{Q}[q]$ \begin{equation*} \sum_{[n_1^{e_1},\ldots, n_s^{e_s}] \in P(n)} (-1)^{\sum e_i} \prod_{i=1}^s \binom{M(n_i)}{e_i} \end{equation*} ranging over all partitions of $n$. This sum equals $-q$ if $n=1$ and it equals $0$ for $n=2,\ldots,50$. I suspect it equals $0$ for all $n>1$. Is this true?

$\endgroup$
3
  • $\begingroup$ I think you mean $M(n)(q)$ to be the number of irreducible polynomials of degree $n$ in $\mathbb F_q[X]$. $\endgroup$
    – Wojowu
    Oct 22 '16 at 10:30
  • $\begingroup$ The sum is actually $-q$ for $n=1$. $\endgroup$ Oct 22 '16 at 10:46
  • 1
    $\begingroup$ Thanks for the comments - my original question has been corrected accordingly. $\endgroup$ Oct 22 '16 at 11:14
8
$\begingroup$

Yes, it is true. Your expression is the coefficient of $x^n$ in the following product: $$\prod_{P\text{ monic irreducible}} (1-x^{\deg P}) = \prod_{n} (1-x^n)^{M(n)}.$$ The Zeta function of $\mathbb{F}_q[X]$ is $$\sum_{f \text{ monic}} x^{\deg f} = \sum_{n \ge 0} q^n x^n = \frac{1}{1-qx}.$$ The Euler product identity tells us that $$\frac{1}{1-qx} = \prod_{P\text{ monic irreducible}} (1-x^{\deg P})^{-1} =\prod_{n} (1-x^n)^{-M(n)}.$$ Taking its reciprocal, we find that $$1-qx = \prod_{P\text{ monic irreducible}} (1-x^{\deg P}).$$ Now it is just a matter of comparing coefficients on both sides.


Interpretation: Let $\mu: \mathbb{F}_q[X] \to \mathbb{C}$ be the polynomial Möbius function, defined by $$\mu(f) = \begin{cases} 0 & f \text{ not squarefree} \\ (-1)^k & f=p_1 \cdots p_k (p_i \text{ distinct irreducibles}) \end{cases}.$$ The term $\prod_{i=1}^{s} \binom{M(n_i)}{e_i}$ counts the number of monic, squarefree polynomials of degree $n$ whose factorization consists of $e_i$ irreducibles of degree $n_i$. The polynomial Möbius function $\mu(\bullet)$ assumes the value $(-1)^{\sum e_i}$ for each such polynomial. In other words, your sum may be rewritten as $$\sum_{f \text{ monic, squarefree of degree }n} \mu(f).$$ Since $\mu(f)=0$ for $f$ which is not squarefree, your claim is the same as $$n>1 \implies \sum_{f \text{ monic of degree }n} \mu(f) = 0.$$ This is classical, and due to L. Carlitz, whose proof was exactly as above. It should be compared with the following equivalent formulation of the Riemann Hypothesis: $$\sum_{n \le x } \mu(n) = O(x^{\frac{1}{2}+\varepsilon}),$$ where this time $\mu$ is the integer Möbius function.


It is interesting to ask whether $\sum_{f\text { monic of degree }n} \mu(f)$ may be evaluated without the use of formal power series and the Euler product identity. I will present such a way. Let $M_q$ denote the set of monics in $\mathbb{F}_q[X]$. Given two functions $\alpha, \beta : M_q \to \mathbb{C}$, one defines their "Dirichlet convolution" as the following function: $$(\alpha*\beta) (f) = \sum_{d_1 \cdot d_2 = f} \alpha(d_1) \beta(d_2).$$ Let $\zeta$ denote the constant function $1$ on $M_q$. Let $\delta_{1}$ denote the indicator function of the constant polynomial $1$. The "defining" property of $\mu$ is $$\mu * \zeta = \delta_1.$$ By summing the above over all monic polynomials of degree $n$ (>0) and changing the order of summation, we get that $$\sum_{\deg d \le n} \mu(d) q^{n-\deg d} = 0,$$ or equivalently $$\sum_{\deg d \le n} \frac{\mu(d)}{q^{\deg d}} =0.$$ Plugging $n=m,m+1$ in the above and subtracting, we get that $$m>0 \implies \sum_{\deg d = m+1} \mu(d) = 0.$$

$\endgroup$
1
  • 1
    $\begingroup$ Thanks a lot for the quick, precise, and clear answer to my question! $\endgroup$ Oct 22 '16 at 11:18
3
$\begingroup$

Here is a reformulation of Ofir Gorodetsky's excellent answer to my question: Let $(a(n))_{n \geq 1}$ be a sequence of rational numbers. Define the transformed sequence $T(a)$ of $a$ to have $n$th element \begin{equation*} T(a)(n) = \sum_{n_1^{e_1} \cdots n_s^{e_s} \in P(n)} (-1)^{\sum e_i} \prod_{i=1}^s \binom{A(n_i)}{e_i}, \qquad n \geq 1 \end{equation*} Then \begin{equation*} 1+ \sum_{n \geq 1} T(a)(n)x^n = \prod_{n \geq 1} (1-x^n)^{a(n)} \end{equation*} We now apply this to the sequence $M(n)(q)$. From the classical formula \begin{equation*} \frac{1}{1-qx} = \prod_{n \geq 1} (1-x^n)^{-M(n)(q)} \end{equation*} we get that \begin{equation*} 1+ \sum_{n \geq 1} T(M(n)(q))x^n = \prod_{n \geq 1} (1-x^n)^{M(n)(q)} = 1-qx \end{equation*} This shows that $T(M)(1)=-q$ and $T(M)(n)=0$ for all $n>1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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