Multi-Faithful Spanning Trees of Infinite Graphs

For an end and a tree T of a graph G we denote respectively by m() and m _T () the maximum numbers of pairwise disjoint rays of G and T belonging to , and we define tm() := min{m _T(): T is a spanning tree of G}. In this paper we give partial answers — affirmative and negative ones — to the general problem of determining if, for a function f mapping every end of G to a cardinal f() such that tm() f() m(), there exists a spanning tree T of G such that m _T () = f() for every end of G.     

On the asymptotic behaviour of first passage times for transient random walk

Summary Let _x denote the time at which a random walk with finite positive mean first passes into (x, ), wherex0. This paper establishes the asymptotic behaviour of Pr { _x >n} asn for fixedx in two cases. In the first case the left hand tail of the step-distribution is regularly varying, and in the second the step-distribution satisfies a one-sided Cramér type condition. As a corollary, it follows that in the first case Pr { _x >n}/Pr{ ₀ >n} coincides with the limit of the same quantity for recurrent random walk satisfying Spitzer's condition, but in the second case the limit is more complicated.     

über straffe Wahrscheinlichkeitsverteilungen im Raum der Schwartzschen Distributionen

Zusammenfassung In den letzten Jahren erschien eine Reihe von Arbeiten, die sich systematisch mit Wahrscheinlichkeitsverteilungen auf topologischen Gruppen, Halbgruppen, topologischen RÄumen und topologischen linearen RÄumen beschÄftigten. Als besonders geeignet für eine topologische Wahrscheinlichkeitstheorie erwiesen sich hierbei die sogenannten straffen (tight) Wahrscheinlichkeitsverteilungen (vgl. Le Cam [3], Hildenbrand [11], Prochoeov [20], Varadarajan [25]).Die vorliegende Arbeit befa\t sich mit straffen Wahrscheinlichkeitsverteilungen im Raum D, dem topologischen Dualraum des Raumes D der auf der reellen Zahlengeraden definierten beliebig oft differenzierbaren Funktionen mit kompaktem TrÄger Tr .Der Ausgangspunkt für die Untersuchung von Zufallselementen mit Werten in linearen RÄumen, die nicht notwendig BanachrÄume sind, war wohl der von GELFAND [8] eingeführte Begriff des verallgemeinerten stochastischen Prozesses (VSP). Solange man bei einem solchen Proze\ Eigenschaften untersucht, die sich mit Hilfe seiner endlichdimensionalen Randverteilungen Q_{1,...,n}, _i D, beschreiben lassen, wird man sich wie im Fall eines gewöhnlichen stochastischen Prozesses natürlich die Frage stellen, ob ein geeigneter Standard-stichprobenraum existiert, etwa der Raum D, so da\ sich jeder VSP auffassen lÄ\t als Wahrscheinlichkeitsverteilung auf einem geeigneten hinreichend umfangreichen -Ring von Teilmengen des Raumes D. Die fundamentale Arbeit von MINLOS [18] gab hierzu die Lösung: Durch ein vertrÄgliches System endlichdimensionaler Wahrscheinlichkeitsverteilungen Q_{1,...,n}, _i D, mit gewissen Eigenschaften, die denen der Randverteilungen eines VSP entsprechen, lÄ\t sich auf dem SystemB der Zylindermengen des Raumes D eine sogenannte schwache Verteilung definieren, von der gezeigt wird, da\ sie -additiv ist. Durch EinschrÄnkung des Raumes der sogenannten Testfunktionen auf den metrisierbaren Teilraum D _K{ D:Tr K, K kompakt in } von D lÄ\t sich dieses Ergebnis wie folgt verschÄrfen: Die durch ein vertrÄgliches System endlichdimensionaler Randverteilungen Q_{1,...,n}, _i D, mit entsprechenden Eigenschaften, auf dem System B _K der Zylindermengen des Raumes D_K definierte schwache Verteilung K ist straff bezüglich der schwachen Topologie (D_K, D_K) in D_K.Die Frage nach der Gültigkeit einer entsprechenden VerschÄrfung für das Dualsystem >DD<, bzw. allgemeiner für ein Dualsystem E, F mit nicht notwendig metrisierbarem F, bildete den Gegenstand neuerer Untersuchungen, über deren Ergebnisse auf dem letzten Berkeley Symposium E. Mourier berichtete (vgl. [19]).Im ersten Kapitel der vorliegenden Arbeit des Verfassers wird demgegenüber eine Methode aufgezeigt, mit deren Hilfe, unter Verwendung des Minlosschen Satzes in seiner ursprünglichen Form, auf direktem Wege für das Dualsystem >D, D< der Nachweis gelingt, da\ eine schwache Verteilung auf B nicht nur -additiv, sondern automatisch straff ist (bzgl. der schwachen Topologie (D, D) in D) und sich somit eindeutig fortsetzen lÄ\t zu einer straffen Wahrscheinlichkeitsverteilung auf dem System 83 der Boreischen Mengen in D, welches den von den Zylindermengen erzeugten -Ring (B) umfa\t. Mit anderen Worten wird damit gezeigt, da\ man jeden VSP auffassen kann als straffe Wahrscheinlichkeitsverteilung auf den Boreischen Mengen in D. Wir sprechen dann auch von einer zufÄlligen Distribution.Im zweiten Kapitel betrachten wir spezielle zufÄllige Distributionen, nÄmlich Normal-verteilungen v, die aus Randverteilungen hervorgehen, welche n-dimensionale Normal-verteilungen sind, und beschÄftigen uns mit dem Problem der Äquivalenz und SingularitÄtzweier Normalverteilungen v₁ und v₂ in D. Für den Fall v₁ = v, v₂= v_{f 0}, wo v_{f 0}(Z) =v(Z – f₀), ZB fD, zeigte DUDLEY [6], da\ entweder Äquivalenz oder SingularitÄt vorliegt, wobei er ein notwendiges und hinreichendes Kriterium für den Fall der Äquivalenz angibt. Aus der Theorie der gewöhnlichen stochastischen Prozesse ist nun bekannt, da\ die beiden Wahrschein-lichkeitsma\e, die zwei beliebigen Gau\schen Prozessen auf dem Raum ihrer Realisierungen entsprechen, entweder Äquivalent oder singular sind. Es lag deshalb nahe, nach einem Kriterium zu suchen, welches es einerseits gestattet, im Fall zweier beliebiger Normalverteilungen v₁ und v₂ in D zu entscheiden, wann Äquivalenz vorliegt, und welches andererseits die naheliegende Vermutung bestÄtigt, da\ für zwei Normalverteilungen in D dieselbe Alternative wie im eben zitierten klassischen Fall vorliegt. Dieses Problem wird gelöst, indem wir zeigen, da\ sich ein von Kallianfur-Oodaira [13] aufgestelltes Kriterium für die Äquivalenz zweier Normalverteilungen auf den Boreischen Mengen eines separablen Hilbertraumes auf den Distributionsraum D übertragen lÄ\t.Im dritten Kapitel beschÄftigen wir uns mit der Frage der Äquivalenz zweier beliebiger (nicht notwendig normaler) Wahrscheinlichkeitsverteilungen in D.Abschlie\end möchte der Autor Herrn Professor Dr. K. Krickeberg (Heidelberg) für die Anregung zu dieser Arbeit sowie für die Unterstützung wÄhrend ihrer Durchführung herzlich danken.     

