The largest 5th pivot may be the root of a 61st degree polynomial

Resumo Técnico: O Maior Fator de Crescimento para $n=5$ e a Abordagem Híbrida Numérico-Simbólica

1. O Problema

O artigo aborda uma questão clássica e complexa da álgebra linear numérica: qual é o maior fator de crescimento possível ($g(A)$) ao realizar a eliminação de Gauss com pivoteamento completo (complete pivoting) em matrizes reais $n \times n$?

O fator de crescimento é definido como:
$$g(A) = \frac{\max_{i,j} |U_{ij}|}{\max_{i,j} |A_{ij}|}$$
onde $A = LU$ é a fatoração. Um fator de crescimento grande implica instabilidade numérica. Embora os valores exatos para $n=1, 2, 3, 4$ sejam conhecidos ($1, 2, 2.25, 4$), o valor para $n=5$ permaneceu um problema aberto por décadas.

• Contexto Histórico: Desde 1988, otimização numérica (usando pacotes como NPSOL e LANCELOT) sugeriu consistentemente um valor máximo de aproximadamente 4.1325. No entanto, não havia uma prova matemática rigorosa de que este fosse o máximo exato, nem uma forma algébrica fechada para esse número.
• Limites Conhecidos: O limite superior teórico para $n=5$ havia sido estabelecido em 1969 por Tornheim como $4 \frac{17}{18} \approx 4.94$.

2. Metodologia: Uma Fusão de Computação Numérica e Exata

Os autores (Chen, Edelman e Urschel) desenvolveram uma abordagem inovadora que combina otimização numérica moderna com técnicas de álgebra computacional exata. A metodologia segue três etapas principais:

1. Otimização Numérica (JuMP):

   • Utilizam o pacote JuMP (Julia for Mathematical Programming) para realizar otimização não linear.
   • O objetivo é encontrar matrizes que maximizem o fator de crescimento e, crucialmente, identificar quais restrições de igualdade (constraints) estão "ativas" (apertadas) na solução ótima.
   • Para $n=5$, a otimização sugere uma estrutura específica de pivoteamento onde 14 das 25 entradas da matriz inicial são $\pm 1$, e as demais variáveis satisfazem um conjunto específico de igualdades.

2. Bases de Gröbner (Eliminação de Variáveis):

   • Com as restrições de igualdade identificadas numericamente, o problema é transformado em um sistema de equações polinomiais.
   • Utilizam Bases de Gröbner (computadas via Mathematica) para eliminar variáveis dependentes não lineares. Isso reduz o sistema complexo de equações multivariadas para um sistema mais simples, eliminando variáveis como $x, y, z$ e focando na variável do fator de crescimento $g$.

3. Polinômio Discriminante (Otimização Exata):

   • Após a eliminação das variáveis auxiliares, resta uma relação polinomial entre o fator de crescimento $g$ e uma variável remanescente (ex: $z$).
   • Para encontrar o máximo exato de $g$, eles calculam o discriminante do polinômio resultante em relação a $z$. As raízes desse discriminante correspondem aos pontos críticos onde o máximo pode ocorrer.
   • Isso resulta na obtenção de um polinômio univariado em $g$ cujas raízes são os candidatos ao valor máximo.

Para Limites Superiores (Seção 3):
Para melhorar o limite superior, os autores utilizam aritmética de intervalos combinada com algoritmos de branch-and-bound. Eles:

• Construíram "caixas" (boxes) que cobrem o espaço de todas as matrizes $3 \times 3$ normalizadas com fator de crescimento alto.
• Derivaram uma condição necessária (Inequação 3.1) que relaciona a matriz $5 \times 5$ com submatrizes $3 \times 3$.
• Usaram computação exata para provar que certas combinações de submatrizes de alto crescimento são incompatíveis, reduzindo o limite superior.

3. Principais Contribuições e Resultados

A. O Valor Exato para $n=5$ (Conjectura e Prova Parcial)

• O Polinômio de 61º Grau: Os autores demonstram que o valor numérico observado de $4.1325...$ é exatamente a raiz real única de um polinômio de 61º grau com coeficientes inteiros, denotado como $P_5(g)$.
• O Valor:
  $$g \approx 4.13251707863247285422...$$
• Teorema 2.2: Eles provam rigorosamente que, dentro do conjunto de matrizes que satisfazem as restrições de igualdade sugeridas pela otimização numérica (a "Sequência 2.1"), este valor de 4.1325... é de fato o máximo.
• Conjectura 2.1: Os autores conjecturam que este limite inferior é, de fato, o máximo global para qualquer matriz $5 \times 5$ com pivoteamento completo, apesar da explosão combinatória de outras estruturas de restrições impossíveis de verificar exaustivamente.

B. Resultados para $n=6, 7, 8$
A mesma metodologia foi aplicada a dimensões maiores, produzindo novos limites inferiores (que os autores suspeitam serem máximos):

• $n=6$: O valor é exatamente 5.
• $n=7$: O valor é a raiz de um polinômio de 6º grau ($g \approx 6.0569...$).
• $n=8$: O valor é 8 (alcançado por matrizes de Hadamard e outras não-Hadamard).

C. Melhoria do Limite Superior para $n=5$

• Os autores reduziram o limite superior conhecido de $4.94$ (Tornheim, 1969) para 4.84 (Teorema 3.5).
• Embora ainda haja uma lacuna entre o limite inferior (4.1325...) e o superior (4.84), a redução demonstra a eficácia da nova técnica de análise combinada com aritmética de intervalos.

4. Significado e Impacto

1. Natureza Algébrica do Problema: O trabalho revela que o fator de crescimento máximo, embora surja de um problema de otimização contínua, possui uma estrutura algébrica profunda, sendo a raiz de um polinômio de grau elevado (61) com coeficientes inteiros. Isso desafia a intuição de que tais problemas numéricos teriam soluções "simples" ou racionais.
2. Nova Abordagem Híbrida: O artigo estabelece um novo paradigma na álgebra linear numérica: usar a otimização numérica moderna não apenas para encontrar soluções aproximadas, mas para descobrir a estrutura algébrica exata (as restrições ativas) que permite a prova matemática rigorosa subsequente.
3. Homenagem a Nick Higham: O artigo é dedicado à memória de Nick Higham, um dos maiores especialistas em estabilidade de algoritmos numéricos, cujas obras anteriores sobre o fator de crescimento inspiraram este trabalho.
4. Sequência Matemática Estranha: Se as conjecturas estiverem corretas, a sequência dos maiores fatores de crescimento para $n=1$ a $8$ seria:
   $$1, 2, 2.25, 4, \text{(raiz de polinômio de 61º grau)}, 5, \text{(raiz de polinômio de 6º grau)}, 8$$
   Uma sequência que mistura números racionais simples com raízes algébricas complexas.

Em suma, o paper fornece a melhor evidência matemática até a data de que o fator de crescimento para $n=5$ é exatamente a raiz de um polinômio específico de 61º grau, fechando uma lacuna de décadas de investigação numérica e abrindo caminho para a resolução de casos de dimensões superiores.