The design of composite permutations with applications to DES-like S-boxes

This paper presents an iterative construction method for building composite permutations. Its efficiency is based on the concepts of pre-computation and equivalence classes. Equivalence class representatives of permutations on four bits are pre-computed. These class representatives can serve as input to the construction method, however, the results are also of independent interest for applications in cryptography. A well-known example of a cryptosystem using composite permutations for its Substitution boxes (S-boxes) is the Data Encryption Standard (DES). Throughout the paper, DES-like S-boxes are defined as mappings satisfying all design criteria as disclosed by one of the designers of DES. All permutations on four bits with DES-like properties are identified. Starting with pre-computed representatives of classes with such permutations, two iterations of a specialized version of the algorithm are applied to obtain bounds on the minimum differential uniformity and minimum non-linear uniformity of DES-like S-boxes. It is established that the two values cannot be less than eight, and that DES-like S-boxes for which the values are both equal to 12 do exist. In addition, if the non-linear uniformity of each of the four permutations in a DES-like S-box is at most six, as in all DES S-boxes, then its non-linear uniformity cannot be less than ten and its minimum differential uniformity equals 12.     

A compact representation for permutation groups

A data structure is presented which enables an arbitary permutation group of degree n to be represented in O(n²) space. An algorithm is provided which, given a permutation group specified in the usual way as a set of generators, constructs the proposed representation in time O(n⁵). The data structure supports fast membership testing, and is more economical than those previously suggested, both in terms of its size and the time required for its initialisation. Essential use is made of the proposed data structure in an efficient algorithm for generating systems of coset representatives; this algorithm may be used to solve certain instances of the so-called “isomorph rejection” problem.     

Sets of permutations that generate the symmetric group pairwise

The paper contains proofs of the following results. For all sufficiently large odd integers n, there exists a set of ²n−1 permutations that pairwise generate the symmetric group Sn. There is no set of ²n−1+1 permutations having this property. For all sufficiently large integers n with n≡2mod4, there exists a set of ²n−2 even permutations that pairwise generate the alternating group An. There is no set of ²n−2+1 permutations having this property.     

Free actions on handlebodies

The equivalence (or weak equivalence) classes of orientation-preserving free actions of a finite group G on an orientable three-dimensional handlebody of genus g?1 can be enumerated in terms of sets of generators of G. They correspond to the equivalence classes of generating n-vectors of elements of G, where n=1+(g−1)/|G|, under Nielsen equivalence (or weak Nielsen equivalence). For Abelian and dihedral G, this allows a complete determination of the equivalence and weak equivalence classes of actions for all genera. Additional information is obtained for other classes of groups. For all G, there is only one equivalence class of actions on the genus g handlebody if g is at least 1+?(G)|G|, where ?(G) is the maximal length of a chain of subgroups of G. There is a stabilization process that sends an equivalence class of actions to an equivalence class of actions on a higher genus, and some results about its effects are obtained.     

Baxter permutations and plane bipolar orientations

We present a simple bijection between Baxter permutations of size n and plane bipolar orientations with n edges. This bijection translates several classical parameters of permutations into natural parameters of orientations, and has remarkable symmetry properties. By specialising it to Baxter permutations avoiding the pattern 3142, we obtain a bijection with non-separable planar maps, which had been described only in an implicit recursive manner so far (up to simple symmetries). A further specialization yields a bijection between permutations avoiding 3142 and 2413 and series-parallel maps.     

Green's relations in finite function semigroups

Let? _n be the set of all partial functions on ann-element setX _n , i.e., the set of all functions whose domain and range are subsets ofX _n . Green's equivalence relations?, ?, ? and? are considered, and the number and cardinality of the corresponding equivalence classes are determined. The number of idempotent and generalized idempotent elements in? _n is also determined.     

Cyclotomic factors of the descent set polynomial

We introduce the notion of the descent set polynomial as an alternative way of encoding the sizes of descent classes of permutations. Descent set polynomials exhibit interesting factorization patterns. We explore the question of when particular cyclotomic factors divide these polynomials. As an instance we deduce that the proportion of odd entries in the descent set statistics in the symmetric group Sn only depends on the number on 1's in the binary expansion of n. We observe similar properties for the signed descent set statistics.     

The maximal-inversion statistic and pattern-avoiding permutations

We define a new combinatorial statistic, maximal-inversion, on a permutation. We remark that the number M(n,k) of permutations in S_n with k maximal-inversions is the signless Stirling number c(n,n−k) of the first kind. A permutation π in S_n is uniquely determined by its maximal-inversion set . We prove it by making an algorithm for retrieving the permutation from its maximal-inversion set. Also, we remark on how the algorithm can be used directly to determine whether a given set is the maximal-inversion set of a permutation. As an application of the algorithm, we characterize the maximal-inversion set for pattern-avoiding permutations. Then we give some enumerative results concerning permutations with forbidden patterns.     

On sorting by 3-bounded transpositions

Heath and Vergara [Sorting by short block moves, Algorithmica 28 (2000) 323-352] proved the equivalence between sorting by 3-bounded transpositions and sorting by correcting skips and correcting hops. This paper explores various algorithmic as well as combinatorial aspects of correcting skips/hops, with the aim of understanding 3-bounded transpositions better.We show that to sort any permutation via correcting hops and skips, ⌊n/2⌋ correcting skips suffice. We also present a tighter analysis of the approximation algorithm of Heath and Vergara, and a possible simplification. Along the way, we study the class H_n of those permutations of S_n which can be sorted using correcting hops alone, and characterize large subsets of this class. We obtain a combinatorial characterization of the set G_n⊆S_n of all correcting-hop-free permutations, and describe a linear-time algorithm to optimally sort such permutations. We also show how to efficiently sort a permutation with a minimum number of correcting moves.     