Opérateurs de mise en mémoire et traduction de Gödel

Résumé En-calcul, la stratégie de réduction à gauche (appel par nom) a, comme on sait, de bonnes propriétés mathématiques; en particulier, elle termine toujours si on l'applique à un terme normalisable. Mais, avec cette stratégie, l'argument d'une fonction est recalculé à chaque utilisation.Pour éviter ce défaut, on définit la notion «d'opérateur de mise en mémoire» (pour un type de données). SiT est un opérateur de mise en mémoire, pour les entiers par exemple, on remplace l'évaluation, par réduction gauche, de (où est un entier et un -terme quelconque) par celle deT; et celle-ci revient à ramener d'abord à une forme réduite ₀, puis à appliquer à ₀. On a donc ainsi simulé «l'appel par valeur» dans la stratégie de réduction à gauche.Le théorème principal (Corollaire du Théorème 4.1) montre que, dans un 1-calcul typé du second ordre, en utilisant la traduction de Gödel de la logique classique en logique intuitionniste, on peut trouver un type (spécification) très simple pour les opérateurs de mise en mémoire. Il donne donc aussi un moyen d'obtenir ces opérateurs, à savoir de démontrer ce type dans le calcul des prédicats intuitionniste du second ordre.

---

In-calculus, the strategy of leftmost reduction (call-by-name) is known to have good mathematical properties; in particular, it always terminates when applied to a normalizable term. On the other hand, with this strategy, the argument of a function is re-evaluated at each time it is used.To avoid this drawback, we define the notion of storage operator, for each data type. IfT is a storage operator for integers, for example, let us replace the evaluation, by leftmost reduction, of (where is an integer, and any-term) by the evaluation oft. Then, this computation is the same as the following: first compute up to some reduced form ₀, and then apply to ₀. So, we have simulated call-by-value evaluation within the strategy of leftmost reduction.The main theorem of the paper (Corollary of Theorem 4.1) shows that, in a second order-calculus, using Gödel's translation of classical intuitionistic logic, we can find a very simple type (or specification) for storage operators. Thus, it gives a way to get such operators, which is to prove this type in second order intuitionistic predicate calculus.

     

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.

     

