On TDP permutations

A permutation :i| _i , 0i<n is called a TDP permutation ifi–a _i j–a _j (modn) fori j. This paper finds all TDP permutations forn15, discusses the method for generating TDP permutations, and finally by applying MLE method obtains a formula for estimating the number of TDP permutations forn> 15.Project supported by National Natural Science Foundation of China.     

A compactness property of Dedekind σ-completef-rings

We prove that Dedekind -completef-rings are boundedly countably atomic compact in the language (+, –, ·,, , ). This means that whenever is a countable set of atomic formulae with parameters from some Dedekind -completef-ringA every finite subsystem of which admits a solution in some fixed productK of bounded closed intervals ofA, then admits a solution inK.Presented by M. Henriksen.     

On distance-regular graphs withk i =k j,II

Let be a distance-regular graph of diameterd andi-th valencyk _i. We show that ifk ₂ = k_j for 2 +j d and 2 <j, then is a polygon (k = 2) or an antipodal 2-cover (k _d = 1). We also give a short proof of Terwilliger's inequality for bipartite distance-regular graphs and a refinement of Ivanov's argument on diameter bound.     

Finite Representability of ℓp in Quotients of Banach Spaces

A typical result of the paper states that if X is a Banach space with a basis and for some 1pq, the spaces _p and _q are finitely block representable in every block subspace of X, then every block subspace of X admits a block quotient Z such that for every r[p,q], the space _r is finitely block representable in Z. Results of a similar nature are also established for ^N _p-block-sequences and asymptotic spaces.     

An Extension of the Roots Separation Theorem

Let T _n be an n×n unreduced symmetric tridiagonal matrix with eigenvalues ₁<₂<< _n and W _k is an (n–1)×(n–1) submatrix by deleting the kth row and the kth column from T _n , k=1,2,...,n. Let _{12 n–1} be the eigenvalues of W _k . It is proved that if W _k has no multiple eigenvalue, then ₁<₁<₂<₂<< _n–1< _n–1< _n ; otherwise if _i = _i+1 is a multiple eigenvalue of W _k , then the above relationship still holds except that the inequality _i < _i+1< _i+1 is replaced by _i = _i+1= _i+1.     

Tensor Banach algebras of projective type. I

We construct a tensor Banach functorT that establishes a correspondence between every projectively admissible Banach spaceE over a complete normed fieldK with a tensor Banach algebra of projective typeT .All-Union Scientific-Research Center for the Study of Surfaces and the Vacuum. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 91, No. 1, pp. 17–29, April, 1992.     

On the Similarity of Analytic Matrix Functions

Consider a domain , and two analytic matrix-valued functions functions . Consider also points and positive integers n ₁, n ₂, . . . , n _N . We are interested in the existence of an analytic function such that X(ω) is invertible, and G(ω) coincides with X(ω)F(ω)X(ω)⁻¹ up to order n _j at the point ω _j . We will see that such a function exists provided that F(ω _j ),G(ω _j ) have cyclic vectors, and the characteristic polynomials of F,G coincide up to order n _j at ω _j . This allows one to give a short proof to a result of Huang, Marcantognini and Young concerning spectral interpolation in the unit disk. The author was partially supported by a grant from the National Science Foundation. Received: September 8, 2006. Accepted: January 11, 2007.     

Interacting Brownian particles and the Wigner law

Summary In this paper, we study interacting diffusing particles governed by the stochastic differential equationsdX _j (t)= _n dB _j (t) –D _jØ_n(X ₁,...,X _n)dt,j=1, 2,...,n. Here theB _jare independent Brownian motions in ^d , and Ø _n (X ₁,...,X _n)= _{n ij} V(X _iX _j) + _ni U(X ₁). The potentialV has a singularity at 0 strong enough to keep the particles apart, and the potentialU serves to keep the particles from escaping to infinity. Our interest is in the behaviour as the number of particles increases without limit, which we study through the empirical measure process. We prove tightness of these processes in the case ofd=1,V(x)=–log|x|,U(x)=x ²/2 where it is possible to prove uniqueness of the limiting evolution and deduce that a limiting measure-valued process exists. This process is deterministic, and converges to the Wigner law ast. Some information on the rates of convergence is derived, and the case of a Cauchy initial distribution is analysed completely.Supported by SERC grant number GR/H 00444     

Estimation of a K-Functional of Higher Order in Terms of a K-Functional of Lower Order

Let U _j be a finite system of functionals of the form , and let be the subspace of the Sobolev space , 1 p +, that consists only of functions g such that U _j(g) = 0 for k _j < r. It is assumed that there exists at least one jump _j for every function _j , and if _j = _s for j s, then k _j k _s. For the K-functional

Monotone subsequences in (0, 1)-matrices

A (0, 1)-matrix contains anS ₀(k) if it has 0-cells (i, j ₁), (i + 1,j ₂),..., (i + k – 1,j _k) for somei andj ₁ < ... < j_k, and it contains anS ₁(k) if it has 1-cells (i ₁,j), (i ₂,j + 1),...,(i _k ,j + k – 1) for somej andi ₁ < ... <i _k . We prove that ifM is anm × n rectangular (0, 1)-matrix with 1 m n whose largestk for anS ₀(k) isk ₀ m, thenM must have anS ₁(k) withk m/(k ₀ + 1). Similarly, ifM is anm × m lower-triangular matrix whose largestk for anS ₀(k) (in the cells on or below the main diagonal) isk ₀ m, thenM has anS ₁(k) withk m/(k ₀ + 1). Moreover, these results are best-possible.     

Finding the αn-th largest element

