Solving polynomial inequalities over spaces of convex sets and applications

Résumé Technique : Résolution d'inégalités polynomiales sur des espaces d'ensembles convexes et applications

Énoncé du Problème
L'article traite du problème de l'élimination d'inconnues dans des systèmes finis d'inégalités de confinement récursives où les inconnues sont des sous-ensembles convexes d'un espace vectoriel réel de dimension finie $V$. Contrairement aux théories d'élimination classiques (par exemple, l'élimination de Gauss ou de Fourier–Motzkin) qui opèrent sur des variables scalaires, ce travail traite de variables valant des ensembles. Les contraintes sont définies par des expressions formelles impliquant :

• Des combinaisons linéaires convexes de variables et de paramètres.
• Des unions finies.
• Des sommes de Minkowski.
• Une opération spécialisée appelée joint géométrique positif ($A \mathring{\star} B$), qui encode des combinaisons convexes strictes (intérieurs relatifs de segments de droite) plutôt que seulement l'enveloppe convexe.

Le défi principal est que les algèbres classiques d'ensembles convexes (utilisant la somme de Minkowski et l'union) ne sont pas stables sous les substitutions requises pour l'élimination car elles ne parviennent pas à suivre l'« information de l'intérieur relatif » générée par les combinaisons convexes strictes. L'article recherche une procédure d'élimination symbolique qui préserve la solution unique de plus petit ensemble convexe.

Méthodologie
Les auteurs développent un cadre algébrique formel et un algorithme inspiré de l'élimination de Gauss pour résoudre ces systèmes.

1. Algèbre Formelle des Opérations d'Ensembles :
   Les auteurs définissent une algèbre formelle impliquant quatre opérations : la mise à l'échelle, la somme de Minkowski, l'union et le joint géométrique positif. Ils introduisent une classe d'ensembles appelés hémidèdre, définis comme des unions finies d'intérieurs relatifs de polytopes. Cette classe est démontrée comme étant fermée sous les opérations définies et est cruciale pour maintenir la structure des solutions.

2. Caractérisation Algébrique de la Plus Petite Solution :
   La contribution théorique centrale est une procédure finie (Théorème 3) qui transforme un système d'inégalités $X_i \geq \phi_i$ en une forme triangulaire supérieure où les inconnues sont éliminées des membres de droite. Cette procédure repose sur trois lemmes clés :

   • Lemme de Réarrangement : Réécrit les inégalités pour isoler l'inconnue $X$ dans une structure spécifique impliquant $X \mathring{\star} M$.
   • Lemme de Annulation : Élimine l'inconnue $X$ du membre de droite de sa propre inégalité tout en préservant la plus petite solution.
   • Lemme de Substitution : Substitue systématiquement l'expression résolue d'une variable dans les inégalités des autres, préservant la plus petite solution.

Ce processus produit un ensemble de polynômes $\phi^*_i$ dépendant uniquement des paramètres, tels que la plus petite solution pour la variable $X_i$ est l'enveloppe convexe de l'évaluation de $\phi^*_i$.

3. Réalisation Itérative :
   L'article fournit également une construction itérative (Lemme 2.25) montrant que la plus petite solution peut être réalisée comme la limite d'une suite croissante d'ensembles, analogue à la construction de point fixe de Kleene, bien que l'élimination algébrique fournisse une description finie et non itérative.

Résultats Clés

• Théorème 1 (Résultat Principal I) : Pour tout système d'inégalités où les ensembles de paramètres appartiennent à une famille $\mathcal{B}$ possédant la « propriété de bonne clôture » (fermée sous les opérations définies), la solution unique de plus petit ensemble consiste en des ensembles qui appartiennent également à $\mathcal{B}$. Si $\mathcal{B}$ possède la « propriété de bonne clôture effective » (permettant le calcul algorithmique de ces opérations), la solution peut être calculée efficacement.

  • Corollaire 1 : Spécifiquement, si les paramètres sont des unions finies d'hémidèdres, les ensembles de coordonnées de la plus petite solution sont des hémidèdres et admettent des descriptions semi-linéaires sans quantificateurs.

• Théorème 2 (Résultat Principal II) : La théorie est appliquée aux enveloppes de lamination. Étant donné un espace vectoriel $V = U \oplus \bigoplus_{i=1}^k W_i$ avec $\dim W_i = 1$, et un ensemble de directions admissibles $\Lambda = \bigcup_{i=1}^k (U + W_i)$, l'enveloppe de lamination $G^{(\infty)}_\Lambda(S)$ de tout ensemble fini $S$ est prouvée être semi-algébrique et calculable efficacement par une formule sans quantificateurs.

  • La stratégie de preuve consiste à réduire le problème à un système d'inégalités sur des « fibres de grille » (intersections de l'enveloppe avec les fibres sur une grille finie dans l'espace $W$).
  • Il est démontré que pour des grilles suffisamment fines, ces fibres sont la plus petite solution à un système d'inégalités spécifique, permettant l'application du Théorème 1.
  • L'enveloppe complète est ensuite reconstruite à partir de ces fibres en utilisant l'élimination de quantificateurs efficace.

Signification et Revendications
L'article revendique plusieurs contributions distinctes :

1. Nouvelle Théorie d'Élimination : Il établit une théorie de type élimination de Gauss pour les systèmes d'inégalités sur des espaces d'ensembles convexes, un cadre distinct des travaux antérieurs sur les demi-anneaux polyédriques ou les algèbres de Kleene.
2. Gestion de la Convexité Stricte : En introduisant le joint géométrique positif et les hémidèdres, la théorie conserve les données d'incidence de bordure (intérieurs relatifs) qui sont typiquement supprimées dans les demi-anneaux polyédriques. Cela est essentiel pour les applications où le comportement précis de la frontière compte.
3. Semi-algébricité des Enveloppes de Lamination : Le papier prouve que les enveloppes de lamination pour une classe spécifique de ensembles de directions (où les sous-espaces transverses sont de dimension 1) sont semi-algébriques. Ceci est significatif car :
   • La séquence d'itérations définissant l'enveloppe n'a pas besoin de se stabiliser (contrairement aux enveloppes convexes standards).
   • L'enveloppe résultante n'a pas besoin d'être semi-linéaire (elle peut avoir des frontières courbes, par exemple $z=xy$).
   • L'enveloppe n'a pas besoin d'être fermée.
   • Les résultats précédents sur la semi-algébricité pour cette classe étaient limités aux cas où la dimension du sous-espace « de base » $U$ était petite (0 ou 1). Ce travail lève cette restriction, permettant une $\dim U$ arbitraire.

Applications
La principale application discutée est en cryptographie, spécifiquement dans l'étude des protocoles de calcul multipartite sécurisé. L'existence de protocoles sécurisés pour certaines distributions est réduite à des problèmes d'appartenance aux enveloppes de lamination. L'article note que le comportement de la frontière de ces enveloppes est critique pour ces applications cryptographiques et ne peut être traité par les techniques étudiant l'« enveloppe convexe fonctionnelle » (qui est toujours fermée et plus simple). Les résultats étendent les précédents théorèmes de semi-algébricité (par exemple, le travail de Matoušek sur les enveloppes D-convexes) à des contextes plus généraux pertinents pour ces problèmes cryptographiques.

Les auteurs déclarent explicitement que, bien que la technique soit motivée par la cryptographie, ils croient qu'elle a des applications au-delà de l'exemple spécifique fourni, bien qu'ils ne détaillent pas d'autres applications futures spécifiques.