On the Rate of Clustering to the Strassen Set for Increments of the Uniform Empirical Process

We obtain outer rates of clustering in the functional laws of the iterated logarithm of Deheuvels and Mason⁽¹¹⁾ and Deheuvels,⁽⁷⁾ which describe local oscillations of empirical processes. Considering increment sizes a _n 0 such that na _n and na _n(log n)^–7/3 we show that the sets of properly rescaled increment functions cluster with probability one to the _n-enlarged Strassen ball in B(0, 1) endowed with the uniform topology, where _n 0 may be chosen so small as (log (1/a _n) + log log n)^–2/3 for any sufficiently large . This speed of coverage is reduced for smaller a _n.     

A new continuation method for complementarity problems with uniformP-functions

The complementarity problem with a nonlinear continuous mappingf from the nonnegative orthantR ₊ ⁿ ofR ⁿ intoR ⁿ can be written as the system of equationsF(x, y) = 0 and(x, y) R ₊ ²ⁿ , whereF denotes the mapping from the nonnegative orthantR ₊ ²ⁿ ofR ²ⁿ intoR ₊ ⁿ × Rⁿ defined byF(x, y) = (x ₁y₁,,x_ny_n, f₁(x) – y₁,, f_n(x) – y_n) for every(x, y) R ₊ ²ⁿ . Under the assumption thatf is a uniformP-function, this paper establishes that the mappingF is a homeomorphism ofR ₊ ²ⁿ ontoR ₊ ⁿ × Rⁿ. This result provides a theoretical basis for a new continuation method of tracing the solution curve of the one parameter family of systems of equationsF(x, y) = tF(x ⁰, y⁰) and(x, y) R ₊ ²ⁿ from an arbitrary initial point(x ⁰, y⁰) R ₊ ²ⁿ witht = 1 until the parametert attains 0. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving linear complementarity problems with positive semi-definite matrices.     

A functional inequality for real-analytic functions

