Calibrations and the size of Grassmann faces

Summary In the past fifteen years or so, convex geometry and the theory of calibrations have provided a deeper understanding of the behavior and singular structure ofm-dimensional area-minimizing surfaces inR ⁿ . Calibrations correspond to faces of the GrassmannianG(m,R ⁿ ) of orientedm-planes inR ⁿ , viewed as a compact submanifold of the exterior algebra ^m R ⁿ . Large faces typically provide many examples of area-minimizing surfaces. This paper studies the sizes of such faces. It also considers integrands more general than area. One result implies that form-dimensional surfaces inR ⁿ , with 2 m n – 2, for any integrand , there are -minimizing surfaces with interior singularities.     

Error Bounds for Asymptotic Expansion of the Conditional Variance of the Scale Mixtures of the Multivariate Normal Distribution

Let X= A ^1/2 G be a scale mixture of a multivariate normal distribution with X, G ⁿ , Gis a multivariate normal vector, and A is a positive random variable independent of the multivariate random vector G. This study presents asymptotic results of the conditional variance-covariance, Cov(X ₂|X ₁), X ₁ ^m , m < n, under some moment expressions. A new representation form is also presented for conditional expectation of the scale variable on the random vector X ₁ ^m , m < n. Both the asymptotic expression and the representation are manageable and in computable form. Finally, an example is presented to illustrate how the computations are carried out.     

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.     

Differentiability of functions: approximate,global, and differentiability along curves over non-archimedean fields

This paper is devoted to the study of approximate and global smoothness and smoothness along curves of functions f(x ₁,...,x _m ) of variables x ₁,...,x _m in infinite fields with nontrivial non-Archimedean valuations and relations between them. Theorems on classes of smoothness C ⁿ or of functions with partial difference quotients continuous or bounded uniformly continuous on bounded domains up to order n are investigated. We prove that from f ○ u ∈ C ⁿ (K, K ^l) or f ○ u ∈ (K, K ^l) for each C ^∞ or curve u: K → K ^m it follows that f ∈ C ⁿ (K ^m , K ^l) or f ∈ (K ^m , K ^l), where m ≥ 2. Then the classes of smoothness C ^n,r and and more general in the sense of Lipschitz for partial difference quotients are considered and theorems for them are proved. Moreover, the approximate differentiability of functions relative to measures is defined and investigated. Its relations with the Lipschitzian property and almost everywhere differentiability are studied. Non-Archimedean analogs of classical theorems of Kirzsbraun, Rademacher, Stepanoff, and Whitney are formulated and proved, and substantial differences between two cases are found. Finally, theorems about relations between approximate differentiability by all variables and along curves are proved. Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 52, Functional Analysis, 2008.     

Unique determination of the convolutions of measures in Rm,m⩾2, by their restriction to a set

Restrictions are indicated on a complex-valued measure in the spaceR ^m ,m 2., under which the n-fold convolution ^n*,n 2, is uniquely determined by its values on any semispacex ₁<r, rR.Translated from Teoriya Funktsii, Funktsional'nyi Analiz i Ikh Prilozheniya, No. 50, pp. 86–90, 1988.     

On the extreme spectral properties of Toeplitz matrices generated byL 1 functions with several minima/maxima

In this paper we are concerned with the asymptotic behavior of the smallest eigenvalue ₁ ⁽ⁿ⁾ of symmetric (Hermitian)n ×n Toeplitz matricesT _n (f) generated by an integrable functionf defined in [–, ]. In [7, 8, 11] it is shown that ₁ ⁽ⁿ⁾ tends to essinff =m _f in the following way: ₁ ⁽ⁿ⁾ –m _f 1/n ^2k . These authors use three assumptions:A1)f –m _f has a zero inx =x ₀ of order 2k.A2)f is continuous and at leastC ^2k in a neighborhood ofx ₀.A3)x =x ₀ is the unique global minimum off in [–, ]. In [10] we have proved that the hypothesis of smoothnessA2 is not necessary and that the same result holds under the weaker assumption thatf L ¹[–, ]. In this paper we further extend this theory to the case of a functionf L ¹[–, ] having several global minima by suppressing the hypothesisA3 and by showing that the maximal order 2k of the zeros off –m _f is the only parameter which characterizes the rate of convergence of ₁ ⁽ⁿ⁾ tom _f .     

