A note on the discriminator
type: Item
instance of: scholarly article
title: A note on the discriminator
zbMATH Open document ID: 0924.11017
published in: Journal of Number Theory
publication date: 1999-11-15T00:00:00Z
review text: 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 characterizati…
reviewed by: Pieter Moree
Mathematics Subject Classification ID: 11C08
Mathematics Subject Classification ID: 11R09
zbMATH DE Number: 1268048
zbMATH Keywords: incongruence
zbMATH Keywords: value set
zbMATH Keywords: discriminator
zbMATH Keywords: Bertrand's postulate
zbMATH Keywords: polynomials
author: Michael E. Zieve
MaRDI profile type: Publication
OpenAlex ID: W2014210148
cites work: Note on a problem of Chowla
cites work: A note on the incongruence of consecutive integers to a fixed power
cites work: The distribution of polynomials over finite fields
cites work: Q3900124
cites work: On a conjecture of Schur
cites work: Galois Groups and Complex Multiplication
cites work: Q3941473
cites work: Q4325515
cites work: The incongruence of consecutive values of polynomials
cites work: Dickson polynomial discriminators
cites work: A new criterion for permutation polynomials
cites work: Q3476923
cites work: Q3136954
DOI: 10.1006/JNTH.1998.2256
description: scientific article; zbMATH DE number 1268048