Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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) $$

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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