A note on the discriminator (Q1281639)

Let \(f(x)\in \mathbb{Z}[X]\) 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),\dots, f(n)\) are distinct modulo \(k\). If no such \(k\) exists, we put \(D_f(n)= \infty\). The function \(D_f\) has been called the discriminator, since it represents the least modulus which `discriminates' the consecutive values of the polynomial \(f\). The discriminator was introduced for \(f= x^2\) by \textit{L. K. Arnold, S. J. Benkoski} and \textit{B. J. McCabe} [Am. Math. Mon. 92, 275-277 (1985; Zbl 0573.10002)], in connection with an algorithm to quickly determine the square roots of a long sequence of integers. Various authors studied the discriminator for specific choices of \(f\), thus Schumer and Steinig looked at cubes and fourth powers. The general cyclic polynomial \(f=X^d\) was considered by \textit{P. S. Bremser, P. D. Schumer} and \textit{L. C. Washington} [J. Number Theory 35, 105-108 (1990; Zbl 0712.11003)]. The main problem is to find an easy characterization for the discriminator. Thus Bremser et al. proved that if \(n\geq B_d\), where \(B_d\) is related to Bertrand's postulate for arithmetic progressions with modulus \(d\), then \(D_{X^d}(n)= \min\{k\mid k\geq n\), \(k\) squarefree; \((\varphi(k),d)= 1\}\), where \(\varphi\) denotes Euler's totient. They proved a similar result for \(d\) even. The reviewer and \textit{G. L. Mullen} [J. Number Theory 59, 88-105 (1996; Zbl 0858.11057)] dealt with the case where \(f\) is a Dickson polynomial (these include cyclic polynomials). The reviewer noticed around 1994 that most published characterizations for \(D_f\) up to that time had the format \(D_f(n)= \min\{k\geq n:f\) permutes \(\mathbb{Z}/ k\mathbb{Z}\}\), valid for every \(n\) large enough, and in [Finite Fields Appl. 2, 321-335 (1996; Zbl 0893.11007)], using some results from the theory of permutation polynomials, established conditions on \(f\) under which such a characterization holds. This encompassed all previous characterizations with \(f\) of odd degree. Thus the study of the discriminator sheds some light as to how good the permutation properties of \(f\) are and might, indeed, even be used to quantify this. In the present paper the author, by using some original ideas, extends the result of the reviewer to a larger class of polynomials \(f\). He also points out that his methods apply to many polynomials for which his conditions are not satisfied. He demonstrates this by a detailed analysis of the case where \(f= 5X^3- 2X\). He shows that for this choice of \(f\) the image of \(D_f\) contains infinitely many integers that are not in the set of integers \(k\) for which \(f\) permutes \(\mathbb{Z}/ k\mathbb{Z}\). In a paper in preparation by the author and the reviewer they introduce new methods that completely determine \(D_f\) in this case (and allow one to do so for many other \(f\)). More important, they improve on the author's improvement of the result of the reviewer, by making use of a result by Bombieri on exponential sums and Weil's bound.