The smooth Banach submanifold B*(E, F) in B(E, F)

Let E,F be two Banach spaces,B(E,F),B+(E,F),Φ(E,F),SΦ(E,F) and R(E,F) be bounded linear,double splitting,Fredholm,semi-Frdholm and finite rank operators from E into F,respectively. Let Σ be any one of the following sets:{T ∈Φ(E,F):Index T=constant and dim N(T)=constant},{T ∈ SΦ(E,F):either dim N(T)=constant< ∞ or codim R(T)=constant< ∞} and {T ∈ R(E,F):Rank T=constant< ∞}. Then it is known that Σ is a smooth submanifold of B(E,F) with the tangent space TAΣ={B ∈ B(E,F):BN(A)-R(A) } for any A ∈Σ. However,for ...     

Eine Bemerkung zu einem Satz von W. Hahn aus der Stabilitätstheorie linearer Systeme

A short proof of the following theorem ofW. Hahn is given: LetP be a real n×n matrix,B=1/2(P+P ^T ),A=1/2(P?P ^T ) and letB be negative semidefinite. All eigenvalues ofA have negative real parts if and only if, rank (B, AB, ..., A ^n?1 B)=n.     

A problem related to Foulkes’s conjecture

In this paper we study a class of symmetric matricesT indexed by positive integers m≥ n≥2 and defined as follows: for any positive integersp andq let ?_p,q be the set of partitions ofU = {1,2,3, ...,pq} into p blocks each of sizeq. Letm ≥n ≥ 2 be positive integers. By atransversal of α = A₁/A₂/.../A_n ∈ ?_n,m we mean a partitionß = B₁/B₂/.../B_m ∈ ? _m,n such that ‖A _i ∩B _j = 1 for every i= 1,2, ...,n and everyj = 1,2, ...,m. LetM be the zero-one matrix with rows indexed by the elements of ?_n,m and columns indexed by the elements of ?_m,n such that M_αß = 1 iffß is a transversal of α. We are interested in finding the eigenvalues and eigenspaces of the symmetric matrixT = MM^t. The nonsingularity ofT implies Foulkes’s Conjecture (for these values of m andn). In the casen = 2 we completely determine the eigenvalues and eigenspaces of T and in so doing demonstrate the non-singularity ofT. Forn = 3 we develop a fast algorithm for computing the eigenvalues ofT, and give numerical results in the cases m = 3,4, 5, 6.     

Adams theorem on Bernoulli numbers revisited

If we denote B_n to be nth Bernoulli number, then the classical result of Adams (J. Reine Angew. Math. 85 (1878) 269) says that p^?|n and (p−1)?n, then p^?|B_n where p is any odd prime p>3. We conjecture that if (p−1)?n, p^?|n and p?+1?n for any odd prime p>3, then the exact power of p dividing B_n is either ? or ?+1. The main purpose of this article is to prove that this conjecture is equivalent to two other unproven hypotheses involving Bernoulli numbers and to provide a positive answer to this conjecture for infinitely many n.     

On a restricted cross-intersection problem

Suppose A and B are families of subsets of an n-element set and L is a set of s numbers. We say that the pair (A,B) is L-cross-intersecting if |A∩B|∈L for every A∈A and B∈B. Among such pairs (A,B) we write PL(n) for the maximum possible value of |A||B|. In this paper we find an exact bound for PL(n) when n is sufficiently large, improving earlier work of Sgall. We also determine P{2}(n) and P{1,2}(n) exactly, which respectively confirm special cases of a conjecture of Ahlswede, Cai and Zhang and a conjecture of Sgall.     

On a problem of P. Erdös

Let n be a positive integer and let A = {a₁,…, a_s}, B = {b₁,…, b_t} be two sets of positive integers such that the product set consists of st distinct numbers. Then, for a certain positive constant c, $\text{st ≤ c}\text{n}{}^2\text{log}\text{n}$, establishing a conjecture made by P. Erdös.     

Asymptotic behaviour of multiperiodic functions scaled by Pisot numbers

Let β > 1 be a Pisot number andg be a positive Hölder continuous function with period one and g(0) = 1. The multiperiodic functionG(ξ)=Π _n=0 ^∞ g(ξ/βⁿ) is studied and the asymptotic behaviour ofI _G(T) = ∫ ₀ ^T G(ξ)dξ investigated. We prove that the limit of logI(T)/ logT exists asT tends to infinity. We also provide a method to calculate this limit for the caseg(ξ) = cos² 2πξ, corresponding to the Fourier transform of the Bernoulli convolution associated to the golden number (or some of its generalizations).     

