A study on monotone self-dual Boolean functions

This paper shows that monotone self-dual Boolean functions in irredundant disjuntive normal form (IDNF) do not have more variables than disjuncts. Monotone self-dual Boolean functions in IDNF with the same number of variables and disjuncts are examined. An algorithm is proposed to test whether a monotone Boolean function in IDNF with n variables and n disjuncts is self-dual. The runtime of the algorithm is O(n³).     

Invariant functions of the elements of the powers of a square matrix

A square matrix A is raised to any real power n, negative or fractional values being permitted when Aⁿ can be defined; C is a matrix that commute with A. Linear identities existing between the elements of Aⁿ or C are investigated, in such a way that the number of elements in each identity is minimized in general. Both this number and the method of investigation depend on the Jordan canonical form of A, but if A has a special property, some of these identities and their method of derivation are independent of the Jordan canonical form.     

Hajós' graph-coloring conjecture: Variations and counterexamples

For each integer n ≥ 7, we exhibit graphs of chromatic number n that contain no subdivided K_n as a subgraph. However, we show that a graph with chromatic number 4 contains as a subgraph a subdivided K₄ in which each triangle of the K₄ is subdivided to form an odd cycle.     

Finiteness in restricted simplicial decomposition

Simplicial decomposition is an important form of decomposition for large non-linear programming problems with linear constraints. Von Hohenbalken has shown that if the number of retained extreme points is n + 1, where n is the number of variables in the problem, the method will reach an optimal simplex after a finite number of master problems have been solved (i.e., after a finite number of major cycles). However, on many practical problems it is infeasible to allocate computer memory for n + 1 extreme points. In this paper, we present a version of simplicial decomposition where the number of retained extreme points is restricted to r, 1 ? r ? n + 1, and prove that if r is sufficiently large, an optimal simplex will be reached in a finite number of major cycles. This result insures rapid convergence when r is properly chosen and the decomposition is implemented using a second order method to solve the master problem.     

A note on the sampling distribution of the information content of the priority vector of a consistent pairwise comparison judgment matrix of AHP

The sampling distribution of the information content (entropy) of the priority vector of a consistent pairwise comparison judgment matrix, PCJM(n) using the Analytic Hierarchy Process (AHP) is studied by Noble and Sanchez, where n is the number of criteria associated with the matrix. They concluded simulation experiments with sample size of 1000 and found that the distribution is normal for n=4,5,...,15. When we increased the sample size to 2000, to 3000,..., to 8000, we found that the sampling distribution of entropy is not normal for all n, n=4,5,...,15. By using BestFit software system and using sample sizes of 8000, we found that the best-fitted and the second-best-fitted distributions of the entropy are either Weibull or normal for n?4. If we consider the most number of best fitted distributions as the criteria, then Weibull should be considered as the sampling distribution of the entropy for n?4. For n=3, beta should be considered as the best-fitted distribution.     

On periodic groups of odd period n ≥ 1003

In the paper, using the Adyan-Lysenok theorem claiming that, for any odd number n ≥ 1003, there is an infinite group each of whose proper subgroups is contained in a cyclic subgroup of order n, it is proved that the set of groups with this property has the cardinality of the continuum (for a given n). Further, it is proved that, for m ≥ k ≥ 2 and for any odd n ≥ 1003, the m-generated free n-periodic group is residually both a group of the above type and a k-generated free n-periodic group, and it does not satisfy the ascending and descending chain conditions for normal subgroups either.     

Existence of multiple normal mode trajectories on convex energy surfaces of even,classical Hamiltonian systems

Hamiltonian systems of n degrees of freedom for which the Hamiltonian is a function that is even both in its joint n coordinate variables as well as in its joint n momentum variables are discussed. For such systems the number of distinct trajectories which correspond to particular periodic solutions (normal modes) with the same energy, is investigated. To that end a constrained dual action principle is introduced. Applying min-max methods to this variational problem, several results are obtained, among which the existence of at least n distinct trajectories if specific conditions are satisfied.     

Positive integers expressible as a sum of three squares in essentially only one way

The set S consisting of those positive integers n which are uniquely expressible in the form n = a² + b² + c², $\text{a ≧ b ≧ c ≧ 0}$, is considered. Since n ∈ S if and only if 4n ∈ S, we may restrict attention to those n not divisible by 4. Classical formulas and the theorem that there are only finitely many imaginary quadratic fields with given class number imply that there are only finitely many n ∈ S with n = 0 (mod 4). More specifically, from the existing knowledge of all the imaginary quadratic fields with odd discriminant and class number 1 or 2 it is readily deduced that there are precisely twelve positive integers n such that n ∈ S and n ≡ 3 (mod 8). To determine those n ∈ S such that n ≡ 1, 2, 5, 6 (mod 8) requires the determination of the imaginary quadratic fields with even discriminant and class number 1, 2, or 4. While the latter information is known empirically, it has not been proved that the known list of 33 such fields is complete. If it is complete, then our arguments show that there are exactly 21 positive integers n such that n ∈ S and n ≡ 1, 2, 5, 6 (mod 8).     

Asymptotic normality of the number of small distances between random points in a cube

Draw n random points from a cube, and consider the number of distances smaller than r between those points. When n → ∞, r → 0 simultaneously, and within certain relations to each other, this number is seen to be asymptotically normal.     

2N Noncollinear points determine at least 2N directions

