Cycle types of complete mappings of finite fields

DOI10.1016/J.JALGEBRA.2021.09.017MaRDI QIDQ2664512zbMATH OpenOpenAlexFDO

Publication date 17 November 2021

Published in Journal of Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.00140

complete mappings cycle structure cyclotomic mappings cyclotomy finite fields

Permutations, words, matrices (05A05) Cyclotomy (11T22) Other character sums and Gauss sums (11T24) Arithmetic theory of polynomial rings over finite fields (11T55)

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

m a t h b b F_{q}

that fix

0

and restrict to the multiplication

x m a p s t o a_{i} x

by a fixed element

a_{i} i n m a t h b b F_{q}

on each coset

C_{i}

of a given subgroup

C

of

m a t h b b F_{q}^{a s t}

. The gist of two of our main results is that as long as

q

is large enough relative to the index

| m a t h b b F_{q}^{a s t} : C |

, all cycle types of first-order cyclotomic permutations with only long cycles on

m a t h b b F_{q}^{a s t}

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 + o p e r a t o r n a m e i d

permute the nonzero field elements in one cycle.

Review text

There is a much wider interest among algebraists to study complete mappings as a tool to construct orthogonal Latin squares. The existence of such mappings is also a fascinating area of study for many mathematicians. Let \((G, +)\) be an additive (though not necessarily abelian) group. A function \(f : G \longrightarrow G\) is called a \textit{complete mapping} of \(G\) if both \(f\) and \(f +id : g \longrightarrow f(g) +g\) are permutations of \(G\). In case \(G\) is the underlying additive group of a field \(K\), a complete mapping of \(G\) is also called a complete mapping of \(K\). For a divisor \(d\) of \(q - 1\), an \textit{index \(d\) first-order cyclotomic mapping} of \(\mathbb{F}_{q}\) is a function \(f : \mathbb{F}_{q} \longrightarrow \mathbb{F}_{q}\) such that \[ f(x) = \begin{cases} 0 & \quad\text{ if } x = 0 \\ a_{i}x & \quad\text{ if } x \in C_{i} \text{ for some } i = 0, 1, . . . , d - 1, \end{cases}. \] where \(a_{0}, a_{1}, . . . , a_{d-1} \in \mathbb{F}_{q}\) are fixed and \(C_{i} = \omega ^{i}C\) where \(\omega\) is a fixed primitive root of \(\mathbb{F}_{q}\) and \(C\) denotes the index \(d\) subgroup of \(\mathbb{F}^{*}_{q}\) . The three main theorems in the article are as follows: Theorem 1. Let \(d\) and \(n\) be positive integers, and let \( \varepsilon > 0\). There is a \(q_{0} = q_{0}(d, n, \epsilon) > 0\) such that for all prime powers \(q \geq q_{0}\) with \(q \equiv 1 \mod d\) and all \(c_{1}, c_{2}, \ldots, c_{n} \in \mathbb{F}_{q}\), every cycle type of a first-order cyclotomic permutation of \(\mathbb{F}_{q}\) of index \(d\) all of whose cycles on \(\mathbb{ F}_{q}^{*}\) are of length at least \( \varepsilon q\) can be realized as the cycle type of a first-order cyclotomic permutation \(f\) of \(\mathbb{F}_{q}\) such that \(f +c_{1} id, f +c_{2} id, \ldots, f +c_{n} id\) are permutations of \(\mathbb{F}_{q}\). Theorem 2. Let \(d\) and \(n\) be positive integers. There is a \(q_{1} = q_{1}(d, n) > 0\) such that for all prime powers \(q \geq q_{1}\) with \(q \equiv 1 (mod \ d)\), the following holds: Let \(c_{1}, c_{2}, \ldots, c_{n} \in\mathbb{F}_{q}\) be pairwise distinct, and let \(s_{1}, s_{2}, \ldots, s_{n}\) be functions \(M \longrightarrow M\) where \(M = \mathbb{F}_{q}^{*} /C\) is the set of all cosets in \(\mathbb{F}_{q}^{*}\) of the index \(d\) subgroup \(C\) of \(\mathbb{F}_{q}^{*}\). Then there is a first-order cyclotomic mapping \(f\) of \(\mathbb{F}_{q}\) of index \(d\) such that for all \(j = 1, 2, \ldots, n \) and all cosets \(\mathcal{C}\) of \(C\) in \(\mathbb{F}_{q}^{*}\) , one has \((f + c_{j} id)(\mathcal{C}) = s_{j}(\mathcal{C})\). Theorem 3. Let \(d > 1\) be an integer. There is a constant \(C = C(d) > 0\) such that if \(q\) is a prime power with \(q \equiv 1 \pmod d\) and \(q \geq C\), then the finite field \(\mathbb{F}_{q}\) admits a complete mapping \(f\) with \(f(0) = 0\) such that both \(f\) and \(f +id\) permute \(\mathbb{F}_{q}^{*}\) cyclically and \(f\) is not an additive function \(\mathbb{F}_{q} \longrightarrow \mathbb{F}_{q}\). The article spread over 34 pages has covered several technical concepts, theorems and lemmas from 36 references. Careful reading is required to understand the proof of the main theorems. Also, the authors have put forward three challenging open questions related to theorem 3 for further research.

Recommendations

Cites work

Cited in

(6)

Describes a project that uses

Uses Software

GAP

This page was built for publication: Cycle types of complete mappings of finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2664512)