The Enumeration of Permutations with a Prescribed Number of “Forbidden” Patterns

We initiate a general approach for the fast enumeration of permutations with a prescribed number of occurrences of “forbidden” patterns that seems to indicate that the enumerating sequence is always P-recursive. We illustrate the method completely in terms of the patterns “abc,” “cab,” and “abcd.”     

On “bent” functions

Let P(x) be a function from GF(2ⁿ) to GF(2). P(x) is called “bent” if all Fourier coefficients of (−1)^P(x) are ±1. The polynomial degree of a bent function P(x) is studied, as are the properties of the Fourier transform of (−1)^P(x), and a connection with Hadamard matrices.     

Some Asymptotic Formulae for Gaussian Distributions

This paper considers asymptotic expansions of certain expectations which appear in the theory of large deviation for Gaussian random vectors with values in a separable real Hilbert space. A typical application is to calculation of the “tails” of distributions of smooth functionals,p(r)=P{Φ(r⁻¹ξ)0},r→∞, e.g., the probability that a centered Gaussian random vector hits the exterior of a large sphere surrounding the origin. The method provides asymptotic formulae for the probability itself and not for its logarithm in a situation, where it is natural to expect thatp(r)=c′r^D exp{−c″r²}. Calculations are based on a combination of the method of characteristic functionals with the Laplace method used to find asymptotics of integrals containing a fast decaying function with “small” support.     

Topological group criterion for in compact-open-like topologies, II

We continue from “part I” our address of the following situation. For a Tychonoff space Y, the “second epi-topology” σ is a certain topology on C(Y), which has arisen from the theory of categorical epimorphisms in a category of lattice-ordered groups. The topology σ is always Hausdorff, and σ interacts with the point-wise addition + on C(Y) as: inversion is a homeomorphism and + is separately continuous. When is + jointly continuous, i.e. σ is a group topology? This is so if Y is Lindelöf and Čech-complete, and the converse generally fails. We show in the present paper: under the Continuum Hypothesis, for Y separable metrizable, if σ is a group topology, then Y is (Lindelöf and) Čech-complete, i.e. Polish. The proof consists in showing that if Y is not Čech-complete, then there is a family of compact sets in βY which is maximal in a certain sense.     

A “Generalized Trace Formula” for Bell numbers

The nth Bell number B_n is the number of ways to partition a set of n elements into nonempty subsets. We generalize the “trace formula” of Barsky and Benzaghou [1], which asserts that for an odd prime p and an appropriate constant τ_p, the relation B_n=-Tr(^n-1-τ_p)B_τp holds in , where is a root of and is the trace form. We deduce some new interesting congruences for the Bell numbers, generalizing miscellaneous well-known results including those of Radoux [4].     

Random creation and dispersion of mass

Consider evolution of density of a mass or a population, geographically situated in a compact region of space, assuming random creation-annihilation and migration, or dispersion of mass, so the evolution is a random measure. When the creation-annihilation and dispersion are diffusions the situation is described formally by a stochastic partial differential equation; ignoring dispersion make approximations to the initial density by atomic measures and if the corresponding discrete random measures converge “in law” to a unique random measure call it a solution. To account for dispersion Trotter's product formula is applied to semiflows corresponding to dispersion and creation-annihilation. Existence of solutions has been a conjecture for several years despite a claim in ([2], J. Multivariate Anal. 5, 1–52). We show that solutions exist and that non-deterministic solutions are “smeared” continuous-state branching diffusions.     

Mathematical foundations of a cultural project or Ramchandra's treatise “through the unsentimentalised light of mathematics”

The nineteenth century witnessed a number of projects of cultural rapprochement between the knowledge traditions of the East and West. This paper discusses the attempt to render elementary calculus amenable to an Indian audience in the indigenous mathematical idiom, undertaken by an Indian polymath, Ramchandra. The exercise is specifically located in his book A Treatise on the Problems of Maxima and Minima. The paper goes on to discuss the “vocation of failure” of the book within the context of encounter and the pedagogy of mathematics.     

Exact Misclassification Probabilities for Plug-In Normal Quadratic Discriminant Functions: II. The Heterogeneous Case

