Border bases and order ideals: a polyhedral characterization

Abstract

Border bases arise as a canonical generalization of Gröbner bases. We provide a polyhedral characterization of all order ideals (and hence border bases) that are supported by a zero-dimensional ideal: order ideals that support a border basis correspond one-to-one to integral points of the order ideal polytope. In particular, we establish a crucial connection between the ideal and its combinatorial structure. Based on this characterization we adapt the classical border basis algorithm to allow for computing border bases for arbitrary order ideals, which are independent of term orderings. We also show that finding a maximum weight order ideal that supports a border basis is NP-hard, and that the convex hull of admissible order ideals has no polynomial polyhedral description.

26 pages; corrected typos. arXiv admin note: substantial text overlap with arXiv:0911.0859

References in corpus (4)

• Approximation Limits of Linear Programs (Beyond Hierarchies)
• Stable normal forms for polynomial system solving
• Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
• Computing Border Bases without using a Term Ordering

Cited by in corpus (2)

• On the weak order ideal associated to linear codes
• The numerical statistical fan for noisy experimental designs