On the characterization of minimal value set polynomials

We give an explicit characterization of all minimal value set polynomials in F-q[x] whose set of values is a subfield F-q', of F-q. We show that the set of such polynomials, together with the constants of F-q', is an F-q'-vector space of dimension 2([Fq:Fq']). Our approach not only provides the exact number of such polynomials, but also yields a construction of new examples of minimal value set polynomials for some other fixed value sets. In the latter case, we also derive a non-trivial lower bound for the number of such polynomials. (C) 2012 Elsevier Inc. All rights reserved.