The parity of the number of quasigroups

Let I(n) be the number of isomorphism classes of quasigroups of order n. Despite prior enumerations showing that I(n) is odd for 1≤n≤11, we find that I(12) is even. We also give a method for finding the parity of I(n), which we use to show that I(n) is odd for n∈{13,14,15,16,17,19,21}.     

On the number of transversals in Cayley tables of cyclic groups

It is well known that if n is even, the addition table for the integers modulo n (which we denote by B_n) possesses no transversals. We show that if n is odd, then the number of transversals in B_n is at least exponential in n. Equivalently, for odd n, the number of diagonally cyclic latin squares of order n, the number of complete mappings or orthomorphisms of the cyclic group of order n, the number of magic juggling sequences of period n and the number of placements of n non-attacking semi-queens on an n×n toroidal chessboard are at least exponential in n. For all large n we show that there is a latin square of order n with at least (3.246)ⁿ transversals.We diagnose all possible sizes for the intersection of two transversals in B_n and use this result to complete the spectrum of possible sizes of homogeneous latin bitrades.We also briefly explore potential applications of our results in constructing random mutually orthogonal latin squares.     

On the complexity of calculating factorials

It is shown that n! can be evaluated with time complexity O(log log nM (n log n)), where M(n) is the complexity of multiplying two n-digit numbers together. This is effected, in part, by writing n! in terms of its prime factors. In conjunction with a fast multiplication this yields an O(n(log n log log n)²) complexity algorithm for n!. This might be compared to computing n! by multiplying 1 times 2 times 3, etc., which is ω(n² log n) and also to computing n! by binary splitting which is O(log nM(n log n)).     

Structure of cubic mapping graphs for the ring of Gaussian integers modulo n

Let ? _n [i] be the ring of Gaussian integers modulo n. We construct for ?n[i] a cubic mapping graph Γ(n) whose vertex set is all the elements of ?n[i] and for which there is a directed edge from a ∈ ?n[i] to b ∈ ?n[i] if b = a ³. This article investigates in detail the structure of Γ(n). We give suffcient and necessary conditions for the existence of cycles with length t. The number of t-cycles in Γ₁(n) is obtained and we also examine when a vertex lies on a t-cycle of Γ₂(n), where Γ₁(n) is induced by all the units of ?n[i] while Γ₂(n) is induced by all the zero-divisors of ?n[i]. In addition, formulas on the heights of components and vertices in Γ(n) are presented.     

On the maximum of Stirling numbers of the second kind

A technique is illustrated for finding an estimate of the Stirling numbers of the second kind, S_{n, r}(1 ? r ? n), as n → ∞, for a certain range of values of r. It is shown how the estimation can be found to any given degree of approximation. Finally, the location of the maximum of S_{n, r} (1 ? r ? n) and the value of the maximum are computed.     

On the spectrum of n quasigroups with given conjugate invariant subgroup

