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 .     

An asymptotically tight bound on the number of semi-algebraically connected components of realizable sign conditions

We prove an asymptotically tight bound (asymptotic with respect to the number of polynomials for fixed degrees and number of variables) on the number of semi-algebraically connected components of the realizations of all realizable sign conditions of a family of real polynomials. More precisely, we prove that the number of semi-algebraically connected components of the realizations of all realizable sign conditions of a family of s polynomials in R[X ₁, …,X _k ] whose degrees are at most d is bounded by

Computing the dimension of a semi-algebraic set

In this paper, we consider the problem of computing the real dimension of a given semi-algebraic subset of R ^k, where R is a real closed field. We prove that the dimension k′ of a semi-algebraic set described by s polynomials of degree d in k variables can be computed in time

VC Dimensions of Principal Component Analysis

Motivated by statistical learning theoretic treatment of principal component analysis, we are concerned with the set of points in ℝ ^d that are within a certain distance from a k-dimensional affine subspace. We prove that the VC dimension of the class of such sets is within a constant factor of (k+1)(d−k+1), and then discuss the distribution of eigenvalues of a data covariance matrix by using our bounds of the VC dimensions and Vapnik’s statistical learning theory. In the course of the upper bound proof, we provide a simple proof of Warren’s bound of the number of sign sequences of real polynomials.     

Polynomials with bounds and numerical approximation

We discuss the generation of polynomials with two bounds —an upper bound and a lower bound— on compact sets \(\mathcal C=[0,1]^{d}\subset \mathbb {R}^{d}\) in view on numerical approximation and scientific computing. The presentation is restricted to d = 1,2. We show that a composition formula based on a weighted 4-squares Euler identity generates all such polynomials in dimension d=1. It yields a new algebraic or compositional approach to the classical problem related to polynomials with minimal uniform norm. The theoretical generalization to the multivariate case is discussed in dimension d=2 by means of the 8-squares Degen identity and the connection with quaternions algebras is made explicit. Numerical results in dimension d=1 illustrate the potentialities of this approach and some implementation details are provided.     

A fascinating polynomial sequence arising from an electrostatics problem on the sphere

A positive unit point charge approaching from infinity a perfectly spherical isolated conductor carrying a total charge of +1 will eventually cause a negatively charged spherical cap to appear. The determination of the smallest distance ρ(d) (d is the dimension of the unit sphere) from the point charge to the sphere where still all of the sphere is positively charged is known as Gonchar’s problem. Using classical potential theory for the harmonic case, we show that 1+ρ(d) is equal to the largest positive zero of a certain sequence of monic polynomials of degree 2d?1 with integer coefficients which we call Gonchar polynomials. Rather surprisingly, ρ(2)?is the Golden ratio and ρ(4) the lesser known Plastic number. But Gonchar polynomials have other interesting properties. We discuss their factorizations, investigate their zeros and present some challenging conjectures.     

On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-Algebraic Sets

In this paper we prove new bounds on the sum of the Betti numbers of closed semi-algebraic sets and also give the first single exponential time algorithm for computing the Euler characteristic of arbitrary closed semi-algebraic sets. Given a closed semi-algebraic set S R ^k defined as the intersection of a real variety, Q=0, deg(Q)≤d, whose real dimension is k', with a set defined by a quantifier-free Boolean formula with no negations with atoms of the form P _i =0, P _i ≥ 0, P _i ≤ 0, deg(P _i ) ≤ d, 1≤ i≤ s, we prove that the sum of the Betti numbers of S is bounded by s ^k' (O(d)) ^k . This result generalizes the Oleinik—Petrovsky—Thom—Milnor bound in two directions. Firstly, our bound applies to arbitrary unions of basic closed semi-algebraic sets, not just for basic semi-algebraic sets. Secondly, the combinatorial part (the part depending on s ) in our bound, depends on the dimension of the variety rather than that of the ambient space. It also generalizes the result in [4] where a similar bound is proven for the number of connected components. We also prove that the sum of the Betti numbers of S is bounded by s ^k' 2 ^{O(k2 m4)} in case the total number of monomials occurring in the polynomials in is m. Using the tools developed for the above results, as well as some additional techniques, we give the first single exponential time algorithm for computing the Euler characteristic of arbitrary closed semi-algebraic sets. Received September 9, 1997, and in revised form March 18, 1998, and October 5, 1998.     

Two Remarks on Blocking Sets and Nuclei in Planes of Prime Order

In this paper we characterize a sporadic non-Rédei Type blocking set of PG(2,7) having minimum cardinality, and derive an upper bound for the number of nuclei of sets in PG(2,q) having less than q+1 points. Our methods involve polynomials over finite fields, and work mainly for planes of prime order.     

The Discrepancy of Boxes in Higher Dimension