Equivalence classes of second-order ordinary differential equations with only a three-dimensional Lie algebra of point symmetries and linearisation

There are seven equivalence classes of second-order ordinary differential equations possessing only three Lie point symmetries and hence not linearisible by means of a point transformation. We examine the representatives of these classes for linearisibility by means of other types of transformation. In particular we compare the potential for linearisibility and the possession of the Painlevé property. The complete symmetry group is realised in the standard algebra for each of the equivalence classes.     

Integral Self-Affine Tiles in {\Bbb R}^n Part II: Lattice Tilings

Let A be an expanding n × n integer matrix with |det (A)| = m. A standard digit set ${\cal D}Let A be an expanding n×n integer matrix with |det(A)|=m. Astandard digit set D for A is any complete set of coset representatives for? ⁿ /A(? ⁿ ). Associated to a given D is a setT (A, D), which is the attractor of an affine iterated function system, satisfyingT=∪ _d∈D (T+d). It is known thatT (A, D) tiles? ⁿ by some subset of? ⁿ . This paper proves that every standard digit set D gives a setT (A, D) that tiles? ⁿ with a lattice tiling.     

FINITE PERMUTATION REPRESENTATION OF A SUBGROUP OF PICARD GROUP＊

We investigate action of a subgroup G1 of the Picard group on finite sets using coset diagrams.We show that its actions on the sets of 3,4,5,6,8,and 12 elements yield building blocks of Coset diagrams ...     

Asymptotics of the moments of the number of cycles of a random A-permutation

We consider random permutations uniformly distributed on the set of all permutations of degree n whose cycle lengths belong to a fixed set A (the so-called A-permutations). In the present paper, we establish an asymptotics of the moments of the total number of cycles and of the number of cycles of given length of this random permutation as n → ∞.     

A transfer algorithm for hierarchical clustering

Transfer algorithms are usually used to optimize an objective function that is defined on the set of partitions of a finite set X. In this paper we define an equivalence relation ? on the set of fuzzy equivalence relations on X and establish a bijection from the set of hierarchies on X to the set of equivalence classes with respect to ?. Thus, hierarchies can be identified with fuzzy equivalence relations and the transfer algorithm can be modified in order to optimize an objective function that is defined on the set of hierarchies on X.     

Independent permutations,as related to a problem of Moser and a theorem of Pólya

We introduce the notion of a set of independent permutations on the domain {0, 1,… n ? 1}, and obtain bounds on the size of the largest such set. The results are applied to a problem proposed by Moser in which he asked for the largest number of nodes in a d-cube of side n such that no n of these nodes are collinear. Independent permutations are also related to the problem of placing n non-capturing superqueens (chess queens with wrap-around capability) on an n × n board. As a special case of this treatment we obtain Pólya's theorem that this problem can be solved if and only if n is not a multiple of 2 or 3.     

An expression for the number of equivalence classes of Latin squares under row and column permutations

In this paper equivalence classes of Latin squares induced by row and column permutations are considered. An expression for the number of such classes for an nth order Latin square is obtained in terms of Latin rectangles with n rows. In the case where n is prime the expression gives a simple result for those squares invariant under a permutation other than the identity.     

Some results concerning cryptographically significant mappings over GF(2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>)

In this paper we investigate the existence of permutation polynomials of the form F(x) = x ^d  + L(x) over GF(2 ⁿ ), L being a linear polynomial. The results we derive have a certain impact on the long-term open problem on the nonexistence of APN permutations over GF(2 ⁿ ), when n is even. It is shown that certain choices of exponent d cannot yield APN permutations for even n. When n is odd, an infinite class of APN permutations may be derived from Gold mapping x ³ in a recursive manner, that is starting with a specific APN permutation on GF(2 ^k ), k odd, APN permutations are derived over GF(2 ^k+2i ) for any i ≥ 1. But it is demonstrated that these classes of functions are simply affine permutations of the inverse coset of the Gold mapping x ³. This essentially excludes the possibility of deriving new EA-inequivalent classes of APN functions by applying the method of Berveglieri et al. (approach proposed at Asiacrypt 2004, see [3]) to arbitrary APN functions.     

Pattern avoidance for alternating permutations and Young tableaux

We define a class Ln,k of permutations that generalizes alternating (up-down) permutations and give bijective proofs of certain pattern-avoidance results for this class. As a special case of our results, we give bijections between the set A2n(1234) of alternating permutations of length 2n with no four-term increasing subsequence and standard Young tableaux of shape 〈n³〉, and between the set A2n+1(1234) and standard Young tableaux of shape 〈³n−1,2,1〉. This represents the first enumeration of alternating permutations avoiding a pattern of length four. We also extend previous work on doubly-alternating permutations (alternating permutations whose inverses are alternating) to our more general context.The set Ln,k may be viewed as the set of reading words of the standard Young tableaux of a certain skew shape. In the last section of the paper, we expand our study to consider pattern avoidance in the reading words of standard Young tableaux of any skew shape. We show bijectively that the number of standard Young tableaux of shape λ/μ whose reading words avoid 213 is a natural μ-analogue of the Catalan numbers (and in particular does not depend on λ, up to a simple technical condition), and that there are similar results for the patterns 132, 231 and 312.