For f (X ) # Z[X], let D f (n) be the least positive integer k for which f (1), ..., f (n) are distinct modulo k. Several results have been proven about the function D f in recent years, culminating in Moree's characterization of D f (n) whenever f lies in a certain (large) subset of Z[X ] and n is sufficiently large. We give several improvements of Moree's result, as well as further results on the function D f . 1998 Academic Press
be a polynomial over the integers. For any positive integer n, let D f (n) denote the least positive integer k such that f (1), .. . , f (n) are distinct modulo k. If no such k exists, we put D f (n)= . The function D f has been called the discriminator,'' since it represents the least modulus which discriminates the consecutive values of the polynomial f. This function was originally studied for cyclic polynomials f =X d , in which case the main result is due to Bremser et al. [2]. When d is odd they showed that, for any sufficiently large n, D f (n) is the least integer k n for which the induced mapping f : ZΓkZ Γ ZΓk Z is a permutation. This result can be interpreted as saying that no polynomial f (X )=X d , with d odd, can almost'' permute ZΓkZ for large k; for, if the first several values of f are distinct modulo k, the result shows that f must in fact permute ZΓk Z. Subsequent work showed that a similar conclusion can be drawn for other types of polynomials f. Moree and Mullen [11] extended the above result to the case where f is a Dickson polynomial of degree coprime to 6. The Dickson polynomial of degree d 1 and parameter a # Z is defined to be the unique polynomial g d (X, a) # Z[X ] for which g d (X+aΓX, a)=X d + (aΓX ) d ; explicitly, g d (X, a)= : wdΓ2x i=0 d d&i \ d&i i + (&a) i X d&2i .