Upper bounds on the depth of symmetric Boolean functions

A new method for implementing the counting function with Boolean circuits is proposed. It is based on modular arithmetic and allows us to derive new upper bounds for the depth of the majority function of n variables: 3.34log₂ n over the basis B ₂ of all binary Boolean functions and 4.87log₂ n over the standard basis B ₀ = {∧, ∨, ?}. As a consequence, the depth of the multiplication of n-digit binary numbers does not exceed 4.34log₂ n and 5.87log₂ n over the bases B ₂ and B ₀, respectively. The depth of implementation of an arbitrary symmetric Boolean function of n variables is shown to obey the bounds 3.34log₂ n and 4.88log₂ n over the same bases.     

The “best” partition of an integer

An algorithm, based on a conjecture, to compute a permutation whose repeated application to a given set will yield a maximum number of different orderings of that set is presented. The algorithm gives the lengths of the cycles required. This problem turns out to be equivalent to the problem of determining a partitionB(n) ofn for which the least common multiple (l.c.m.) of the numbers ofB(n) is maximal.     

On the number of linear forms in logarithms

Let n be a positive integer. In this paper we estimate the size of the set of linear forms b₁loga₁+b₂loga₂+?+bnlogan, where |bi|?Bi and 1?ai?Ai are integers, as Ai,Bi→∞.     

The cotype constant and an almost euclidean decomposition for finite-dimensional normed spaces

Every 2n-dimensional normed spaceE contains twon-dimensional subspacesE ₁ andE ₂ which are orthogonal with respect to the inner product induced by the John ellipsoid ofE and which satisfyd(E _i, l ₂ ⁿ )≦f(K ₂(E)), wheref(K ₂(E)) is some number that depends only on the cotype constant ofE, denotedK ₂(E). Supported in part by NSF grant DMS 8401906.     

The representation and perturbation of theW-weighted Drazin inverse

LetA andE bem x n matrices andW an n xm matrix, and letA _d,W denote the W-weighted Drazin inverse ofA. In this paper, a new representation of the W-weighted Drazin inverse ofA is given. Some new properties for the W-weighted Drazin inverseA _d,W and B_d,W are investigated, whereB =A+E. In addition, the Banach-type perturbation theorem for the W-weighted Drazin inverse ofA andB are established, and the perturbation bounds for ∥B_d,W∥ and ∥B_{d, W}, -A_d,W∥/∥A_d,W∥ are also presented. WhenA andB are square matrices andW is identity matrix, some known results in the literature related to the Drazin inverse and the group inverse are directly reduced by the results in this paper as special cases.     

The distance between certainn-dimensional Banach spaces

IfE andF aren-dimensional Banach spaces, ifE has cotype 2, and if the ball ofF* has a small number of extreme points, then the Banach-Mazur distanced(E, F)≦C √nlogn. The techniques lead to the formally stronger result: IfE andF* have type 2 constantsa andb, respectively, thend(E, F)≦√n(a+b). IfE isn-dimensional, the identity map onE, when restricted to a large subspace ofE, factors through with normC √n. The authors’ work was supported in part, respectively, by NSF grant numbers MCS 78-02194, MCS 79-02489, and MCS 77-04174.     

On fixed point sets of homeomorphisms of then-ball

Conditions are investigated under which a subsetA can be the fixed point set of a homeomorphism ofB ⁿ . If eitherA ∩ ?B ⁿ ≠ Ø andn arbitrary orA ∩ ?B ⁿ =Ø andn even it is necessary and sufficient thatA is non-empty and closed. IfA ∩ ?B ⁿ =Ø andn odd, conditions which are either necessary or sufficient (but not both) are given.     

On a continuous analogue of the stochastic difference equation Xn=ρXn-1+Bn

Let B₁, B₂, ... be a sequence of independent, identically distributed random variables, letX₀ be a random variable that is independent ofB_n forn?1, let ρ be a constant such that 0<ρ<1 and letX₁,X₂, ... be another sequence of random variables that are defined recursively by the relationshipsX_n=ρX_n-1+B_n. It can be shown that the sequence of random variablesX₁,X₂, ... converges in law to a random variableX if and only ifE[log⁺¦B₁¦]<∞. In this paper we let {B(t):0≦t<∞} be a stochastic process with independent, homogeneous increments and define another stochastic process {X(t):0?t<∞} that stands in the same relationship to the stochastic process {B(t):0?t<∞} as the sequence of random variablesX₁,X₂,...stands toB₁,B₂,.... It is shown thatX(t) converges in law to a random variableX ast →+∞ if and only ifE[log⁺¦B(1)¦]<∞ in which caseX has a distribution function of class L. Several other related results are obtained. The main analytical tool used to obtain these results is a theorem of Lukacs concerning characteristic functions of certain stochastic integrals.     

