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     

On the complexity of approximating a KKT point of quadratic programming

We present a potential reduction algorithm to approximate a Karush—Kuhn—Tucker (KKT) point of general quadratic programming (QP). We show that the algorithm is a fully polynomial-time approximation scheme, and its running-time dependency on accuracy (0, 1) is O((l/) log(l/) log(log(l/))), compared to the previously best-known result O((l/)²). Furthermore, the limit of the KKT point satisfies the second-order necessary optimality condition of being a local minimizer. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research support in part by NSF grants DDM-9207347 and DMI-9522507, and the Iowa Business School Summer Grant.     

Criticality in a model for thermal ignition in three or more dimensions

An explicitly resolvable model, which was instroduced in a previous paper (see [1]), is used to obtain exact behaviour of its bifurcation curves. The model closely approximates the true Arrhenius law for a spherical vessel of reacting material undergoing an exothermic reaction in three or more dimensions. For a sequence of values of a parameter, which is the reciprocal of the dimensionless activation energy, the number of the solutions changes for certain values of the eigenparameter Further, there exist solutions for all then is non-zero.

---

Zusammenfassung Mit Hilfe eines explizit lösbaren Modells, das in einer früheren Arbeit eingeführt wurde (siehe [1]), erhält man das exakte Verhalten der zugehörigen Verzweigungskurven. Das Modell approximiert gut das Arrheniussche Gesetz für exotherme Reaktionen in einem sphärischen Topf in drei oder mehr Dimensionen. Für eine Folge von Werten des Parameters, welches als Reziproke der dimensionslosen Aktivierungsenergie dient, ändert sich die Anzahl der Lösungen zum Eigenwert, der durch gesteuert wird. Weiter gibt es für alle mindestens eine Lösung, sofern 0 gilt.

---

---

Supported in part by the Deutsche Forschungsgemeinschaft and in part by the Victoria University of Wellington Fellowship Committee.     

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.     

A general minimax theorem

This paper is concerned with minimax theorems for two-person zero-sum games (X, Y, f) with payofff and as main result the minimax equality inf supf (x, y)=sup inff (x, y) is obtained under a new condition onf. This condition is based on the concept of averaging functions, i.e. real-valued functions defined on some subset of the plane with min {x, y}< (x, y)x, y} forx y and (x, x)=x. After establishing some simple facts on averaging functions, we prove a minimax theorem for payoffsf with the following property: Forf there exist averaging functions and such that for any x₁, x₂ X, > 0 there exists x₀ X withf (x₀, y) > f (x₁,y),f (x₂,y))– for ally Y, and for any y₁, y₂ Y, > 0 there exists y₀ Y withf (x, y₀) (f (x, y₁),f (x, y₂))+. This result contains as a special case the Fan-König result for concave-convex-like payoffs in a general version, when we take linear averaging with (x, y)=x+(1–)y, (x, y)=x+(1–)y, 0 <, < 1.Then a class of hide-and-seek games is introduced, and we derive conditions for applying the minimax result of this paper.

---

Zusammenfassung In dieser Arbeit werden Minimaxsätze für Zwei-Personen-Nullsummenspiele (X, Y,f) mit Auszahlungsfunktionf behandelt, und als Hauptresultat wird die Gültigkeit der Minimaxgleichung inf supf (x, y)=sup inff (x, y) unter einer neuen Bedingung an f nachgewiesen. Diese Bedingung basiert auf dem Konzept mittelnder Funktionen, d.h. reellwertiger Funktionen, welche auf einer Teilmenge der Ebene definiert sind und dort der Eigenschaft min {x, y} < < (x, y)x, y} fürx y, (x, x)=x, genügen. Nach der Herleitung einiger einfacher Aussagen über mittelnde Funktionen beweisen wir einen Minimaxsatz für Auszahlungsfunktionenf mit folgender Eigenschaft: Zuf existieren mittelnde Funktionen und, so daß zu beliebigen x₁, x₂ X, > 0 mindestens ein x₀ X existiert mitf (x₀,y) (f (x ₁,y),f (x₂,y)) – für alley Y und zu beliebigen y₁, y₂ Y, > 0 mindestens ein y₀ Y existiert mitf (x, y₀) (f (x, y₁),f (x, y ₂))+ für allex X. Dieses Resultat enthält als Spezialfall den Fan-König'schen Minimaxsatz für konkav-konvev-ähnliche Auszahlungsfunktionen in einer allgemeinen Version, wenn wir lineare Mittelung mit (x, y)=x+(1–)y, (x, y)= x+(1–)y, 0 <, < 1, betrachten.Es wird eine Klasse von Suchspielen eingeführt, welche mit dem vorstehenden Resultat behandelt werden können.

     

