Complexity of solution of linear systems in rings of differential operators

Suppose given a k₁×k₂ system of linear equations over the Weyl algebraA _n = F[X₁,...X₁,D₄,...,D_n] or over the algebra of differential operatorsK _n = F[X₁,...X₁,D₄,...,D_n], where the degree of each coefficient of the system is less than d. It is proved that if the system is solvable overA _n, orK _n, respectively, then it has a solution of degree at most (k, d)²⁰⁽ⁿ⁾.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 192, pp. 47–59, 1991.     

A Regulator Formula for Milnor K-groups

The classical Abel–Jacobi map is used to geometrically motivate the construction of regulator maps from Milnor K-groups K _n ^M (C(X)) to Deligne cohomology. These maps are given in terms of some new, explicit (n – 1)-currents, higher residues of which are defined and related to polylogarithms. We study their behavior in families X _s and prove a rigidity result for the regulator image of the Tame kernel, which leads to a vanishing theorem for very general complete intersections.     

On improved estimators of the generalized variance

Treated in this paper is the problem of estimating with squared error loss the generalized variance | Σ | from a Wishart random matrix S: p × p W_p(n, Σ) and an independent normal random matrix X: p × k N(ξ, Σ I_k) with ξ(p × k) unknown. Denote the columns of X by X₍₁₎ ,…, X_(k) and set ψ⁽⁰⁾(S, X) = {(n − p + 2)!/(n + 2)!} | S |, ψ⁽ⁱ⁾(X, X) = min[ψ⁽ⁱ⁻¹⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!} | S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |] and Ψ⁽ⁱ⁾(S, X) = min[ψ⁽⁰⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!}| S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |], i = 1,…,k. Our result is that the minimax, best affine equivariant estimator ψ⁽⁰⁾(S, X) is dominated by each of Ψ⁽ⁱ⁾(S, X), i = 1,…,k and for every i, ψ⁽ⁱ⁾(S, X) is better than ψ⁽ⁱ⁻¹⁾(S, X). In particular, ψ^(k)(S, X) = min[{(n − p + 2)!/(n + 2)!} | S |, {(n − p + 2)!/(n + 2)!} | S + X₍₁₎X′₍₁₎|,…,| {(n − p + k + 2)!/(n + k + 2)!} | S + X₍₁₎X′₍₁₎ + + X_(k)X′_(k)|] dominates all other ψ's. It is obtained by considering a multivariate extension of Stein's result (Ann. Inst. Statist. Math. 16, 155–160 (1964)) on the estimation of the normal variance.     

On the Aleksandrov-Fenchel inequality involving zonoids

The equality case in the general quadratic inequality V(K, L, K ₁, ..., K _n–2)² V(K, K, K ₁, ..., K _n–2) V(L, L, K ₁, ..., K _n–2) for mixed volumes is settled under the assumption that K and L are centrally symmetric and K ₁, ..., K _n–2 are zonoids. This result partly confirms a conjecture on the general case made in an earlier paper.     

The occurrence of large values in stationary sequences

Summary A direct proof is given of the Tanny (1974) result that for certain non-decreasing sequences a _n , it is true that lim supa _n ^–1 X _n = 0 or + with probability one for all ergodic stationary sequences X _n . The condition on a _n is shown to be necessary. For all non-decreasing a _n and stationary X _n , lim sup a _n ^–1 X _n= lim sup a _n ^–1 X _–n a.s. Similar continuous-time theorems are also given.This research supported in part by the Natural Sciences and Engineering Research Council of Canada     

An identity on the maximum of a set of random variables

It is shown that if X₁, X₂, …, X_n are symmetric random variables and max(X₁, …, X_n)⁺ = max(0, X₁, …, X_n), then E[max(X₁,…,X_n)⁺]=[max(X₁,X₁,+X₂,+X₁,+X₃,…X₁,+X_n)⁺], and in the case of independent identically distributed symmetric random variables, E[max(X₁, X₂)⁺] = E[(X₁)⁺] + (1/2)E[(X₁ + X₂)⁺], so that for independent standard normal random variables, E[max(X₁, X₂)⁺] = (1/√2π)[1 + (1/√2)].     

Oscillation in the initial segment complexity of random reals

