Kleine Nullstellen homogener quadratischer Gleichungen

Let 0 be a real quadratic form inn variables, which takes on integral values on ⁿ . Denote by the largest coefficient of in absolute value. Suppose vanishes on ad-dimensional rational subspace. It is shown that has a zero (x ₁,...,x _n ⁿ \{(0,...,0)} with max |x _i ^(n-d/2d).     

On the Approximation of Certain Mass Distributions Appearing in Distance Geometry

Let X be a compact subset of the n-dimensional Euclidean space R ⁿ . A theorem of G. Björck implies the existence of a unique probability measure ₀ which maximizes the value _{X X} d ₂(x, y) d(x) d(y), where ranges over all probability measures on X and d ₂ denotes the Euclidean distance on R ⁿ . In this paper we introduce and investigate an algorithm which is easy to describe and which inductively constructs a sequence = x ₁, x ₂,... in X such that is uniformly distributed with respect to ₀. Geometrical and topological interpretations and applications, and concrete numerical examples are given.     

Extended Classical Asymptotic Expansions in the Case of Gaussian Limit Distribution

Let X, X ₁, X ₂,... be a sequence of independent and identically distributed random variables with common distribution function F. Denote by F _n the distribution function of centered and normed sum S _n . Let F belong to the domain of attraction of the standard normal law , that is, lim F _n (x)= (x), as n , uniformly in x . We obtain extended asymptotic expansions for the particular case where the distribution function F has the density p(x) = cx ^––1 ln(x), x > r, where 2, , c > 0, and r > 1. We write the classical asymptotic expansion (in powers of n ^–1/2) and then add new terms of orders n ^–/2 ln n, n ^–/2 ln^-1 n, etc., where 0.     

Bestimmung der Eigenwerte und Eigenvektoren einer Matrix mit Hilfe des Quotienten-Differenzen-Algorithmus

Summary Two previous papers (in Vol. V) describe theory and some applications of the quotient-difference (=QD-) algorithm. Here we give an extension which allows the determination of the eigenvectors of a matrix. Letx ₍₀₎ ¹ , ...,x ₍₀₎ ⁿ be a coordinate system in whichA has Jacobi form (such a system may be constructed with methods ofC. Lanczos orW. Givens). Then the QD-algorithm allows the construction of a sequence of coordinate systemsx ₍₂₎ ¹ , ...,x ₍₂₎ ⁿ , (=0, 1, 2, ...) which converge for to the system of the eigenvectors ofA.     

A Bernstein Property of Affine Maximal Hypersurfaces

Let x: M A ^{n + 1} be a locally strongly convex hypersurface, given as a graph of a locally strongly convexfunction x _{n + 1} =f(x ₁, ..., x _n )defined in a domain A ⁿ . We introduce a Riemannian metricG ^# = (² f/x _i x _j )dx _i dx _j on M. In this paper, we investigate the affine maximalhypersurfaces which are complete with respect to the metricG ^# and prove a Bernstein property for the affine maximalhypersurfaces.     

On the Embedding of an Affine Space into a Projective Space

Let k, K be fields, and assume that |k| 4 and n, m 2, or |k| = 3 and n 3, m 2. Then, for any embedding of AG(n, k) into PG(m, K), there exists an isomorphism from k into K and an (n+1) × (m+1) matrix B with entries in K such that can be expressed as (x₁,x₂,...,x_n) = [(1,x₁ ,x₂ ,...,x_n )B], where the right-hand side is the equivalence class of (1,x₁ ,x₂ ,...,x_n )B. Moreover, in this expression, is uniquely determined, and B is uniquely determined up to a multiplication of element of K*. Let l 1, and suppose that there exists an embedding of AG(m+l, k) into PG(m, K) which has the above expression. If we put r = dim _k K, then we have r 3 and m > 2 l-1)/(r-2). Conversely, there exists an embedding of AG(l+m, k) into PG(m, K) with the above expression if K is a cyclic extension of k with dim _k K=r 3, and if m 2l/(r-2) with m even or if m 2l/(r-2) +1 with m odd.     

Ein beliebig startender SIMPLEX-Algorithmus

Zusammenfassung Die betrachtete Aufgabe der linearen Programmierung lautet: man maximiereC _T x unter den Bedingungenx0,A xd, wobeix,c R ⁿ ,d R ^m ,A=(m×n)-Matrix. Fallsd0, muß man nach herkömmlichen Verfahren zuerst einen zulässigen Ausgangspunkt finden, um den eigentlichen SIMPLEX-Algorithmus starten zu können. Die beschriebene Methode wendet den eigentlichen SIMPLEX-Algorithmus sofort solange auf jeweils noch verletzte Restriktionend _i <0 an, bis entweder alle eingehalten sind, und optimiert schließlich die gegebene Zielfunktion, oder gibt an, daß eine zulässige Lösung der Aufgabe nicht existiert.

---

