# Maximal Distinct Roots in $F_q$

Let $a\in F_q[x]$, and let $r(\cdot)$ denote the number of distinct roots over $F_q$. For any $i|q$, prove that $$\max_{\deg(a)=1}r(x^i-a)=r(x^i-x)$$

-

Hints: Show that for every $a,b \in F_q$,

1. $r(x^i - ax) \le r(x^i - x)$.

2. $r(x^i - ax - b) \le r(x^i - ax)$.

For 1), factor out an $x$, then use the fact that the roots of $x^{i-1}-1$ form a multiplicative subgroup. For 2), use the fact that the roots of $x^i - ax$ form an additive subgroup.

-
Very nice! However, I am only able to show inequality for 2., not equality (which is sufficient to solve the problem). Can you clarify how you established equality? Lastly, if possible let me know where you have seen this trick before. – pre-kidney Feb 3 '13 at 18:54
Sorry, it should be an inequality. But that's good enough for the problem. I will fix the answer. – Ted Feb 3 '13 at 18:55
Thanks! What was the inspiration for your proof, and can we extend to other $i$ as well? – pre-kidney Feb 3 '13 at 18:57
Where I've seen this before: One way to construct the finite field of order $p^n$ is to take the splitting field of $x^{p^n}-x$ over $F_p$, and note that the roots of this polynomial form a subfield. This problem is similar. The first inequality will extend to other $i$, but second won't because you really need the power of $p$ to get an additive homomorphism. – Ted Feb 3 '13 at 19:00
I was hoping for a different answer. It is clear that you need $i|q$ for additivity, but my real question is: can we make progress without using these homomorphisms. i.e., if the result is true for other $i$, there should be a proof that doesn't use additivity. You seem certain that it doesn't hold for other $i$; do you have a counterexample? – pre-kidney Feb 3 '13 at 19:05