An isolation theorem for decomposable forms of purely real algebraic fields of degree n⩾3

Let M be a complete module of a purely algebraic field of degree n3, let be the lattice of this module and let F(X) be its form. By we denote any lattice for which we have = , where is a nondiagonal matrix satisfying the condition ¦-I¦ , I being the identity matrix. The complete collection of such lattices will be denoted by {}. To each lattice we associate in a natural manner the decomposable form F(X). The complete collection of forms, corresponding to the set {}, will be denoted by {F} It is shown that for any given arbitrarily small interval (N–, N+), one can select an such that for each F(X) from {F} there exists an integral vector X₀ such that N– < F(X₀) < N+.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 112, pp. 167–171, 1981.     

Local Stochastic Channeling Theory: Kinetic Functions in the Case of Interaction Between Fast Particles and Lattice Atoms

We investigate the motion of high-energy particles in a crystal with regard to their interaction with the thermal vibrations of the lattice atoms using analytic methods in the theory of Markov processes including the local Fokker–Planck equation. We construct a local matrix of random actions, which is used to introduce the main kinetic functions in the traverse-energy space, namely, the function a() of energy losses due to the dynamic friction and the diffusion function b(). We show that the singularities of the functions a() and b() are related to the distinction between the contributions to the kinetics from particles moving in three different regimes, namely, in the channeling, quasichanneling, and chaotic motion modes.     

Periodic solutions of singularly perturbed delay equations

We consider a general class of singularly perturbed delay differential systems depending on a singular parameter and another parameter . For =0, the equation defines a mapT which undergoes a generic period doubling at =0. If the bifurcation is supercritical (subcritical), these period two points define a stable period two square wave (unstable period two pulse wave). We give conditions on the vector field such that there is a sectorS in the , plane such that there is a unique periodic orbit if the parameters are inS, the orbit is stable (unstable) if the period doubling bifurcation is supercritical (subcritical) and approaches the square (pulse) wave as 0.Partially supported by NSF and DARPA.     

Comparison of Normal Linear Experiments by Quadratic Forms