We prove that the red—blue discrepancy of the set system formed by n points and n axis-parallel boxes in <bo>R</bo> ^d can be as high as n ^Ω(1) in any dimension d= Ω(log n) . This contrasts with the fixed-dimensional case d=O(1) , where the discrepancy is always polylogarithmic. More generally we show that in any dimension 1<d= O(log n) the maximum discrepancy is 2 ^Ω(d) . Our result also leads to a new lower bound on the complexity of off-line orthogonal range searching. This is the problem of summing up weights in boxes, given n weighted points and n boxes in <bo>R</bo> ^d . We prove that the number of arithmetic operations is at least Ω(nd+ nlog log n) in any dimension d=O(log n) . Received June 30, 2000, and in revised form November 9, 2000. Online publication April 6, 2001.     

Notes on the Roots of Ehrhart Polynomials

We determine lattice polytopes of smallest volume with a given number of interior lattice points. We show that the Ehrhart polynomials of those with one interior lattice point have largest roots with norm of order n², where n is the dimension. This improves on the previously best known bound n and complements a recent result of Braun where it is shown that the norm of a root of a Ehrhart polynomial is at most of order n². For the class of 0-symmetric lattice polytopes we present a conjecture on the smallest volume for a given number of interior lattice points and prove the conjecture for crosspolytopes. We further give a characterisation of the roots of Ehrhart polyomials in the three-dimensional case and we classify for n ≤ 4 all lattice polytopes whose roots of their Ehrhart polynomials have all real part -1/2. These polytopes belong to the class of reflexive polytopes.     

Constrained near-minimax approximation by weighted expansion and interpolation using Chebyshev polynomials of the second,third, and fourth kinds

Well known results on near-minimax approximation using Chebyshev polynomials of the first kind are here extended to Chebyshev polynomials of the second, third, and fourth kinds. Specifically, polynomial approximations of degreen weighted by (1–x ²)^1/2, (1+x)^1/2 or (1–x)^1/2 are obtained as partial sums of weighted expansions in Chebyshev polynomials of the second, third, or fourth kinds, respectively, to a functionf continuous on [–1, 1] and constrained to vanish, respectively, at ±1, –1 or +1. In each case a formula for the norm of the resulting projection is determined and shown to be asymptotic to 4^–2logn +A +o(1), and this provides in each case and explicit bound on the relative closeness of a minimax approximation. The constantA that occurs for the second kind polynomial is markedly smaller, by about 0.27, than that for the third and fourth kind, while the latterA is identical to that for the first kind, where the projection norm is the classical Lebesgue constant _n . The results on the third and fourth kind polynomials are shown to relate very closely to previous work of P.V. Galkin and of L. Brutman.Analogous approximations are also obtained by interpolation at zeros of second, third, or fourth kind polynomials of degreen+1, and the norms of resulting projections are obtained explicitly. These are all observed to be asymptotic to 2^–1logn +B +o(1), and so near-minimax approximations are again obtained. The norms for first, third, and fourth kind projections appear to be converging to each other. However, for the second kind projection, we prove that the constantB is smaller by a quantity asymptotic to 2^–1log2, based on a conjecture about the point of attainment of the supremum defining the projection norm, and we demonstrate that the projection itself is remarkably close to a minimal (weighted) interpolation projection.All four kinds of Chebyshev polynomials possess a weighted minimax property, and, in consequence, all the eight approximations discussed here coincide with minimax approximations when the functionf is a suitably weighted polynomial of degreen+1.     

Cubature Formulas of a Nonalgebraic Degree of Precision

We deal with cubature formulas that are exact for polynomials and also for polynomials multiplied by r, where r is the Euclidean distance to the origin. A general lower bound for the number of nodes for a specified degree of precision is given. This bound is improved for centrally symmetric integrals. A set of constraints (consistency conditions) is introduced for the construction of fully symmetric formulas. For one dimension and arbitrary degree, it is shown that the lower bound is sharp for centrally symmetric integrals. For higher dimensions, as an illustration, cubature formulas are only constructed for low degrees. March 6, 2000. Date revised: April 30, 2001. Date accepted: May 31, 2001.     

Faber polynomials corresponding to rational exterior mapping functions

Faber polynomials corresponding to rational exterior mapping functions of degree (m, m − 1) are studied. It is shown that these polynomials always satisfy an (m + 1)-term recurrence. For the special case m = 2, it is shown that the Faber polynomials can be expressed in terms of the classical Chebyshev polynomials of the first kind. In this case, explicit formulas for the Faber polynomials are derived.     

Random walks with different directions