We study oscillation in the prefix-free complexity of initial segments of 1-random reals. For upward oscillations, we prove that _∑n∈ω²−g(n) diverges iff (^∃∞n)K(X?n)>n+g(n) for every 1-random X∈ω². For downward oscillations, we characterize the functions g such that (^∃∞n)K(X?n)<n+g(n) for almost every X∈ω². The proof of this result uses an improvement of Chaitin's counting theorem—we give a tight upper bound on the number of strings σ∈n² such that K(σ)<n+K(n)−m.The work on upward oscillations has applications to the K-degrees. Write XK_?Y to mean that K(X?n)?K(Y?n)+O(1). The induced structure is called the K-degrees. We prove that there are comparable () 1-random K-degrees. We also prove that every lower cone and some upper cones in the 1-random K-degrees have size continuum.Finally, we show that it is independent of ZFC, even assuming that the Continuum Hypothesis fails, whether all chains of 1-random K-degrees of size less than ℵ₀² have a lower bound in the 1-random K-degrees.     

Central limit theorems in D[0, 1]

Summary Let X be a stochastic process with sample paths in the usual Skorohod space D[0, 1]. For a sequence {X _n} of independent copies of X, let S _n=X₁++X_n. Conditions which are either necessary or sufficient for the weak convergence of n ^–1/2(S _n–ES_n) to a Gaussian process with sample paths in D[0, 1] are discussed. Stochastically continuous processe are considered separately from those with fixed discontinuities. A bridge between the two is made by a Decomposition central limit theorem.     

Second-order linearity of the general signed-rank statistic

Let X₁,…, X_n be i.i.d. random variables symmetric about zero. Let R_i(t) be the rank of |X_i − tn^−1/2| among |X₁ − tn^−1/2|,…, |X_n − tn^−1/2| and T_n(t) = Σ_{i = 1}ⁿφ((n + 1)⁻¹R_i(t))sign(X_i − tn^−1/2). We show that there exists a sequence of random variables V_n such that sup_{0 ≤ t ≤ 1} |T_n(t) − T_n(0) − tV_n| → 0 in probability, as n → ∞. V_n is asymptotically normal.     

Numerical properties of Chern classes of certain covering manifolds

In this paper, we study numerical properties of Chern classes of certain covering manifolds. One of the main results is the following: Let ψ : X → Pⁿ be a finite covering of the n-dimensional complex projective space branched along a hypersurface with only simple normal crossings and suppose X is nonsingular. Let c_i(X) be the i-th Chern class of X. Then (i) if the canonical divisor K_X is numerically effective, then (−1)^kc_k(X) (k ≥ 2) is numerically positive, and (ii) if X is of general type, then (−1)ⁿcⁱ_l (X) cⁱ_r, (X) > 0, where i_l + … + i_r = n. Furthermore we show that the same properties hold for certain Kummer coverings.     

A uniform bound for the deviation of empirical distribution functions

If X₁, …, X_n are independent R^d-valued random vectors with common distribution function F, and if F_n is the empirical distribution function for X₁, …, X_n, then, among other things, it is shown that P{sup_x F_n(x) ε} 2e²(2n)^de^−2nε2 for all nε² ≥ d². The inequality remains valid if the X_i are not identically distributed and F(x) is replaced by Σ_iP{X_i ≤ x}/n.     

Generalized Hyers–Ulam–Rassias stability of n-sesquilinear-quadratic mappings on Banach modules over -algebras

Assume that X is a left Banach module over a unital C^*-algebra A. It is shown that almost every n-sesquilinear-quadratic mapping h:X×X×Xⁿ→A is an n-sesquilinear-quadratic mapping when holds for all x,y,z₁,…,z_nX.Moreover, we prove the generalized Hyers–Ulam–Rassias stability of an n-sesquilinear-quadratic mapping on a left Banach module over a unital C^*-algebra.     

Higher order representations of the Robbins–Monro process

For quasi-linear regression functions, the Robbins–Monro process X_n is decomposed in a sum of a linear form and a quadratic form both defined in the observation errors. Under regularity conditions, the remainder term is of order O(n^−3/2) with respect to the L_p-norm. If a cubic form is added, the remainder term can be improved up to an order of O(n⁻²). As a corollary the expectation of X_n is expanded up to an error of order O(n⁻²). This is used to correct the bias of X_n up to an error of order O(n^−3/2 log n).     

A Remark on Self-Normalization for Dependent Random Variables

Let (X _t , t ∈ Z) be a stationary process, and let S _n = ∑_{1⩽ i⩽n} X _i . In this paper, we consider the central limit theorem for the self-normalized sequence S _n /U _n , where U _n ² = ∑_1⩽j⩽N Y _j ² , Y _j = ∑_{(j−1)m<i⩽jm} X _i , n = mN. We show how such a self-normalization works for AR(1) and MA(q) processes.__________Published in Lietuvos Matematikos Rinkinys, Vol. 45, No. 2, pp. 173–183, April–June, 2005.     

A new graphic characterization of non singular quadrics of PG(r,q)

