Illuminating high-dimensional convex sets

A setL of points in thed-spaceE ^d is said toilluminate a familyF={S ₁, ...,S _n } ofn disjoint compact sets inE ^d if for every setS _i inF and every pointx in the boundary ofS _i there is a pointv inL such thatv illuminatesx, i.e. the line segment joiningv tox intersects the union of the elements ofF in exactly {x}.The problem we treat is the size of a setS needed to illuminate a familyF={S ₁, ...,S _n } ofn disjoint compact sets inE ^d . We also treat the problem of putting these convex sets in mutually disjoint convex polytopes, each one having at most a certain number of facets.     

The Arrow-Barankin-Blackwell theorem in a dual space setting

In 1953 Arrow, Barankin, and Blackwell proved that, ifR ⁿ is equipped with its natural ordering and ifF is a closed convex subset ofR ⁿ , then the set of points inF that can be supported by strictly positive linear functionals is dense in the set of all efficient (maximal) points ofF. Many generalizations of this density result to infinite-dimensional settings have been given. In this note, we consider the particular setting where the setF is contained in the topological dualY ^* of a partially ordered, nonreflexive normed spaceY, and the support functionals are restricted to be either nonnegative or strictly positive elements in the canonical embedding ofY inY ^*. Three alternative density results are obtained, two of which generalize a space-specific result due to Majumdar for the dual system (Y,Y ^*)=(L ¹,L ).This research was supported in part by funds provided by the Provident Chair of Excellence in Applied Mathematics at the University of Tennessee, Chattanooga, Tennessee.     

Matrix functions with arbitrarily prescribed left and right partial indices

We prove that ifn2 and , are two given vectors inZ ⁿ, then there exists a matrix function inL ^n×n (T) which has a right Wiener-Hopf factorization inL ² with the partial indices and a left Wiener-Hopf factorization inL ² with the partial indices .     

Maintaining the minimal distance of a point set in polylogarithmic time

A dynamic data structure is given that maintains the minimal distance in a set ofn points ink-dimensional space inO((logn) ^k log logn) amortized time per update. The size of the data structure is bounded byO(n(logn) ^k ). Distances are measured in the MinkowskiL _t -metric, where 1 t . This is the first dynamic data structure that maintains the minimal distance in polylogarithmic time for fully on-line updates.This work was supported by the ESPRIT II Basic Research Actions Program, under Contract No. 3075 (project ALCOM).     

Equivalent Characterization of Entire Functions of Exponential Type

In this paper, we show that a necessary and sufficient condition for the fulfillment of the relation s _m ^(k) (f) – f^(k) _p 0 as m , 1 < p < , k 0,1,2,..., is that f B _,p , where B _,p = B L _p (R), and B denotes the subset of all entire functions of exponential type which are bounded on R, B _,p is usually called Paley-Wiener class, and s _m (f) is the unique cardinal spline of degree m – 1 interpolating f at the integers. Moreover, we obtain three equivalent forms for the characterization of the class B _,p .     

Building ofGL(m, D) and centralizers

LetG=GL(m, D) whereD is a central division algebra over a commutative nonarchimedean local fieldF. LetE/F be a field extension contained inM(m, D). We denote byI (resp.I _E) the nonextended affine building ofG (resp. of the centralizer ofE ^x inG). In this paper we prove that there exists a uniqueG _E-equivariant affine mapj _EI_EI. It is injective and its image coincides with the set ofE ^x-fixed points inI. Moreover, we prove thatj _E is compatible with the Moy-Prasad filtrations.This author's contribution was written while he was a post-doctoral student at King's College London and supported by an european TMR grant     

Milnor K-Groups and Finite Field Extensions

Let E/F be a finite separable field extension and let m denote the integral part of log₂ [E : F]. David Leep recently showed that if char(F) 2, then for n m the nth power of the fundamental ideal in the Witt ring of E satisfies the equality I ⁿ E = I ^n–m F · I ^m E. The aim of this note is to prove the analogous equality for the Milnor K-groups, that is K _n E = K _n–m F · K _m E for n m. In either of these equalities one may not replace m by m – 1, as examples of certain m-quadratic extensions indicate.     

On the Harris Recurrence of Iterated Random Lipschitz Functions and Related Convergence Rate Results

A result by Elton⁽⁶⁾ states that an iterated function system

Ü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     

A cellation of the Grassmann manifold

Motivated by the computation of equilibria in economic models with incomplete asset markets, a cellation of the Grassmann manifold is constructed by restricting a common atlas. The Grassmann manifold ofm-planes inn-dimensional space is shown to be a union ofn choosem congruentm(n−m)-dimensional topological disks whose interiors are disjoint.     

On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials

LetS be a triangulation of andf(z) = z ^d +a _d–1 z ^d–1++a ₀, a complex polynomial. LetF be the piecewise linear approximation off determined byS. For certainS, we establish an upper bound on the complexity of an algorithm which finds zeros ofF. This bound is a polynomial in terms ofn, max{a _i } _i , and measures of the sizes of simplices inS.     

Relations between a manifold and its focal set

Summary Throughout this paper, smooth meansC . All manifolds and embeddings will be smooth. By aclosed m-manifold we mean a compact connected manifold of dimensionm, without boundary.LetM be a closedm-manifold (m>0), andf: ME ⁿ an embedding in Euclideann-space. The focal points off are the centres of principal curvature (with respect to some normal direction) of the embedded manifoldf(M). These points form thefocal set C(f) off.The starting point for our investigation is the following problem. Is there any relation between the topological structure ofM and the relative positions ofC(f) andf(M) inE ⁿ ? In particular, canf be so chosen thatC(f) andf(M) are disjoint? We say that such an embedding isnonfocal.We find that there are manifolds for which no such embedding exists.     

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     