Let tⁿ be a vector of n positive integers that sum to 2n ? 1. Let u denote a vector of n or more positive integers that sum to n², and call u, n-universal if for every possible choice of t¹, t²,…, tⁿ, the components of the tⁱ can be arranged in the successive rows of an n-row matrix (with 0 in each unused cell) so that u is the vector of column sums.It is shown that (n,…, n)_{(n times)} is n-universal for every n. More generally, for odd n, any choice of t¹, t³,…, tⁿ can be placed in rows so that the column sums are (n, n?1,…, 2, 1); for even n, any choice of t², t⁴,…, tⁿ can be placed in rows so that the column sums are (n, n ?1,…, 2, 1). Hence, any u that can be obtained from the sum of two rows whose nonzero components are, respectively, n, n ?1,…, 2, 1 and n ?1, n ?2,…, 2, 1 (in any order, with 0's elsewhere) is n-universal.The problem examined is closely related to the graph conjecture that trees on 2, 3,…, n + 1 vertices can be superposed to yield the complete graph on n + 1 vertices.     

On the number of A-mappings

Suppose that $ \mathfrak{S} $ _n is the semigroup of mappings of the set of n elements into itself, A is a fixed subset of the set of natural numbers ?, and V _n (A) is the set of mappings from $ \mathfrak{S} $ _n whose contours are of sizes belonging to A. Mappings from V _n (A) are usually called A-mappings. Consider a random mapping σ _n , uniformly distributed on V n(A). Suppose that ν _n is the number of components and λ _n is the number of cyclic points of the random mapping σ _n . In this paper, for a particular class of sets A, we obtain the asymptotics of the number of elements of the set V _n (A) and prove limit theorems for the random variables ν _n and λ _n as n → ∞.     

On the focus order of planar polynomial differential equations

This paper is devoted to finding the highest possible focus order of planar polynomial differential equations. The results consist of two parts: (i) we explicitly construct a class of concrete systems of degree n, where n+1 is a prime p or a power of a prime pk, and show that these systems can have a focus order n²−n; (ii) we theoretically prove the existence of polynomial systems of degree n having a focus order n²−1 for any even number n. Corresponding results for odd n and more concrete examples having higher focus orders are given too.     

Partitions weighted by the parity of the crank

The ‘crank’ is a partition statistic which originally arose to give combinatorial interpretations for Ramanujan's famous partition congruences. In this paper, we establish an asymptotic formula and a family of Ramanujan type congruences satisfied by the number of partitions of n with even crank Me(n) minus the number of partitions of n with odd crank Mo(n). We also discuss the combinatorial implications of q-series identities involving Me(n)−Mo(n). Finally, we determine the exact values of Me(n)−Mo(n) in the case of partitions into distinct parts. These values are at most two, and zero for infinitely many n.     

Note on the size of binary Armstrong codes

We show for binary Armstrong codes Arm(2, k, n) that asymptotically n/k ≤ 1.224, while such a code is shown to exist whenever n/k ≤ 1.12. We also construct an Arm(2, n ? 2, n) and Arm(2, n ? 3, n) for all admissible n.     

On the Chatyrko-Hattori solution of de Groot's question

Let Zn=(n[0,1]×(0,1])∪(∂(n[0,1])×{0}). De Groot asked: Is cmpZn?n for every n? It is known that the answer is yes for n=1 and 2. V.A. Chatyrko and Y. Hattori [Fund. Math. 172 (2002) 107-115] showed that the answer is no for n?5. It is shown that the answer is also no for n=4. The question is unresolved for n=3.     

An Almost Accurate Location of the Maximum Stirling Number(s) of the Second Kind

The Stirling number of the second kind S(n, k) is the number of ways of partitioning a set of n elements into k nonempty subsets. It is well known that the numbers S(n, k) are unimodal in k, and there are at most two consecutive values K _n such that (for fixed n) S(n, K _n ) is maximal. We determine asymptotic bounds for K _n , which are unexpectedly good and improve earlier results. The method used here shows a possible strategy for obtaining numerical bounds such that in almost all cases K _n can be uniquely determined.     

On the resolvent of the Laplacian on functions for degenerating surfaces of finite geometry

We consider families (Yn) of degenerating hyperbolic surfaces. The surfaces are geometrically finite of fixed topological type. Let Zn be the Selberg Zeta function of Yn, and let zn be the contribution of the pinched geodesics to Zn. Extending a result of Wolpert's, we prove that Zn(s)/zn(s) converges to the Zeta function of the limit surface if Re(s)>1/2. The technique is an examination of resolvent of the Laplacian, which is composed from that for elementary surfaces via meromorphic Fredholm theory. The resolvent ⁻¹(Δn−t) is shown to converge for all t∉[1/4,∞). We also use this property to define approximate Eisenstein functions and scattering matrices.     

On some algorithmic problems regarding the hairpin completion

We consider a few algorithmic problems regarding the hairpin completion. The first problem we consider is the membership problem of the hairpin and iterated hairpin completion of a language. We propose an O(nf(n)) and O(n²f(n)) time recognition algorithm for the hairpin completion and iterated hairpin completion, respectively, of a language recognizable in O(f(n)) time. We show that the n factor is not needed in the case of hairpin completion of regular and context-free languages. The n² factor is not needed in the case of iterated hairpin completion of context-free languages, but it is reduced to n in the case of iterated hairpin completion of regular languages. We then define the hairpin completion distance between two words and present a cubic time algorithm for computing this distance. A linear time algorithm for deciding whether or not the hairpin completion distance with respect to a given word is connected is also discussed. Finally, we give a short list of open problems which appear attractive to us.     

Characterization of the types of maximum noninteger vertices in the relaxation polyhedron of the four-index axial assignment problem

For the relaxation polyhedron M(4, n) in the four-index axial assignment problem of order n, n ≥ 3, a characterization of all possible types (except for a single case) of maximum noninteger vertices, i.e., vertices with 4n — 3 fractional components is proposed. A formula enumerating all the maximum noninteger vertices of the same type in M(4, n) is derived.     

The limiting spectral distribution of the product of the Wigner matrix and a nonnegative definite matrix

Let W_n be n×n Hermitian whose entries on and above the diagonal are independent complex random variables satisfying the Lindeberg type condition. Let T_n be n×n nonnegative definitive and be independent of W_n. Assume that almost surely, as n→∞, the empirical distribution of the eigenvalues of T_n converges weakly to a non-random probability distribution.Let . Then with the aid of the Stieltjes transforms, we show that almost surely, as n→∞, the empirical distribution of the eigenvalues of A_n also converges weakly to a non-random probability distribution, a system of two equations determining the Stieltjes transform of the limiting distribution. Important analytic properties of this limiting spectral distribution are then derived by means of those equations. It is shown that the limiting spectral distribution is continuously differentiable everywhere on the real line except only at the origin and that a necessary and sufficient condition is available for determining its support. At the end, the density function of the limiting spectral distribution is calculated for two important cases of T_n, when T_n is a sample covariance matrix and when T_n is the inverse of a sample covariance matrix.     

Determination of the element numbers of the regular polytopes

Let ?? be a set of n-dimensional polytopes. A set ?? of n-dimensional polytopes is said to be an element set for ?? if each polytope in ?? is the union of a finite number of polytopes in ?? identified along (n ? 1)-dimensional faces. The element number of the set ?? of polyhedra, denoted by e(??), is the minimum cardinality of the element sets for ??, where the minimum is taken over all possible element sets ${\Omega \in \mathcal{E}(\Sigma)}$ . It is proved in Theorem 1 that the element number of the convex regular 4-dimensional polytopes is 4, and in Theorem 2 that the element numbers of the convex regular n-dimensional polytopes is 3 for n ?? 5. The results in this paper together with our previous papers determine completely the element numbers of the convex regular n-dimensional polytopes for all n ?? 2.     

On the complement of the set of n-collinear points in PG(3, n)

Let ${S = (\mathcal{P}, \mathcal{L}, \mathcal{H})}$ be the finite planar space obtained from the 3-dimensional projective space PG(3, n) of order n by deleting a set of n-collinear points. Then, for every point ${p\in S}$ , the quotient geometry S/p is either a projective plane or a punctured projective plane, and every line of S has size n or n + 1. In this paper, we prove that a finite planar space with lines of size n + 1 ? s and n + 1, (s ≥ 1), and such that for every point ${p\in S}$ , the quotient geometry S/p is either a projective plane of order n or a punctured projective plane of order n, is obtained from PG(3, n) by deleting either a point, or a line or a set of n-collinear points.     

Computing the stationary distribution for infinite Markov chains

In a situation where the unique stationary distribution vector of an infinite irreducible positive-recurrent stochastic matrix P is not analytically determinable, numerical approximations are needed. This paper partially synthesizes and extends work on finite-vector approximative solutions obtained from nxn northwest corner truncations _(n)P of P, from the standpoints of (pointwise convergence) algorithms as n→∞, and the manner of their computer implementation with a view to numerical stability and conditioning. The problem for finite n is connected with that of finding the unique stationary distribution of the finite stochastic matrix _(n)P? obtained from _(n)P by augmenting a column.