Upper bound on the number of complete maps (Q1364111): Difference between revisions

The study of the asymptotic number of complete maps for the case of permutations begun in [\textit{I. Kovalenko} and \textit{M. Kuper}, An upper bound on the number of complete maps (1995)]. According to [\((*)\) \textit{J. Dénes} and \textit{A. D. Keedwell}, Latin squares and their applications (1974; Zbl 0283.05014)], a complete map of a set \(A\) with the operation \(\circ\) is a bijection \(f: A\to A\) such that the map defined by the formula \(x\to x\circ f(x)\) is also a bijection. If \(A\) is the set of permutations of order \(n\) and \(\circ\) is the operation of addition \(\pmod n\), then no complete maps exist for even \(n\); at the same time, for odd \(n\), the probability that a random permutation is a complete map will be less than \(\exp\{-cn\}\) for sufficiently large \(n\). In \((*)\) it is proved that \(c\geq 0.08854\). The objective of this article is to improve the bound on \(c\), specifically to show that \(c\geq\ln 2/2\approx 0.35\). We also give an enumeration algorithm for all complete maps in a given class with \(2^{(n-1)/2}\) elements. This may increase by the same factor the ``efficiency'' of random search for a complete map.