Let X and Y be observation vectors in normal linear experiments =N(A, V) and F = N(B, W). We write > Fif for any quadratic form YGY there exists a quadratic formXHX such that E(XHX) = E(Y'GY) and var(X'HX) var(Y'GY).The relation > is characterized by the matrices A, B, V and W. Moreoversome connections with known orderings of linear experiments are given.     

Estimates of the asphericity of sections of convex bodies

We define the function (n, k) to be the infimum of all such that any bounded centrally symmetric convex body inR ⁿ possesses an -asphericalk-dimensional central section. It is proved that (3, 2)=2–1 and (n, n-1)n-1-1. Several related functions are defined and their values on the pairs (n, n-1) are estimated.Translated from Ukrainskií Geometricheskií Sbornik, Issue 28, 1985, pp. 76–79.     

Almost Fredholm operators in von Neumann algebras

LetA be a von Neumann algebra,J be the ideal of compact operators relative toA and letF ₊ be the left-Fredholm class ofA. We call almost left-Fredholm the class = {A A: if P A is a projection and AP J then P J}. Then and the inclusion is proper unlessA is semifinite and has a non-large center. satisfies all of the algebraic properties ofF ₊ but it is generally not open. IfA is semifinite then A iff there are central projectionsG with G = I such that AG F₊(AG). Let :A A/J. Then the left almost essential spectrum ofA A, , coincides with the set of eigenvalues of (A)     

Inverse power law potentials in rectangular configurations

Summary Calculations based on a (distance)^– intermolecular potential (>3) enable study of the effects on adsorption of the geometry of the solid. This paper gives the closed form solution for the adsorptive potential about a homogeneous solid rectangular corner; and, through systematic superposition, closed form solutions for the following configurations also: the rectangular corner of a cavity; laminae and rectangular cracks occupying a quarter plane; semi-infinite rectangular prisms and prismatic cavities; rectangular parallelepipeds and brick-shaped cavities. These various results are developed in detail for the cases =6 and =4. The paradox that potentials for >3 seem to be obtainable more readily than Newtonian potentials (=1) is explained by the existence only for >3 of simple fundamental solutions for infinite homogeneous solid configurations.

---

Zusammenfassung Berechnungen, denen ein intermolekulares Potential der Form (Abstand)^– (>3) zugrunde gelegt ist, ermöglichen eine Untersuchung von Effekten der Adsorption auf die Geometrie des Festkörpers. Die vorliegende Arbeit gibt die Lösung in geschlossener Form für das Adsorptionspotential um eine feste, homogene, rechtwinklige Ecke an. Ausserdem werden durch systematische Superposition Lösungen in geschlossener Form für die folgenden Konfigurationen angegeben: die rechtwinklige Innenecke einer Mulde; viertelunendliche, ebene Platten und rechteckige Spalten; halbunendliche, reckteckige Prismen und prismatische Mulden; Quader und quaderförmige Höhlen. Diese Ergebnisse sind ausführlich dargestellt für die Fälle =4. Das Paradoxon. dass Potentiale mit >3 scheinbar leichter zugänglich sind als das Gravitationspotential (=1), wird dadurch erklärt, dass nur für >3 einfache Grundlösungen für unendliche, homogene Festköperkonfigurationen existieren.

     

Normal forms for vector fields with respect to an arbitrary dilation

Homogenous vector fields of degree one with respect to an arbitrary dilation ^r may be regarded as a natural extension of the linear vector fields. This paper is concerned with the problem of computing normal forms for vector fields that can be expanded in terms of homogeneous fields of degree greater than or equal to one with respect to an arbitrary dilation ^r . In particular, necessary and sufficient conditions are given for the existence of a local coordinate change that transforms an analytic field into a homogeneous field of degree one with respect to an arbitrary dilation ^r .This research was partially supported by National Science Foundation (Grant DMS-9301039), and by Istituto Nazionale di Alta Matematica F. Severi.     

The correctness problem for best approximations by trigonometric polynomials in the class W o r H[ω]C

Suppose thatk, rz₊, W _o ^r H[]_C= {ff is a 2-periodic function,f C^r [–, ], (f^(r), ) ()}, T_k is the space of trigonometric polynomials of order k, p_k(f)T_k is the polynomial of best uniform approximation to f, and E_k(f) is the error of the best approximation. It is shown that for an arbitrary > 0 we have,where for 0<&#x2A7D;(1),k > 0.R () is the root of the equation , and for k = 0 or > (1) we have R()=.Translated from Matematicheskie Zametki, Vol. 22, No. 1, pp. 85–101, July, 1977.The author thanks S. B. Stechkin for posing the problem and for his attention to this work.     

S-Continued Fraction Method for the Investigation of a Complex Dielectric Constant of Two-Components Composite

The aim of this contribution is to examine the S-continued fraction method of obtaining bounds on the effective dielectric constant _e of a two-phase composite for the case where the dielectric coefficients ₁and ₂ of both components are either complex or real. The starting point for our study is a power expansion of _e (z) at(z)=0 (z)=₂/₁-1. The obtained S-continued fraction bounds have an interesting mathematical structure convenient for theoretical and numerical investigations of _e. They also agree with the earlier estimations reported by Bergman and Milton. Specific examples of calculation of bounds on _e by theS-continued fraction method are also provided.     

Asymptotic behavior of the solution of an elliptic boundary value problem in a thin domain

The asymptotic behavior as h0 of the solution of a mixed boundary value problem is investigated for an elliptic (in the sense of Petrovskii) system of second-order differential equations in the n-dimensional cylinder Q _h =×(–h/2, h/2) of small altitude h; is a domain in R ⁿ –1. The limit problem in contains a small parameter =h , (0, 1), for higher-order derivatives and degenerates regularly, as 0, into an elliptic problem of a lower order. It is shown that the limit problem and its corresponding degenerate problem (=0) are uniquely solvable. An estimate for the difference of solutions of the original and the limit problem in the energy norm is established. As an example, a problem on the deformation of a thin plate in the framework of the Cosserat continuum is considered.Translated from Problemy Matematicheskogo Analiza, No. 11, pp. 191–208, 1990.     

Homogenization of a Singularly Perturbed Parabolic Problem in a Thick Periodic Junction of the Type 3:2:1

We prove a convergence theorem and obtain asymptotic (as 0) estimates for a solution of a parabolic initial boundary-value problem in a junction that consists of a domain ₀ and a large number N ² of -periodically located thin cylinders whose thickness is of order = O(N ^–1).     

A finite element method for a singularly perturbed boundary value problem

Summary We examine the problem:u+a(x)u–b(x)u=f(x) for 0<x<1,a(x)>0,b(x)>, ² = 4>0,a, b andf inC ² [0, 1], in (0, 1],u(0) andu(1) given. Using finite elements and a discretized Green's function, we show that the El-Mistikawy and Werle difference scheme on an equidistant mesh of widthh is uniformly second order accurate for this problem (i.e., the nodal errors are bounded byCh ², whereC is independent ofh and ). With a natural choice of trial functions, uniform first order accuracy is obtained in theL (0, 1) norm. On choosing piecewise linear trial functions (hat functions), uniform first order accuracy is obtained in theL ¹ (0, 1) norm.     

Isolation theorem for forms corresponding to purely real algebraic fields

Let M be the complete module of a purely real algebraic field of degree n 3, let be a lattice in this module, and let F(X) be its form. We use to denote any lattice for which we have = , where is a nondiagonal matrix for which – I . With each lattice we can associate a factorizable formF (X) in a natural manner. We denote the complete set of forms corresponding to the set {} by {F (X)}. It is proved that for any > 0 there exists an > 0 such that for eachF (X) {F } we have |F (X₀₎| for some integer vector X₀ 0.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 185, pp. 5–12, 1990.In conclusion, the author would like to express his deep gratitude to B. F. Skubenko for stating the problem and for his constant attention.     

Large deviations for the invariant measure of a reaction-diffusion equation with non-Gaussian perturbations

Summary In this paper we establish a large deviations principle for the invariant measure of the non-Gaussian stochastic partial differential equation (SPDE) _t v =v +f(x,v )+(x,v ) . Here is a strongly-elliptic second-order operator with constant coefficients, h:=DH _xx-h, and the space variablex takes values on the unit circleS ¹. The functionsf and are of sufficient regularity to ensure existence and uniqueness of a solution of the stochastic PDE, and in particular we require that 0<mM wherem andM are some finite positive constants. The perturbationW is a Brownian sheet. It is well-known that under some simple assumptions, the solutionv ² is aC ^k (S ¹)-valued Markov process for each 0<1/2, whereC (S ¹) is the Banach space of real-valued continuous functions onS ¹ which are Hölder-continuous of exponent . We prove, under some further natural assumptions onf and which imply that the zero element ofC (S ¹) is a globally exponentially stable critical point of the unperturbed equation _t ⁰ = ⁰ +f(x,⁰), that has a unique stationary distributionv ^K, on (C (S ¹), (C ^K (S ¹))) when the perturbation parameter is small enough. Some further calculations show that as tends to zero,v ^K, tends tov ^K,0, the point mass centered on the zero element ofC (S ¹). The main goal of this paper is to show that in factv ^K, is governed by a large deviations principle (LDP). Our starting point in establishing the LDP forv ^K, is the LDP for the process , which has been shown in an earlier paper. Our methods of deriving the LDP forv ^K, based on the LDP for are slightly non-standard compared to the corresponding proofs for finite-dimensional stochastic differential equations, since the state spaceC (S ¹) is inherently infinite-dimensional.This work was performed while the author was with the Department of Mathematics, University of Maryland, College Park, MD 20742, USA