I recently became aware of how much I deeply don’t understand the quantum end of theoretical compsci, so I’m trying to get a decent handle on that.
I’ve also been doing work on some problems related to the behavior of polynomials over finite fields. Theorem: Let F_q be a finite field with q elements, and let f be a polynomial of degree n with coefficients lying in F. Then if the image of f is not all of F, then the number of elements in the image of f is bounded by q - (q-1)/n. See here for a proof.
One corollary of this is the following: Let f be a non-trivial cyclotomic polynomial. Then over a finite field F_q, the size of the image of is bounded by q - (q-1)/n. This follows from observing that if a non-trivial cyclotomic polynomial has a root in some finite field then it factors into linear factors in the obvious way and thus has more than one zero. Either way we can apply the above theorem.
This has lead to think about the sizes of the images of polynomials over finite fields in general. In particular, in the cyclotomic case can we improve the q - (q-1)/n bound substantially? And is there some nice way of describing what polynomials are subject to this bound over all but finitely many finite fields?
I recently became aware of how much I deeply don’t understand the quantum end of theoretical compsci, so I’m trying to get a decent handle on that.
I’ve also been doing work on some problems related to the behavior of polynomials over finite fields. Theorem: Let F_q be a finite field with q elements, and let f be a polynomial of degree n with coefficients lying in F. Then if the image of f is not all of F, then the number of elements in the image of f is bounded by q - (q-1)/n. See here for a proof.
One corollary of this is the following: Let f be a non-trivial cyclotomic polynomial. Then over a finite field F_q, the size of the image of is bounded by q - (q-1)/n. This follows from observing that if a non-trivial cyclotomic polynomial has a root in some finite field then it factors into linear factors in the obvious way and thus has more than one zero. Either way we can apply the above theorem.
This has lead to think about the sizes of the images of polynomials over finite fields in general. In particular, in the cyclotomic case can we improve the q - (q-1)/n bound substantially? And is there some nice way of describing what polynomials are subject to this bound over all but finitely many finite fields?