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.     

Separation of hypersurfaces

We give a generalization of results obtained in [15]. LetK ⁿ denote the set of embedded hypersurfaces in ⁿ⁺¹; for all xSⁿ and MK ⁿ we denote by C _x ^M the apparent contour ofM in the directionx. Then we give a sufficient condition on WSⁿ such that the map _W ^{K n}:K ⁿ P(T Sⁿ) , defined by _W ^{K n} (M)={C _w ^M ¦ wW}, is injective.     

Complete stability of large order statistics

Fix an integerr1. For eachnr, letM _nr be the rth largest ofX ₁,...,X _n, where {X _n,n1} is a sequence of i.i.d. random variables. Necessary and sufficient conditions are given for the convergence of _n=r n P[|M _nr /a _n –1|<] for every >0, where {a _n} is a real sequence and –1. Moreover, it is shown that if this series converges for somer1 and some >–1, then it converges for everyr1 and every >–1.     

Intersection queries in sets of disks

In this paper we develop some new data structures for storing a set of disks that can answer different types of intersection queries efficiency. If the disks are non-intersecting we obtain a linear size data structure that can report allk disks intersecting a query line segment in timeO(n ⁺ +k), wheren is the number of disks,=log₂(1+5)–1 0.695, and is an arbitrarily small positive constant. If the segment is a full line, the query time becomesO(n +k). For intersecting disks we obtain anO(n logn) size data structure that can answer an intersection query in timeO(n ^2/3 log² n+k). We also present a linear size data structure for ray shooting queries, whose query time isO(n ).The research of the first two authors was supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). The work of the third author was supported byDimacs (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center — NSF-STC88-09648.     

Über eine Verallgemeinerung der Nicoletti-Aufgabe für Funktional-Differentialgleichungen mit voreilendem Argument

We consider a functional differential equation (1) (t)=F(t,) fort[0,+) together with a generalized Nicoletti condition (2)H()=. The functionF: [0,+)×C ⁰[0,+)B is given (whereB denotes the Banach space) and the value ofF (t, ) may depend on the values of (t) fort[0,+);H: C ⁰[0,+)B is a given linear operator and B. Under suitable assumptions we show that when the solution :[0,+)B satisfies a certain growth condition, then there exists exactly one solution of the problem (1), (2).     

Parameter-dependent renewal theorems with applications

Let ₁, ₂, ... be a sequence of i.i.d. random variables with positive mean and finite variance and letr(b), b0, be real numbers tending to 0 asb . Definings _n=₁+...+_n andS _n=S_n(b)=s_n+r(b)n, the stopping time =(b)=inf {n>/1:S_n >b} whereb=b(b) , will be considered with special regard to the excess over the boundaryR _b=s+r(b)–b. It turns out that the limiting distribution ofR _b is the same as in the caser(b)0 for allb. Proving this, Blackwell's renewal theorem and its integral version have to be established first in the above stated situation. Finally, an expansion ofE to vanishing terms asb will be provided and applied to some examples arising in economics.

---

Zusammenfassung Seien ₁, ₂, ... unabhängige identisch verteilte Zufallsgrößen mit positivem Erwartungswert und endlicher Varianz sowier(b), b0, reelle Zahlen mitr(b)0 für b. Sei ferners ₁, s₂, ... der zugehörige Summenprozeß,S _n= S_n(b)=s_n+r(b)n fürn1 und =(b)=inf {n1: S_n>b, wobeib=b(b) fürb . Es wird gezeigt, daß die asymptotische Verteilung des ExzessesR _b=s +r(b) –b mit der im Fallr(·)0 übereinstimmt. Dazu werden sowohl das Blackwellsche Erneuerungstheorem als auch seine Integralversion in der vorher beschriebenen parameterabhängigen Situation geeignet formuliert und bewiesen. Als Folgerung ergibt sich dann eine asymptotische Entwicklung vonE(b) fürb bis zu Termen o(1). Anh- and einiger Beispiele aus dem ökonomischen Bereich wird schließlich noch aufgezeigt, wo Approximationen fürE(b) von Interesse sein können.

     

A strong approximation for logarithmic averages of partial sums of random variables

LetS _n be the partial sums of -mixing stationary random variables and letf(x) be a real function. In this note we give sufficient conditions under which the logarithmic average off(S _n / _n ) converges almost surely to _– f(x)d(x). We also obtain strong approximation forH(n)= _k=1 ⁿ k ^–1 f(S _k /k)=logn _– f(x)d(x) which will imply the asymptotic normality ofH(n)/log^1/2 n. But for partial sums of i.i.d. random variables our results will be proved under weaker moment condition than assumed for -mixing random variables.     

On the convergence of orthogonal series to +∞

For any sequence of numbers _n0, _n=1 a _n ² =, a uniformly bounded orthonormal system of continuous functions _n(x) which is complete in L₂ (0, 1), and a sequence of numbers b_n(0< b_na_n) are constructed such that _n=1 ^Emphasis> b_nn(x)= everywhere on (0, 1).Translated from Matematicheskie Zametki, Vol. 11, No. 5, pp. 499–508, May, 1972.     

The Laplacian with Robin Boundary Conditions on Arbitrary Domains

Using a capacity approach, we prove in this article that it is always possible to define a realization of the Laplacian on L ²() with generalized Robin boundary conditions where is an arbitrary open subset of R ⁿ and is a Borel measure on the boundary of . This operator generates a sub-Markovian C ₀-semigroup on L ²(). If d=d where is a strictly positive bounded Borel measurable function defined on the boundary and the (n–1)-dimensional Hausdorff measure on , we show that the semigroup generated by the Laplacian with Robin boundary conditions has always Gaussian estimates with modified exponents. We also obtain that the spectrum of the Laplacian with Robin boundary conditions in L ^p () is independent of p[1,). Our approach constitutes an alternative way to Daners who considers the (n–1)-dimensional Hausdorff measure on the boundary. In particular, it allows us to construct a conterexample disproving Daners' closability conjecture.     

Number of no nisomorphic subgraphs in an n-point graph

LetG(n) be the set of all nonoriented graphs with n enumerated points without loops or multiple lines, and let v_k(G) be the number of mutually nonisomorphic k-point subgraphs of G G(n). It is proved that at least |G(n)| (1–1/n) graphs G G(n) possess the following properties: a) for any k [6log₂n], where c=–c log₂c–(1–c)×log₂(1–c) and c>1/2, we havev _k(G) > C _n ^k (1–1/n²); b) for any k [cn + 5 log₂n] we havev _k(G) = C _n ^k . Hence almost all graphs G G(n) containv(G) 2ⁿ pairwise nonisomorphic subgraphs.Translated from Matematicheskie Zametki, Vol. 9, No. 3, pp. 263–273, March, 1971.     