We consider the problem of discriminating between two independent multivariate normal populations, N_p(μ₁, Σ₁) and N_p(μ₂, Σ₂), having distinct mean vectors μ₁ and μ₂ and distinct covariance matrices Σ₁ and Σ₂. The parameters μ₁, μ₂, Σ₁, and Σ₂ are unknown and are estimated by means of independent random training samples from each population. We derive a stochastic representation for the exact distribution of the “plug-in” quadratic discriminant function for classifying a new observation between the two populations. The stochastic representation involves only the classical standard normal, chi-square, and F distributions and is easily implemented for simulation purposes. Using Monte Carlo simulation of the stochastic representation we provide applications to the estimation of misclassification probabilities for the well-known iris data studied by Fisher (Ann. Eugen.7 (1936), 179–188); a data set on corporate financial ratios provided by Johnson and Wichern (Applied Multivariate Statistical Analysis, 4th ed., Prentice–Hall, Englewood Cliffs, NJ, 1998); and a data set analyzed by Reaven and Miller (Diabetologia16 (1979), 17–24) in a classification of diabetic status.     

Best Interpolatory Approximation in Normed Linear Spaces

A theory of best approximation with interpolatory contraints from a finite-dimensional subspaceMof a normed linear spaceXis developed. In particular, to eachxX, best approximations are sought from a subsetM(x) ofMwhichdependson the elementxbeing approximated. It is shown that this “parametric approximation” problem can be essentially reduced to the “usual” one involving a certainfixedsubspaceM₀ofM. More detailed results can be obtained when (1) Xis a Hilbert space, or (2) Mis an “interpolating subspace” ofX(in the sense of [1]).     

Effacement des dérivations et spectres premiers des algèbres quantiques

Given any (commutative) field k and any iterated Ore extension R=k[X₁][X₂;σ₂,δ₂][X_N;σ_N,δ_N] satisfying some suitable assumptions, we construct the so-called “Derivative-Elimination Algorithm.” It consists of a sequence of changes of variables inside the division ring F=Fract(R), starting with the indeterminates (X₁,…,X_N) and terminating with new variables (T₁,…,T_N). These new variables generate some quantum-affine space such that . This algorithm induces a natural embedding which satisfies the following property:

Full-size image

. We study both the derivative-elimination algorithm and natural embedding and use them to produce, for the general case, a (common) proof of the “quantum Gelfand–Kirillov” property for the prime homomorphic images of the following quantum algebras: , (wW), R_q[G] (where G denotes any complex, semi-simple, connected, simply connected Lie group with associated Lie algebra and Weyl group W), quantum matrices algebras, quantum Weyl algebras and quantum Euclidean (respectively symplectic) spaces. Another application will be given in [G. Cauchon, J. Algebra, to appear]: In the general case, the prime spectrum of any quantum matrices algebra satisfies the normal separation property.     

On the limiting Pitman efficiency of some rank tests of independence

The limiting (as the significance level approaches 0) Pitman efficiency of a new “regression-based” rank test of independence to Kendall's tau and Spearman's rho is derived. The result is based on a version of [17], Ann. Statist.4 1003–1011) on coincidence of the limiting Pitman efficiency and the local (as the alternative approaches the hypothesis) approximate Bahadur efficiency. [7], Trans. Amer. Math. Soc.87, 173–186) result is applied to verify the main assumption of Wieand's paper. This approach is shown to be useful in some other situations, also.     

A Generalized φ-Divergence for Asymptotically Multivariate Normal Models

I. Csiszár's (Magyar. Tud. Akad. Mat. Kutató Int. Közl8 (1963), 85–108) -divergence, which was considered independently by M. S. Ali and S. D. Silvey (J. R. Statist. Soc. Ser. B28 (1966), 131–142) gives a goodness-of-fit statistic for multinomial distributed data. We define a generalized φ-divergence that unifies the -divergence approach with that of C. R. Rao and S. K. Mitra (“Generalized Inverse of Matrices and Its Applications,” Wiley, New York, 1971) and derive weak convergence to a χ² distribution under the assumption of asymptotically multivariate normal distributed data vectors. As an example we discuss the application to the frequency count in Markov chains and thereby give a goodness-of-fit test for observations from dependent processes with finite memory.     

Uniqueness of Minimal Projections in Smooth Matrix Spaces

