New central polynomials for the matrix algebra

Forn≥3 we find a central polynomial of degree (n−1)²+4 for then×n matrix algebra over a field of characteristic 0. Forn=3,4 our polynomial coincides with the known central polynomials of minimal degree and forn>4 the result gives new central polynomials. Until now, forn>4 the minimal degree of the known central polynomials wasn ². Partially supported by the Alexander von Humboldt Foundation in Germany and by Grant MM2/91 of the Ministry of Education and Science in Bulgaria.     

Criteria for validity of the maximum modulus principle for solutions of linear parabolic systems

We consider systems of partial differential equations of the first order int and of order 2s in thex variables, which are uniformly parabolic in the sense of Petrovskii. We show that the classical maximum modulus principle is not valid inR ⁿ×(0,T] fors≥2. For second order systems we obtain necessary and, separately, sufficient conditions for the classical maximum modulus principle, to hold in the layerR ⁿ×(0,T] and in the cylinder μ×(0,T], where μ is a bounded subdomain ofR ⁿ. If the coefficients of the system do not depend ont, these conditions coincide. The necessary and sufficient condition in this case is that the principal part of the system is scalar and that the coefficients of the system satisfy a certain algebraic inequality. We show by an example that the scalar character of the principal part of the system everywhere in the domain is not necessary for validity of the classical maximum modulus principle when the coefficients depend both onx andt. The research of the first author was supported by the Ministry of Absorption, State of Israel.     

Derivation modules of orthogonal duals of hyperplane arrangements

Let A be an n × d matrix having full rank n. An orthogonal dual A^⊥ of A is a (d-n) × d matrix of rank (d−n) such that every row of A^⊥ is orthogonal (under the usual dot product) to every row of A. We define the orthogonal dual for arrangements by identifying an essential (central) arrangement of d hyperplanes in n-dimensional space with the n × d matrix of coefficients of the homogeneous linear forms for which the hyperplanes are kernels. When n ≥ 5, we show that if the matroid (or the lattice of intersection) of an n-dimensional essential arrangement contains a modular copoint whose complement spans, then the derivation module of the orthogonally dual arrangement ^⊥ has projective dimension at least ⌈ n(n+2)/4 ⌉ - 3.Hal Schenck partially supported by NSF DMS 03-11142, NSA MDA 904-03-1-0006, and ATP 010366-0103.     

Castles in the air revisited

We show that the total number of faces bounding any one cell in an arrangement ofn (d−1)-simplices in ℝ ^d isO(n ^d−1 logn), thus almost settling a conjecture of Pach and Sharir. We present several applications of this result, mainly to translational motion planning in polyhedral environments. We than extend our analysis to derive other results on complexity in arrangements of simplices. For example, we show that in such an arrangement the total number of vertices incident to the same cell on more than one “side” isO(n ^d−1 logn). We, also show that the number of repetitions of a “k-flap,” formed by intersectingd−k given simplices, along the boundary of the same cell, summed over all cells and allk-flaps, isO(n ^d−1 log² n). We use this quantity, which we call theexcess of the arrangement, to derive bounds on the complexity ofm distinct cells of such an arrangement. Work on this paper by the first author has been partially supported by National Science Foundation Grant CCR-92-11541. Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-90-J-1284, by National Science Foundation Grants CCR-89-01484 and CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F.—the German-Israeli Foundation for Scientific Reseach and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

Algorithms for ham-sandwich cuts

Given disjoint setsP ₁,P ₂, ...,P _d inR ^d withn points in total, ahamsandwich cut is a hyperplane that simultaneously bisects theP _i . We present algorithms for finding ham-sandwich cuts in every dimensiond>1. Whend=2, the algorithm is optimal, having complexityO(n). For dimensiond>2, the bound on the running time is proportional to the worst-case time needed for constructing a level in an arrangement ofn hyperplanes in dimensiond−1. This, in turn, is related to the number ofk-sets inR ^d−1 . With the current estimates, we get complexity close toO(n ^3/2 ) ford=3, roughlyO(n ^8/3 ) ford=4, andO(n ^d−1−a(d) ) for somea(d)>0 (going to zero asd increases) for largerd. We also give a linear-time algorithm for ham-sandwich cuts inR ³ when the three sets are suitably separated. A preliminary version of the results of this paper appeared in [16] and [17]. Part of this research by J. Matoušek was done while he was visiting the School of Mathematics, Georgia Institute of Technology, Atlanta, and part of his work on this paper was supported by a Humboldt Research Fellowship. W. Steiger expresses gratitude to the NSF DIMACS Center at Rutgers, and his research was supported in part by NSF Grants CCR-8902522 and CCR-9111491.     

