Distribution of values of polynomial Fermat quotients
type: Item
instance of: scholarly article
title: Distribution of values of polynomial Fermat quotients
zbMATH Open document ID: 1305.11104
author: Igor E. Shparlinski
author: Arne Winterhof
published in: Finite Fields and their Applications
publication date: 2013-01-14T00:00:00Z
review text: In analogy with the Fermat quotient \((a^{p-1}-1)/p\pmod p\) defined for primes \(p\) and integers \(a\) coprime to \(p\), the authors define for an irreducible polynomial \(P\in {\mathbb F}_q[X]\) of degree \(n\geq 2\) and a polynomial \(A\in {\mathbb F}_q[X]\) of degree at most \(n-1\) the quotient \(q_P(A)\equiv (A^{q^n-1}-1)/P\pmod P\). Here \(q=p^r\) is a power of the prime \(p\). In the paper under review, the authors study the number of fixed points and the image size of the map \(q_P(A)\) when \(P\) is fixed and \(A\) varies in the set \({\mathcal P}_{n,q}\) of polynomials of degree at most \(n-1\) in \({\mathbb F}_q[X]\). Denoting by \(N_P(n,q)\) for the number of such fixed points, the authors prove that \[ N_P(n,q)\leq \left\{ \begin{matrix} 1+c_q\frac{q^{n-\lceil n/p\rceil-1}-1}{q-1} & n=2,~3,~{\text{or}}~n\geq 4~{\text{and}}~q\in \{2,4\},\\ q^{n/2}+1/2, & n\geq 4~{\text{and}}~q~{\text{is~odd}},\\ 2^n, & n\geq 4~{\text{and}}~q\geq 8~{\text{is~even}}. \end{matrix}\right. \] Here, \(c_q=2\) if \(q\) is odd and \(c_q=1\) if \(q\) is even. Denoting \(M_P(n,q)\) for the image size of \(q_P(A)\) when \(A\) varies in \({\mathcal P}_{n,q}\), they prove that \[ 1+\frac{q^n-q^{\lceil n/p\rceil}}{q-1}\geq {\mathcal M}_P(n,q)\geq \left\{ \begin{matrix} q^{\lceil 3/p\rceil}+1, & n=3,\\ (1+o(1)) \frac{q^{n-2}(q-1)}{n(n-1)}, & n\geq 4\end{matrix}\right. \] as \(q^n\to\infty\). The classical ``Prime Number Theorem'' in this context, which is the asymptotic estimate \(q^k/k\) for the number of irreducible monic polynomials of degree \(k\) in \({\mathbb F}_q[X]\) plays an important role in some of the proofs.
reviewed by: Florian Luca
Mathematics Subject Classification ID: 11T06
Mathematics Subject Classification ID: 11T55
zbMATH DE Number: 6125342
zbMATH Keywords: Fermat quotients
zbMATH Keywords: polynomials
zbMATH Keywords: fixed points
zbMATH Keywords: image size
zbMATH Keywords: multiplicity of values
MaRDI profile type: Publication
full work available at URL: j.ffa.2012.10.004
OpenAlex ID: W2018018612
DOI: 10.1016/J.FFA.2012.10.004
Recommended article: The distribution of values of polynomials over a finite field
Recommended article: Statistical distribution of Fermat quotients
Recommended article: Distribution of roots of polynomial congruences
Recommended article: Q5817513
Recommended article: Value distribution of cyclotomic polynomial coefficients
Recommended article: Distribution of polynomial discriminants modulo a prime
Recommended article: Q3666917
Recommended article: On the distribution of quadratic residues
Recommended article: THE DISTRIBUTION OF DIVISORS OF POLYNOMIALS
description: scientific article; zbMATH DE number 6125342