Estimating L ∞ Norms by L 2k Norms for Functions on Orbits

Abstract. Let G be a compact group acting in a real vector space V . We obtain a number of inequalities relating the L ^∞ norm of a matrix element of the representation of G with its L ^2k norm for a positive integer k . As an application, we obtain approximation algorithms to find the maximum absolute value of a given multivariate polynomial over the unit sphere (in which case G is the orthogonal group) and for the assignment problem of degree d , a hard problem of combinatorial optimization generalizing the quadratic assignment problem (in which case G is the symmetric group).     

A dimension series for multivariate splines

For a polyhedral subdivision Δ of a region in Euclideand-space, we consider the vector spaceC _k ^r (Δ) consisting of allC ^r piecewise polynomial functions over Δ of degree at mostk. We consider the formal power series ∑ _k≥0 dim_? C _k ^r (Δ)λ^k and show, under mild conditions on Δ, that this always has the formP(λ)/(1?λ) ^d+1, whereP(λ) is a polynomial in λ with integral coefficients which satisfiesP(0)=1,P(1)=f _d (Δ), andP′(1)=(r+1)f _d?1 ⁰ (Δ). We discuss how the polynomialP(λ) and bases for the spacesC _k ^r (Δ) can be effectively calculated by use of Gröbner basis techniques of computational commutative algebra. A further application is given to the theory of hyperplane arrangements.     

Subalgebras of the Stanley—Reisner Ring

In [2], Billera proved that the R -algebra of continuous piecewise polynomial functions (C ⁰ splines) on a d -dimensional simplicial complex Δ embedded in R ^d is a quotient of the Stanley—Reisner ring A _Δ of Δ. We derive a criterion to determine which elements of the Stanley—Reisner ring correspond to splines of higher-order smoothness. In [5], Lau and Stiller point out that the dimension of C ^r _k (Δ) is upper semicontinuous in the Zariski topology. Using the criterion, we give an algorithm for obtaining the defining equations of the set of vertex locations where the dimension jumps. Received June 2, 1997, and in revised form December 22, 1997, and March 24, 1998.     

Polynomial-Time Computation of the Degree of Algebraic Varieties in Zero Characteristic and Its Applications

Let k be a ground field of zero characteristic, and let V be an algebraic variety over k given as the locus of a family of polynomials of degree less than d in n variables. In the paper, we construct algorithms that have working time that is polynomial in the size of the input and d ⁿ and compute the following: the degree of the variety V, the dimension of V in a neighborhood of a given point, the multiplicity of a given point of V, and a representative system of smooth points with their tangent spaces on each component of V. Also, we construct an algorithm for deciding whether a given morphism between two given algebraic varieties V and V' is dominant. Bibliography: 17 titles.     

Separable polynomials over finite dimensional algebras

In [5] it was shown that for a polynomial P of precise degree n with coefficients in an arbitrary m-ary algebra of dimension d as a vector space over an algebraically closed fields, the zeros of P together with the homogeneous zeros of the dominant part of P form a set of cardinality n^d or the cardinality of the base field. We investigate polynomials with coefficients in a d dimensional algebra A without assuming the base field k to be algebraically closed. Separable polynomials are defined to be those which have exactly n^d distinct zeros in [Ktilde] ?_k A [Ktilde] where [Ktilde] denotes an algebraic closure of k. The main result states that given a separable polynomial of degree n, the field extension L of minimal degree over k for which L ?_k A contains all nd zeros is finite Galois over k. It is shown that there is a non empty Zariski open subset in the affine space of all d-dimensional k algebras whose elements A have the following property: In the affine space of polynomials of precise degree n with coefficients in A there is a non empty Zariski open subset consisting of separable polynomials; in other polynomials with coefficients in a finite dimensional algebra are “generically” separable.     

Cohomology vanishing¶and a problem in approximation theory

For a simplicial subdivison Δ of a region in k ⁿ (k algebraically closed) and r∈N, there is a reflexive sheaf ? on P ⁿ , such that H ⁰(?(d)) is essentially the space of piecewise polynomial functions on Δ, of degree at most d, which meet with order of smoothness r along common faces. In [9], Elencwajg and Forster give bounds for the vanishing of the higher cohomology of a bundle ℰ on P ⁿ in terms of the top two Chern classes and the generic splitting type of ℰ. We use a spectral sequence argument similar to that of [16] to characterize those Δ for which ? is actually a bundle (which is always the case for n= 2). In this situation we can obtain a formula for H ⁰(?(d)) which involves only local data; the results of [9] cited earlier allow us to give a bound on the d where the formula applies. We also show that a major open problem in approximation theory may be formulated in terms of a cohomology vanishing on P ² and we discuss a possible connection between semi-stability and the conjectured answer to this open problem. Received: 9 April 2001     

Embedding smooth diffeomorphisms in flows