Closure Properties of Solutions to Heat Inequalities

We prove that if u ₁,u ₂:(0,∞)×ℝ ^d →(0,∞) are sufficiently well-behaved solutions to certain heat inequalities on ℝ ^d then the function u:(0,∞)×ℝ ^d →(0,∞) given by also satisfies a heat inequality of a similar type provided . On iterating, this result leads to an analogous statement concerning n-fold convolutions. As a corollary, we give a direct heat-flow proof of the sharp n-fold Young convolution inequality and its reverse form. Both authors were supported by EPSRC grant EP/E022340/1.     

Tight upper bounds for the discrepancy of half-spaces

We show that the discrepancy of anyn-point setP in the Euclideand-space with respect to half-spaces is bounded byC _d n ^1/2−1/2d , that is, a mapping χ:P→{−1,1} exists such that, for any half-space γ, γ, |Σ _p∈P⋂γ χ(p)|≤C _d n ^1/2-1/2d . In fact, the result holds for arbitrary set systems as long as theprimal shatter function isO(m ^d ). This matches known lower bounds, improving previous upper bounds by a factor. Part of this research was done at the Third Israeli Computational Geometry Workshop in Ramot and during a visit at Tel Aviv University in December 1993. Also supported in part by Charles University Grant No. 351 and Czech Republic Grant GAČR 201/93/2167.     

Cyclotomic and simplicial matroids

We show that two naturally occurring matroids representable over ℚ are equal: thecyclotomic matroid μ_n represented by then ^th roots of unity 1, ζ, ζ², …, ζ^n-1 inside the cyclotomic extension ℚ(ζ), and a direct sum of copies of a certain simplicial matroid, considered originally by Bolker in the context of transportation polytopes. A result of Adin leads to an upper bound for the number of ℚ-bases for ℚ(ζ) among then ^th roots of unity, which is tight if and only ifn has at most two odd prime factors. In addition, we study the Tutte polynomial of μ_n in the case thatn has two prime factors. First author supported by NSF Postdoctoral Fellowship. Second author supported by NSF grant DMS-0245379.     

Better lower bounds on detecting affine and spherical degeneracies

We show that in the worst case, Ω(n ^d ) sidedness queries are required to determine whether a set ofn points in ℝ ^d is affinely degenerate, i.e., whether it containsd+1 points on a common hyperplane. This matches known upper bounds. We give a straightforward adversary argument, based on the explicit construction of a point set containing Ω(n ^d ) “collapsible” simplices, any one of which can be made degenerate without changing the orientation of any other simplex. As an immediate corollary, we have an Ω(n ^d ) lower bound on the number of sidedness queries required to determine the order type of a set ofn points in ℝ ^d . Using similar techniques, we also show that Ω(n ^d+1) in-sphere queries are required to decide the existence of spherical degeneracies in a set ofn points in ℝ ^d . An earlier version of this paper was presented at the 34th Annual IEEE Symposium on Foundations of Computer Science [8]. This research has been supported by NSF Presidential Young Investigator Grant CCR-9058440.     

The smallest degree sum that yields potentially Kr,r-graphic sequences

We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(K_r,r,n) such that every n-term graphic sequence π = (d₁,d₂,...,d_n) with term sum σ(π) = d₁ + d₂ + ... + d_n ≥ σ(K_r,r,n) is potentially K_r,r-graphic, where K_r,r is an r × r complete bipartite graph, i.e. π has a realization G containing K_r,r as its subgraph. In this paper, the values σ(K_r,r,n) for even r and n ≥ 4r² - r - 6 and for odd r and n ≥ 4r² + 3r - 8 are determined.     

Accounting for boundary effects in nearest-neighbor searching