Let X=(M(n, m), ·), where · fulfills Condition 0.3 and W=M(n, 1)+M(1, m). A formula for a minimal projection from X onto W is given in (E. W. Cheney and W. A. Light, 1985, “Approximation Theory in Tensor Product Spaces,” Lecture Notes in Mathematics, Springer-Verlag, Berlin; E. J. Halton and W. A. Light, 1985, Math. Proc. Cambridge Philos. Soc.97, 127–136; and W. A. Light, 1986, Math. Z.191, 633–643). We will show that this projection is the unique minimal projection (see Theorem 2.1).     

On the rate of approximation in the central limit theorem for dependent random variables and random vectors

Large “O” and small “o” approximations of the expected value of a class of smooth functions (f C^r(R)) of the normalized partial sums of dependent random variable by the expectation of the corresponding functions of normal random variables have been established. The same types of approximations are also obtained for dependent random vectors. The technique used is the Lindberg-Levy method generalized by Dvoretzky to dependent random variables.     

The n-width of the unit ball of H

Let E be a compact subset of the open unit disc Δ and let H^q be the Hardy space of analytic functions f on Δ for which stf¦^q has a harmonic majorant. We determine the value of the Kolmogorov, Gel'fand, and linear n-widths in L^p(E, μ) of the restriction to E of the unit ball of H^q when p q or when 1 q < p < ∞ and E is “small”.     

Fast pattern-matching on indeterminate strings

In a string x on an alphabet Σ, a position i is said to be indeterminate iff x[i] may be any one of a specified subset {λ₁,λ₂,…,λ_j} of Σ, 2j|Σ|. A string x containing indeterminate positions is therefore also said to be indeterminate. Indeterminate strings can arise in DNA and amino acid sequences as well as in cryptological applications and the analysis of musical texts. In this paper we describe fast algorithms for finding all occurrences of a pattern p=p[1..m] in a given text x=x[1..n], where either or both of p and x can be indeterminate. Our algorithms are based on the Sunday variant of the Boyer–Moore pattern-matching algorithm, one of the fastest exact pattern-matching algorithms known. The methodology we describe applies more generally to all variants of Boyer–Moore (such as Horspool's, for example) that depend only on calculation of the δ (“rightmost shift”) array: our method therefore assumes that Σ is indexed (essentially, an integer alphabet), a requirement normally satisfied in practice.     

Some results on embeddings of algebras, after de Bruijn and McKenzie

In 1957, N.G. de Bruijn showed that the symmetric group Sym(Ω) on an infinite set Ω contains a free subgroup on 2^card(Ω) generators, and proved a more general statement, a sample consequence of which is that for any group A of cardinality card(Ω), the group Sym(Ω) contains a coproduct of 2^card(Ω) copies of A, not only in the variety of all groups, but in any variety of groups to which A belongs. His key lemma is here generalized to an arbitrary variety of algebras V, and formulated as a statement about functors Set V. From this one easily obtains analogs of the results stated above with “group” and Sym(Ω) replaced by “monoid” and the monoid Self(Ω) of endomaps of Ω, by “associative K-algebra” and the K-algebra End_K (V) of endomorphisms of a K-vector-space V with basis Ω, and by “lattice” and the lattice Equiv(Ω) of equivalence relations on Ω. It is also shown, extending another result from de Bruijn's 1957 paper, that each of Sym(Ω), Self(Ω) and End_K(V) contains a coproduct of 2^card(Ω) copies of itself.That paper also gave an example of a group of cardinality 2^card(Ω) that was not embeddable in Sym(Ω), and R. McKenzie subsequently established a large class of such examples. Those results are shown here to be instances of a general property of the lattice of solution sets in Sym(Ω) of sets of equations with constants in Sym(Ω). Again, similar results - this time of varying strengths - are obtained for Self(Ω), End_K(V), and Equiv(Ω), and also for the monoid Rel(Ω) of binary relations on Ω.Many open questions and areas for further investigation are noted.     

On semidirectly closed pseudovarieties of aperiodic semigroups

The aim of this work is to study the unknown intervals of the lattice of aperiodic pseudovarieties which are semidirectly closed and answer questions proposed by Almeida in his book “Finite Semigroups and Universal Algebra”. The main results state that the intervals [V^*(B₂),ER∩LR] and [V^*(B₂¹),ER∩A] are not trivial, and that both contain a chain isomorphic to the chain of real numbers. These results are a consequence of the study of the semidirectly closed pseudovariety generated by the aperiodic Brandt semigroup B₂.