In this paper we study the problem on embedding germs of smooth diffeomorphisms in flows in higher dimensional spaces. First we prove the existence of embedding vector fields for a local diffeomorphism with its nonlinear term a resonant polynomial. Then using this result and the normal form theory, we obtain a class of local Ck diffeomorphisms for k∈N∪{∞,ω} which admit embedding vector fields with some smoothness. Finally we prove that for any k∈N∪{∞} under the coefficient topology the subset of local Ck diffeomorphisms having an embedding vector field with some smoothness is dense in the set of all local Ck diffeomorphisms.     

Buchsbaum Stanley–Reisner Rings and Cohen–Macaulay Covers

First, we give a new criterion for Buchsbaum Stanley–Reisner rings to have linear resolutions. Next, we prove that every (d ? 1)-dimensional complex Δ of initial degree d is contained in the same dimensional Cohen–Macaulay complex whose (d ? 1)th reduced homology is isomorphic to that of Δ. We call such a simplicial complex a Cohen–Macaulay cover of Δ. And we also show that all the intermediate complexes between Δ and its Cohen–Macaulay cover are Buchsbaum provided that Δ is Buchsbaum. As an application, we determine the h-vectors of the 3-dimensional Buchsbaum Stanley–Reisner rings with initial degree 3.     

A higher-order large-scale regularity theory for random elliptic operators

We develop a large-scale regularity theory of higher order for divergence-form elliptic equations with heterogeneous coefficient fields a in the context of stochastic homogenization. The large-scale regularity of a-harmonic functions is encoded by Liouville principles: The space of a-harmonic functions that grow at most like a polynomial of degree k has the same dimension as in the constant-coefficient case. This result can be seen as the qualitative side of a large-scale C^k,α-regularity theory, which in the present work is developed in the form of a corresponding C^k,α-“excess decay” estimate: For a given a-harmonic function u on a ball B_R, its energy distance on some ball B_r to the above space of a-harmonic functions that grow at most like a polynomial of degree k has the natural decay in the radius r above some minimal radius r₀.

Though motivated by stochastic homogenization, the contribution of this paper is of purely deterministic nature: We work under the assumption that for the given realization a of the coefficient field, the couple (φ, σ) of scalar and vector potentials of the harmonic coordinates, where φ is the usual corrector, grows sublinearly in a mildly quantified way. We then construct “kth-order correctors” and thereby the space of a-harmonic functions that grow at most like a polynomial of degree k, establish the above excess decay, and then the corresponding Liouville principle.     

On partial polynomial interpolation

The Alexander-Hirschowitz theorem says that a general collection of k double points in Pⁿ imposes independent conditions on homogeneous polynomials of degree d with a well known list of exceptions. We generalize this theorem to arbitrary zero-dimensional schemes contained in a general union of double points. We work in the polynomial interpolation setting. In this framework our main result says that the affine space of polynomials of degree ?d in n variables, with assigned values of any number of general linear combinations of first partial derivatives, has the expected dimension if d≠2 with only five exceptional cases. If d=2 the exceptional cases are fully described.     

Stable Local Bases for Multivariate Spline Spaces

We present an algorithm for constructing stable local bases for the spaces ^r_d(Δ) of multivariate polynomial splines of smoothness r1 and degree dr2ⁿ+1 on an arbitrary triangulation Δ of a bounded polyhedral domain Ω ⁿ, n2.     

Darboux points and integrability of homogeneous Hamiltonian systems with three and more degrees of freedom. Nongeneric cases

In this paper the problem of classification of integrable natural Hamiltonian systems with n degrees of freedom given by a Hamilton function, which is the sum of the standard kinetic energy and a homogeneous polynomial potential V of degree k > 2, is investigated. It is assumed that the potential is not generic. Except for some particular cases a potential V is not generic if it admits a nonzero solution of equation V′(d) = 0. The existence of such a solution gives very strong integrability obstructions obtained in the frame of the Morales-Ramis theory. This theory also gives additional integrability obstructions which have the form of restrictions imposed on the eigenvalues (λ ₁, …, λ _n ) of the Hessian matrix V″(d) calculated at a nonzero d ∈ ℂ ⁿ satisfying V′(d) = d. In our previous work we showed that for generic potentials some universal relations between (λ ₁, …, λ _n ) calculated at various solutions of V′ (d) = d exist. These relations allow one to prove that the number of potentials satisfying the necessary conditions for the integrability is finite. The main aim of this paper was to show that relations of such forms also exist for nongeneric potentials. We show their existence and derive them for the case n = k = 3 applying the multivariable residue calculus. We demonstrate the strength of the results analyzing in details the nongeneric cases for n = k = 3. Our analysis covers all the possibilities and we distinguish those cases where known methods are too weak to decide if the potential is integrable or not. Moreover, for n = k = 3, thanks to this analysis, a three-parameter family of potentials integrable or superintegrable with additional polynomial first integrals which seemingly can be of an arbitrarily high degree with respect to the momenta was distinguished.      

