On random permutations of finite groups

Given a finite abelian group G,  consider a uniformly random permutation of the set of all elements of G. Compute the difference of each pair of consecutive elements along the permutation. What is the number of occurrences of \(h\in G\setminus \{0\}\) in this sequence of differences? How do these numbers of occurrences behave for several group elements simultaneously? Can we get similar results for non-abelian G? How do the answers change if differences are replaced by sums? In this paper, we answer these questions. Moreover, we formulate analogous results in a general combinatorial setting.

     

Binomial differentially 4 uniform permutations with high nonlinearity

Differentially 4 uniform permutations with high nonlinearity on fields of even degree are crucial to the design of S-boxes in many symmetric cryptographic algorithms. Until now, there are not many known such functions and all functions known are power functions. In this paper, we construct the first class of binomial differentially 4 uniform permutations with high nonlinearity on ${\mathbb{F}}_{2^{6m}}$, where m is an odd integer. This result gives a positive answer to an open problem proposed in Bracken and Leander (2010) [7].     

On finite differences,permutations, and Quadratic residues

Let p be an odd prime and n an integer relatively prime to p. In this work three criteria which give the value of the Legendre symbol ($\text{n}\text{p}$) are developed. The first uses two adjacent rows of Pascal's triangle which depend only on p to express ($\text{n}\text{p}$) explicitly in terms of the numerically least residues (mod p) of the numbers n, 2n, …, [$\text{(p + 1)}\text{4}\text{]n}$ or of the numbers $\text{[}\text{(p + 1)}\text{4}\text{]n,…, [}\text{(p ? 1)}\text{2}\text{]n}$. The second, analogous to a theorem of Zolotareff and valid only if p ≡ 1 (mod 4), expresses ($\text{n}\text{p}$) in terms of the parity of the permutation of the set {$\text{1,2,…, (}\text{(p? 1)}\text{2}$} defined by the absolute values of the numerically least residues of $\text{n, 2n,…,[}\text{(p? 1}\text{2}\text{]n}$. The third is a result dual to Gauss' lemma which can be derived directly without Euler's criterion. The applications of the dual include a proof of Gauss' lemma free of Euler's criterion and a proof of the Quadratic Reciprocity Law.     

On non-monomial APcN permutations over finite fields of even characteristic

Recently, a new concept called the c-differential uniformity was proposed by Ellingsen et al. (2020), which generalizes the notion of differential uniformity measuring the resistance against differential cryptanalysis. Since then, finding functions having low c-differential uniformity has attracted the attention of many researchers. However it seems that, at this moment, there are not many non-monomial permutations having low c-differential uniformity. In this paper, we present new classes of (almost) perfect c-nonlinear non-monomial permutations over a binary field.     

Binomial permutations over finite fields with even characteristic

Designs, Codes and Cryptography - In this paper, we study binomials having the form $$x^r(a+x^{3(q-1)})$$ over the finite field $$\mathbb {F}_{q^2}$$ with $$q=2^m$$ , and determine all the...     

The Hopf algebra of uniform block permutations

We introduce the Hopf algebra of uniform block permutations and show that it is self-dual, free, and cofree. These results are closely related to the fact that uniform block permutations form a factorizable inverse monoid. This Hopf algebra contains the Hopf algebra of permutations of Malvenuto and Reutenauer and the Hopf algebra of symmetric functions in non-commuting variables of Gebhard, Rosas, and Sagan. These two embeddings correspond to the factorization of a uniform block permutation as a product of an invertible element and an idempotent one. Aguiar supported in part by NSF grant DMS-0302423. Orellana supported in part by the Wilson Foundation.     

On permutations with limited repetition

This note considers the enumeration of r-permutations with limited repetition, where each of the n objects to be permuted may appear at most s times. A recursive formula and an asymptotic expression are obtained and the problem is related to the (extended) birthday problem.     

On uniform local dispersion on a family of G-orbits

Consider a topological space T which is the union of a family of G-orbits, where G is a locally euclidean group G acting on T. On every G-orbit consider a probability which is absolutely continuous with respect to the image measure of the normalized restriction of the Haar measure on some compact neighborhood of the identity in G. Assume that the densities of the probabilities on the orbits have a common upper bound. Let μ be a probability on T which is the integral over the measures on the orbits with respect to some probability μ′ on T. It is shown that this specific kind of integral representation of μ does not depend on the size of the compact neighborhood of the identity in G.     

Compatible additive permutations of finite integral bases

Let be an additive permutation of a finite integral base. It is shown that ifB is symmetric, then there is a unique additive permutation ofB which is compatible with in the sense that ^–1 is also an additive permutation; and that, further, ifB is asymmetric, then there is no additive permutation ofB which is compatible with. Thus, in the symmetric case, there are no additively compatible sets (of permutations) forB of size greater than 3. This contrasts with the situation for completely compatible sets (equivalently, additive sequences of permutations) where for certainB compatible sets of size (resp. length) 4 or less are known, but where nothing is known of sets of greater size (resp. length). It is also noted how this result restricts the possibility of a useful multiplication theorem for the additive analogue of perfect systems of difference sets and graceful graphs.     

On convex permutations

A selection of points drawn from a convex polygon, no two with the same vertical or horizontal coordinate, yields a permutation in a canonical fashion. We characterise and enumerate those permutations which arise in this manner and exhibit some interesting structural properties of the permutation class they form. We conclude with a permutation analogue of the celebrated Happy Ending Problem.     

On TDP permutations

A permutation :i| _i , 0i<n is called a TDP permutation ifi–a _i j–a _j (modn) fori j. This paper finds all TDP permutations forn15, discusses the method for generating TDP permutations, and finally by applying MLE method obtains a formula for estimating the number of TDP permutations forn> 15.Project supported by National Natural Science Foundation of China.     

A recursive construction of t‐wise uniform permutations

We present a recursive construction of a (2t + 1)‐wise uniform set of permutations on 2n objects using a combinatorial design, a t‐wise uniform set of permutations on n objects and a (2t + 1)‐wise uniform set of permutations on n objects. Using the complete design in this procedure gives a t‐wise uniform set of permutations on n objects whose size is at most t²ⁿ, the first non‐trivial construction of an infinite family of t‐wise uniform sets for . If a non‐trivial design with suitable parameters is found, it will imply a corresponding improvement in the construction. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 531–540, 2015     

Constructing permutations of finite fields via linear translators

Methods for constructing large families of permutation polynomials of finite fields are introduced. For some of these permutations the cycle structure and the inverse mapping are determined. The results are applied to lift minimal blocking sets of PG(2,q) to those of PG(2,qn).     

A polynomial realization of the Hopf algebra of uniform block permutations

We provide a polynomial realization of the Hopf algebra UBP of uniform block permutations defined by Orellana and Aguiar (2008) [11]. We describe an embedding of the dual of the Hopf algebra WQSym into UBP, and as a consequence, obtain a polynomial realization of it.