An arithmetic of complete permutations with constraints, II: case studies

Using the arithmetic of complete permutations developed in the first part of this paper, we investigate the spectra of certain constraints with respect to central, integral bases which are of interest for the purposes of giving further constructions either of complete permutations with constraints or of irregular, critical perfect systems of difference sets. We also present, in the appendices, catalogues of examples and enumerative data based on computer studies.     

Binomial posets, Möbius inversion, and permutation enumeration

A unified method is presented for enumerating permutations of sets and multisets with various conditions on their descents, inversions, etc. We first prove several formal identities involving Möbius functions associated with binomial posets. We then show that for certain binomial posets these Möbius functions are related to problems in permutation enumeration. Thus, for instance, we can explain “why” the exponential generating function for alternating permutations has the simple form (1 + sin x)/(cos x). We can also clarify the reason for the ubiquitous appearance of e^x in connection with permutations of sets, and of ξ(s) in connection with permutations of multisets.     

The structure of the centralizer of a permutation

Relative to the symmetric groups S_n the structure of centralizers of permutations are known as direct products of certain general wreath products. A recent generalization of the cycle notation for partial one-one transformations (charts) is applied to show that relative to the symmetric inverse semigroups C_n the structure of centralizers of permutations are also direct products of certain subsemigroups of a wreath product, and this latter wreath product includes the former as a subgroup. A necessary and sufficient condition is given for two charts to commute and the approach for the C_n-case parallels and generalizes the one for the S_n-case. As a result, the C_n-case yields the standard known characterizations of commuting permutations, as well as formulas for the orders of centralizers as corollaries. It is an open problem to extend these results to the centralizers of arbitrary charts in C_n. This research was partially supported by a Mary Washington College Faculty Development Grant.     

Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three

We consider the problem of enumerating the permutations containing exactly k occurrences of a pattern of length 3. This enumeration has received a lot of interest recently, and there are a lot of known results. This paper presents an alternative approach to the problem, which yields a proof for a formula which so far only was conjectured (by Noonan and Zeilberger). This approach is based on bijections from permutations to certain lattice paths with “jumps,” which were first considered by Krattenthaler.     

Higher order conservation laws and a higher order Noether's theorem

Consider a general variational problem of a functional whose domain of definition consists of integral manifolds of an exterior differential system. In particular, this induces classical variational problems with constraints. With the assumption of existence of enough admissable variations the Euler-Lagrange equations associated to this problem are obtained. By studying a spectral sequence associated to the infinite prolongation of them, we extend the classical notion of infinitesimal Noether symmetries to what we shall call the “higher order Noether symmetries,” and a higher order Noether's theorem identifying the higher order conservation laws and the higher order Noether symmetries is obtained. These in turn are isomorphic to the solution space of certain linear differential operator. From these we also get a systematic method of computing the higher order conservation laws of certain determined PDE systems.     

The triples of geometric permutations for families of disjoint translates

A line meeting a family of pairwise disjoint convex sets induces two permutations of the sets. This pair of permutations is called a geometric permutation. We characterize the possible triples of geometric permutations for a family of disjoint translates in the plane. Together with earlier studies of geometric permutations this provides a complete characterization of realizable geometric permutations for disjoint translates.     

Perfect difference families,perfect difference matrices,and related combinatorial structures

