Probability of finding polynomials in a field

Question

Let $K$ be a finite field with $q$ elements and $n\ge q,n\in \mathbb N$.Determine the probability when choosing a polynomial from the set of polynomials of degree $n$ from $K[X]$ , it will have no roots in $K$. Can somebody help me, please? I'm not so good at polynomial.

I've found that the polynomial $X^q-X$ has all elements of $K$ as roots.

Answer 1

Consider the subspace $V$ of polynomials in $K[x]$ of degree $<q$. Let's turn $V$ into a set of functions $F(K,K)$ from $K$ to itself by evaluating the polynomials at all the points of $K$. This is a $K$-linear mapping $ev:V\to F(K,K)$.

• The polynomials $\in V\setminus\{0\}$ can have at most $q-1$ zeros in $K$, so the kernel of $ev$ must be trivial. Hence $ev$ is injective.
• Because $\dim_KV=q=\dim_KF(K,K)$, it follows that $ev$ is a bijection. In other words, we get each and every function in $F(K,K)$ exactly once by evaluating the polynomials in $V$.
• The conclusion of the previous bullet then holds for each coset of $V$ in $K[x]$ as well (we can extend the definition of $ev$ to all of $K[x]$).
• Given that $n\ge q$, the collection of polynomials of degree exactly $n$ is a union of disjoint cosets $f+V$ where $f$ ranges over some set of representatives.
• The probability of a function in $F(K,K)$ not having any zeros is $(1-1/q)^q$. By the previous bullets this holds for all the cosets $f+V$ as well, and therefore also for any union of such cosets.