Discrete Spectrum of Differential Operators in Spectral Gaps under Nonnegative Perturbations of High Order

Let A be a self-adjoint elliptic second-order differential operator, let (, ) be an inner gap in the spectrum of A, and let B(t) = A + tW ^* W, where W is a differential operator of higher order. Conditions are obtained under which the spectrum of the operator B(t) in the gap (, ) is either discrete, or does not accumulate to the right-hand boundary of the spectral gap, or is finite. The quantity N(, A, W, ), (, ), > 0 (the number of eigenvalues of the operator B(t) passing the point (, ) as t increases from 0 to ) is considered. Estimates of N(, A, W, ) are obtained. For the perturbation W ^* W of a special form, the asymptotics of N(, A, W, ) as + is given. Bibliography: 5 titles.     

Algebraic Properties of the Mikusiński Convolution Algebra

Let M be the space of all continuous, complex valued functions defined on [0, ]. This, with the convolution operation (^f*g)(t) = ₀ ^{t f}(t–)g() d yields a commutative, associative algebra. A new proof that M is a Jacobson radical algebra is given. The ideal structures of M and its Dorroh extension to an algebra, M¹, with unity are investigated. The algebraic properties of M are used to obtain new proofs of existence and uniqueness of solutions for certain integral and integro-differential equations.     

Stability and uniqueness of the solution of the inverse kinematic problem of seismology in higher dimensions

The following inverse kinematic problem of seismology is considered. In the compact domain M of dimension ,2 with the metric, we consider the problem of constructing a new metricdu=nds according to the known formula where ,M and K_, is the geodesic in the metric du, connecting the points , . One proves uniqueness and one obtains a stability estimate, where the refraction indices n₁, n₂ are the solutions of the inverse kinematic problem, constructed relative to the functions ₁, ₂, respectively, is the differential form on M×Mwhere =₂–₁,.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akad. Nauk SSSR, Vol. 84, pp. 3–6, 1979.     

Isometries of symmetric operator spaces associated with AFD factors of typeII and symmetric vector-valued spaces

If is a surjective isometry of the separable symmetric operator spaceE(M, ) associated with the approximately finite-dimensional semifinite factorM and if · _E(M,) is not proportional to · _{L 2}, then there exist a unitary operatorUM and a Jordan automorphismJ ofM such that(x)=UJ(x) for allxME(M, ). We characterize also surjective isometries of vector-valued symmetric spacesF((0, 1), E(M, )).Research supported by the Australian Research Council     

Hypercubic 4 and 5-Designs from Double-Error-Correcting BCH Codes

An ordered orthogonal array OOA(, k, n) is a binary 2 ^k × n matrix with the property that for each complete -set of columns, each possible -tuple occurs in exactly 2 ^k– rows of those columns (for definition of a complete -set, see below). Constructions of OOA(, k, n) for = 4 and = 5 are given.     

Multi-E-Reflective and Bireflective Subcategories of Partial Algebras

A category PAlg() of partial algebras of a given type will be introduced. Then we will present a categorical concept in order to characterize those subcategories of PAlg(), which are closed under the formation of various kinds of subobjects. We will also give a characterization for bireflective subcategories of PAlg(), which enables us to show, that the subcategory Alg() consisting of all total algebras of type is the smallest bireflective subcategory of PAlg().     

An explicit solution of the linear filtering problem for certain classes of nonrational spectral densities

We present an explicit solution of the problem of optimal linear filtering: the recovery of the useful signal(s) at the instantt+, (>0,<0, or=0) from known values of the received signal(s)=(s)+(s) in the past, i.e., at the instantt–s, s0. In doing so we assume the random processes(s) and /gr(s) are stationary and jointly stationary, while the stationary process of noise (s) with zero mean is assumed to be mutually correlated and jointly stationary with the process(s) under the assumption that there exists a common spectral densityf() for these processes.Translated fromTeoriya Sluchaínykh Protsessov, Vol. 14, pp. 83–91, 1986.     

Base drag effects on maximum lift-to-drag ratio airfoils at moderate supersonic speeds