The existence problems of perfect difference families with block size k, k=4,5, and additive sequences of permutations of length n, n=3,4, are two outstanding open problems in combinatorial design theory for more than 30 years. In this article, we mainly investigate perfect difference families with block size k=4 and additive sequences of permutations of length n=3. The necessary condition for the existence of a perfect difference family with block size 4 and order v, or briefly (v, 4,1)‐PDF, is v≡1(mod12), and that of an additive sequence of permutations of length 3 and order m, or briefly ASP (3, m), is m≡1(mod2). So far, (12t+1,4,1)‐PDFs with t<50 are known only for t=1,4−36,41,46 with two definiteexceptions of t=2,3, and ASP (3, m)'s with odd 3<m<200 are known only for m=5,7,13−29,35,45,49,65,75,85,91,95,105,115,119,121,125,133,135,145,147,161,169,175,189,195 with two definite exceptions of m=9,11. In this article, we show that a (12t+1,4,1)‐PDF exists for any t⩽1,000 except for t=2,3, and an ASP (3, m) exists for any odd 3<m<200 except for m=9,11 and possibly for m=59. The main idea of this article is to use perfect difference families and additive sequences of permutations with “holes”. We first introduce the concepts of an incomplete perfect difference matrix with a regular hole and a perfect difference packing with a regular difference leave, respectively. We show that an additive sequence of permutations is in fact equivalent to a perfect difference matrix, then describe an important recursive construction for perfect difference matrices via perfect difference packings with a regular difference leave. Plenty of perfect difference packings with a desirable difference leave are constructed directly. We also provide a general recursive construction for perfect difference packings, and as its applications, we obtain extensive recursive constructions for perfect difference families, some via incomplete perfect difference matrices with a regular hole. Examples of perfect difference packings directly constructed are used as ingredients in these recursive constructions to produce vast numbers of perfect difference families with block size 4. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 415–449, 2010     

Upper integral and its geometric meaning

The Hahn definition of the integral is recalled, the requirement of measurability of the integrand omitted. Both the upper and lower integrals comply with this definition and so does any measurable function between them. The outer product measure of the hypograph of a nonnegative bounded nonmeasurable function is equal to the upper integral which is equal to one of the Fan integrals. The outer measure of the graph of a bounded nonmeasurable function is equal to the difference between the upper and lower integrals. A norm for not necessarily measurable functions is defined with the upper integral. The linear space with this norm is complete. The convergence in this space implies the convergence in outer measure. The distance as an outer measure of the symmetric difference of two sets gives us a complete metric space of classes of subsets.      

Optimal and perfect difference systems of sets

Difference systems of sets (DSS) were introduced in 1971 by Levenstein for the construction of codes for synchronization, and are closely related to cyclic difference families. In this paper, algebraic constructions of difference systems of sets using functions with optimum nonlinearity are presented. All the difference systems of sets constructed in this paper are perfect and optimal. One conjecture on difference systems of sets is also presented.     

Restricted Symmetric Permutations

Pattern-avoiding involutions, which have received much enumerative attention, are pattern-avoiding permutations which are invariant under the natural action of a certain subgroup of D ₈, the symmetry group of a square. Three other nontrivial subgroups of D ₈ also have invariant permutations under this action. For each of these subgroups, we enumerate the set of permutations which are invariant under the action of the subgroup and which also avoid a given set of forbidden patterns. The sets of forbidden patterns we consider include all subsets of S ₃. For each subgroup we also give a bijection between the invariant permutations and certain symmetric signed permutations. Received September 14, 2006     

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.     

L-fuzzy quantifiers of type determined by fuzzy measures

The aim of this paper is, first, to introduce two new types of fuzzy integrals, namely, -fuzzy integral and →-fuzzy integral. The first integral is based on a fuzzy measure of L-fuzzy sets and the second one on a complementary fuzzy measure of L-fuzzy sets, where L is a complete residuated lattice. Some of their properties and a relation to the fuzzy (Sugeno) integral are investigated. Second, using these integrals, two classes of monadic L-fuzzy quantifiers of type 1 are defined. These L-fuzzy quantifiers can be used for modeling the semantics of natural language quantifiers like “all”, “some”, “many”, “none”, “at most half”, etc. Several semantic properties of these L-fuzzy quantifiers are studied.     

Precomplete Clones on Infinite Sets which are Closed under Conjugation

We show that on an infinite set, there exist no other precomplete clones closed under conjugation except those which contain all permutations. Since on base sets of some infinite cardinalities, in particular on countably infinite ones, the precomplete clones containing the permutations have been determined, this yields a complete list of the precomplete conjugation-closed clones in those cases. In addition, we show that there exist no precomplete submonoids of the full transformation monoid which are closed under conjugation except those which contain the permutations; the monoids of the latter kind are known.     

On a problem of Diophantus for rationals