A property of the planar measure of the lemniscates

In this paper, we establish the following conjecture: There exists a constant K such that every lemniscate E(α,c), α∈Cn, c>0, contains a disk B(α,c) with μ(E(α,c))?Kμ(B(α,c)), where μ is the planar measure. We prove this conjecture for any family of lemniscates with at the most three foci and for any family of lemniscates where its foci satisfy a suitable condition.     

Efficient partition trees

We prove a theorem on partitioning point sets inE ^d (d fixed) and give an efficient construction of partition trees based on it. This yields a simplex range searching structure with linear space,O(n logn) deterministic preprocessing time, andO(n ^1?1/d (logn) ^O(1)) query time. WithO(nlogn) preprocessing time, where δ is an arbitrary positive constant, a more complicated data structure yields query timeO(n ^1?1/d (log logn) ^O(1)). This attains the lower bounds due to Chazelle [C1] up to polylogarithmic factors, improving and simplifying previous results of Chazelleet al. [CSW]. The partition result implies that, forr ^d≤n ^1?δ, a (1/r)-approximation of sizeO(r ^d) with respect to simplices for ann-point set inE ^d can be computed inO(n logr) deterministic time. A (1/r)-cutting of sizeO(r ^d) for a collection ofn hyperplanes inE ^d can be computed inO(n logr) deterministic time, provided thatr≤n ^1/(2d?1).     

An Efficient Algorithm for the Complex Roots Problem

Given a univariate polynomialf(z) of degreenwith complex coefficients, whose norms are less than 2^min magnitude, the root problem is to find all the roots off(z) up to specified precision 2^−μ. Assuming the arithmetic model for computation, we provide an algorithm which has complexityO(nlog⁵nlogB), whereb= χ + μ, and χ = max{n,m}. This improves on the previous best known algorithm of Pan for the problem, which has complexityO(n²log²nlog(m+ μ)). A remarkable property of our algorithm is that it does not require any assumptions about the root separation off, which were either explicitly, or implicitly, required by previous algorithms. Moreover it also has a work-efficient parallel implementation. We also show that both the sequential and parallel implementations of the algorithm work without modification in the Boolean model of arithmetic. In this case, it follows from root perturbation estimates that we need only specify θ = ⌈n(B+ logn+ 3)⌉ bits of the binary representations of the real and imaginary parts of each of the coefficients off. We also show that by appropriate rounding of intermediate values, we can bound the number of bits required to represent all complex numbers occurring as intermediate quantities in the computation. The result is that we can restrict the numbers we use in every basic arithmetic operation to those having real and imaginary parts with at most φ bits, where[formula]and[formula]Thus, in the Boolean model, the overall work complexity of the algorithm is only increased by a multiplicative factor ofM(φ) (whereM(ψ) =O(ψ(log ψ) log log ψ) is the bit complexity for multiplication of integers of length ψ). The key result on which the algorithm is based, is a new theorem of Coppersmith and Neff relating the geometric distribution of the zeros of a polynomial to the distribution of the zeros of its high order derivatives. We also introduce several new techniques (splitting sets and “centered” points) which hinge on it. We also observe that our root finding algorithm can be efficiently parallelized to run in parallel timeO(log⁶nlogB) usingnprocessors.     

On a Regev-Seeman conjecture about ℤ2-graded tensor products

If A,B are superalgebras then, besides A?B, a ?₂-graded tensor product A $ \bar \otimes $ B arises. Kemer proved that if A,B are T-prime algebras then A? B is multi-linear equivalent to a suitable T-prime algebra C. Regev and Seeman conjectured that this holds for A $ \bar \otimes $ B as well. In this paper we prove their conjecture is true indeed, by means of G-graded polynomial identities. The results obtained are valid over any infinite field of characteristic ≠ 2.     

The error bound of the perturbation of the Drazin inverse

Let A and E be n×n matrices and B = A + E. Denote the Drazin inverse of A by A^D. In this paper we give an upper bound for the relative error ∥B^D ? A^D∥/∥A^D∥₂ and a lower bound for ∥B^D∥₂ under certain circumstances. The continuity properties and the derivative of the Drazin inverse are also considered.