On the lower Markov spectrum

C. Hightower found two infinite sequences of gaps in the Markov spectrum, ( _n , _n ) and ( _n , _n ) with _n and _n both Markov elements, converging to . This paper exhibits Markov elements _n ^* and _n ^* such that, for alln 1, ( _n ^* , _n ) and ( _{n n} ^* ) are gaps in the Markov spectrum. Other results include showing that, for alln 1, _n is completely isolated, while the other endpoints of the gaps are limit points in the Markov spectrum.     

Asymptotic limit law for the close approach of two trajectories in expanding maps of the circle

Summary Given two pointsx, yS ¹ randomly chosen independently by a mixing absolutely continuous invariant measure of a piecewise expanding and smooth mapf of the circle, we consider for each >0 the point process obtained by recording the timesn>0 such that |f ⁿ (x)–f ⁿ (y)|. With the further assumption that the density of is bounded away from zero, we show that when tends to zero the above point process scaled by –1 converges in law to a marked Poisson point process with constant parameter measure. This parameter measure is given explicity by an average on the rate of expansion off.Partially supported by FAPESP grant number 90/3918-5     

Verschärfung einer Ungleichung von Ky Fan

Summary In this paper we prove the following:IfA _n ,G _n andH _n (resp.A _n ,G _n andH _n ) denote the arithmetic, geometric and harmonic means ofa ₁,, a _n (resp. 1 –a ₁,, 1 –a _n ) and ifa _i (0, 1/2],i = 1,,n, then(G _n /G _n ) ⁿ (A _n /A _n ) ^n-1 H _n /H _n , (^*) with equality holding forn = 1,2. Forn 3 equality holds if and only ifa ₁ = =a _n . The inequality (^*) sharpens the well-known inequality of Ky Fan:G _n /G _n A _n /A _n .

     

Nilpotent commuting varieties of reductive Lie algebras

Let G be a connected reductive algebraic group over an algebraically closed field k of characteristic p0, and =LieG. In positive characteristic, suppose in addition that p is good for G and the derived subgroup of G is simply connected. Let =() denote the nilpotent variety of , and ^nil():={(x,y)×|[x,y]=0}, the nilpotent commuting variety of . Our main goal in this paper is to show that the variety ^nil() is equidimensional. In characteristic 0, this confirms a conjecture of Vladimir Baranovsky; see [2]. When applied to GL(n), our result in conjunction with an observation in [2] shows that the punctual (local) Hilbert scheme _n Hilb ⁿ (²) is irreducible over any algebraically closed field. Mathematics Subject Classification (2000) 20G05     

