Polynomial growth rates

We consider linear equations v^′=A(t)v with a polynomial asymptotic behavior, that can be stable, unstable and central. We show that this behavior is exhibited by a large class of differential equations, by giving necessary and sufficient conditions in terms of generalized “polynomial” Lyapunov exponents for the existence of polynomial behavior. In particular, any linear equation in block form in a finite-dimensional space, with three blocks having “polynomial” Lyapunov exponents respectively negative, positive, and zero, has a nonuniform version of polynomial trichotomy, which corresponds to the usual notion of trichotomy but now with polynomial growth rates. We also obtain sharp bounds for the constants in the notion of polynomial trichotomy. In addition, we establish the persistence under sufficiently small nonlinear perturbations of the stability of a nonuniform polynomial contraction.     

A new approach to Euler splines

Starting from the exponential Euler polynomials discussed by Euler in “Institutions Calculi Differentialis,” Vol. II, 1755, the author introduced in “Linear operators and approximation,” Vol. 20, 1972, the so-called exponential Euler splines. Here we describe a new approach to these splines. Let t be a constant such that t=|t|e^iα, −π<α<π,t≠0,t≠1.. Let S₁(x:t) be the cardinal linear spline such that S₁(v:t) = t^v for all v ε Z. Starting from S₁(x:t) it is shown that we obtain all higher degree exponential Euler splines recursively by the averaging operation . Here S_n(x:t) is a cardinal spline of degree n if n is odd, while is a cardinal spline if n is even. It is shown that they have the properties S_n(v:t) = t^v for v ε Z.     

Representation of a class of locally convex (M)-lattices

We prove a representation theorem for Hausdorff locally convex (M)-lattices which are Dedekind σ-complete, and whose topologies are order σ-continuous and monotonically complete. These turn out to be the weighted spaces c₀(T, H), defined in the paper for T ≠ and H ^T₊. We also characterize the dual of c₀(T, H), as the space l¹ (T, H) defined in the last section. The known representation (on c₀(T)) of Banach (M)-lattices with order continuous norm follows as a particular case. We obtain these results by first proving a new general isomorphism theorem, which seems to be of independent interest. Our notion of “monotonic topological completeness” is weaker than the usual completeness and seems to be very convenient in the framework of topological ordered vector spaces.     

Generalized Gaussian quadrature formulas

Existence and uniqueness of canonical points for best L₁-approximation from an Extended Tchebycheff (ET) system, by Hermite interpolating “polynomials” with free nodes of preassigned multiplicities, are proved. The canonical points are shown to coincide with the nodes of a “generalized Gaussian quadrature formula” of the form (*) which is exact for the ET-system. In (*), ∑_{j = 0}^{v_i − 2} ≡ 0 if v_i = 1, the v_i (> 0), I = 1,…, n, are the multiplicities of the free nodes and v₀0, v_{n + 1} 0 of the boundary points in the L₁-approximation problem, ∑_{i = 0}^{n + 1} v_i is the dimension of the ET-system, and σ is the weight in the L₁-norm.The results generalize results on multiple node Gaussian quadrature formulas (v₁,…, v_n all even in (*)) and their relation to best one-sided L₁-approximation. They also generalize results on the orthogonal signature of a Tchebycheff system (v₀ = v_{n + 1} = 0, v_i = 1, I = 1,…, n, in (*)), and its role in best L₁-approximation. Recent works of the authors were the first to treat Gaussian quadrature formulas and orthogonal signatures in a unified way.     

Newton's solution to the equiangular spiral problem and a new solution using only the equiangular property

This paper is a study of Proposition IX of Book I of Newton's Principia, the problem of determining the centripetal force for an equiangular spiral. In Newton's main proof of this proposition there is an error concerning his reason for the figure SPRQT being “given in kind,” and a very interesting technique of varying things in the neighborhood of a limit. This main proof utilized Newton's formula for the limit of SP²QT²/QR given in Corollary I to Proposition VI of the Principia. Newton also gave an alternate proof which utilized his formula for SY²PV given in Corollary III to Proposition VI. The “given” of Proposition IX was “a spiral PQS, cutting all the radii SP, SQ, &c., in a given angle.” Both the main proof and the alternate proof implicitly depend on the property of the equiangular spiral that the radius of curvature at any point is proportional to the pole distance SP. We here offer a new proof of Newton's proposition which does not depend on this implicit assumption.     

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.     

