Solving polynomial inequalities over spaces of convex sets and applications

Resumo Técnico: Resolução de Inequações Polinomiais sobre Espaços de Conjuntos Convexos e Aplicações

Enunciado do Problema
O artigo aborda o problema da eliminação de incógnitas em sistemas finitos de inequações de contenção recursiva onde as incógnitas são subconjuntos convexos de um espaço vetorial real de dimensão finita $V$. Diferente das teorias de eliminação clássicas (ex: eliminação de Gauss ou Fourier–Motzkin) que operam sobre variáveis escalares, este trabalho lida com variáveis de valores de conjuntos. As restrições são definidas por expressões formais envolvendo:

• Combinações lineares convexas de variáveis e parâmetros.
• Uniões finitas.
• Somas de Minkowski.
• Uma operação especializada chamada junção geométrica positiva ($A \mathring{\star} B$), que codifica combinações convexas estritas (interiores relativos de segmentos de reta) em vez de apenas o fecho convexo.

O desafio principal é que as álgebras padrão de conjuntos convexos (usando soma de Minkowski e união) não são estáveis sob as substituições exigidas pela eliminação, pois falham em rastrear a "informação do interior relativo" gerada por combinações convexas estritas. O trabalho busca um procedimento de eliminação simbólica que preserve a única menor solução de valor de conjunto convexo de tais sistemas.

Metodologia
Os autores desenvolvem um arcabouço algébrico formal e um algoritmo inspirado na eliminação gaussiana para resolver esses sistemas.

1. Álgebra Formal de Operações de Conjuntos:
   Os autores definem uma álgebra formal envolvendo quatro operações: escala, soma de Minkowski, união e junção geométrica positiva. Eles introduzem uma classe de conjuntos chamados hemiedros, definidos como uniões finitas de interiores relativos de politopos. Esta classe mostra-se fechada sob as operações definidas e é crucial para manter a estrutura das soluções.

2. Caracterização Algébrica da Menor Solução:
   A principal contribuição teórica é um procedimento finito (Teorema 3) que transforma um sistema de inequações $X_i \geq \phi_i$ em uma forma triangular superior onde as incógnitas são eliminadas dos lados direitos. Este procedimento baseia-se em três lemas fundamentais:

   • Lema de Rearranjo: Reescreve as inequações para isolar a incógnita $X$ em uma estrutura específica envolvendo $X \mathring{\star} M$.
   • Lema de Cancelamento: Elimina a incógnita $X$ do lado direito de sua própria inequação enquanto preserva a menor solução.
   • Lema de Substituição: Substitui sistematicamente a expressão resolvida de uma variável nas inequações de outras, preservando a menor solução.

   Este processo resulta em um conjunto de polinômios $\phi^*_i$ dependentes apenas dos parâmetros, de tal modo que a menor solução para a variável $X_i$ é o fecho convexo da avaliação de $\phi^*_i$.

3. Realização Iterativa:
   O artigo também fornece uma construção iterativa (Lema 2.25) mostrando que a menor solução pode ser realizada como o limite de uma sequência crescente de conjuntos, análogo à construção de ponto fixo de Kleene, embora a eliminação algébrica forneça uma descrição finita e não iterativa.

Principais Resultados

• Teorema 1 (Resultado Principal I): Para qualquer sistema de inequações onde os conjuntos de parâmetros pertencem a uma família $\mathcal{B}$ com a "propriedade de fechamento boa" (fechada sob as operações definidas), a única menor solução consiste em conjuntos que também pertencem a $\mathcal{B}$. Se $\mathcal{B}$ possui a "propriedade de fechamento boa efetiva" (permitindo o cálculo algorítmico dessas operações), a solução pode ser computada efetivamente.

  • Corolário 1: Especificamente, se os parâmetros são uniões finitas de hemiedros, os conjuntos de coordenadas da menor solução são hemiedros e admitem descrições semilineares livres de quantificadores.

• Teorema 2 (Resultado Principal II): A teoria é aplicada a invólucros de laminação (lamination hulls). Dado um espaço vetorial $V = U \oplus \bigoplus_{i=1}^k W_i$ com $\dim W_i = 1$, e um conjunto de direções admissíveis $\Lambda = \bigcup_{i=1}^k (U + W_i)$, prova-se que o invólucro de laminação $G^{(\infty)}_\Lambda(S)$ de qualquer conjunto finito $S$ é semi-algébrico e efetivamente computável por uma fórmula livre de quantificadores.

  • A estratégia de prova envolve reduzir o problema a um sistema de inequações sobre "fibras de grade" (interseções do invólucro com fibras sobre uma grade finita no espaço $W$).
  • Mostra-se que, para grades suficientemente finas, estas fibras são a menor solução de um sistema específico de inequações, permitindo a aplicação do Teorema 1.
  • O invólucro completo é então reconstruído a partir destas fibras usando eliminação de quantificadores efetiva.

Significância e Alegações
O artigo alega várias contribuições distintas:

1. Nova Teoria de Eliminação: Estabelece uma teoria do tipo eliminação de Gauss para sistemas de inequações sobre espaços de conjuntos convexos, um cenário distinto de trabalhos anteriores sobre semiridutos poliédricos ou álgebras de Kleene.
2. Tratamento da Convexidade Estrita: Ao introduzir a junção geométrica positiva e os hemiedros, a teoria retém dados de incidência de fronteira (interiores relativos) que são tipicamente suprimidos em semiridutos poliédricos. Isso é essencial para aplicações onde o comportamento preciso da fronteira é importante.
3. Semi-algebraicidade de Invólucros de Laminação: O artigo prova que os invólucros de laminação para uma classe específica de conjuntos de direções (onde os subespaços transversais são de dimensão 1) são semi-algébricos. Isto é significativo porque:
   • A sequência de iterações que define o invólucro não precisa estabilizar (ao contrário dos fechos convexos padrão).
   • O invólucro resultante não precisa ser semi-linear (pode ter fronteiras curvas, ex: $z=xy$).
   • O invólucro não precisa ser fechado.
   • Resultados anteriores sobre a semi-algebraicidade para esta classe estavam limitados a casos onde a dimensão do subespaço "base" $U$ era pequena (0 ou 1). Este trabalho remove essa restrição, permitindo $\dim U$ arbitrário.

Aplicações
A principal aplicação discutida é na criptografia, especificamente no estudo de protocolos de computação segura de duas partes. A existência de protocolos seguros para certas distribuições é reduzida a problemas de pertinência para invólucros de laminação. O artigo observa que o comportamento da fronteira destes invólucros é crítico para estas aplicações criptográficas e não pode ser tratado por técnicas que estudam o "fecho convexo funcional" (que é sempre fechado e mais simples). Os resultados estendem teoremas anteriores de semi-algebraicidade (ex: o trabalho de Matoušek sobre invólucros D-convexos) para configurações mais gerais relevantes para estes problemas criptográficos.

Os autores afirmam explicitamente que, embora a técnica seja motivada pela criptografia, acreditam que ela tenha aplicações além do exemplo específico fornecido, embora não detalhem outras aplicações futuras específicas.