Solving polynomial inequalities over spaces of convex sets and applications

Resumen Técnico: Resolución de Inecuaciones Polinómicas sobre Espacios de Conjuntos Convexos y Aplicaciones

Planteamiento del Problema
El artículo aborda el problema de la eliminación de incógnitas en sistemas finitos de inecuaciones de contención recursiva donde las incógnitas son subconjuntos convexos de un espacio vectorial real de dimensión finita $V$. A diferencia de las teorías de eliminación clásicas (por ejemplo, la eliminación gaussiana o la de Fourier–Motzkin) que operan sobre variables escalares, este trabajo trata con variables de valores de conjunto. Las restricciones están definidas por expresiones formales que involucran:

• Combinaciones lineales convexas de variables y parámetros.
• Uniones finitas.
• Sumas de Minkowski.
• Una operación especializada llamada unión geométrica positiva ($A \mathring{\star} B$), que codifica combinaciones convexas estrictas (interiores relativos de segmentos) en lugar de solo la envolvente convexa.

El desafío principal es que las álgebras estándar de conjuntos convexos (usando la suma de Minkowski y la unión) no son estables bajo las sustituciones requeridas para la eliminación, ya que no logran rastrear la "información del interior relativo" generada por las combinaciones convexas estrictas. El trabajo busca un procedimiento de eliminación simbólica que preserve la única solución de valor de conjunto convexo más pequeña.

Metodología
Los autores desarrollan un marco algebraico formal y un algoritmo inspirado en la eliminación gaussiana para resolver estos sistemas.

1. Álgebra Formal de Operaciones de Conjuntos:
   Los autores definen un álgebra formal que involucra cuatro operaciones: escalamiento, suma de Minkowski, unión y unión geométrica positiva. Introducen una clase de conjuntos llamados hemiedros, definidos como uniones finitas de interiores relativos de politopos. Se demuestra que esta clase es cerrada bajo las operaciones definidas y es crucial para mantener la estructura de las soluciones.

2. Caracterización Algebraica de la Solución Más Pequeña:
   La contribución teórica central es un procedimiento finito (Teorema 3) que transforma un sistema de inecuaciones $X_i \geq \phi_i$ en una forma triangular superior donde las incógnitas se eliminan de los lados derechos. Este procedimiento depende de tres lemas clave:

   • Lema de Reordenamiento: Reescribe las inecuaciones para aislar la incógnita $X$ en una estructura específica que involucra $X \mathring{\star} M$.
   • Lema de Cancelación: Elimina la incógnita $X$ del lado derecho de su propia inecuación preservando la solución más pequeña.
   • Lema de Sustitución: Sustituye sistemáticamente la expresión resuelta para una variable en las inecuaciones de otras, preservando la solución más pequeña.

Este proceso produce un conjunto de polinomios $\phi^*_i$ que dependen únicamente de los parámetros, tales que la solución más pequeña para la variable $X_i$ es la envolvente convexa de la evaluación de $\phi^*_i$.

3. Realización Iterativa:
   El artículo también proporciona una construcción iterativa (Lema 2.25) que muestra que la solución más pequeña puede realizarse como el límite de una secuencia creciente de conjuntos, análoga a la construcción de punto fijo de Kleene, aunque la eliminación algebraica proporciona una descripción finita y no iterativa.

Resultos Clave

• Teorema 1 (Resultado Principal I): Para cualquier sistema de inecuaciones donde los conjuntos de parámetros pertenecen a una familia $\mathcal{B}$ con la "propiedad de clausura buena" (cerrada bajo las operaciones definidas), la solución única más pequeña consiste en conjuntos que también residen en $\mathcal{B}$. Si $\mathcal{B}$ posee la "propiedad de clausura buena efectiva" (que permite la computación algorítmica de estas operaciones), la solución puede computarse efectivamente.

  • Corolario 1: Específicamente, si los parámetros son uniones finitas de hemiedros, los conjuntos de coordenadas de la solución más pequeña son hemiedros y admiten descripciones semi-lineales libres de cuantificadores.

• Teorema 2 (Resultado Principal II): La teoría se aplica a envolventes de laminación. Dado un espacio vectorial $V = U \oplus \bigoplus_{i=1}^k W_i$ con $\dim W_i = 1$, y un conjunto de direcciones admisibles $\Lambda = \bigcup_{i=1}^k (U + W_i)$, se demuestra que la envolvente de laminación $G^{(\infty)}_\Lambda(S)$ de cualquier conjunto finito $S$ es semi-algebraica y computable efectivamente mediante una fórmula libre de cuantificadores.

  • La estrategia de prueba implica reducir el problema a un sistema de inecuaciones sobre "fibras de rejilla" (intersecciones de la envolvente con fibras sobre una rejilla finita en el espacio $W$).
  • Se demuestra que, para rejillas suficientemente finas, estas fibras son la solución más pequeña a un sistema específico de inecuaciones, lo que permite aplicar el Teorema 1.
  • La envolvente completa se reconstruye a partir de estas fibras utilizando la eliminación de cuantificadores efectiva.

Significación y Reivindicaciones
El artículo reivindica varias contribuciones distintas:

1. Nueva Teoría de Eliminación: Establece una teoría de tipo eliminación gaussiana para sistemas de inecuaciones sobre espacios de conjuntos convexos, un entorno distinto al de los trabajos previos sobre semianillos poliédricos o álgebras de Kleene.
2. Manejo de la Convexidad Estricta: Al introducir la unión geométrica positiva y los hemiedros, la teoría retiene los datos de incidencia de frontera (interiores relativos) que típicamente se suprimen en los semianillos poliédricos. Esto es esencial para aplicaciones donde el comportamiento preciso de la frontera es importante.
3. Semi-algebraicidad de las Envolventes de Laminación: El artículo demuestra que las envolventes de laminación para una clase específica de conjuntos de direcciones (donde los subespacios transversos son de dimensión 1) son semi-algebraicas. Esto es significativo porque:
   • La secuencia de iteraciones que define la envolvente no necesita estabilizarse (a diferencia de las envolventes convexas estándar).
   • La envolvente resultante no necesita ser semi-lineal (puede tener fronteras curvas, por ejemplo, $z=xy$).
   • La envolvente no necesita ser cerrada.
   • Los resultados previos sobre la semi-algebraicidad para esta clase se limitaban a casos donde la dimensión del subespacio "base" $U$ era pequeña (0 o 1). Este trabajo elimina esa restricción, permitiendo un $\dim U$ arbitrario.

Aplicaciones
La aplicación principal discutida es en criptografía, específicamente en el estudio de la computación segura de dos partes. La existencia de protocolos seguros para ciertas distribuciones se reduce a problemas de membresía para envolventes de laminación. El artículo señala que el comportamiento de la frontera de estas envolventes es crítico para estas aplicaciones criptográficas y no puede ser manejado por técnicas que estudian la "envolvente convexa funcional" (que es siempre cerrada y más simple). Los resultados extienden los teoremas de semi-algebraicidad previos (por ejemplo, el trabajo de Matoušek sobre envolventes D-convexas) a entornos más generales relevantes para estos problemas criptográficos.

Los autores declaran explícitamente que, si bien la técnica está motivada por la criptografía, creen que tiene aplicaciones más allá del ejemplo específico proporcionado, aunque no detallan otros posibles usos futuros.