Partitioning arrangements of lines II: Applications

In this paper we present efficient deterministic algorithms for various problems involving lines or segments in the plane, using the partitioning algorithm described in a companion paper [A3]. These applications include: (i) anO(m ^2/3 n ^2/3 · log^2/3 n · log^/3 (m/n)+(m+n) logn) algorithm to compute all incidences betweenm points andn lines, where is a constant <3.33; (ii) anO(m ^2/3 n ^2/3 · log^5/3 n · log^/3 (m/n)+(m+n) logn) algorithm to computem faces in an arrangement ofn lines; (iii) anO(n ^4/3 log^(+2)/3 n) algorithm to count the number of intersections in a set ofn segments; (iv) anO(n ^4/3 log^{( + 2)/3} n) algorithm to count red-blue intersections between two sets of segments, and (v) anO(n ^3/2 log^/3 n) algorithm to compute spanning trees with low stabbing number for a set ofn points. We also present an algorithm that, given set ofn points in the plane, preprocesses it, in timeO(nm log^+1/2 n), into a data structure of sizeO(m) forn lognmn ², so that the number of points ofS lying inside a query triangle can be computed inO((n/m) log^3/2 n) time.Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. A preliminary version of this paper appears in theProceedings of the 5th ACM Symposium on Computational Geometry, 1989, pp. 11–22.     

The complexity of many cells in arrangements of planes and related problems

We consider several problems involving points and planes in three dimensions. Our main results are: (i) The maximum number of faces boundingm distinct cells in an arrangement ofn planes isO(m ^2/3 n logn +n ²); we can calculatem such cells specified by a point in each, in worst-case timeO(m ^2/3 n log³ n+n ² logn). (ii) The maximum number of incidences betweenn planes andm vertices of their arrangement isO(m ^2/3 n logn+n ²), but this number is onlyO(m ^3/5– n ^4/5+2 +m+n logm), for any>0, for any collection of points no three of which are collinear. (iii) For an arbitrary collection ofm points, we can calculate the number of incidences between them andn planes by a randomized algorithm whose expected time complexity isO((m ^3/4– n ^3/4+3 +m) log² n+n logn logm) for any>0. (iv) Givenm points andn planes, we can find the plane lying immediately below each point in randomized expected timeO([m ^3/4– n ^3/4+3 +m] log² n+n logn logm) for any>0. (v) The maximum number of facets (i.e., (d–1)-dimensional faces) boundingm distinct cells in an arrangement ofn hyperplanes ind dimensions,d>3, isO(m ^2/3 n ^d/3 logn+n ^d–1). This is also an upper bound for the number of incidences betweenn hyperplanes ind dimensions andm vertices of their arrangement. The combinatorial bounds in (i) and (v) and the general bound in (ii) are almost tight.Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by NSF Grant CCR-8714565. Work by the third author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-82-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD—the Israeli National Council for Research and Development. An abstract of this paper has appeared in theProceedings of the 13th International Mathematical Programming Symposium, Tokyo, 1988, p. 147.     

The Automorphism Group of the Subsequence Poset B m,n

