Quasirandom arithmetic permutations

In [J.N. Cooper, Quasirandom permutations, 2002, to appear], the author introduced quasirandom permutations, permutations of Z_n which map intervals to sets with low discrepancy. Here we show that several natural number-theoretic permutations are quasirandom, some very strongly so. Quasirandomness is established via discrete Fourier analysis and the Erd?s-Turán inequality, as well as by other means. We apply our results on Sós permutations to make progress on a number of questions relating to the sequence of fractional parts of multiples of an irrational. Several intriguing open problems are presented throughout the discussion.     

Brauer groups are not characterized by Ulm invariants

Two important invariants of a fieldF are its Brauer groupB(F) and its character groupX(F). IfF is countable, these are countable abelian torsion groups, and so are determined by their Ulm invariants. We show here that Ulm’s invariants do not determine Brauer groups or character groups of uncountable fields. An essential tool, which is entirely group theoretic in nature, is a fact about ultraproducts of torsion groups. Supported in part by NSF Grant No. DMS-8500883. Supported in part by NSA Grant No. MDA904-85-H-0014. Supported in part by NSF Grant No. DMS-8500929.     

Null vectors, 3-point and 4-point functions in conformal field theory

We consider 3-point and 4-point correlation functions in a conformal field theory with a W-algebra symmetry. Whereas in a theory with only Virasoro symmetry the three-point functions of descendant fields are uniquely determined by the three-point function of the corresponding primary fields this is not the case for a theory withW ₃ algebra symmetry. The generic 3-point functions of W-descendant fields have a countable degree of arbitrariness. We find, however, that if one of the fields belongs to a representation with null states that this has implications for the 3-point functions. In particular, if one of the representations is doubly degenerate, then the 3-point function is determined up to an overall constant. We extend our analysis to 4-point functions and find that if two of the W-primary fields are doubly degenerate then the intermediate channels are limited to a finite set and that the corresponding chiral blocks are determined up to an overall constant. This corresponds to the existence of a linear differential equation for the chiral blocks with two completely degenerate fields as has been found in the work of Bajnok et al.Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 98. No. 3, pp. 500–508, March, 1994     

A ternary 4-point approximating subdivision scheme

In the implementation of subdivision scheme, three of the most important issues are smoothness, size of support, and approximation order. Our objective is to introduce an improved ternary 4-point approximating subdivision scheme derived from cubic polynomial interpolation, which has smaller support and higher smoothness, comparing to binary 4-point and 6-point schemes, ternary 3-point and 4-point schemes (see Table 2). The method is easily generalized to ternary (2n + 2)-point approximating subdivision schemes. We choose a ternary scheme because a way to get smaller support is to raise arity. And we use polynomial reproduction to get higher approximation order easily.     

Varieties defined by permutations

Let be a symmetric group on a set {1,2,...,n}. For an arbitrary permutation π of , we consider a variety _n G _π ofn-groupoids (A, f) satisfying the identityf(x ₁,x ₂,...,x _n )=f(x _π(1),x _π(2)...,x _π(n)). It is proved that if lengths of all independent cycles of π are positive degrees of one numberm ≥2 then _n G _π has a finite dimension equal to the number of prime divisors ofm. The dimension of a variety, in this event, is the least upper bound of lengths of independent bases for the collection of all strong Mal’tsev conditions satisfied in that variety. Translated fromAlgebra i Logika, Vol. 39, No. 1, pp. 104–118, January–February, 2000.     

Almost perfect nonlinear families which are not equivalent to permutations

An important problem on almost perfect nonlinear (APN) functions is the existence of APN permutations on even-degree extensions of ${\mathbb{F}}_2$ larger than 6. Browning et al. (2010) gave the first known example of an APN permutation on the degree-6 extension of ${\mathbb{F}}_2$. The APN permutation is CCZ-equivalent to the previously known quadratic Kim κ-function (Browning et al. (2009)). Aside from the computer based CCZ-inequivalence results on known APN functions on even-degree extensions of ${\mathbb{F}}_2$ with extension degrees less than 12, no theoretical CCZ-inequivalence result on infinite families is known. In this paper, we show that Gold and Kasami APN functions are not CCZ-equivalent to permutations on infinitely many even-degree extensions of ${\mathbb{F}}_2$. In the Gold case, we show that Gold APN functions are not equivalent to permutations on any even-degree extension of ${\mathbb{F}}_2$, whereas in the Kasami case we are able to prove inequivalence results for every doubly-even-degree extension of ${\mathbb{F}}_2$.     

Conjugation of injections by permutations