An n-Dimensional Hahn-Banach Extension Theorem and Minimal Projections

Let T~=_i=1 ⁿ _irv_i:V V=[v₁,. . . .,v_n] X, where _i V* and X is a Banach space. Let T= _i=1 ⁿu_iv_i: X V be an extension of T~ to all of X (i.e., u_i X*) such that T has minimal (operator) norm. (E.g., if T~=I, T is a minimal projection from X onto V.) Then it is necessary and sufficient that u:=u_1,. . . ,u_n is given by (v:=v₁,. . . ,v_n)ext_v(u) Vⁿ,where the notion of a v-extremal (ext_v) of u is properly defined.The condition above leads in many important cases to a simple geometric interpretation of minimal projections. Furthermore, by applying this formula to the case X=L^p, we obtain a linear n-dimensional analog of the Hölder equality condition (M is given by ext_v(u)=Mv)1/p u · Mv = 1/q u · Mv,wherever v is differentiable.We point out several applications, including the determination of the absolute projection constant of _n ^p      

A superfast algorithm for multi-dimensional Padé systems

For a vector ofk+1 matrix power series, a superfast algorithm is given for the computation of multi-dimensional Padé systems. The algorithm provides a method for obtaining matrix Padé, matrix Hermite Padé and matrix simultaneous Padé approximants. When the matrix power series is normal or perfect, the algorithm is shown to calculate multi-dimensional matrix Padé systems of type (n ₀,...,n _k ) inO(n · log²n) block-matrix operations, where n=n ₀+...+n _k . Whenk=1 and the power series is scalar, this is the same complexity as that of other superfast algorithms for computing Padé systems. Whenk>1, the fastest methods presently compute these matrix Padé approximants with a complexity ofO(n²). The algorithm succeeds also in the non-normal and non-perfect case, but with a possibility of an increase in the cost complexity.Supported in part by NSERC grant No. A8035.Partially supported by NSERC operating grant No. 6194.     

Characterizations of logA≥logB and normaloid operators via Heinz inequality

In 1951, Heinz showed the following useful norm inequality:If A, B0and XB(H), then AXB ^r X^1–r A ^r XB ^r holds for r [0, 1]. In this paper, we shall show the following two applications of this inequality:Firstly, by using Furuta inequality, we shall show an extension of Cordes inequality. And we shall show a characterization of chaotic order (i.e., logAlogB) by a norm inequality.Secondly, we shall study the condition under which , where is Aluthge transformation ofT. Moreover we shall show a characterization of normaloid operators (i.e.,r(T)=T) via Aluthge transformation.     

Fibred links and a construction of real singularities via complex geometry

This note gives a method for constructing real analytic maps from ²ⁿ into ², with an isolated critical point at 0 ²ⁿ , for alln>1. This provides infinite families of real singularities which fiber a la Milnor.Research partially supported by CONACYT, Mexico, grant 1206-E92103.     

Infinitesimal obstructions to weakly mixing

Let ^t be the flow (parametrized with respect to arc length) of a smooth unit vector field v on a closed Riemannian manifold M ⁿ , whose orbits are geodesics. Then the (n-1)-plane field normal to v, v, is invariant under d ^t and, for each x M, we define a smooth real function _x (t) : (1 + _i (t)), where the _i(t) are the eigenvalues of AA ^T, A being the matrix (with respect to orthonormal bases) of the non-singular linear map d^2t , restricted to v at the point _x ^-t M ⁿ.Among other things, we prove the Theorem (Theorem II, below). Assume v is also volume preserving and that _x ^' (t) 0 for all x M and real t; then, if _x ^t : M M is weakly missng for some t, it is necessary that vx 0 at all x M.     

A chord-stretching map of a convex loop is an isometry

Let ⁿ be n-dimensional Euclidean space, and let : [0, L] ⁿ and : [0, L] ⁿ be closed rectifiable arcs in ⁿ of the same total length L which are parametrized via their arc length. is said to be a chord-stretched version of if for each 0s tL, |(t)–(s)| |(t)–(s)|. is said to be convex if is simple and if ([0, L]) is the frontier of some plane convex set. Individual work by Professors G. Choquet and G. T. Sallee demonstrated that if were simple then there existed a convex chord-stretched version of . This result led Professor Yang Lu to conjecture that if were convex and were a chord-stretched version of then and would be congruent, i.e. any chord-stretching map of a convex arc is an isometry. Professor Yang Lu has proved this conjecture in the case where and are C ² curves. In this paper we prove the conjecture in general.