Solving polynomial inequalities over spaces of convex sets and applications

Technical Summary: Solving Polynomial Inequalities over Spaces of Convex Sets and Applications

Problem Statement
The paper addresses the problem of eliminating unknowns from finite systems of recursive containment inequalities where the unknowns are convex subsets of a finite-dimensional real vector space $V$. Unlike classical elimination theories (e.g., Gaussian elimination or Fourier–Motzkin) which operate on scalar variables, this work deals with set-valued variables. The constraints are defined by formal expressions involving:

• Convex linear combinations of variables and parameters.
• Finite unions.
• Minkowski sums.
• A specialized operation called positive geometric join ($A \mathring{\star} B$), which encodes strict convex combinations (relative interiors of line segments) rather than just the convex hull.

The primary challenge is that standard algebras of convex sets (using Minkowski sum and union) are not stable under the substitutions required for elimination because they fail to track "relative-interior information" generated by strict convex combinations. The paper seeks a symbolic elimination procedure that preserves the unique smallest convex-set-valued solution of such systems.

Methodology
The authors develop a formal algebraic framework and a Gaussian-elimination-inspired algorithm to solve these systems.

1. Formal Algebra of Set Operations:
   The authors define a formal algebra involving four operations: scaling, Minkowski sum, union, and positive geometric join. They introduce a class of sets called hemihedra, defined as finite unions of relative interiors of polytopes. This class is shown to be closed under the defined operations and is crucial for maintaining the structure of the solutions.

2. Algebraic Characterization of the Smallest Solution:
   The core theoretical contribution is a finite procedure (Theorem 3) that transforms a system of inequalities $X_i \geq \phi_i$ into an upper-triangular form where the unknowns are eliminated from the right-hand sides. This procedure relies on three key lemmas:

   • Rearrangement Lemma: Rewrites inequalities to isolate the unknown $X$ in a specific structure involving $X \mathring{\star} M$.
   • Cancellation Lemma: Eliminates the unknown $X$ from the right-hand side of its own inequality while preserving the smallest solution.
   • Substitution Lemma: Systematically substitutes the solved expression for one variable into the inequalities of others, preserving the smallest solution.

   This process yields a set of polynomials $\phi^*_i$ depending only on the parameters, such that the smallest solution for variable $X_i$ is the convex hull of the evaluation of $\phi^*_i$.

3. Iterative Realization:
   The paper also provides an iterative construction (Lemma 2.25) showing that the smallest solution can be realized as the limit of an increasing sequence of sets, analogous to Kleene's fixed-point construction, though the algebraic elimination provides a finite, non-iterative description.

Key Results

• Theorem 1 (Main Result I): For any system of inequalities where the parameter sets belong to a family $\mathcal{B}$ with the "good closure property" (closed under the defined operations), the unique smallest solution consists of sets that also lie in $\mathcal{B}$. If $\mathcal{B}$ has the "effective good closure property" (allowing algorithmic computation of these operations), the solution can be effectively computed.

  • Corollary 1: Specifically, if parameters are finite unions of hemihedra, the coordinate sets of the smallest solution are hemihedra and admit quantifier-free semi-linear descriptions.

• Theorem 2 (Main Result II): The theory is applied to lamination hulls. Given a vector space $V = U \oplus \bigoplus_{i=1}^k W_i$ with $\dim W_i = 1$, and a set of admissible directions $\Lambda = \bigcup_{i=1}^k (U + W_i)$, the lamination hull $G^{(\infty)}_\Lambda(S)$ of any finite set $S$ is proven to be semi-algebraic and effectively computable by a quantifier-free formula.

  • The proof strategy involves reducing the problem to a system of inequalities over "grid fibers" (intersections of the hull with fibers over a finite grid in the $W$-space).
  • It is shown that for sufficiently fine grids, these fibers are the smallest solution to a specific system of inequalities, allowing the application of Theorem 1.
  • The full hull is then reconstructed from these fibers using effective quantifier elimination.

Significance and Claims
The paper claims several distinct contributions:

1. New Elimination Theory: It establishes a Gaussian-elimination-type theory for systems of inequalities over spaces of convex sets, a setting distinct from prior work on polyhedral semirings or Kleene algebras.
2. Handling Strict Convexity: By introducing the positive geometric join and hemihedra, the theory retains boundary-incidence data (relative interiors) that are typically suppressed in polyhedral semirings. This is essential for applications where the precise boundary behavior matters.
3. Semi-algebraicity of Lamination Hulls: The paper proves that lamination hulls for a specific class of direction sets (where the transverse subspaces are 1-dimensional) are semi-algebraic. This is significant because:
   • The sequence of iterates defining the hull need not stabilize (unlike standard convex hulls).
   • The resulting hull need not be semi-linear (it can have curved boundaries, e.g., $z=xy$).
   • The hull need not be closed.
   • Previous results on semi-algebraicity for this class were limited to cases where the dimension of the "base" subspace $U$ was small (0 or 1). This work removes that restriction, allowing arbitrary $\dim U$.

Applications
The primary application discussed is in cryptography, specifically in the study of secure two-party computation. The existence of secure protocols for certain distributions is reduced to membership problems for lamination hulls. The paper notes that the boundary behavior of these hulls is critical for these cryptographic applications and cannot be handled by techniques studying the "functional convex hull" (which is always closed and simpler). The results extend previous semi-algebraicity theorems (e.g., Matoušek's work on D-convex hulls) to more general settings relevant to these cryptographic problems.

The authors explicitly state that while the technique is motivated by cryptography, they believe it has applications beyond the specific example provided, though they do not detail other specific future applications.