Lösung von Differentialgleichungen mit Splinefunktionen. Eine Störungstheorie

Summary In this paper non-linear splines (depending onn+1 parameters) are used to patch up the solution of an initial value problem in intervals of stepsizeh. The elements of the solution are fixed byq smoothness conditions andd conditions derived from the differential equation in an appropriate setup. The feasibility of the method can be connected to that of the polynomial spline method by a perturbation type argument. Thus the question of convergence forh0 is closely connected to the linear (polynomial) case.A new elementary prove is given for divergence of the polynomial splines ifq is larger thand+1, as was done by Mülthei [4] with other techniques.A byproduct is an extention of the famous result for polynomial interpolation by Runge on equidistant grids that interpolation of a given function by splines of too high smoothness can cause divergence forh0.

Diese Arbeit ist mit Unterstützung des von der Deutschen Forschungsgemeinschaft getragenen Sonderforschungsbereiches 72 entstanden     

The Hardy inequality and the heat equation with magnetic field in any dimension

In the Euclidean space of any dimension d, we consider the heat semigroup generated by the magnetic Schrödinger operator from which an inverse-square potential is subtracted to make the operator critical in the magnetic-free case. Assuming that the magnetic field is compactly supported, we show that the polynomial large-time behavior of the heat semigroup is determined by the eigenvalue problem for a magnetic Schrödinger operator on the (d ? 1)-dimensional sphere whose vector potential reflects the behavior of the magnetic field at the space infinity. From the spectral problem on the sphere, we deduce that in d = 2 there is an improvement of the decay rate of the heat semigroup by a polynomial factor with power proportional to the distance of the total magnetic flux to the discrete set of flux quanta, while there is no extra polynomial decay rate in higher dimensions. To prove the results, we establish new magnetic Hardy-type inequalities for the Schrödinger operator and develop the method of self-similar variables and weighted Sobolev spaces for the associated heat equation.     

TURBS—Topologically Unrestricted Rational B-Splines

We present a new approach to the construction of piecewise polynomial or rational C ^k -spline surfaces of arbitrary topological structure. The basic idea is to use exclusively parametric smoothness conditions, and to solve the well-known problems at extraordinary points by admitting singular parametrizations. The smoothness of the spline surfaces is guaranteed by specifying a regular smooth reparametrization explicitly. The resulting space of topologically unrestricted rational B-splines (TURBS) is linear and possesses a natural refinement property. Compared with all known methods the construction principle of TURBS is of striking simplicity and the required polynomial bi-degree is essentially decreased from O(k ² ) to d=2k+2 . January 5, 1996. Date revised: September 5, 1996.     

Colorful Strips

We study the following geometric hypergraph coloring problem: given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing sufficiently many points contains all colors. We show that if the strip contains at least 2k − 1 points, such a coloring can always be found. In dimension d, we show that the same holds provided the strip contains at least k(4 ln k + ln d) points. We also consider the dual problem of coloring a given set of axis-aligned strips so that any sufficiently covered point in the plane is covered by k colors. We show that in dimension d the required coverage is at most d(k − 1) + 1. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. From the computational point of view, we show that deciding whether a three-dimensional point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete. This shows a big contrast with the planar case, for which this decision problem is easy.     

Effective construction of an algebraic variety nonsingular in codimension one over a ground field of zero characteristic

Let k be a field of zero characteristic finitely generated over a primitive subfield. Let f be a polynomial of degree at most d in n variables, with coefficients from k, irreducible over an algebraic closure [`(k)] \bar{k} . Then we construct an algebraic variety V nonsingular in codimension one and a finite birational isomorphism V → Z(f), where Z(f) is the hypersurface of all common zeros of the polynomial f in the affine space. The running time of the algorithm for constructing V is polynomial in the size of the input. Bibliography: 8 titles.     

A note on Fröberg's conjecture for forms of equal degrees

In this note we study ideals generated by generic forms in polynomial rings over any algebraicly closed field of characteristic zero. We prove for many cases that the $(d+k)$-th graded component of an ideal generated by generic forms of degree d has the expected dimension (given by dimension count). And as a consequence of our result, we obtain that ideals generated by several generic forms of degrees d usually have the expected Hilbert series. The precise form of this expected Hilbert series, in general, is known as Fröberg's conjecture.     

The Representation of Polyhedra by Polynomial Inequalities

A beautiful result of Brocker and Scheiderer on the stability index of basic closed semi-algebraic sets implies, as a very special case, that every d -dimensional polyhedron admits a representation as the set of solutions of at most d(d+1)/2 polynomial inequalities. Even in this polyhedral case, however, no constructive proof is known, even if the quadratic upper bound is replaced by any bound depending only on the dimension. Here we give, for simple polytopes, an explicit construction of polynomials describing such a polytope. The number of used polynomials is exponential in the dimension, but in the two- and three-dimensional case we get the expected number d(d+1)/2 .