Covering abelian groups with cyclic subsets

Summary Letk andm be positive integers. An abelian groupG is said to have ann-cover if there is a subsetS ofG consisting ofn elements such that every non-zero element ofG can be expressed in the formig for some elementg inS and integeri, 1 i k. Lets _n (k) be the largest order of abelian groups that have ann-cover. We investigate the behavior ofs _n (k)/k ask andn is fixed.     

Maximal plurisubharmonic functions and the polynomial hull of a completely circled fibration

LetX(-ϱB ^m ×C ⁿ be a compact set over the unit sphere ϱB ^m such that for eachz∈ϱB ^m the fiberX _z ={ω∈C ⁿ ;(z, ω)∈X} is the closure of a completely circled pseudoconvex domain inC ⁿ . The polynomial hull ofX is described in terms of the Perron-Bremermann function for the homogeneous defining function ofX. Moreover, for each point (z ₀,w ₀)∈Int there exists a smooth up to the boundary analytic discF:Δ→B ^m ×C ⁿ with the boundary inX such thatF(0)=(z ₀,w ₀). This work was supported in part by a grant from the Ministry of Science of the Republic of Slovenia.     

Hadamard matrices generated by an adaptation of generalized quaternion type array

The purpose of this paper is to prove that ifq 1 (mod 4) andq – 2 are both prime powers, then there exists an Hadamard matrix of order 4q. We rely on relative Gauss sums and generalized quaternion type array. Under the same assumption onq, E. Spence has obtained an Hadamard matrix of order 4q by using a relative difference set and the Goethals-Seidel array. We believe that the matrix constructed here is inequivalent to Spence's matrix, in general.Notation q a power of a primep - Z the rational integer ring - F = GF(q) a finite field withq elements - K = GF(q ^s ) an extension ofF of degrees 2 - F ^× multiplicative group ofF - a primitive element ofK - S _F absolute trace fromF - S _K/F relative trace fromK toF - N _K/F relative norm fromK toF - I _m the unit matrix of orderm - J _m the matrix of orderm with every element + 1 - e the column vector of ordern with every element + 1 - A ^* the transpose of a matrixA - J _m (x) 1 +x + x ² + ... +x ^m-1     

The projection theorem for spectral sets

LetG be a locally compact group with polynomial growth and symmetricL ¹-algebra andN a closed normal subgroup ofG. LetF be a closedG-invariant subset of Prim_* L ¹(N) andE={ker; with |N(k(F))=0}. We prove thatE is a spectral subset of Prim_* L ¹(G) ifF is spectral. Moreover we give the following application to the ideal theory ofL ¹(G). Suppose that, in addition,N is CCR andG/N is compact. Then all primary ideals inL ¹(G) are maximal, provided allG-orbits in Prim_* L ¹(N) are spectral.Dedicated to Professor Elmar Thoma on the occasion of his 60th birthday     

Galerkin method and optimal error algorithms in hilbert spaces

Summary We consider operator equations of the formLu=f, whereL belongs to the class of linear, bounded (by a constantM) and coercive (with a constantm) operators from a Hilbert spaceV onto its dualV ^* andf belongs to a Hilbert spaceWV ^*. We study optimality of the Galerkin methodP _n ^* Lu _n =P _n ^* f, whereu _n V _n ,V _n is subspace ofV, P _n is the orthogonal projector ontoV _n andP _n ^* is dual toP _n . We show that the Galerkin method is quasi optimal independently of the choice of the subspaceV _n and the spaceW ifM>m. In the caseM=m, optimality of the method depends strongly on the choice ofV _n andW. Therefore we define a new algorithm which is always optimal (independently of the choice ofV _n andW and relations betweenM andm).     

Truncation error bounds for limit-periodic continued fractionsK(a n /1) with lima n =0

Summary Truncation error bounds are developed for continued fractionsK(a _n /1) where |a _n |1/4 for alln sufficiently large. The bounds are particularly suited (some are shown to be best) for the limit-periodic case when lima _n =0. Among the principal results is the following: If |a _n |/n ^p for alln sufficiently large (with constants >0,p>0), then |f–f _m |C[D/(m+2)] ^p(m+2) for allm sufficiently large (for some constantsC>0,D>0). Heref denotes the limit (assumed finite) ofK(a _n /1) andf _m denotes itsmth approximant. Applications are given for continued fraction expansions of ratios of Kummer functions₁ F ₁ and of ratios of hypergeometric functions₀ F ₁. It is shown thatp=1 for₁ F ₁ andp=2 for₀ F ₁, wherep is the parameter determining the rate of convergence. Numerical examples indicate that the error bounds are indeed sharp.Research supported in part by the National Science Foundation under Grant MCS-8202230 and DMS-8401717     

On integer points in polyhedra

We give an upper bound on the number of vertices ofP _I , the integer hull of a polyhedronP, in terms of the dimensionn of the space, the numberm of inequalities required to describeP, and the size of these inequalities. For fixedn the bound isO(m ^{n n–} ). We also describe an algorithm which determines the number of integer points in a polyhedron to within a multiplicative factor of 1+ in time polynomial inm, and 1/ when the dimensionn is fixed.Supported by Sonderfschungsbereich 303 (DFG) and NSF grant ECS-8611841.Partially supported by NSF grant DMS-8905645.Supported by NSF grants ECS-8418392 and CCR-8805199.mcd%vax.oxford.ac.uk