In this paper we are interested in the automorphism group of the poset B _{m, n} . B _{m, n} constitutes the words obtained from the cyclic word of length n on an alphabet of m letters in by deleting on all possible ways and their natural order. We prove: Résumé: Le but de ce papier est la détermination du groupe d"automorphismes des ordres B _{m, n} . Il s"agit des mots obtenus à partir du mot cyclique de longeur n sur un alphabet de m lettres par suppression successive de lettres et ordonnés naturellement. On prouve: AutB _{m, n} = {S _n for 1 n m, S ₂ S _2m-n for m + 1n 2m - 1, S ₂for 2m n.     

On a characterization of complete matrix rings

Peter R. Fuchs established in 1991 a new characterization of complete matrix rings by showing that a ringR with identity is isomorphic to a matrix ringM _n (S) for some ringS (and somen 2) if and only if there are elementsx andy inR such thatx ^n–1 0,x ⁿ=0=y ²,x+y is invertible, and Ann(x ^n–1)Ry={0} (theintersection condition), and he showed that the intersection condition is superfluous in casen=2. We show that the intersection condition cannot be omitted from Fuchs' characterization ifn3; in fact, we show that if the intersection condition is omitted, then not only may it happen that we do not obtain a completen ×n matrix ring for then under consideration, but it may even happen that we do not obtain a completem ×m matrix ring for anym2.     

Compact Laws of the Iterated Logarithm for B-Valued Random Variables with Two-Dimensional Indices

Let be a real separable Banach space and {X, X _{n, m}; (n, m) N ²} B-valued i.i.d. random variables. Set . In this paper, the compact law of the iterated logarithm, CLIL(D), for B-valued random variables with two-dimensional indices ranging over a subset D of N ² is studied. There is a gap between the moment conditions for CLIL(N ¹) and those for CLIL(N ²). The main result of this paper fills this gap by presenting necessary and sufficient conditions for the sequence to be almost surely conditionally compact in B, where, for 0, 1 r 2, N ^r (, ) = {(n, m) N ²; n m n exp{(log n) ^r–1 (n)}} and (·) is any positive, continuous, nondecreasing function such that (t)/(log log t) is eventually decreasing as t , for some > 0.     

Sobolev spaces associated to a polyhedron and Fourier integral operations inR n

The theory of the Sobolev spacesH _m ^p (R ⁿ ) (mR,p polyhedron in R ²ⁿ )of [BG]is revisited here in the frame of new classes of pseudodifferential operators related to the same polyhedron p.These operators generalize to corresponding classes of Fourier integral operators, for which we present the main lines of a symbolic calculus and results of continuity on the H _m ^p (R ⁿ ) spaces.     

Combinatorial complexity bounds for arrangements of curves and spheres

We present upper and lower bounds for extremal problems defined for arrangements of lines, circles, spheres, and alike. For example, we prove that the maximum number of edges boundingm cells in an arrangement ofn lines is (m ^2/3 n ^2/3 +n), and that it isO(m ^2/3 n ^2/3 (n) +n) forn unit-circles, where(n) (and later(m, n)) is a function that depends on the inverse of Ackermann's function and grows extremely slowly. If we replace unit-circles by circles of arbitrary radii the upper bound goes up toO(m ^3/5 n ^4/5 (n) +n). The same bounds (without the(n)-terms) hold for the maximum sum of degrees ofm vertices. In the case of vertex degrees in arrangements of lines and of unit-circles our bounds match previous results, but our proofs are considerably simpler than the previous ones. The maximum sum of degrees ofm vertices in an arrangement ofn spheres in three dimensions isO(m ^4/7 n ^9/7 (m, n) +n ²), in general, andO(m ^3/4 n ^3/4 (m, n) +n) if no three spheres intersect in a common circle. The latter bound implies that the maximum number of unit-distances amongm points in three dimensions isO(m ^3/2 (m)) which improves the best previous upper bound on this problem. Applications of our results to other distance problems are also given.The research of the second author was supported by the National Science Foundation under Grant CCR-8714565. Work by the fourth author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation and the IBM Corporation, and by a research grant from the NCRD, the Israeli National Council for Research and Development. A preliminary version of this paper has appeared in theProceedings of the 29th IEEE Symposium on Foundations of Computer Science, 1988.     

The number of edges of many faces in a line segment arrangement

We show that the maximum number of edges boundingm faces in an arrangement ofn line segments in the plane isO(m ^2/3 n ^2/3+n(n)+nlogm). This improves a previous upper bound of Edelsbrunner et al. [5] and almost matches the best known lower bound which is (m ^2/3 n ^2/3+n(n)). In addition, we show that the number of edges bounding anym faces in an arrangement ofn line segments with a total oft intersecting pairs isO(m ^2/3 t ^1/3+n(t/n)+nmin{logm,logt/n}), almost matching the lower bound of (m ^2/3 t ^1/3+n(t/n)) demonstrated in this paper.Work on this paper by the first and fourth authors has been partially supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484. Work by the first author has also been supported by an AT&T Bell Laboratories Ph.D. scholarship at New York University and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center (NSF-STC88-09648). Work by the second author has been supported by NSF under Grants CCR-87-14565 and CCR-89-21421. Work by the fourth author has additionally been supported by grants from the U.S.-Israeli Binational Science Foundation, the NCRD (the Israeli National Council for Research and Development) and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli National Academy of Sciences.     

Hölder type quasicontinuity

It is proved that a functionuL ^m,p (R ⁿ ) (which coincides with the Sobolev spaceW ^1,p (R ⁿ ) ifm=1) coincides with a Hölder continuous functionw outside a set of smallm,q-capacity, whereq<p. Moreover, ifm=1, then the functionw can be chosen to be close tou in theW ^1,p -norm.     

Bounds for arrays of dots with distinct slopes or lengths

Ann×m sonar sequence is a subset of then×m grid with exactly one point in each column, such that the vectors determined by them are all distinct. We show that for fixedn the maximalm for which a sonar sequence exists satisfiesn–Cn ^11/20<m<n+4n ^2/3 for alln andm>n+c logn log logn for infinitely manyn.Another problem concerns the maximal numberD of points that can be selected from then×m grid so that all the vectors have slopes. We proven ^1/2Dn ^4/5 Supported by Hungarian National Foundation for Scientific Research, Grant No. 1901Research conducted by Herbert Taylor was sponsored in part by the Office of Naval Research under ONR Contract No. N00014-90-J-1341.     

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.     

The complexity and construction of many faces in arrangements of lines and of segments

We show that the total number of edges ofm faces of an arrangement ofn lines in the plane isO(m ^2/3– n ^2/3+2 +n) for any>0. The proof takes an algorithmic approach, that is, we describe an algorithm for the calculation of thesem faces and derive the upper bound from the analysis of the algorithm. The algorithm uses randomization and its expected time complexity isO(m ^2/3– n ^2/3+2 logn+n logn logm). If instead of lines we have an arrangement ofn line segments, then the maximum number of edges ofm faces isO(m ^2/3– n ^2/3+2 +n (n) logm) for any>0, where(n) is the functional inverse of Ackermann's function. We give a (randomized) algorithm that produces these faces and takes expected timeO(m ^2/3– n ^2/3+2 log+n(n) log² n logm).The first author is pleased to acknowledge partial support by the Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and the National Science Foundation under Grant CCR-8714565. Work on this paper by the third author has been supported by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation Grant DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD-the Israeli National Council for Research and Development. A preliminary version of this paper has appeared in theProceedings of the 4th ACM Symposium on Computational Geometry, 1988, pp. 44–55.     

An Extension of the Pizzetti Formula for Polyharmonic Functions

We represent the integral over the unit ball B in R ⁿ of any poly-harmonic function u(x) of degree m as a linear combination with constant coefficients of the integrals of its Laplacians ^j u (j = 0,...,m - 1) over any fixed(n - 1)-dimensional hypersphere S() of radius (0 1). In case = 0 theformula reduces to the classical Pizzetti formula. In particular, the cubature formula derived here integrates exactly all algebraic polynomials of degree 2m - 1.     

Some examples of random walks on free products of discrete groups

Summary We consider the random walk (X_n) associated with a probability p on a free product of discrete groups. Knowledge of the resolvent (or Green's function) of p yields theorems about the asymptotic behaviour of the n-step transition probabilities p^*n(x)=P(X_n= x¦ X₀=e) as n. Woess [15], Cartwright and Soardi [3] and others have shown that under quite general conditions there is behaviour of the type p^*n(x)C_x^– n n^– 3/2. Here we show on the other hand that if G is a free product of m copies ofZ ^r and if (X_n) is the « average » of the classical nearest neighbour random walk on each of the factorsZ ^r, then while it satisfies an « n^–3/2 — law » for r small relative to m, it switches to an n^– r/2 -law for large r. Using the same techniques, we give examples of irreducible probabilities (of infinite support) on the free groupZ ^*m which satisfyn ^– for .