Consider the linear programming problem: maximizec ^T x s.t.x0,A xd, wherex,cR _n ,d R _m ,A=(m×n)-matrix. Ifd0, the ordinary SIMPLEX-algorithm can only be started after some feasible solution has been found. The above procedure instead takes advantage of the SIMPLEX-algorithm from the very beginning by using violated constraints as objective functions until either all of them hold (which allows subsequent optimization of the original objective function) or it can be stated that there exists no feasible solution at all.

     

Almost sure behaviour ofF-valued random fields

Summary LetX _n, n ^d be a field of independent random variables taking values in a semi-normed measurable vector spaceF. For a broad class of fields _n, ^d of positive numbers, the almost sure behaviour of _knX_k/_n, n ^d is studied. The main result allows us to deduce some new and well-known theorems for fields of independentF random variables from related results for fields of independent real random variables.Supported in part by the Youth Science Foundation of China, No. 19001018Supported by the National Natural Science Foundation of China     

On the concept of code-isomorphy

LetF be a finite set of cardinality ¦F¦ =q 2,n 1 an integer and :F ⁿ×Fⁿ₀ theHamming metric. Acode isomorphism C D between two block codesC,D Fⁿ is defined as an isometry which can be extended to an isometry of the whole space Fⁿ. Any permutation S _n of the positions canonically induces a so-calledequivalence map Aut Fⁿ; any system (₁,₂,...,_n) ofn permutations of the character setF induces a so-calledconfiguration Aat Fⁿ. The group Aut Fⁿ of all isometries of Fⁿ turns out to be semidirect product of the configuration group with the symmetric group of degreen. The codeword estimating failure probability of a maximum likelihood codeword estimator for aq-nary symmetric channel does not depend on the transmitted codeword, if the automorphism group of the code acts transitively on the set of codewords. When using a systematic (n, k)-encoder, the symbol decoding failure probability does not depend on the transmitted symbol or on the time of transmission if the configuration group and the automorphism group act transitively on the set of codewords resp. on the set of thek information positions.In memoriam Giuseppe Tallini     

Asymptotics of Dominated Gaussian Maxima

Let {X _n , n1} be a sequence of independent Gaussian random vectors in R ^d d2. In this paper an asymptotic evaluation of P{max₁in X _i a _n Z+b _n } with Z another Gaussian random vector is obtained for a _n, b _n R ^d two vectors obeying certain conditions.     

Random polytopes in thed-dimensional cube

LetC ^d be the set of vertices of ad-dimensional cube,C ^d ={(x ₁, ...,x _d ):x _i =±1}. Let us choose a randomn-element subsetA(n) ofC ^d . Here we prove that Prob (the origin belongs to the convA(2d+x2d))=(x)+o(1) ifx is fixed andd . That is, for an arbitrary>0 the convex hull of more than (2+)d vertices almost always contains 0 while the convex hull of less than (2-)d points almost always avoids it.     

A class of nonlinear complementarity problems for multifunctions

Given a continuous mapF:R ⁿ R ⁿ and a lower semicontinuous positively homogeneous convex functionh:R ⁿ R, the nonlinear complementarity problem considered here is to findxR ₊ ⁿ andyh(x), the subdifferential ofh atx, such thatF(x)+y0 andx ^T (F(x)+y)=0. Some existence theorems for the above problem are given under certain conditions on the mapF. An application to quasidifferentiable convex programming is also shown.The authors are grateful to Professor O. L. Mangasarian and the referee for their substantive suggestions.     

Über einen Satz von Shl. Sternberg in der Theorie der analytischen Iterationen

Let X=X ₁,...,X _n be the ring of formal power series inn indeterminates over . LetF:XAX+B(X)=(F ⁽¹⁾(X),...,F ⁽ⁿ⁾(X))(X) ⁿ denote an automorphism of X and let ₁,..., _n be the eigenvalues of the linear partA ofF. We will say thatF has an analytic iteration (a. i.) if there exists a family (F _t (itX)) _t of automorphisms such thatF _t(X) has coefficients analytic int and such thatF ₀=X,F ₁=F,F _t+t=F_tF_t for allt,t. Let now a set=(ln₁,...,ln _n ) of determinations of the logarithms be given. We ask if there exists an a. i. ofF such that the eigenvalues of the linear partA(t) ofF _t(X) are . We will give necessary and sufficient conditions forF to have such an a. i., namely thatF is conjugate to a semicanonical formN=T ^–1FT such that inN ^(k)(X) there appear at most monomialsX ₁ ¹ ...X _n ⁿ . This generalizes a result of Shl.Sternberg.

---

---

Herrn Prof. Dr. E. Hlawka zum 60. Geburtstag gewidmet     

On the parametrix for a class of Schrödinger operators with potentials of quadratic growth

Summary Let E(t, h) be the Fourier Integral Operator representing the parametrix of the propagator for the Schrödinger equation Q=ih_t, Q=– 1/2h²_x + V(x), where V is a potential of quadratic growth inR ⁿ. It is proved that E(t, h) coincides exactly with the Schwarte kernel of the propagator if and only if V is a positive quadratic form, i.e. if the corresponding physical system is a n-dimensional harmonic oscillator.     