Let Ω be a countably infinite set, Inj(Ω) the monoid of all injective endomaps of Ω, and Sym(Ω) the group of all permutations of Ω. Also, let f,g,h∈Inj(Ω) be any three maps, each having at least one infinite cycle. (For instance, this holds if f,g,h∈Inj(Ω)∖Sym(Ω).) We show that there are permutations a,b∈Sym(Ω) such that h=afa ⁻¹ bgb ⁻¹ if and only if |Ω∖(Ω)f|+|Ω∖(Ω)g|=|Ω∖(Ω)h|. We also prove a generalization of this statement that holds for infinite sets Ω that are not necessarily countable.     

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].     

Counting permutations by their alternating runs

We find a formula for the number of permutations of [n] that have exactly s runs up and down. The formula is at once terminating, asymptotic, and exact. The asymptotic series is valid for n→∞, uniformly for s?(1−?)n/logn (?>0).     

Representations of hypergroups by generalized permutations

Special classes of generalized permutations are introduced and studied. An interpretation of them is given and they are used to represent finite hypergroups.Presented by I. Rosenberg.     

Counting the 10-point graphs by partition

In this paper we discuss old and new theoretical methods for computing the number of graphs with a given partition. We also show how a judicious combination of these methods gives rise to a procedure that is sufficiently powerful to make possible the enumeration of all graphs on 10 points according to their partitions.     

Constructing new differentially 4-uniform permutations from known ones

In this paper we study a new construction of differentially 4-uniform permutations from known ones and the inverse function. We focus on constructing methods of [20]. We split a finite field into its subfield and remainder, and, we choose known differentially 4-uniform permutations over the subfield and the inverse function over the entire field. As a result, we obtain two families of differentially 4-uniform permutations.     

Counting permutations by successions and other figures

Let π=(π(1), π(2),…, π(n)) be a permutation of the arbitrary n-set S of positive integers. A p-succession (alternately, p-rise) in π is any pair π(i), π(i+1) with π(i+1)=π(i)+1p, i=1,2,…, n-1 (alternately, π(i+1)?π(i)+p). A succession (alternately, rise) is just a p-succession (alternately, p-rise) with p=1. A p-run in π is a subsequence i, i+1,…,i+p-1 of the permutation π. We show that the number of permutations of S which have precisely α rises and β successions depends only on n=¦S¦, α, β, and l, where l is the number of maximal subsets {i,i+1,…,i+j)} of S, and determine an explicit recursion and generating function for these numbers. The same methodology is applied to count permutations of S by number of rises and figures of a more general type, where a specific criterion characterizes such figures. As a special case, we obtain the generating function when the figure is a p-run. Finally, we enumerate permutations of S by number of p-successions. Additional results are provided relating this particular enumeration problem to the special case of ordinary successions (p=1).     

On the permutations generated by Sturmian words

Infinite permutations of use in this article were introduced in [1]. Here we distinguish the class of infinite permutations that are generated by the Sturmian words and inherit their properties. We find the combinatorial complexity of these permutations, describe their Rauzy graphs, frequencies of subpermutations, and recurrence functions. We also find their arithmetic complexity and Kamae complexity.     

Reconstruction of permutations distorted by reversal errors

The problem of reconstructing permutations on n elements from their erroneous patterns which are distorted by reversal errors is considered in this paper. Reversals are the operations reversing the order of a substring of a permutation. To solve this problem, it is essential to investigate structural and combinatorial properties of a corresponding Cayley graph on the symmetric group Sym_n generated by reversals. It is shown that for any n?3 an arbitrary permutation π is uniquely reconstructible from four distinct permutations at reversal distance at most one from π where the reversal distance is defined as the least number of reversals needed to transform one permutation into the other. It is also proved that an arbitrary permutation is reconstructible from three permutations with a probability p₃→1 and from two permutations with a probability as n→∞. A reconstruction algorithm is presented. In the case of at most two reversal errors it is shown that at least erroneous patterns are required in order to reconstruct an arbitrary permutation.     

Constructing new differentially 4-uniform permutations from the inverse function

Two new families of differentially 4-uniform permutations over ${\mathbb{F}}_{2^{2m}}$ are constructed by modifying the values of the inverse function on some subfield of ${\mathbb{F}}_{2^{2m}}$ and by applying affine transformations on the function. The resulted 4-uniform permutations have high nonlinearity and algebraic degree. A family of differentially 6-uniform permutations with high nonlinearity and algebraic degree is also constructed by making the modification on an affine subspace of ${\mathbb{F}}_{2^{2m}}$.