Let $K$ be a finite field with $q$ elements, $q \ge 3.$ We denote by $M$ the set of polynomials in $K[X]$ of degree $q-2$ whose coefficients are nonzero and pairwise distinct. Find the number of polynomials in $M$ that have $q-2$ distinct roots in $K.$ Marian Andronache
Problem
Source: Romanian National Olympiad 2016, grade 12, problem 4
Tags: abstract algebra, Field theory
10.01.2024 22:51
Filipjack wrote: Let $K$ be a finite field with $q$ elements, $q \ge 3.$ We denote by $M$ the set of polynomials in $K[X]$ of degree $q-2$ whose coefficients are nonzero and pairwise distinct. Find the number of polynomials in $M$ that have $q-2$ distinct roots in $K.$ Marian Andronache Here is the official solution (in Romanian).
15.07.2024 23:25
Clearly any polynomial in $M$ cannot have $0$ as a root since it has nonzero constant term. Let $K^\times=:\langle g\rangle$. Lemma. For an integer $r$, \[ \sum_{a\in K^\times}a^r= \begin{cases} -1 & \mathrm{if}\ q-1\mid r\\ 0 & \mathrm{otherwise} \end{cases} \]Proof. If $q-1\mid r$, then $a^r=1$ for all $a\in K^\times$ so the sum equals $-1$. Otherwise, we have \[ \sum_{a\in K^\times}a^r=\sum_{i=0}^{q-2}g^{ri}=\frac{(g^r)^{q-1}-1}{g^r-1}=0 \]by Lagrange. $\square$ Note that for $f\in M$ and \[ f(x)=:\sum_{i=0}^{q-2}a_ix^i, \]we have \[ f(g^r)=\sum_{i=0}^{q-2}a_i(g^i)^r=\sum_{a\in K^\times}\pi(a)a^r \]for a permutation $\pi$ of $K^\times$. Furthermore, $f$ is determined uniquely by $\pi$ since $a_i=\pi(g^i)$. So we are counting the number of permutations $\pi$ such that \[ b_\pi(r):=\sum_{a\in K^\times}\pi(a)a^r=0 \]for all positive integers $r\leq q-1$, with one exception. Consider the $(q-1)\times(q-1)$ matrix $T$ over $K$ given by $t_{ij}=j^i$. Then \[ T \begin{pmatrix} \pi(1)\\ \pi(2)\\ \pi(3)\\ \vdots\\ \pi(q-1) \end{pmatrix} = \begin{pmatrix} 1^1 & 2^1 & 3^1 & \cdots & (q-1)^1\\ 1^2 & 2^2 & 3^2 & \cdots & (q-1)^2\\ 1^3 & 2^3 & 3^3 & \cdots & (q-1)^3\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1^{q-1} & 2^{q-1} & 3^{q-1} & \cdots & (q-1)^{q-1} \end{pmatrix} \begin{pmatrix} \pi(1)\\ \pi(2)\\ \pi(3)\\ \vdots\\ \pi(q-1) \end{pmatrix} = \begin{pmatrix} b_\pi(1)\\ b_\pi(2)\\ b_\pi(3)\\ \vdots\\ b_\pi(q-1) \end{pmatrix}. \]It is easy to see that \[ T^{-1}=- \begin{pmatrix} 1^{-1} & 1^{-2} & 1^{-3} & \cdots & 1^{-(q-1)}\\ 2^{-1} & 2^{-2} & 2^{-3} & \cdots & 2^{-(q-1)}\\ 3^{-1} & 3^{-2} & 3^{-3} & \cdots & 3^{-(q-1)}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ (q-1)^{-1} & (q-1)^{-2} & (q-1)^{-3} & \cdots & (q-1)^{-(q-1)} \end{pmatrix} \]by Lemma. If $b_\pi(i)\neq 0$ only when $i=c$, then \[ \begin{pmatrix} \pi(1)\\ \pi(2)\\ \pi(3)\\ \vdots\\ \pi(q-1) \end{pmatrix} =T^{-1} \begin{pmatrix} b_\pi(1)\\ b_\pi(2)\\ b_\pi(3)\\ \vdots\\ b_\pi(q-1) \end{pmatrix} \]equals $b_\pi(c)$ times column $c$ of $T^{-1}$. This vector contains all elements of $K^\times$ as entries iff $\gcd(c,q-1)=1$. Since there are $q-1$ choices for $b_\pi(c)$, there are $\boxed{(q-1)\varphi(q-1)}$ such permutations $\pi$. $\square$