Givenn data points ind-dimensional space, nearest-neighbor searching involves determining the nearest of these data points to a given query point. Most averagecase analyses of nearest-neighbor searching algorithms are made under the simplifying assumption thatd is fixed and thatn is so large relative tod thatboundary effects can be ignored. This means that for any query point the statistical distribution of the data points surrounding it is independent of the location of the query point. However, in many applications of nearest-neighbor searching (such as data compression by vector quantization) this assumption is not met, since the number of data pointsn grows roughly as 2 ^d .Largely for this reason, the actual performances of many nearest-neighbor algorithms tend to be much better than their theoretical analyses would suggest. We present evidence of why this is the case. We provide an accurate analysis of the number of cells visited in nearest-neighbor searching by the bucketing andk-d tree algorithms. We assumem ^dpoints uniformly distributed in dimensiond, wherem is a fixed integer ≥2. Further, we assume that distances are measured in theL _∞ metric. Our analysis is tight in the limit asd approaches infinity. Empirical evidence is presented showing that the analysis applies even in low dimensions. A preliminary version of this paper appeared in theProceedings of the 11th Annual ACM Symposium on Computational Geometry, 1995, pp. 336–344. Part of this research was conducted while the first author was visiting the Max-Planck-Institut für Informatik, Saarbrücken, Germany. The first author was supported by the ESPRIT Basic Research Actions Program, under Contract No. 7141 (project ALCOM II). The support of the National Science Foundation under Grant CCR-9310705 is gratefully acknowledged by the second author. The third author was supported in part by AT&T Bell Laboratories and the Society of Fellows at Harvard University.     

Construction of Optimal Cubature Formulas Related to?Computer Tomography

We study the problem of the optimization of approximate integration on the class of functions defined on the parallelepiped Π _d =[0,a ₁]×⋅⋅⋅×[0,a _d ], a ₁,…,a _d >0, having a given majorant for the modulus of continuity (relative to the l ₁-metric in ℝ ^d ). An optimal cubature formula, which uses as information integrals of f along intersections of Π _d with n arbitrary (d−1)-dimensional hyperplanes in ℝ ^d (d>1) is obtained. We also find an asymptotically optimal sequence of cubature formulas, whose information functionals are integrals of f along intersections of Π _d with shifts of (d−2)-dimensional coordinate subspaces of ℝ ^d (d>2).     

On Chow and Brauer groups of a product of Mumford curves

Let C₁,···,C_d be Mumford curves defined over a finite extension of and let X=C₁×···×C_d. We shall show the following: (1) The cycle map CH₀(X)/n → H^2d(X, μ_n^⊗d) is injective for any non-zero integer n. (2) The kernel of the canonical map CH₀(X)→Hom(Br(X),) (defined by the Brauer-Manin pairing) coincides with the maximal divisible subgroup in CH₀(X).     

Recurrence in unipotent groups and ergodic nonabelian group extensions

LetT be a measure-preserving and ergodic transformation of a standard probability space (X,S, μ) and letf:X → SUT _d (ℝ) be a Borel map into the group of unipotent upper triangulard ×d matrices. We modify an argument in [12] to obtain a sufficient condition for the recurrence of the random walk defined byf, in terms of the asymptotic behaviour of the distributions of the suitably scaled mapsf(n,x)=(fT ⁿ⁻¹·fT ⁿ⁻²…fT·f). We give examples of recurrent cocycles with values in the continuous Heisenberg group H₁(ℝ)=SUT₃(ℝ), and we use a recurrent cocycle to construct an ergodic skew-product extension of an irrational rotation by the discrete Heisenberg group H₁(ℤ)=SUT₃(ℤ). The author was partially supported by the FWF research project P16004-MAT.     

On Asymptotic Behavior for Singularities of the Powers of Mean Curvature Flow