We find sharp bounds for the number of moves required to bring a permutation to the form n(n ?1),…, 1 if a move consists of inverting some increasing substrings.If we invert every maximal increasing substring in each move we need at most n ? 1 moves.If n is even and we start with 1, 2,…, n and we do not invert the entire permutation at once, then we need at least n moves.The lower bound implies that when n ? 4 is even, n points which are not collinear determine at least n different directions, as do n + 1. These bounds are sharp.     

Bilinear and quadratic variants on the Littlewood-Offord problem

If f(x ₁, …, x _n ) is a polynomial dependent on a large number of independent Bernoulli random variables, what can be said about the maximum concentration of f on any single value? For linear polynomials, this reduces to one version of the classical Littlewood-Offord problem: Given nonzero constants a ₁, …,a _n , what is the maximum number of sums of the form ±a ₁ ± a ₂ ± … ± a _n which take on any single value? Here we consider the case where f is either a bilinear form or a quadratic form. For the bilinear case, we show that the only forms having concentration significantly larger than n ^?1 are those which are in a certain sense very close to being degenerate. For the quadratic case, we show that no form having many nonzero coefficients has concentration significantly larger than n ^?1/2. In both cases the results are nearly tight.     

Minimal 2-spheres in a complex projective space

In this paper conformal minimal 2-spheres immersed in a complex projective space are studied by applying Lie theory and moving frames. We give differential equations of Kähler angle and square length of the second fundamental form. By applying these differential equations we give characteristics of conformal minimal 2-spheres of constant Kähler angle and obtain pinching theorems for curvature. We also discuss conformal minimal 2-spheres of constant normal curvature and prove that there does not exist any linearly full minimal 2-sphere immersed in a complex projective space CPn (n>2) with non-positive constant normal curvature. We also prove that a linearly full minimal 2-sphere immersed in a complex projective space CPn (n>2) with constant normal curvature and constant Kähler angle is of constant curvature.     

Asymptotic bounds for the number of convex n-ominoes

Unit squares having their vertices at integer points in the Cartesian plane are called cells. A point set equal to a union of n distinct cells which is connected and has no finite cut set is called an n-omino. Two n-ominoes are considered the same if one is mapped onto the other by some translation of the plane. An n-omino is convex if all cells in a row or column form a connected strip. Letting c(n) denote the number of different convex n-ominoes, we show that the sequence ((c(n))¹ⁿ: n=1,2,…) tends to a limit γ and γ=2.309138….     

On colored set partitions of type B n

Generalizing Reiner’s notion of set partitions of type B _n , we define colored B _n -partitions by coloring the elements in and not in the zero-block respectively. Considering the generating function of colored B _n -partitions, we get the exact formulas for the expectation and variance of the number of non-zero-blocks in a random colored B _n -partition. We find an asymptotic expression of the total number of colored B _n -partitions up to an error of O(n ^?1/2log^7/2 n], and prove that the centralized and normalized number of non-zero-blocks is asymptotic normal over colored B _n -partitions.     

On Congruence of Complex Matrices

For each of a standard set of normal forms for (n × n) complex matrices under the relation of congruence, explicit matrices are exhibited which transform, via congruence, the normal form to its transpose.     

Revisits for transient random walk

For a random walk on the integers define R_n as the number of (distinct) states visited in the first n steps and Z_n as the number of states visited in the first n steps which are never revisited. Here we deal with transient walks. The increments of Z_n form a stationary process and various central limit results and an iterated logarithm result are obtained for Z_n from known results on stationary processes. Furthermore, the limit behaviour of R_n is closely related to that of Z_n; this relationship is elucidated and corresponding limit results for R_n are then read off from those for Z_n.     

Unsolvability of binary forms

A property of a binary unit is obtained which is invariant in all number fields of fixed degree n, n ≥ 3. This property is then used to formulate a necessary condition for the solvability of a binary form.     

On the lattice of matric-extensible radicals

A radical α in the universal class of associative rings is called matric-extensible if α (R _n) = (α (R))_n for any ring R, and natural number n, where R _n denotes the nxn matrix ring with entries from R. We investigate matric-extensibility of the lower radical determined by a simple ring S. This enables us to find necessary and sufficient conditions for the lower radical determined by S to be an atom in the lattice of hereditary matric-extensible radicals. We also show that this lattice has atoms which are not of this form. We then describe all atoms of the lattice, and show that it is atomic.     

Sorting Using Complete Subintervals and the Maximum Number of Runs in a Randomly Evolving Sequence

We study the space requirements of a sorting algorithm where only items that at the end will be adjacent are kept together. This is equivalent to the following combinatorial problem: Consider a string of fixed length n that starts as a string of 0’s, and then evolves by changing each 0 to 1, with the n changes done in random order. What is the maximal number of runs of 1’s? We give asymptotic results for the distribution and mean. It turns out that, as in many problems involving a maximum, the maximum is asymptotically normal, with fluctuations of order n ^1/2, and to the first order well approximated by the number of runs at the instance when the expectation is maximized, in this case when half the elements have changed to 1; there is also a second order term of order n ^1/3. We also treat some variations, including priority queues and sock-sorting. The proofs use methods originally developed for random graphs.     

Embedding and splitting ordinary differential equations in normal form

We introduce an embedding of real or complex n-dimensional space Kⁿ as an algebraic variety V which is determined by the action of a linear one-parameter group. Every analytic vector field on Kⁿ corresponds to some embedded vector field on V. For a symmetric vector field this embedded vector field splits into a reduced system and a direct sum of non-autonomous linear systems. Examples and applications are mostly concerned with Poincaré-Dulac normal forms. Embeddings provide a natural setting for perturbations of symmetric systems, in particular of systems in normal form up to some degree.