Asymptotic tensor rank is characterized by polynomials

Resumo Técnico: O Posto Assintótico de Tensores é Caracterizado por Polinômios

Contexto do Problema
O posto assintótico de tensores, denotado por $\tilde{R}(T)$, é um parâmetro fundamental na teoria da complexidade algébrica, definido como o limite $\lim_{n \to \infty} R(T^{\boxtimes n})^{1/n}$, onde $R$ é o posto de tensor padrão e $\boxtimes$ é o produto de Kronecker. Este parâmetro é central para determinar o expoente de multiplicação de matrizes $\omega$, sendo que $2\omega = \tilde{R}(\langle 2, 2, 2 \rangle)$. Apesar de sua importância, as propriedades computacionais e estruturais do posto assintótico são mal compreendidas. Um grande problema em aberto é se $\tilde{R}(T)$ é computável. Além disso, a conjectura do posto assintótico de Strassen postula que $\tilde{R}(T)$ é igual ao maior posto de achatamento (flattening rank) de $T$, o que implicaria que ele é sempre um inteiro e fácil de computar. Embora trabalhos recentes tenham estabelecido propriedades de discretude para parâmetros assintóticos sobre corpos finitos, o comportamento sobre corpos infinitos (como os números complexos) permanecia amplamente desconhecido.

Metodologia
Os autores abordam o problema analisando a estrutura geométrica dos conjuntos de nível subjacentes do posto assintótico e de funcionais relacionados. Eles introduzem o conceito de "funcionais admissíveis", uma classe de funções em potências de tensores que satisfazem propriedades específicas (subaditividade, submultiplicatividade, invariância por permutação, etc.), a qual inclui o posto assintótico e todos os pontos no espectro assintótico de Strassen.

A inovação metodológica central é provar que, para qualquer tal funcional admissível $\mathcal{F}$ e qualquer número real $r$, o conjunto de nível subjacente $\{T : \tilde{\mathcal{F}}(T) \leq r\}$ é Zariski-fechado. Isso é alcançado através de um argumento de decomposição mostrando que o supremo do funcional sobre o fechamento de Zariski de um conjunto $A$ é igual ao supremo sobre $A$ mesmo. Isso se baseia em expressar elementos no fechamento como combinações lineares de potências de tensores de elementos em $A$ e utilizar a análise de duplo-bloqueio assintótico.

Para estender esses resultados de formatos de tensores fixos para o conjunto de todos os tensores (dimensões arbitrárias), os autores desenvolvem novos limites inferiores para transformações de tensor-para-matriz (especificamente, quantidades $Q_{i,j}(T)$ representando o maior posto de matriz obtível em pernas específicas via restrição). Eles provam uma desigualdade relacionando o produto desses postos de transformação ao posto de achatamento $R_I(T)$, generalizando resultados anteriores para $k=3$.

Contribuições Principais e Resultados

1. Caracterização Polinomial e Computabilidade de Cima para Baixo:
   O artigo prova que o posto assintótico de tensores é "computável de cima para baixo". Para qualquer corpo computável $F$ e qualquer limite real $r$, existe um algoritmo que, dado um tensor $T$, decide se $\tilde{R}(T) \leq r$. Este algoritmo baseia-se no fato de que o conjunto de nível subjacente é Zariski-fechado, o que significa que é definido pelo desaparecimento de uma lista finita de polinômios. Embora o artigo não construa explicitamente esses polinômios, a existência deles é garantida.

2. Conjuntos de Nível Subjacente Zariski-Fechados:
   O Teorema 1.2 estabelece que, para qualquer corpo $F$, ordem $k$ e limite $r$, o conjunto $\{T : \tilde{R}(T) \leq r\}$ é Zariski-fechado. Consequentemente, o posto assintótico é semicontínuo inferior na topologia euclidiana sobre $\mathbb{C}$. Isso implica que, se uma sequência de tensores converge para um tensor limite, e todos os tensores na sequência têm posto assintótico no máximo $r$, o tensor limite também terá posto assintótico no máximo $r$.

3. Discretude de Cima para Baixo (Bem-Ordenação):
   O Teorema 1.3 prova que o conjunto de valores $\mathcal{R} = \{\tilde{R}(T) : T \in F^{d_1} \otimes \dots \otimes F^{d_k}, d_i \in \mathbb{Z}_{\geq 1}\}$ é bem-ordenado. Isso significa que qualquer sequência não crescente de postos assintóticos deve eventualmente estabilizar.

   • Implicação para Multiplicação de Matrizes: Existe uma constante $\epsilon > 0$ tal que nenhum tensor possui um posto assintótico estritamente entre $2\omega$ e $2\omega + \epsilon$. Qualquer sequência de limites superiores para $\omega$ que se aproxima dele de cima deve eventualmente "travar" no valor real.
   • Este resultado se generaliza para todas as funções no espectro assintótico de Strassen (Teorema 1.5).

4. Fechamento Euclidiano sobre $\mathbb{C}$:
   Os Teoremas 1.4 e 4.1 mostram que, quando o corpo base é $\mathbb{C}$, o conjunto de valores assumidos pelo posto assintótico é fechado na topologia euclidiana. Isso significa que o limite de qualquer sequência convergente de postos assintóticos é, em si, o posto assintótico de algum tensor.

5. Generalização para o Espectro Assintótico:
   Os autores estendem esses resultados estruturais para todo o espectro assintótico de tensores $\Delta(F, k)$. Eles provam que, para qualquer $F \in \Delta(F, k)$, o conjunto de valores atingidos é bem-ordenado. Isso é alcançado via a dualidade de Strassen e um "argumento de crescimento" envolvendo os limites inferiores de tensor-para-matriz recém-derivados (Teorema 3.2).

Significado e Alegações
O artigo alega que estes resultados fornecem uma compreensão estrutural fundamental do posto assintótico de tensores que estava ausente anteriormente, particularmente sobre corpos infinitos.

• Implicações Computacionais: A propriedade de ser "computável de cima para baixo" sugere que, embora computar o posto exato possa ser difícil, verificar um limite superior é algoritmicamente viável via avaliação polinomial.
• Implicações Estruturais: A bem-ordenação (discretude de cima para baixo) descarta a possibilidade de postos assintóticos acumularem-se arbitrariamente próximos de um valor sem o atingir. Isso fornece evidência apoiando a conjectura de Strassen, que implicaria que o conjunto de valores é simplesmente os números naturais $\mathbb{N}$.
• Problemas em Aberto: Os autores declaram explicitamente que não provam a discretude de baixo para cima (ou seja, se sequências crescentes de postos devem estabilizar). Eles observam que a conjectura de Strassen implicaria isso, mas permanece uma questão em aberto. Eles também deixam em aberto a irreduzibilidade dos conjuntos de nível subjacente para $k \geq 3$.

O trabalho faz a ponte entre a geometria algébrica (topologia de Zariski) e a teoria da complexidade, oferecendo novas ferramentas para analisar o expoente de multiplicação de matrizes e a estrutura dos parâmetros de tensores sem resolver a própria conjectura do posto assintótico.