Michael E. Zieve:
A note on the discriminator,
J. Number Theory 73 (1998), 122–138. MR 2000a:11037

(The published version is available online.)

Let  g(X)  be a polynomial with integer coefficients. For any positive integer  n , let  Dg(n)  denote the least positive integer  k  such that  g(1), g(2), ..., g(n)  are distinct modulo  k  (assuming some such  k  exists). The function  Dg  has been called the `discriminator', since it represents the least modulus which discriminates the consecutive values of  g.  We describe a large class of polynomials  g  having the property that the map  ag(a)  induces a bijection on  Z /Dg(n)  for all sufficiently large  n.  The special case  g = Xd  was treated previously by Bremser, Schumer, and Washington, and further special cases were addressed by Moree and Mullen and Moree. The results of the present paper apply to a significantly larger class of polynomials than those of previous papers. We also give various examples showing our results cannot be improved in certain ways, and we give information about the prime factorization of  Dg  in case  g  does not permute  Z /Dg(n).

The theme of our main result is that, if  g  is not injective on  Z /k,  then this non-injectivity is witnessed by the values of  g  at two positive integers much smaller than  k.  This complements work of Bombieri and Davenport, who showed under the same hypothesis that non-surjectivity is witnessed by some positive integer much smaller than  k  which does not occur as a value of  g  modulo  k.


Michael Zievehome page   publication list