As an extension of Polya’s classical result on random walks on the square grids (\({\mathbf {Z}}^d\)), we consider a random walk where the steps, while still have unit length, point to different directions. We show that in dimensions at least 4, the returning probability after n steps is at most \(n^{-d/2 - d/(d-2) +o(1) }\), which is sharp. The real surprise is in dimensions 2 and 3. In dimension 2, where the traditional grid walk is recurrent, our upper bound is \(n^{-\omega (1) }\), which is much worse than in higher dimensions. In dimension 3, we prove an upper bound of order \(n^{-4 +o(1) }\). We find a new conjecture concerning incidences between spheres and points in \({\mathbf {R}}^3\), which, if holds, would improve the bound to \(n^{-9/2 +o(1) }\), which is consistent to the \(d \ge 4\) case. This conjecture resembles Szemerédi-Trotter type results and is of independent interest.     

Lower bounds for off-line range searching

This paper proves three lower bounds for variants of the following rangesearching problem: Given n weighted points inR ^d andn axis-parallel boxes, compute the sum of the weights within each box: (1) if both additions and subtractions are allowed, we prove that Ω(n log logn) is a lower bound on the number of arithmetic operations; (2) if subtractions are disallowed the lower bound becomes Ω(n(logn/loglogn)^d-1), which is nearly optimal; (3) finally, for the case where boxes are replaced by simplices, we establish a quasi-optimal lower bound of Ω(n^2-2/(d+1))/polylog(n). A preliminary version of this paper appeared inProc. 27th Ann. ACM Symp. on Theory of Computing, May 1995, pp. 733–740. This work was supported in part by NSF Grant CCR-93-01254 and the Geometry Center, University of Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc.     

Doubly-Exponential Growth of the Number of Vectors of Multipilicities for Solutions of Systems of Polynomial

Earlier, D. Yu. Grigoriev and N. N. Vorob'yov obtained an upper bound for the number of vectors of multiplicities for solutions of systems of the form (assuming that the system has a finite number of solutions). In the system above, are polynomials of degrees . In the present paper, we show that the order of growth of this bound is close to the exact one. In particular, in the case d=n, the construction provides a doubly-exponential (in n) number of vectors of multiplicities. Bibliography: 4 titles.     

Quantitative Generalized Bertini-Sard Theorem for Smooth Affine Varieties

Let X ⊂ ℂⁿ be a smooth affine variety of dimension n – r and let f = (f₁,..., f_m): X → ℂ_m be a polynomial dominant mapping. We prove that the set K(f) of generalized critical values of f (which always contains the bifurcation set B(f) of f) is a proper algebraic subset of ℂ_m. We give an explicit upper bound for the degree of a hypersurface containing K(f). If I(X)—the ideal of X—is generated by polynomials of degree at most D and deg f_i ≤ d, then K(f) is contained in an algebraic hypersurface of degree at most (d + (m – 1)(d – 1)+(D – 1)r)_n-rD_r. In particular if X is a hypersurface of degree D and f: X → ℂ is a polynomial of degree d, then f has at most (d + D – 1)_n-1D generalized critical values. This bound is asymptotically optimal for f linear. We give an algorithm to compute the set K(f) effectively. Moreover, we obtain similar results in the real case.     

Periodic Billiard Trajectories in Smooth Convex Bodies

We consider billiard trajectories in a smooth convex body in \mathbbR^d{\mathbb{R}^{d}} and estimate the number of distinct periodic trajectories that make exactly p reflections per period at the boundary of the body. In the case of prime p we obtain the lower bound (d – 2)(p – 1) + 2, which is much better than the previous estimates.     

The Multivariate Integer Chebyshev Problem

The multivariate integer Chebyshev problem is to find polynomials with integer coefficients that minimize the supremum norm over a compact set in ℂ ^d . We study this problem on general sets but devote special attention to product sets such as cube and polydisk. We also establish a multivariate analog of the Hilbert–Fekete upper bound for the integer Chebyshev constant, which depends on the dimension of space. In the case of single-variable polynomials in the complex plane, our estimate coincides with the Hilbert–Fekete result.      

Roots of Ehrhart polynomials arising from graphs

Several polytopes arise from finite graphs. For edge and symmetric edge polytopes, in particular, exhaustive computation of the Ehrhart polynomials not merely supports the conjecture of Beck et al. that all roots α of Ehrhart polynomials of polytopes of dimension D satisfy −D≤Re(α)≤D−1, but also reveals some interesting phenomena for each type of polytope. Here we present two new conjectures: (1) the roots of the Ehrhart polynomial of an edge polytope for a complete multipartite graph of order d lie in the circle |z+\fracd4| ￡ \fracd4|z+\frac{d}{4}| \le \frac{d}{4} or are negative integers, and (2) a Gorenstein Fano polytope of dimension D has the roots of its Ehrhart polynomial in the narrower strip -\fracD2 ￡ Re(a) ￡ \fracD2-1-\frac{D}{2} \leq \mathrm{Re}(\alpha) \leq \frac{D}{2}-1. Some rigorous results to support them are obtained as well as for the original conjecture. The root distribution of Ehrhart polynomials of each type of polytope is plotted in figures.