LetK be ak-set of class [0, 1,m,n]₁ of anr-dimensional projective Galois space PG(r, q) of orderq. We prove that: Ifr = 2s (s 2),k = _2s–1 and if through each point ofK there are exactlyq ^2(s–1) tangent lines and at most _2s–3 n-secant lines, thenK is a non singular quadric of PG(2s,q). Ifr = 2s–1 (s2),k=_2(s–1) +q ^s–1 and if at each point ofK there are exactlyq ^2s–3 –q ^s–2 tangents and at most _2(s–2)+q ^s–2 n-secant lines, thenK is a hyperbolic quadric of PG(2s–1,q).     

A full-invariant theorem and some applications

Let (X,τ₁) and (Y,τ₂) be two Hausdorff locally convex spaces with continuous duals X′ and Y′, respectively, L(X,Y) be the space of all continuous linear operators from X into Y, K(X,Y) be the space of all compact operators of L(X,Y). Let WOT and UOT be the weak operator topology and uniform operator topology on K(X,Y), respectively. In this paper, we characterize a full-invariant property of K(X,Y); that is, if the sequence space λ has the signed-weak gliding hump property, then each λ-multiplier WOT-convergent series ∑_iT_i in K(X,Y) must be λ-multiplier convergent with respect to all topologies between WOT and UOT if and only if each continuous linear operator T :(X,τ₁)→(λ^β,σ(λ^β,λ)) is compact. It follows from this result that the converse of Kalton's Orlicz–Pettis theorem is also true.     

Linear programming and operator means

The shorted operator, the geometric mean, and the cascade limit are all examples of operations that are of the form sup{X¦C + K X ≥ 0}, where K X denotes the Kronecker product of the matrix K with the matrix X, K is a given n by n self-adjoint matrix, and C is a given positive semidefinite matrix. The supremum is taken with respect to the partial order generated by the positive semidefinite matrices. In all of the above examples the matrix K has exactly one negative eigenvalue. We show by linear programming techniques that if K has this property, and X_max = sup{X¦C + K X ≥ 0}, then (X_maxc, c) = inf tr(AY), subject to: −∑_{i,j = 1}ⁿk_ijY_ij ≥ cc^*, Y = {Y_ij)_{i,j = 1}ⁿ ≥ 0} In the case of the geometric mean A#B of two positive semidefinite matrices, this implies the new result that (A#Bc, c) = inf{tr(AY₁₁ + BY₂₂¦Y₁₂ + Y₂₁ ≥ cc^*, Y ≥ 0}.     

Permutation Matrices, Wreath Products, and the Distribution of Eigenvalues

We consider a class of random matrix ensembles which can be constructed from the random permutation matrices by replacing the nonzero entries of the n×n permutation matrix matrix with M×M diagonal matrices whose entries are random Kth roots of unity or random points on the unit circle. Let X be the number of eigenvalues lying in a specified arc I of the unit circle, and consider the standardized random variable (X–E[X])/(Var(X))^1/2. We show that for a fixed set of arcs I ₁,...,I _N , the corresponding standardized random variables are jointly normal in the large n limit, and compare the covariance structures which arise with results for other random matrix ensembles.     

On the Maximal Multiplicity of Parts in a Random Integer Partition

We study the asymptotic behavior of the maximal multiplicity μ_n = μ_n(λ) of the parts in a partition λ of the positive integer n, assuming that λ is chosen uniformly at random from the set of all such partitions. We prove that πμ_n/(6n)^1/2 converges weakly to max _jX_j/j as n→∞, where X₁, X₂, … are independent and exponentially distributed random variables with common mean equal to 1.2000 Mathematics Subject Classification: Primary—05A17; Secondary—11P82, 60C05, 60F05     

The Algebra of Flows in Graphs

We define a contravariant functorKfrom the category of finite graphs and graph morphisms to the category of finitely generated graded abelian groups and homomorphisms. For a graphX, an abelian groupB, and a nonnegative integerj, an element of Hom(K^j(X), B) is a coherent family ofB-valued flows on the set of all graphs obtained by contracting some (j − 1)-set of edges ofX; in particular, Hom(K¹(X), ) is the familiar (real) “cycle-space” ofX. We show thatK ^· (X) is torsion-free and that its Poincaré polynomial is the specializationt^{n − k}T_X(1/t, 1 + t) of the Tutte polynomial ofX(hereXhasnvertices andkcomponents). Functoriality ofK ^· induces a functorial coalgebra structure onK ^· (X); dualizing, for any ringBwe obtain a functorialB-algebra structure on Hom(K ^· (X), B). WhenBis commutative we present this algebra as a quotient of a divided power algebra, leading to some interesting inequalities on the coefficients of the above Poincaré polynomial. We also provide a formula for the theta function of the lattice of integer-valued flows inX, and conclude with 10 open problems.