G-Loops and Permutation Groups

A G-loop is a loop which is isomorphic to all its loop isotopes. We apply some theorems about permutation groups to get information about G-loops. In particular, we study G-loops of order pq, where p < q are primes and p  (q − 1). In the case p = 3, the only G-loop of order 3q is the group of order 3q. The notion “G-loop” splits naturally into “left G-loop” plus “right G-loop.” There exist non-group right G-loops and left G-loops of order n iff n is composite and n > 5.     

Māl, enunciations, and the prehistory of Arabic algebra

Medieval Arabic algebra books intended for practical training generally have in common a first “book” which is divided into two sections: one on the methods of solving simplified equations and manipulating expressions, followed by one consisting of worked-out problems. By paying close attention to the wording of the problems in the books of al-Khwārizmī, Abū Kāmil, and Ibn Badr, we reveal the different ways the word māl was used. In the enunciation of a problem it is a common noun meaning “quantity,” while in the solution it is the proper noun naming the square of “thing” (shay '). We then look into the differences between the wording of enunciations and equations, which clarify certain problems solved without “thing,” and help explain the development of algebra before the time of al-Khwārizmī.     

Orlicz capacities and Hausdorff measures on metric spaces

In the setting of doubling metric measure spaces with a 1-Poincaré inequality, we show that sets of Orlicz Φ-capacity zero have generalized Hausdorff h-measure zero provided thatwhere Θ⁻¹ is the inverse of the function Θ(t)=Φ(t)/t, and s is the “upper dimension” of the metric measure space. This condition is a generalization of a well known condition in Rⁿ. For spaces satisfying the weaker q-Poincaré inequality, we obtain a similar but slightly more restrictive condition. Several examples are also provided.     

Indivisible plexes in latin squares

In this paper, we present two constructions of divisible difference sets based on skew Hadamard difference sets. A special class of Hadamard difference sets, which can be derived from a skew Hadamard difference set and a Paley type regular partial difference set respectively in two groups of orders v ₁ and v ₂ with |v ₁ − v ₂| = 2, is contained in these constructions. Some result on inequivalence of skew Hadamard difference sets is also given in the paper. As a consequence of Delsarte’s theorem, the dual set of skew Hadamard difference set is also a skew Hadamard difference set in an abelian group. We show that there are seven pairwisely inequivalent skew Hadamard difference sets in the elementary abelian group of order 3⁵ or 3⁷, and also at least four pairwisely inequivalent skew Hadamard difference sets in the elementary abelian group of order 3⁹. Furthermore, the skew Hadamard difference sets deduced by Ree-Tits slice symplectic spreads are the dual sets of each other when q ≤ 3¹¹.      

A general framework of compactly supported splines and wavelets

Let {V_k} be a nested sequence of closed subspaces that constitute a multiresolution analysis of L²( ). We characterize the family Φ = {φ} where each φ generates this multiresolution analysis such that the two-scale relation of φ is governed by a finite sequence. In particular, we identify the ε Φ that has minimum support. We also characterize the collection Ψ of functions η such that each η generates the orthogonal complementary subspaces W_k of V_k, . In particular, the minimally supported ψ ε Ψ is determined. Hence, the “B-spline” and “B-wavelet” pair (, ψ) provides the most economical and computational efficient “spline” representations and “wavelet” decompositions of L² functions from the “spline” spaces V_k and “wavelet” spaces W_k, k . A very general duality principle, which yields the dual bases of both {(·−j):j and {η(·−j):j } for any η ε Ψ by essentially interchanging the pair of two-scale sequences with the pair of decomposition sequences, is also established. For many filtering applications, it is very important to select a multiresolution for which both and ψ have linear phases. Hence, “non-symmetric” and ψ, such as the compactly supported orthogonal ones introduced by Daubechies, are sometimes undesirable for these applications. Conditions on linear-phase φ and ψ are established in this paper. In particular, even-order polynomial B-splines and B-wavelets φ_m and ψ_m have linear phases, but the odd-order B-wavelet only has generalized linear phases.     

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

An analytic approximation to the cardinal functions of Gaussian radial basis functions on an infinite lattice

Gaussian radial basis functions (RBFs) have been very useful in computer graphics and for numerical solutions of partial differential equations where these RBFs are defined, on a grid with uniform spacing h, as translates of the “master” function (x;α,h)≡exp(-[α²/h²]x²) where α is a user-choosable constant. Unfortunately, computing the coefficients of (x-jh;α,h) requires solving a linear system with a dense matrix. It would be much more efficient to rearrange the basis functions into the equivalent “Lagrangian” or “cardinal” basis because the interpolation matrix in the new basis is the identity matrix; the cardinal basis C_j(x;α,h) is defined by the set of linear combinations of the Gaussians such that C_j(kh)=1 when k=j and C_j(kh)=0 for all integers . We show that the cardinal functions for the uniform grid are C_j(x;h,α)=C(x/h-j;α) where C(X;α)≈(α²/π)sin(πX)/sinh(α²X). The relative error is only about 4exp(-2π²/α²) as demonstrated by the explicit second order approximation. It has long been known that the error in a series of Gaussian RBFs does not converge to zero for fixed α as h→0, but only to an “error saturation” proportional to exp(-π²/α²). Because the error in our approximation to the master cardinal function C(X;α) is the square of the error saturation, there is no penalty for using our new approximations to obtain matrix-free interpolating RBF approximations to an arbitrary function f(x). The master cardinal function on a uniform grid in d dimensions is just the direct product of the one-dimensional cardinal functions. Thus in two dimensions . We show that the matrix-free interpolation can be extended to non-uniform grids by a smooth change of coordinates.     

On separating a fixed point from zero by invariants

Assume a fixed point v∈V^G can be separated from zero by a homogeneous invariant f∈𝕜[V]^G of degree p^rd, where p>0 is the characteristic of the ground field 𝕜 and p,d are coprime. We show that then v can also be separated from zero by an invariant of degree p^r, which we obtain explicitly from f. It follows that the minimal degree of a homogeneous invariant separating v from zero is a p-power.     

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.     

On Large Sets of v−1 L-Intersecting Steiner Triple Systems of Order v

This paper presents four new recursive constructions for large sets of v–1 STS(v). These facilitate the production of several new infinite families of such large sets. In particular, we obtain for each n2 a large set of 3 ⁿ –1 STS (3 ⁿ ) whose systems intersect in 0 or 3 blocks.     

Spreading Rumors Rapidly Despite an Adversary

In thecollect problem(M. Saks, N. Shavit, and H. Woll,in“Proceedings of the 2nd ACM–SIAM Symposium on Discrete Algorithms, 1991),nprocessors in a shared-memory system must each learn the values ofnregisters. We give a randomized algorithm that solves the collect problem inO(n log³ n) total read and write operations with high probability, even if timing is under the control of a content-oblivious adversary (a slight weakening of the usual adaptive adversary). This improves on both the trivial upper bound ofO(n²) steps and the best previously known bound ofO(n^3/2 log n) steps, and is close to the lower bound of Ω(n log n) steps. Furthermore, we show how this algorithm can be used to obtain a multiuse cooperative collect protocol that isO(log³ n)-competitive in the latency model of Ajtaiet al.(“Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science,” 1994); andO(n^1/2 log^3/2 n)-competitive in the throughput model of Aspnes and Waarts (“Proceedings of the 28th ACM Symposium on Theory of Computing,” 1996). In both cases the competitive ratios are within a polylogarithmic factor of optimal.     

Notes on subtlety and ineffability in P κ λ

A type of subtlety for P_κλ called “strongly subtle” is introduced to show almost ineffability is consistencywise stronger than Shelah property. The following are also shown: is strongly subtle” has rather strong consequences. (ii) The ideal is not strongly subtle} is not λ-saturated , and completely ineffable ideal is not precipitous. (iii) In case that λ^<κ=2^λ, almost λ-ineffability coincides with λ-ineffability. (iv) It is not provable that κ is λ^<κ-ineffable whenever κ is λ-ineffable.Research partially supported by “Grant-in-Aid for Scientific research (C), The Ministry of Education, Science, Sports and Culture of Japan 09640299”, and “Japan Society for the Promotion of Science 14540142”.The author is very grateful to the referee for his correcting many errors and helpful suggestions.     

Existence of nonstationary bubbles in higher dimensions

We are interested in the existence of travelling-waves for the nonlinear Schrödinger equation in R^N with “ψ³−ψ⁵”-type nonlinearity. First, we prove an abstract result in critical point theory (a local variant of the classical saddle-point theorem). Using this result, we get the existence of travelling-waves moving with sufficiently small velocity in space dimension N4.