Cycle types of complete mappings of finite fields

Abstract

We derive several existence results concerning cycle types and, more generally, the "mapping behavior" of complete mappings. Our focus is on so-called first-order cyclotomic mappings, which are functions on a finite field ${\mathbb{F}}_q$ that fix $0$ and restrict to the multiplication $x\mapsto a_{i}x$ by a fixed element $a_i\in {\mathbb{F}}_q$ on each coset $C_i$ of a given subgroup $C$ of ${\mathbb{F}}_q^{\ast }$. The gist of two of our main results is that as long as $q$ is large enough relative to the index $|{\mathbb{F}}_q^{\ast }:C|$, all cycle types of first-order cyclotomic permutations with only long cycles on ${\mathbb{F}}_q^{\ast }$ can be achieved through a complete mapping, as can all permutations of the cosets of $C$. Our third main result provides new examples of complete mappings $f$ such that both $f$ and its associated orthomorphism $f+\mathrm{id}$ permute the nonzero field elements in one cycle.

32 pages