Let q be a nonzero rational number. We investigate for which q there are infinitely many sets consisting of five nonzero rational numbers such that the product of any two of them plus q is a square of a rational number. We show that there are infinitely many square-free such q and on assuming the Parity Conjecture for the twists of an explicitly given elliptic curve we derive that the density of such q is at least one half. For the proof we consider a related question for polynomials with integral coefficients. We prove that, up to certain admissible transformations, there is precisely one set of non-constant linear polynomials such that the product of any two of them except one combination, plus a given linear polynomial is a perfect square.     

Perturbation Stability of Coherent Riesz Systems under Convolution Operators

We study the orthogonal perturbation of various coherent function systems (Gabor systems, Wilson bases, and wavelets) under convolution operators. This problem is of key relevance in the design of modulation signal sets for digital communication over time-invariant channels. Upper and lower bounds on the orthogonal perturbation are formulated in terms of spectral spread and temporal support of the prototype, and by the approximate design of worst-case convolution kernels. Among the considered bases, the Weyl–Heisenberg structure which generates Gabor systems turns out to be optimal whenever the class of convolution operators satisfies typical practical constraints.     

Internal ellipsoidal estimates of attainability sets for linear systems under conditions of uncertainty

The problem of constructing internal ellipsoidal estimates of the geometric difference between two ellipsoids and applying the estimated results for the attainability sets of linear systems with a disturbance is considered. An addition to the existing method of constructing the difference between two ellipsoids is presented, and the previous constraints are removed. In the process of validating the addition, some relationships between certain properties of constructed ellipsoidal estimations and set convexity are given, being the data for the problem. A method for estimating the attainability sets for linear systems with a disturbance, equivalent to the existing approach to systems without disturbances, are given. The disturbances are considered using the obtained results.     

Computations in differential and difference modules

Constructive methods based on the Gröbner bases theory have been used many times in commutative algebra over the past 20 years, in particular, they allow the computation of such important invariants of manifolds given by systems of algebraic equations as their Hilbert polynomials. In differential and difference algebra, the analogous roles play characteristic sets.In this paper, algorithms for computations in differential and difference modules, which allow for the computation of characteristic sets (Gröbner bases) in differential, difference, and polynomial modules and differential (difference) dimension polynomials, are described. The algorithms are implemented in the algorithmic language REFAL.     

On Idomatic Partitions of Direct Products of Complete Graphs

Independent dominating sets in the direct product of four complete graphs are considered. Possible types of such sets are classified. The sets in which every pair of vertices agree in exactly one coordinate, called T ₁-sets, are explicitly described. It is proved that the direct product of four complete graphs admits an idomatic partition into T ₁-sets if and only if each factor has at least three vertices and the orders of at least two factors are divisible by 3.     

States on systems of sets that are closed under symmetric difference

We consider extensions of certain states. The states are defined on the systems of sets that are closed under the formation of the symmetric difference (concrete quantum logics). These systems can be viewed as certain set‐representable quantum logics enriched with the symmetric difference. We first show how the compactness argument allows us to extend states on Boolean algebras over such systems of sets. We then observe that the extensions are sometimes possible even for non‐Boolean situations. On the other hand, a difference‐closed system can be constructed such that even two‐valued states do not allow for extensions. Finally, we consider these questions in a σ‐complete setup and find a large class of such systems with rather interesting state properties.     

Optimal and perfect difference systems of sets from <Emphasis Type="Italic">q</Emphasis>-ary sequences with difference-balanced property

Difference systems of sets (DSS) are important for the construction of codes for synchronization. In this paper, a general construction of optimal and perfect difference systems of sets based on q-ary sequences of period n = −1 (mod q) with difference- balanced property is presented, where q is a prime power. This works for all the known q-ary sequences with ideal autocorrelation, and generalizes the earlier construction based on ternary sequences with ideal autocorrelation. In addition, we construct another class of optimal and perfect difference systems of sets, employing decimation of q-ary d-form sequences of period q ^m −1 with difference-balanced property, which generalizes the previous construction from power functions.