Representing simple d-dimensional polytopes by d polynomials

Gennadiy Averkov, Martin HenkMath. Program 2011 · DOI

TL;DR

This paper proves a long-standing conjecture that any simple d-dimensional polytope can be represented by exactly d polynomial inequalities. The authors provide an explicit constructive method for finding these polynomials, which is a significant advancement over previous non-constructive proofs.

What Problem Does This Paper Address?

The paper tackles the problem of representing geometric objects, specifically convex polytopes, using algebraic inequalities. A convex polytope in d-dimensional space (Rd) can be defined as the intersection of half-spaces, which can be expressed using linear inequalities. However, the question arises: can we represent these polytopes using a smaller set of polynomial inequalities?

Specifically, the paper focuses on the "polynomial representation" of a polytope P, defined as a set of polynomials {p1(x), ..., pn(x)} such that P = {x ∈ Rd : pi(x) ≥ 0 for all i}. The key quantity of interest is s(d, P), the minimum number of polynomials needed for such a representation. While it's known that s(d, P) is at most 2d-1, a conjecture proposed that for any convex d-polytope, s(d, P) = d. This paper confirms this conjecture for a specific, important class of polytopes: simple d-polytopes. A simple polytope is one where each vertex is incident to exactly d facets (the (d-1)-dimensional faces). This is a crucial simplification, as it implies a high degree of regularity at the vertices.

Methods

The core of the paper is a constructive proof of the conjecture for simple d-polytopes. The authors leverage the properties of elementary symmetric polynomials, denoted by σl(y1, ..., ym). These polynomials are formed by summing all products of l distinct variables from a given set.

The construction involves defining a set of polynomials {p0(x), p1(x), ..., pd-1(x)} that represent the simple polytope P. The key idea is to use the affine functions qF(x) associated with each facet F of the polytope. These functions are normalized such that qF(x) = 0 on the facet F and qF(x) ≤ 1 for points within the polytope.

The polynomials pi(x) are then constructed using combinations of these qF(x) functions and the elementary symmetric polynomials. A crucial part of the proof involves showing that these d polynomials indeed define the polytope and that the construction is explicit. The proof also involves intricate analysis of the behavior of these polynomials near the vertices of the polytope and relies on several lemmas that bound the values of these polynomials and their properties.

A significant portion of the paper is dedicated to proving auxiliary lemmas that establish the properties of these constructed polynomials, particularly their non-negativity and their behavior in relation to the polytope's structure. These lemmas involve concepts like normal cones, support functions, and the Hausdorff distance for convergence of sets.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on the mathematical properties of polytopes and polynomials, not on empirical data.

Key Insights and Ideas

  • Confirmation of a Major Conjecture: The paper definitively proves that simple d-polytopes can be represented by exactly d polynomial inequalities, settling a long-standing conjecture in the field. This is a fundamental result for understanding the algebraic nature of geometric objects.
  • Constructive Proof: Unlike previous proofs that relied on non-constructive existence theorems, this paper provides an explicit algorithm and construction for finding these d polynomials. This is a significant practical and theoretical advancement, opening doors for algorithmic applications.
  • Role of Elementary Symmetric Polynomials: The paper highlights the power of elementary symmetric polynomials in constructing these representations. Their properties are central to ensuring the polynomials correctly define the polytope.
  • Connection to Vertex Structure: The simplicity of the polytope (each vertex incident to d facets) is crucial. The construction leverages this regularity, suggesting that the complexity of the representation is directly tied to the combinatorial structure at the vertices.
  • Approximation and Convergence: The paper also explores how these polynomial representations can approximate the polytope and how these approximations converge to the polytope as parameters are adjusted. This connects to broader themes in real algebraic geometry and computational geometry.

Key Results

  • Theorem 1.1: For any simple d-polytope P in Rd, the minimum number of polynomials required for a polynomial representation is exactly d (i.e., s(d, P) = d).
  • Explicit Construction: The paper provides a concrete method to construct these d polynomials, p0(x), ..., pd-1(x), given the affine inequalities defining the polytope.
  • Properties of Constructed Polynomials: The proof establishes that these constructed polynomials satisfy the required inequalities and that the resulting semi-algebraic set precisely defines the polytope.

Limitations and Future Work

  • Simplicity Constraint: The main result is proven for simple d-polytopes. The paper acknowledges that the conjecture s(d, P) = d for all convex d-polytopes remains open. Extending the constructive proof to non-simple polytopes is a natural next step.
  • Algorithmic Complexity: While the proof is constructive, the paper mentions that the algorithm for finding the parameters (like k in Theorem 3.5) can be complex. Further work could focus on optimizing these algorithms for practical computation.
  • Generalization: The paper hints at connections to approximating convex bodies and the construction of algebraic surfaces. Exploring these connections more deeply and generalizing the results to other classes of geometric objects or algebraic structures could be fruitful.

Summary updated

BibTeX
@article{averkov2011representing,
  author = {Gennadiy Averkov and Martin Henk},
  title = {{Representing simple d-dimensional polytopes by d polynomials}},
  journal = {Math. Program.},
  year = {2011},
  doi = {10.1007/s10107-009-0280-y},
}
Figure