Let M^n be a smooth, compact manifold without boundary, and F0 ： M^n→ R^n＋1 a smooth immersion which is convex. The one-parameter families F（·, t） ： M^n× [0, T） → R^n＋1 of hypersurfaces Mt^n= F（·,t）（M^n） satisfy an initial value problem dF/dt （·,t） = -H^k（· ,t）v（· ,t）, F（· ,0） = F0（· ）, where H is the mean curvature and u（·,t） is the outer unit normal at F（·, t）, such that -Hu = H is the mean curvature vector, and k 〉 0 is a constant. This problem is called H^k-fiow. Such flow will develop singularities after finite time. According to the blow-up rate of the square norm of the second fundamental forms, the authors analyze the structure of the rescaled limit by classifying the singularities as two types, i.e., Type Ⅰ and Type Ⅱ. It is proved that for Type Ⅰ singularity, the limiting hypersurface satisfies an elliptic equation; for Type Ⅱ singularity, the limiting hypersurface must be a translating soliton.     

Traversing a Set of Points with a Minimum Number of Turns

Given a finite set of points S in ℝ ^d , consider visiting the points in S with a polygonal path which makes a minimum number of turns, or equivalently, has the minimum number of segments (links). We call this minimization problem the minimum link spanning path problem. This natural problem has appeared several times in the literature under different variants. The simplest one is that in which the allowed paths are axis-aligned. Let L(S) be the minimum number of links of an axis-aligned path for S, and let G _n ^d be an n×…×n grid in ℤ ^d . Kranakis et al. (Ars Comb. 38:177–192, 1994) showed that L(G _n ²)=2n−1 and and conjectured that, for all d≥3, We prove the conjecture for d=3 by showing the lower bound for L(G _n ³). For d=4, we prove that For general d, we give new estimates on L(G _n ^d ) that are very close to the conjectured value. The new lower bound of improves previous result by Collins and Moret (Inf. Process. Lett. 68:317–319, 1998), while the new upper bound of differs from the conjectured value only in the lower order terms. For arbitrary point sets, we include an exact bound on the minimum number of links needed in an axis-aligned path traversing any planar n-point set. We obtain similar tight estimates (within 1) in any number of dimensions d. For the general problem of traversing an arbitrary set of points in ℝ ^d with an axis-aligned spanning path having a minimum number of links, we present a constant ratio (depending on the dimension d) approximation algorithm. Work by A. Dumitrescu was partially supported by NSF CAREER grant CCF-0444188. Work by F. Hurtado was partially supported by projects MECMTM2006-01267 and Gen. Cat. 2005SGR00692. Work by P. Valtr was partially supported by the project 1M0545 of the Ministry of Education of the Czech Republic.     

On the dual Stiefel-Whitney classes of some Grassmann manifolds

We present some non-vanishing dual Stiefel-Whitney classes of the Grassmann manifolds O(n)/O(4) × O(n − 4) for n = 2 ^s + 2 and n = 2 ^s + 3 (s ≧ 3), providing a supplement to results of Hiller, Stong, and Oproiu. Some applications are also mentioned. Part of this research was carried out while the first author was a member of three research teams supported in part by the grant agencies VEGA and APVV, and the second author was a member of a research team supported in part by VEGA.     

Construction of a class of multivariate compactly supported wavelet bases for L 2(? d )

In this paper, for a given d×d expansive matrix M with |detM| = 2, we investigate the compactly supported M-wavelets for L ²(ℝ ^d ). Starting with a pair of compactly supported refinable functions ϕ and [(j)\tilde]\tilde \varphi satisfying a mild condition, we obtain an explicit construction of a compactly supported wavelet ψ such that {2 ^j/2 ψ(M ^j · −k): j ∈ ℤ, k ∈ ℤd} forms a Riesz basis for L ²(ℝ ^d ). The (anti-)symmetry of such ψ is studied, and some examples are also provided.     

On the expected number of k-sets

Given a setS ofn points inR ^d , a subsetX of sized is called ak-simplex if the hyperplane aff(X) has exactlyk points on one side. We studyE _d (k,n), the expected number of k-simplices whenS is a random sample ofn points from a probability distributionP onR ^d . WhenP is spherically symmetric we prove thatE _d (k, n)≤cn ^d−1 WhenP is uniform on a convex bodyK⊂R ² we prove thatE ₂ (k, n) is asymptotically linear in the rangecn≤k≤n/2 and whenk is constant it is asymptotically the expected number of vertices on the convex hull ofS. Finally, we construct a distributionP onR ² for whichE ₂((n−2)/2,n) iscn logn. The authors express gratitude to the NSF DIMACS Center at Rutgers and Princeton. The research of I. Bárány was supported in part by Hungarian National Science Foundation Grants 1907 and 1909, and W. Steiger's research was supported in part by NSF Grants CCR-8902522 and CCR-9111491.     

The use of the disguised Wishart distribution in a Bayesian approach to tolerance region construction

Summary In attacking the problem of this paper (see Section 1), the authors were confronted with finding the distribution of a (k×k) matrix of random variablesR=P′VP, wherePP′=Σ ^-1, and where the (k×k) symmetric matrix Σ^-1 has the Wishart distribution, matrix [(n−1)V]⁻¹, and degrees of freedom (n−1), withV a (k×k) symmetric positive definite matrix of constants. This distribution (whenP is lower triangular with positive diagonal elements), and a related result, has recently been found by the authors and given in Tan and Guttman [7]. In this paper we use these results (stated here without proof in Theorems 1.1 and 1.2) to help us construct a β-expectation tolerance region, when sampling is from thek-variate normal,N(μ,Σ), where Σ is positive definite. This research was partially supported by the National Institute of Health under Grant No. GM 15422, and the Wisconsin Research Foundation.