Solving polynomial inequalities over spaces of convex sets and applications

Technische Samenvatting: Het oplossen van polynoom-ongelijkheden over ruimten van convexe verzamelingen en toepassingen

Probleemstelling
Het artikel behandelt het probleem van het elimineren van onbekenden uit eindige systemen van recursieve insluitingsongelijkheden waarbij de onbekenden convexe deelverzamelingen zijn van een eindig-dimensionale reële vectorruimte $V$. In tegenstelling tot klassieke eliminatietheorieën (bijv. Gauss-eliminatie of Fourier–Motzkin) die opereren op scalaire variabelen, werkt dit werk met verzameling-waardige variabelen. De beperkingen worden gedefinieerd door formele expressies bestaande uit:

• Convexe lineaire combinaties van variabelen en parameters.
• Eindige unies.
• Minkowski-sommen.
• Een gespecialiseerde operatie genaamd de positieve geometrische join ($A \mathring{\star} B$), die strikte convexe combinaties (relatieve interieurs van lijnsegmenten) codeert in plaats van enkel de convexe huls.

De primaire uitdaging is dat standaard algebraën van convexe verzamelingen (gebruikmakend van de Minkowski-som en unie) niet stabiel zijn onder de substituties die vereist zijn voor eliminatie, omdat ze er niet in slagen de "relatieve-interieur-informatie" bij te houden die wordt gegenereerd door strikte convexe combinaties. Dit werk streeft naar een symbolische eliminatieprocedure die de unieke kleinste convex-verzameling-waardige oplossing van dergelijke systemen behoudt.

Methodologie
De auteurs ontwikkelen een formeel algebraïsch kader en een algoritme geïnspireerd op Gauss-eliminatie om deze systemen op te lossen.

1. Formele algebra van verzamelingoperaties:
   De auteurs definiëren een formele algebra bestaande uit vier operaties: schaling, Minkowski-som, unie en de positieve geometrische join. Ze introduceren een klasse van verzamelingen genaamd hemihedra, gedefinieerd als eindige unies van relatieve interieurs van polytopen. Er wordt aangetoond dat deze klasse gesloten is onder de gedefinieerde operaties, wat cruciaal is voor het behoud van de structuur van de oplossingen.

2. Algebraïsche karakterisering van de kleinste oplossing:
   De kern van de theoretische bijdrage is een eindige procedure (Stelling 3) die een systeem van ongelijkheden $X_i \geq \phi_i$ transformeert naar een boven-triangulaire vorm waarbij de onbekenden worden geëlimineerd van de rechterzijden. Deze procedure rust op drie sleutellemma's:

   • Herschikkinglemma (Rearrangement Lemma): Herschrijft ongelijkheden om de onbekende $X$ te isoleren in een specifieke structuur met betrekking tot $X \mathring{\star} M$.
   • Annuleringslemma (Cancellation Lemma): Elimineert de onbekende $X$ van de rechterzijde van zijn eigen ongelijkheid, terwijl de kleinste oplossing behouden blijft.
   • Substitutielemma (Substitution Lemma): Substitueert systematisch de opgeloste expressie voor één variabele in de ongelijkheden van anderen, waarbij de kleinste oplossing behouden blijft.

   Dit proces levert een verzameling polynomen $\phi^*_i$ op die enkel afhangen van de parameters, zodanig dat de kleinste oplossing voor variabele $X_i$ de convexe huls is van de evaluatie van $\phi^*_i$.

3. Iteratieve Realisatie:
   Het artikel biedt ook een iteratieve constructie (Lemma 2.25) die laat zien dat de kleinste oplossing gerealiseerd kan worden als de limiet van een toenemende sequentie van verzamelingen, analoog aan de Kleene-fixpuntconstructie, hoewel de algebraïsche eliminatie een eindige, niet-iteratieve beschrijving biedt.

Belangrijkste Resultaten