Summary Forf ( C ⁿ() and 0 t x letJ _n (f, t, x) = (–1)ⁿ f(–x)f ⁽ⁿ⁾(t) +f(x)f ⁽ⁿ⁾ (–t). We prove that the only real-analytic functions satisfyingJ _n (f, t, x) 0 for alln = 0, 1, 2, are the exponential functionsf(x) = c e ^x,c, . Further we present a nontrivial class of real-analytic functions satisfying the inequalitiesJ ₀ (f, x, x) 0 and ₀ ^x (x – t)^{n – 1}J_n(f, t, x)dt 0 (n 1).     

Algorithms for confluent Vandermonde systems

Two compact algorithms are developed for solving systems of linear equationsV x=b andV ^T a=f, whereV=V( ₀, ₁, ..., _n ) is a confluent Vandermonde matrix of Hermite type. The solution is obtained by one forward and one backward vector recursion, starting with the right hand side. The total amount of storage is only 2n. The number of arithmetic operations needed isO(n ²) and compares favourably with other proposed methods.     

Limit Theorems for the Maximum Terms of a Sequence of Random Variables with Marginal Geometric Distributions

Let X _n1 ^* , ... X _nn ^* be a sequence of n independent random variables which have a geometric distribution with the parameter p _n = 1/n, and M _n ^* = \max\{X _n1 ^* , ... X _nn ^* }. Let Z ₁, Z₂, Z₃, ... be a sequence of independent random variables with the uniform distribution over the set N _n = {1, 2, ... n}. For each j N _n let us denote X _nj = min{k : Z_k = j}, M _n = max{X_n1, ... X_nn}, and let S _n be the 2nd largest among X _n1, X_n2, ... X_nn. Using the methodology of verifying D(u_n) and D'(u_n) mixing conditions we prove herein that the maximum M _n has the same type I limiting distribution as the maximum M _n ^* and estimate the rate of convergence. The limiting bivariate distribution of (S_n, M_n) is also obtained. Let _n, _n N_n, , and T _n = min{M(A_n), M(B_n)}. We determine herein the limiting distribution of random variable T _n in the case _n , _n/_n > 0, as n .     

A Tauberian Theorem for Ergodic Averages,Spectral Decomposability,and the Dominated Ergodic Estimate for Positive Invertible Operators

Suppose that (,) is a -finite measure space, and 1 < p < . Let T:L^p( L ^p() be a bounded invertible linear operator such that T and T ^–1 are positive. Denote by _n(T) the nth two-sided ergodic average of T, taken in the form of the nth (C,1) mean of the sequence {T^j+T^–j}_{j =1} . Martín-Reyes and de la Torre have shown that the existence of a maximal ergodic estimate for T is characterized by either of the following two conditions: (a) the strong convergence of E_n(T)_n=1 ; (b) a uniform A _p p estimate in terms of discrete weights generated by the pointwise action on of certain measurable functions canonically associated with T. We show that strong convergence of the (C,2) means of {T^j+T^–j}_j=1 already implies (b). For this purpose the (C,2) means are used to set up an `averaged' variant of the requisite uniform A _p weight estimates in (b). This result, which can be viewed as a Tauberian-Type replacement of (C,1) means by (C,2) means in (a), leads to a spectral-theoretic characterization of the maximal ergodic estimate by application of a recent result of the authors establishing the strong convergence of the (C,2)-weighted ergodic means for all trigonometrically well-bounded operators. This application also serves to equate uniform boundedness of the rotated Hilbert averages of T with the uniform boundedness of the ergodic averages E_n(T)_{n = 1} .     

Interval-dividing processes

Summary If and then P(n ^–1·[(Y ₁)++(Y _n )] converges to cnts. law on R ¹) = P(n ^–1·[(Y ₁)++(Y _n )] converges to a cnts. law on R ¹). Thus if ,n then n ^–1[(X ₁)+...+(X _n )] converges a.s. The main result here generalizes this: Let X ₍₁₎ ⁿ , X ₍₂₎ ⁿ ,..., X _(n) ⁿ be the order statistics associated with X ₁, X ₂,,X _n. Define random variables Z ₁,Z ₂, by {Z _n =i}={X _n =X _(i) ⁿ }. Then if Z ₁,Z ₂,Z ₃, are independent and P(Z_ni)i/n, and {X _i} is bounded, n ^–1·[(X ₁)++(X _n)] converges a.s.     

Toeplitz operators related to strongly singular Calderón-Zygmund operators

In this paper, the boundedness of Toeplitz operator T _b(f) related to strongly singular Calderón-Zygmund operators and Lipschitz function b ε (ℝⁿ) is discussed from L ^p(ℝⁿ) to L ^q(ℝⁿ), , and from L ^p(ℝⁿ) to Triebel-Lizorkin space . We also obtain the boundedness of generalized Toeplitz operator Θ _α0 ^b from L ^p(ℝⁿ) to L ^q(ℝⁿ), . All the above results include the corresponding boundedness of commutators. Moreover, the boundedness of Toeplitz operator T _b(f) related to strongly singular Calderón-Zygmund operators and BMO function b is discussed on L ^p(ℝⁿ), 1 < p < ∞.     

Asymptotic Density and the Asymptotics of Partition Functions

Let A be a set of positive integers with gcd (A) = 1, and let p _A (n) be the partition function of A. Let c ₀ = 2/3. If A has lower asymptotic density and upper asymptotic density , then lim inf log p _A (n)/c ₀ n and lim sup log p _A (n)/c ₀ n . In particular, if A has asymptotic density > 0, then log p _A (n) c₀n. Conversely, if > 0 and log p _A (n) c ₀ n, then the set A has asymptotic density .     

A lower bound for the optimal crossing-free Hamiltonian cycle problem

Consider a drawing in the plane ofK _n , the complete graph onn vertices. If all edges are restricted to be straight line segments, the drawing is called rectilinear. Consider a Hamiltonian cycle in a drawing ofK _n . If no pair of the edges of the cycle cross, it is called a crossing-free Hamiltonian cycle (cfhc). Let (n) represent the maximum number of cfhc's of any drawing ofK _n , and (n) the maximum number of cfhc's of any rectilinear drawing ofK _n . The problem of determining (n) and (n), and determining which drawings have this many cfhc's, is known as the optimal cfhc problem. We present a brief survey of recent work on this problem, and then, employing a recursive counting argument based on computer enumeration, we establish a substantially improved lower bound for (n) and (n). In particular, it is shown that (n) is at leastk × 3.2684 ⁿ . We conjecture that both (n) and (n) are at mostc × 4.5 ⁿ .This research, part of which was conducted at Queen's University, was supported by an N.S.E.R.C. postgraduate scholarship.     

On the distribution of comparisons in sorting algorithms

We considered the following natural conjecture: For every sorting algorithm every key will be involved in(logn) comparisons for some input. We show that this is true for most of the keys and prove matching upper and lower bounds. Every sorting algorithm for some input will involven–n /2+1 keys in at leastlog₂ n comparisons,>0. Further, there exists a sorting algorithm that will for every input involve at mostn–n ^/c keys in greater thanlog₂ n comparisons, wherec is a constant and>0. The conjecture is shown to hold for natural algorithms from the literature.     

Isotropic random walks in a tree

Summary Let T be an infinite homogeneous tree of order a+1. We study Markov chains {X _n} in T whose transition functions p(x, y)=A[d(x,y)] depend only on the shortest distance between x and y in the graph. The graph T can be represented as a symmetric space of a p-adic matrix group; we prove a series of results using essentially the spherical functions of this symmetric space. Theorem 1. d(X _n,x) n a.s., where >0 if A(0) 1, X ₀=x. Assuming {X _n} is strongly aperiodic, Theorem 2. p ₂(x, y)CRⁿ/n^3/2 for fixed x, y where R=(d) A(d)<1, and if E[d(X₁, X₀)²]<, Theorem 3. R(1–u, x, y) = (1–u)ⁿp_n(x, y)=Ca^–d[exp(–du/)+o_d(1)] as d=d(x,y) uniformly for 0u2. Using Theorem 3, we calculate the Martin boundary Dirichlet kernel of p(x, y) on T, which turns out to be independent of {itA(d)}. We also consider a stepping-stone model of a randomly-mating-and-migrating population on the nodes of T. If initially all individuals are distinct, then in generation n approximately half of the individuals of a given type are within n of a typical one and essentially all are within 2n.This work was partially supported by the National Science Foundation under grant number MCS 75-08098-A01For the academic year 1977–78: Department of Mathematics GN-50, University of Washington, Seattle, Washington 98195 USA     

Spectral functions of zeros in the Besselq-functions

Zeta functions _v(z; q)= _n=1 [j_vn(q)]^–z and partition functions Z_v(t; q)=_n exp[–tj _vn ² (q)] related to the zeros j_vn(q) of the Bessel q-functions J_v(x; q) and J _v ⁽²⁾ (x; q) are studied and explicit formulas for _v(2n; q) at n=±1, ±2, ... are obtained. The poles of _v(z; q) in the complex plane and the corresponding residues are found. Asymptotics of the partition functions Z_v(t; q) at t 0 are investigated.Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 107, No. 3, pp. 397–414, June, 1996.     

Spectral estimates of Cauchy's transform inL 2(Ω)

We prove that the singular numbers of the Cauchy transform onL ²(D) are asymptotically , whiles _n (C _| L _a ² (D))1/n (whereL _a ² (D) is the subspace of analytic functions inL ²(D)). Also, the singular numbers of the logarithmic potential onL ²(D) are asympoticallys _n (L)1/n, whiles _n(L _{|L a} ² (D))1/n ². Our methods yield the asymptotic behavior of the singular numbers of the Cauchy Transform fromL _L ² () intoL ²() where and are rotation-invariant measures on .The author was partly supported by a grant from the national Science Foundation.     

Sur les équations fonctionnelles auxq-différences

Summary In this paper, we study the convergence of formal power series solutions of functional equations of the formP _k(x)(^[k](x))=(x), where ^[k] (x) denotes thek-th iterate of the function.We obtain results similar to the results of Malgrange and Ramis for formal solutions of differential equations: if(0) = 0, and(0) =q is a nonzero complex number with absolute value less than one then, if(x)=a(n)x ⁿ is a divergent solution, there exists a positive real numbers such that the power seriesa(n)q ^sn(n+1)2 x ⁿ has a finite and nonzero radius of convergence.

     

Extremal Eigenvalues of the Laplacian in a Conformal Class of Metrics: The `Conformal Spectrum'

Let M be a compact connected manifold of dimension n endowed witha conformal class C ofRiemannian metrics of volume one. For any integer k 0, we consider the conformal invariant _k ^c (C) defined as the supremum of the k-th eigenvalue _k (g) of the Laplace–Beltrami operator _g , where g runs over C.First, we give a sharp universal lower bound for _k ^c (C) extending to all k a result obtained by Friedlander andNadirashvili for k = 1. Then, we show that the sequence \{ _k ^c (C)\}, that we call `conformal spectrum',is strictly increasing and satisfies, k 0, _k+1 ^c (C) ^n/2– _k ^c (C) ^n/2 n ^n/2 _n , where _n is the volume of the n-dimensionalstandard sphere.When M is an orientable surface of genus , we also considerthe supremum _k ^top()of _k (g) over theset of all the area one Riemannian metrics on M, and study thebehavior of _k ^top() in terms of .     

On a characterization of complete matrix rings

Peter R. Fuchs established in 1991 a new characterization of complete matrix rings by showing that a ringR with identity is isomorphic to a matrix ringM _n (S) for some ringS (and somen 2) if and only if there are elementsx andy inR such thatx ^n–1 0,x ⁿ=0=y ²,x+y is invertible, and Ann(x ^n–1)Ry={0} (theintersection condition), and he showed that the intersection condition is superfluous in casen=2. We show that the intersection condition cannot be omitted from Fuchs' characterization ifn3; in fact, we show that if the intersection condition is omitted, then not only may it happen that we do not obtain a completen ×n matrix ring for then under consideration, but it may even happen that we do not obtain a completem ×m matrix ring for anym2.     

Existence and Stability of Time-Periodic Dissipative Structures in Parabolic Systems of Reaction-Diffusion Type

On the interval 0 x the parabolic system

On Two-Point Boundary Conditions in Optimal Control Problems

Let x=g(t,x(t),u(t)) be the governing equation of an optimal control problem with two-point boundary conditions h ₀(x(a))+h ₁(x(b)) = 0, where x: [a,b] ⁿ is continuous, u: [a,b] ^k-n is piecewise continuous and left continuous, h₀,h₁: ^{n q} are continuously differentiable, and g:[a,b]× ^{k n} is continuous. The paper finds functions _i C¹([a,b]× ⁿ ) such that (x(t),u(t)) is a solution of the governing equation if and only if

Karmarkar's linear programming algorithm and Newton's method

This paper describes a full-dimensional version of Karmarkar's linear programming algorithm, theprojective scaling algorithm, which is defined for any linear program in ⁿ having a bounded, full-dimensional polytope of feasible solutions. If such a linear program hasm inequality constraints, then it is equivalent under an injective affine mappingJ: ^{n m} to Karmarkar's original algorithm for a linear program in ^m havingm—n equality constraints andm inequality constraints. Karmarkar's original algorithm minimizes a potential functiong(x), and the projective scaling algorithm is equivalent to that version of Karmarkar's algorithm whose step size minimizes the potential function in the step direction.The projective scaling algorithm is shown to be a global Newton method for minimizing a logarithmic barrier function in a suitable coordinate system. The new coordinate system is obtained from the original coordinate system by a fixed projective transformationy = (x) which maps the hyperplaneH _opt ={x:c, x =c ₀} specified by the optimal value of the objective function to the hyperplane at infinity. The feasible solution set is mapped under to anunbounded polytope. Letf _LB(y) denote the logarithmic barrier function associated to them inequality constraints in the new coordinate system. It coincides up to an additive constant with Karmarkar's potential function in the new coordinate system. Theglobal Newton method iterate y ^* for a strictly convex functionf(y) defined on a suitable convex domain is that pointy ^* that minimizesf(y) on the search ray {y+ v _N(y): 0} wherev _N(y) =–(² f(y))^–1(f(y)) is the Newton's method vector. If {x ^(k)} are a set of projective scaling algorithm iterates in the original coordinate system andy ^(k) =(x ^(k)) then {y ^(k)} are a set of global Newton method iterates forf _LB(y) and conversely.Karmarkar's algorithm with step size chosen to minimize the potential function is known to converge at least at a linear rate. It is shown (by example) that this algorithm does not have a superlinear convergence rate.