We describe an algorithm for selecting the n-th largest element (where 0<<1), from a totally ordered set ofn elements, using at most (1+(1+o(1))H())·n comparisons whereH() is the binary entropy function and theo(1) stands for a function that tends to 0 as tends to 0. For small values of this is almost the best possible as there is a lower bound of about (1+H())·n comparisons. The algorithm obtained beats the global 3n upper bound of Schönhage, Paterson and Pippenger for <1/3.     

Vector—valued fractal interpolation functions and their box dimension

Summary We introduce continuous functions f: 1 $$ " align="middle" border="0"> , whose graphs are the attractors of certain iterated function systems, and which interpolate a given set of data or interpolation points ={(t _j ,x _j ):j = 0, 1, , M; M >1} according tof(t _j ) =x _j . The box dimension of the graph of these functions is in general non-integral. We present a formula for this dimension. Applications to the approximation of complicated self-affine functions are indicated.     

Algebraic surfaces with an infinite set of planes of oblique symmetry. II

Suppose that G is an infinite group generated by obliquereflections with respect to hyperplanes in the real spaceE ^m and that theµ _j-planes II^µj = II^dj II^j (j = G(u) -orbits of directions of symmetryu (hyperplanes of symmetry conjugate to vectors II^dj pass through _j-planesII ^j). A complete solution of the problem of the mutual position of three II^j is given. Systems of generatrices of the rings of invariants of a series of groups G are found.Translated from Ukrainskii Geometricheskii Sbornik, No. 34, pp. 42–51, 1991.     

Tauberian Theorems for Weighted Means of Double Sequences

Let p := {p _j } _j=0 and q := {q _k } _k–0 be complex (or real) sequences with the property that P _m := _j–0 ^m p _j 0 for all m 0, Q _n := _k–0 ⁿ q _k 0 for all n 0, and both of {P _m } _m=0 and {Q _n } _n=0 are varying away from 1. Assume that {s _mn } is a double sequence in C(or one of R, a Banach space, and an ordered linear space), which is (N¯,p,q; ,) summable to a finite limit, where (,) =(1,1), (1,0), or (0,1). We give necessary and sufficient conditions under which {s _mn } converges in Pringsheim's sense. These conditions are weaker than the two-dimensional analogues of Landau's condition and Schmidt's slow decrease condition. Our results generalize and extend [1 4, 12 15]. We also solve the problems posed in [3, 13, 14].     

Invariant Subspaces for Banach Space Operators with a Multiply Connected Spectrum

We consider a multiply connected domain where denotes the unit disk and denotes the closed disk centered at with radius r _j for j = 1, . . . , n. We show that if T is a bounded linear operator on a Banach space X whose spectrum contains ∂Ω and does not contain the points λ₁, λ₂, . . . , λ _n , and the operators T and r _j (T − λ _j I)⁻¹ are polynomially bounded, then there exists a nontrivial common invariant subspace for T ^* and (T − λ _j I)^*-1.     

An indexed set of density bounds on lattice packings

It has long been known that the admissibility of a lattice with respect to a symmetric convex bodyB is equivalent to being a packing lattice for 1/2B. This fact is the basis of the interplay between the classical theory of the arithmetic minima of positive definite quadratic forms, on the one hand, and the dense lattice packing of spheres inR ⁿ , on the other.We give an indexed set of bounds _L (B) a _j , where 0 j n/2, on the lattice packing density ofB. The casej=0 reduces to the aforementioned long-known fact, andj=1 was proved by Elkies, Odlyzko, and Rush, and was used to obtain record high packing densities for various superballs. The new cases make possible the use of smaller primes in the construction of these dense packings.Supported by National Science Foundation grant DMS-9103233.     

MP-algebras with relative types

In this paper we define anMP-algebra with relative types (B, s, t ₁ t ₂,t ₃) where (B,s) is a monadic algebra and wheret ₁,t ₂,t ₃ arerelative types fromB to itself satisfying:t ₁ (ps(q))=t _i (p)s(q),s(t _i (p))=t _i (p),s(p)t ₁ (p)t ₂ (p)t ₃ (p), ifi j thent _i (p)t _j (p)=0, ifp q) thent ₃ (p) =t ₃ (q) andt ₂(p) t₃ (p) t ₂ (q) t ₃ (q), ifp q =0 thent _i ,(p) t _j (q) t _k (pq) withk=min(i + j, 3). Every relation algebra has anMP-algebra with relative types associated with it. We prove by Givant's results that everyMP-algebra with relative types arises in this way from some relation algebra generated by its rectangles.Presented by B. Jónsson.     

On the 0, 1 facets of the set covering polytope

In this paper, we consider inequalities of the form _jx_j , where _j equals 0 or 1, and is a positive integer. We give necessary and sufficient conditions for such inequalities to define facets of the set covering polytope associated with a 0, 1 constraint matrixA. These conditions are in terms of critical edges and critical cutsets defined in the bipartite incidence graph ofA, and are in the spirit of the work of Balas and Zemel on the set packing problem where similar notions were defined in the intersection graph ofA. Furthermore, we give a polynomial characterization of a class of 0, 1 facets defined from chorded cycles of the bipartite incidence graph. This characterization also yields all the 0, 1 liftings of odd-hole inequalities for the simple plant location polytope.Research partially supported by NSF grant ECS-8601660 and AFORS grant 87-0292.     

Regular Resolution Lower Bounds For The Weak Pigeonhole Principle

We prove that any regular resolution proof for the weak pigeon hole principle, with n holes and any number of pigeons, is of length , (for some global constant > 0).* Research supported by NSF grant CCR-9820831, US-Israel BSF grant 98-00349, and an NSERC grant. Research supported by US-Israel BSF grant 98-00349, and NSF grant CCR-9987077.