• Stelling 1 (Hoofdresultaat I): Voor elk systeem van ongelijkheden waarbij de parametervariabelen behoren tot een familie $\mathcal{B}$ met de "goede afsluitingseigenschap" (gesloten onder de gedefinieerde operaties), bestaat de unieke kleinste oplossing uit verzamelingen die ook in $\mathcal{B}$ liggen. Als $\mathcal{B}$ de "effectieve goede afsluitingseigenschap" bezit (die het algoritmisch berekenen van deze operaties mogelijk maakt), kan de oplossing effectief berekend worden.

  • Corollary 1: Specifiek, indien parameters eindige unies van hemihedra zijn, zijn de coördinaat-verzamelingen van de kleinste oplossing hemihedra en laten zij zich beschrijven door een kwantorvrije semi-lineaire beschrijving.

• Stelling 2 (Hoofdresultaat II): De theorie wordt toegepast op laminaat-hulls (lamination hulls). Gegeven een vectorruimte $V = U \oplus \bigoplus_{i=1}^k W_i$ met $\dim W_i = 1$, en een verzameling toegestane richtingen $\Lambda = \bigcup_{i=1}^k (U + W_i)$, wordt bewezen dat de laminaat-huls $G^{(\infty)}_\Lambda(S)$ van een eindige verzameling $S$ semi-algebraïsch is en effectief berekenbaar is via een kwantorvrije formule.

  • De bewijsstrategie houdt in dat het probleem wordt gereduceerd tot een systeem van ongelijkheden over "grid-vezels" (doorsneden van de huls met vezels over een eindig grid in de $W$-ruimte).
  • Er wordt aangetoond dat voor voldoende fijne grids deze vezels de kleinste oplossing zijn van een specifiek systeem van ongelijkheden, waardoor de toepassing van Stelling 1 mogelijk is.
  • De volledige huls wordt vervolgens gereconstrueerd uit deze vezels met behulp van effectieve kwantor-eliminatie.

Betekenis en Claims
Het artikel claimt verschillende duidelijke bijdragen:

1. Nieuwe Eliminatietheorie: Het vestigt een Gauss-eliminatie-achtige theorie voor systemen van ongelijkheden over ruimten van convexe verzamelingen, een setting die verschilt van eerder werk over polyhedra-semiringen of Kleene-algebra's.
2. Omgaan met Strikte Convexiteit: Door de positieve geometrische join en hemihedra te introduceren, behoudt de theorie rand-incidentie-informatie (relatieve interieurs) die typisch wordt onderdrukt in polyhedra-semiringen. Dit is essentieel voor toepassingen waar het precieze gedrag van de rand ertoe doet.
3. Semi-algebraïciteit van Laminaat-Hulls: Het artikel bewijst dat laminaat-hulls voor een specifieke klasse van richtingverzamelingen (waarbij de transversale deelruimten 1-dimensionaal zijn) semi-algebraïsch zijn. Dit is significant omdat:
   • De sequentie van iteraties die de huls definiëren niet noodzakelijkerwijs stabiliseert (in tegen tegenstelling tot standaard convexe huls-constructies).
   • De resulterende huls niet noodzakelijkerwijs semi-lineair is (het kan gebogen randen hebben, bijv. $z=xy$).
   • De huls niet noodzakelijkerwijs gesloten is.
   • Eerdere resultaten over de semi-algebraïciteit voor deze klasse waren beperkt tot gevallen waarbij de dimensie van de "basis"-deelruimte $U$ klein was (0 of 1). Dit werk heft deze restrictie op, waardoor een willekeurige $\dim U$ is toegestaan.

Toepassingen
De primaire toepassing die wordt besproken, is in de cryptografie, specifers in de studie van veilige twee-partijen berekeningen (two-party computation). Het bestaan van veilige protocollen voor bepaalde distributies wordt gereduceerd tot lidmaatschapsvraagstukken voor laminaat-hulls. Het artikel merkt op dat het randgedrag van deze huls cruciaal is voor deze cryptografische toepassingen en niet behandeld kan worden door technieken die de "functionele convexe huls" bestuderen (die altijd gesloten en eenvoudiger is). De resultaten breiden eerdere semi-algebraïciteit-stellingen (bijv. het werk van Matoušek over D-convexe huls) uit naar algemenere settings die relevant zijn voor deze cryptografische problemen.

De auteurs verklaren expliciet dat hoewel de techniek door cryptografie is gemotiveerd, zij geloven dat het toepassingen heeft buiten het specifieke voorbeeld dat wordt gegeven, hoewel zij andere specifieke toekomstige toepassingen niet in detail uitwerken.