Sobre a Resolução de Restrições Diofantinas Lineares

Ana Paula Tomás

Departamento de Ciência de Computadores & LIACC
Faculdade de Ciências, Universidade do Porto
Rua do Campo Alegre, 823, 4150-180 Porto, Portugal

Março 1997


Resumo

O tema desta tese é o estudo de algoritmos que determinam uma representação finita e completa do conjunto de soluções dum sistema de restrições lineares Diofantinas em naturais. Apresenta os resultados principais da nossa investigação incluindo também um breve resumo de trabalhos sobre este tema relevantes. Na primeira parte descrevemos dois novos métodos para determinar as soluções minimais dum sistema de equações homogéneas, designados por ``Slopes'' e ``Rectangles'', sendo o último uma variante do primeiro. Estes algoritmos determinam o conjunto de soluções minimais de forma monótona, explorando as faces do cone de soluções reais não negativas por ordem crescente de dimensão. Os seus fundamentos matemáticos incluem dois resultados principais. Caracterizamos exactamente as soluções positivas $(X,y,z)$ de $\;aX=By+Cz+V$ que são minimais para a ordem usual em $\mbox{\kern.1em \vrule width.04em height1.62ex
depth-0ex \kern-.02em \sf N}^{m+2}$, sendo $a\in
\mbox{\kern.1em \vrule width.04em height1.62ex
depth-0ex \kern-.02em \sf N}\backslash\{0\}$, $B,C\in \mbox{\kern.1em \vrule width.04em height1.62ex
depth-0ex \kern-.02em \sf N}^m$, $V\in\mbox{\sf Z\kern-.42em Z}^m$, e as variáveis $X\in\mbox{\kern.1em \vrule width.04em height1.62ex
depth-0ex \kern-.02em \sf N}^m$, $y,z\in\mbox{\kern.1em \vrule width.04em height1.62ex
depth-0ex \kern-.02em \sf N}$. Notamos e damos uma prova construtiva para o facto dum sistema de equações Diofantinas $AX=0$ cujo cone solução tem uma face $\cal F$ de dimensão $p$ com $p$ raios extremos ser equivalente a $aX_1 = {\cal A}_{11}X_3+{\cal A}_{12} X_4\;\; \wedge \;\; aX_2 =
{\cal A}_{22} X_4 $, sendo ${\cal A}_{11}$ uma matriz de inteiros não negativos com $p$ colunas, e sendo as variáveis as do sistema dado, sendo o suporte de $\cal F$ dado por $\{i \;\vert\;
\mbox{$x_i$\ em $X_1$\ ou $X_3$}\}$. Assim, para faces de dimensão 2, todas as soluções encontradas pelos algoritmos são minimais. Para faces de dimensão superior, são dados valores a $X_4$, para reduzir o problema a problemas da forma $\;aX=By+Cz+V$. Como corolário do último resultado tem-se ainda uma condição suficiente para que o conjunto de soluções minimais seja o conjunto de soluções minimais naturais dum sistema de congruências. Em suma, este trabalho sugere a análise da estrutura geométrica do conjunto de soluções para a identificação de classes de problemas para os quais um dos algoritmos possa ser mais adequado do que os outros. Mais ainda, dela pode resultar uma melhor estratégia de procura por permitir deduzir limites mais restritivos para as soluções minimais. Na segunda parte desta tese, estudamos métodos para resolução de restrições Diofantinas baseados no algoritmo de Elliott e MacMahon para sistemas de equações. Estes métodos determinam uma decomposição (não ambígua) do conjunto de soluções. O seu estudo deverá prosseguir visando encontrar decomposições mais simples, e critérios que permitam resolver várias restrições em simultâneo, em vez de uma a uma.