Enumerating permutation polynomials. II: \(k\)-cycles with minimal degree.
type: Item
instance of: scholarly article
title: Enumerating permutation polynomials. II: \(k\)-cycles with minimal degree.
zbMATH Open document ID: 1035.11062
DOI: 10.1016/S1071-5797(03)00044-3
author: Claudia Malvenuto
author: Francesco Pappalardi
published in: Finite Fields and their Applications
publication date: 2004-01-19T00:00:00Z
review text: Every permutation \(\sigma\) on the elements of the finite field \(\mathbb F_q\) (\(q>2\)) is uniquely represented by a polynomial \(f_\sigma\in\mathbb F_q[x]\) of degree \(\partial(f_\sigma)\leq q-2\). A lower bound for \(\partial(f_\sigma)\) is given by the number of the fixed points of \(\sigma\) (\(\sigma\not=\text{id}\)). In [Finite Fields Appl. 8, 531--547 (2002; Zbl 1029.11068)], the authors considered the problem of enumerating conjugated permutations on \(\mathbb F_q\) whose corresponding polynomials are of degree \(<q-2\). In this sequel, they turn particularly their attention to permutation polynomials with minimal degree. Let \(m_{[k]}(q)\) denote the number of \(k\)-cycles \(\sigma\) on \(\mathbb F_q\) for which \(\partial(f_\sigma)=q-k\), or equivalently, \(\sum_{c\in\mathbb F_q} c^i(c-\sigma(c))=0\) for \(i=1,\ldots,k-2\). The authors give the upper bound \[ m_{[k]}(q)\leq\frac{(k-1)!}{k}\;q(q-1) \] if \(\text{ char}(\mathbb F_q)>e^{(k-3)/e}\) and the lower bound \[ m_{[k]}(q)\geq\frac{\varphi(k)}{k}\;q(q-1) \] for \(q\equiv1\bmod k\) where \(\varphi\) denotes the Euler totient function. Their proof is based on the relation of \(m_{[k]}(q)\) to the number of solutions in \(\mathbb F_q^{k-2}\) of a system of equations defined over \(\mathbb Z\). The paper concludes with the computation of \(m_{[4]}(q)\) and \(m_{[5]}(q)\) (and \(m_{[6]}(q)\) in parts) by means of computer algebra.
reviewed by: Astrid Reifegerste
Mathematics Subject Classification ID: 11T06
zbMATH DE Number: 2029211
zbMATH Keywords: permutation polynomials over finite fields
zbMATH Keywords: minimal degree
zbMATH Keywords: \(k\)-cycles
zbMATH Keywords: affine algebraic sets
describes a project that uses: Maple
MaRDI profile type: Publication
cites work: The number of permutation polynomials of a given degree over a finite field
cites work: Q4002797
cites work: Enumerating permutation polynomials over finite fields by degree
cites work: When Does a Polynomial Over a Finite Field Permute the Elements of the Field?
cites work: When Does a Polynomial over a Finite Field Permute the Elements of the Field?, II
cites work: Q3328449
cites work: Q3216750
cites work: Enumerating permutation polynomials. I: Permutations with non-maximal degree
cites work: Q4259422
cites work: Q3136948
cites work: The degrees of permutation polynomials over finite fields
Recommended article: Enumerating permutation polynomials. I: Permutations with non-maximal degree
Recommended article: Q3474736
Recommended article: On the Carlitz rank of permutation polynomials
Recommended article: On coefficients of polynomials over finite fields
Recommended article: Q4832293
Recommended article: Enumerating permutation polynomials over finite fields by degree
Recommended article: On a conjecture of Fernando, Hou and Lappano concerning permutation polynomials over finite fields
Recommended article: When Does a Polynomial Over a Finite Field Permute the Elements of the Field?
Recommended article: On the number of permutation polynomials over a finite field
Recommended article: On an open problem of Niederreiter
description: scientific article; zbMATH DE number 2029211