Maximum lift-to-drag ratio airfoils at moderate supersonic speeds are determined using Ackeret's linear theory for the forebody pressure coefficient and Chapman's experimental results for the base pressure coefficient. Two cases are investigated for both laminar flow and turbulent flow: (i) given length and thickness and (ii) given length and enclosed area.For case (i), it is shown that the maximum lift-to-drag ratio airfoil is identical with the minimum drag airfoil. Furthermore, for turbulent flow and given Mach number and Reynolds number, two critical values of the thickness ratio exist, ₁ and ₂. For ₁, the optimum airfoil is a diamond shape with a closed trailing edge and exhibits maximum thickness at midchord; for ₁₂, the optimum airfoil is a diamond shape with a blunt trailing edge and exhibits maximum thickness between midchord and the trailing edge; finally, for ₂, the optimum airfoil is a wedge and exhibits maximum thickness at the trailing edge.For case (ii), it is shown that the maximum lift-to-drag ratio is identical with the minimum drag airfoil. Furthermore, for turbulent flow and given Mach number and Reynolds number, a critical value (A/l ²)₁ of the enclosed area ratio exists. ForA/l ²(A/l ²)₁, the optimum airfoil is biconvex with a closed trailing edge and exhibits maximum thickness at midchord; forA/l ²(A/l ²)₁, the optimum airfoil is biconvex with a blunt trailing edge and exhibits maximum thickness between midchord and the trailing edge.This research, supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-828-67, is a condensed version of the investigations described in Refs. 1–2. The author would like to thank Dr. Angelo Miele for suggesting the problem and helpful discussions.     

The Discrete Spectrum Asymptotics with Respect to a Large Coupling Constant under Strong Nonnegative Perturbations

Let A be a self-adjoint operator, let (, ) be an inner gap in the spectrum of the operator A, and let B(t) = A + tW ^* W, where the operator W(A – iI)^-1 is not necessarily bounded. Conditions are obtained under which the spectrum of B(t) in (, ) is discrete. Let N(, A, W, ), (, ), > 0, be the number of eigenvalues of the operator B(t) passing the point (, ) as t increases from 0 to . The asymptotics of N(, A, W, ) as + is obtained in terms of the spectral asymptotics of a certain self-adjoint compact operator. Bibliography: 5 titles.     

τ-Pseudocompact Mappings

We consider the problem of extending the notion of -pseudocompactness from spaces to continuous mappings, obtain conditions under which the product of -pseudocompact mappings is -pseudocompact. Since any space X can be considered as a continuous mapping from X into a singleton, we obtain consequences of the theorems on multiplicativity of -pseudocompactness for spaces. Thus, we study the notion of -pseudocompact mapping and some its properties similar to those of a pseudocompact space as well as consequences of the obtained assertions for spaces.     

Note on initial topologies on rational vector spaces induced by realvalued linear mappings

LetG be a vector space over the field of rational numbers andf, g:G -linear mappings. equipped with the usual norm topology. Denote by _f , _g the initial topologies onG induced byf respectivelyg.Then the following result holds: If there is a nonvoid open setU whose complement contains at least one inner point such thatf ^–1 U _g , then there is ac withf=cg. In particular, iff0, the topologies coincide.Furthermore, a -linear mappingh: (G, _f )(G, _g ) is continuous if and only if there is a real constantc withg ^o h=cf.Dedicated to Professor János Aczél on his 60th birthday     

Modular Transformations of Ramanujan's Fifth and Seventh Order Mock Theta Functions

In his last letter to Hardy, Ramanujan defined 17 functions F(q), where |q| < 1. He called them mock theta functions, because as q radially approaches any point e ^2ir (r rational), there is a theta function F _r(q) with F(q) – F _r(q) = O(1). In this paper we obtain the transformations of Ramanujan's fifth and seventh order mock theta functions under the modular group generators + 1 and –1/, where q = e ⁱ. The transformation formulas are more complex than those of ordinary theta functions. A definition of the order of a mock theta function is also given.     

Über den algorithmischen Nachweis von Ungleichungen I

We shall develop a method to prove inequalities in a unified manner. The idea is as follows: It is quite often possible to find a continuous functional : ⁿ , such that the left- and the right-hand side of a given inequality can be written in the form (u)(v) for suitable points,v=v(u). If one now constructs a map ^{n n} , which is functional increasing (i.e. for each x ⁿ (which is not a fixed point of ) the inequality (x)<((x)) should hold) one specially gets the chain (u)( u))( ²(u))... ⁿ (u)). Under quite general conditions one finds that the sequence { ⁿ (u)} _n converges tov=v(u). As a consequence one obtains the inequality (u)(v).     

Asymptotic Formulae and Divisor Problems

We investigate the asymptotic behaviour of the summatory functions of _z(n, ), _k(n, ) z ⁽ⁿ⁾ and _k(n, ) z ⁽ⁿ⁾.     

Spectral methods in arithmetic problems

Combining ideas of convolution due to Rankin with spectral considerations of Selberg, the author proposes a new approach to obtaining mean values for certain number-theoretic functions f(n). This approach is illustrated for the examples of functions f(n)=(Mn²+N),(n)(Mn+N), where (n) is the number of divisors of n.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 76, pp. 159–166, 1978.