
For \(q\) a prime power, let \(\mathbb{F}_ q\) denote the finite field of order \(q\) and let \(f\in \mathbb{F}_ q (x)\) be a rational function over \(\mathbb{F}_ q\). \(D\subseteq \mathbb{F}_ q\) will denote the domain of definition of \(f\). In recent years many papers have been written concerning permutation polynomials over \(\mathbb{F}_ q\), i.e. permutations which are induced by polynomials over \(\mathbb{F}_ q\). In this paper the authors consider several more general settings and study three notions of permutation function: (i) \(f\) is a permutation of \(\mathbb{F}_ q\); (ii) \(f\) is a permutation on \(D\); (iii) \(f\) is injective on \(D\). The paper contains many detailed results concerning each of these notions of permutation function as well as their inter-connections. In particular for each of them, a random polynomial-time algorithm test is presented. In addition, for the image or value set size of an arbitrary rational function, a fully polynomial-time randomized approximation scheme is given. Finally the paper concludes with a list of five open questions.
Algebra and Number Theory, Applied Mathematics, permutation function, polynomial-time randomized approximation scheme, permutation polynomials, Structure theory for finite fields and commutative rings (number-theoretic aspects), Polynomials over finite fields, Theoretical Computer Science, random polynomial-time algorithm test, finite field, open questions, Engineering(all)
Algebra and Number Theory, Applied Mathematics, permutation function, polynomial-time randomized approximation scheme, permutation polynomials, Structure theory for finite fields and commutative rings (number-theoretic aspects), Polynomials over finite fields, Theoretical Computer Science, random polynomial-time algorithm test, finite field, open questions, Engineering(all)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