Iterative hyperidentities for theA n,m varieties of semigroups

Iterative hyperidentities are hyperidentities of the special formF ^a (x ₁,...,x _k =F ^a+b (x ₁,...,x _k ). This type of hyperidentity has been considered by Denecke and Pöschel, and by Schweigert. Here we consider iterative hyperidentities for the variety A_n,m of commutative semigroups satisfyingx ⁿ =x ^n+m ,n,m 1. We introduce two parameters(m, n) and(m) associated withn andm, and show thatA _nn,m satisfies the iterative hyperidentitiesF (x ₁,...,x _k =F ^+b (x ₁,...,x _k ) for every arityk. Moreover, the numbers and are minimal, making these hyperidentities irreducible in the sense of Schweigert. We also show how these hyperidentities for A_n,m may be used to prove that no non-trivial proper variety of commutative semigroups can have a finite hyperidentity basis.Presented by W. Taylor.Research supported by NSERC of Canada     

An intersection property of the simple random walks inZ d

Let {S _d (n)} _n0 be the simple random walk inZ ^d , and ^(d)(a,b)={S _d (n)Z ^d :anb}. Supposef(n) is an integer-valued function and increases to infinity asn tends to infinity, andE _n ^(d) ={^(d)(0,n)^(d)(n+f(n),)}. In this paper, a necessary and sufficient condition to ensureP(E _n ^d) ,i.o.)=0, or 1 is derived ford=3, 4. This problem was first studied by P. Erdös and S.J. Taylor.This work is partly supported by the National Natural Sciences Foundation of China.     

On the convergence of projected gradient processes to singular critical points

The projected gradient methods treated here generate iterates by the rulex _k+1=P (x _k –s _k F(x _k )),x ₁ , where is a closed convex set in a real Hilbert spaceX,s _k is a positive real number determined by a Goldstein-Bertsekas condition,P projectsX into ,F is a differentiable function whose minimum is sought in , and F is locally Lipschitz continuous. Asymptotic stability and convergence rate theorems are proved for singular local minimizers in the interior of , or more generally, in some open facet in . The stability theorem requires that: (i) is a proper local minimizer andF grows uniformly in near ; (ii) –F() lies in the relative interior of the coneK of outer normals to at ; and (iii) is an isolated critical point and the defect P (x – F(x)) –x grows uniformly within the facet containing . The convergence rate theorem imposes (i) and (ii), and also requires that: (iv)F isC ⁴ near and grows no slower than x–⁴ within the facet; and (v) the projected Hessian operatorP _{F 2} F()F is positive definite on its range in the subspaceF orthogonal toK . Under these conditions, {x _k } converges to from nearby starting pointsx ₁, withF(x _k ) –F() =O(k ^–2) and x _k – =O(k ^–1/2). No explicit or implied local pseudoconvexity or level set compactness demands are imposed onF in this analysis. Furthermore, condition (v) and the uniform growth stipulations in (i) and (iii) are redundant in ⁿ .     

Estimates for the minimal width of polytopes inscribed in convex bodies

The paper deals with the problem of approximating point sets byn-point subsets with respect to the minimal widthw. Let, in particular, ^d denote the family of all convex bodies in Euclideand-space, letA ^d and letn be an integer greater thand. Then we ask for the greatest number = _n (A) such that everyA A contains a polytope withn vertices which has minimal width at least w(A). We give bounds for _n ( ^d ), for _n (2133; ^d ), and for _n (W ^d ), where 2133; ^d ,W ^d denote the families of centrally symmetric convex bodies and of bodies of constant width, respectively.Dedicated to Professor L. danzer on the occasion of his sixtieth birthdayResearch for this paper was conducted in the academic year 1986/87 while both authors were visiting the University of Washington, Seattle. P. Gritzmann was supported by the Alexander von Humboldt Foundation.     

Sobolev inner products and orthogonal polynomials of Sobolev type

This survey paper deals with polynomials which are orthogonal with respect to scalar products of the form _R F ^T[A]G withF ^T=[f(x), f(Ⅎ(x),...f ^(y)(x)], [A] A _ji =A _ji =A _ij =d _ji (I _ji ) where d _ji is a measure of supportI _ij and [A] is positive semi-definite. Basic properties are indicated or proved in particular cases.     

Slope Estimates of Artin–Schreier Curves

Let X/F_p be an Artin–Schreier curve defined by the affine equation y ^p –y=f(x) where f(x)F_p[x] is monic of degree d. In this paper we develop a method for estimating the first slope of the Newton polygon of X. Denote this first slope by NP₁(X/F_p). We use our method to prove that if p>d2 then NP₁(X/F_p)(p–1)/d/(p–1). If p>2d4, we give a sufficient condition for the equality to hold.