🔢 mathematics

Substitution and quotient of the isotropy group action

Este artigo introduz um método para corrigir soluções parciais de equações de Brent de uma forma que evita a redundância proveniente de ações de grupos de isotropia, gerando assim conjuntos de soluções parametrizados não triviais que produzem infinitos algoritmos inequivalentes de coeficientes racionais para 48 multiplicações.

Autores originais: Xin Li, Yu Wang, Shenglong Hu

Publicado 2026-07-17

📖 4 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Xin Li, Yu Wang, Shenglong Hu

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está tentando resolver um quebra-cabeça massivo e interligado, onde as peças são números e o objetivo é multiplicar enormes grades de números (matrizes) o mais rápido possível. Durante décadas, matemáticos têm caçado a maneira mais eficiente de fazer isso, procurando por "atalhos" que utilizem menos etapas de multiplicação do que o método padrão. Esses atalhos não são apenas sobre economizar tempo; eles são os motores secretos por trás de tudo, desde os gráficos de videogames até a inteligência artificial. As regras deste quebra-cabeça estão escritas em uma linguagem complexa de equações conhecidas como "equações de Brent". Pense nessas equações como um mapa para uma ilha do tesouro de algoritmos supervelozes. No entanto, há uma pegadinha: o mapa está coberto por uma névoa de simetria. Se você encontrar um tesouro, a névoa esconde milhares de outros que parecem diferentes, mas são, na verdade, o mesmo tesouro rotacionado, invertido ou esticado. Essas diferenças "falsas" são causadas pelo que os matemáticos chamam de "ação de grupo de isotropia" — uma maneira sofisticada de dizer que as peças do quebra-cabeça podem ser embaralhadas de formas específicas sem alterar a solução fundamental.

A grande questão tem sido: Como encontrar tesouros realmente novos, em vez de apenas encontrar o mesmo tesouro novamente com uma roupa diferente? Geralmente, quando matemáticos tentam dar um zoom em uma parte específica do mapa para encontrar mais soluções, eles ficam presos. Eles ou encontram um ponto único e isolado (um beco sem saída) ou encontram um caminho inteiro de soluções que são apenas uma versão "rotacionada" da original. É como tentar explorar uma floresta caminhando em círculos; você pode caminhar muito, mas nunca sairá do mesmo clareira. Este artigo, de Xin Li, Yu Wang e Shenglong Hu, introduz uma nova bússola inteligente para quebrar esse ciclo. Eles desenvolveram um método para "fixar" certas partes do quebra-cabeça de uma maneira exata, de modo que, quando você procurar por novas soluções, tenha a garantia de sair da névoa e encontrar caminhos que levem a algoritmos genuinamente diferentes e únicos.

A principal descoberta dos autores é uma técnica matemática que atua como um filtro para essas simetrias. Eles perceberam que a "névoa" de simetria tem uma forma e direção específicas, que podem ser calculadas usando algo chamado "matriz de base tangente" (pense nisso como uma agulha de bússola apontando na direção da simetria). Ao comparar essa bússola com o "espaço nulo" (as direções onde o quebra-cabeça permite movimento), eles encontraram uma regra para escolher quais peças do quebra-cabeça devem ser travadas. Se você travar as peças certas, as peças restantes livres não apenas oscilarão pelo mesmo caminho de simetria de antes; elas se ramificarão em territórios inteiramente novos.

Usando este método, a equipe testou sua teoria em alguns dos quebra-cabeças de multiplicação de matrizes mais famosos e difíceis conhecidos pela ciência. Eles começaram com uma solução conhecida para multiplicar matrizes 4x4 usando 48 etapas, uma solução encontrada por Dumas, Pernet e Sedoglavic. Ao aplicar seu filtro de "quebra de simetria", eles não apenas encontraram uma nova resposta; eles desbloquearam uma família infinita de soluções. Eles provaram que, dentro desta nova família, existem infinitos algoritmos que são matematicamente distintos e não podem ser transformados uns nos outros por simples rotações ou embaralhamentos. Eles também aplicaram isso a soluções para matrizes 3x3 (usando 23 etapas) e 4x4 (usando 49 etapas), descobrindo que, em cada caso, poderiam gerar conjuntos parametrizados de soluções — essencialmente listas infinitas de novos algoritmos únicos — onde anteriormente, pesquisadores poderiam ter encontrado apenas pontos isolados ou loops repetitivos.

O artigo não afirma ter resolvido o mistério definitivo da multiplicação de matrizes para todos os tamanhos, nem diz que todas as soluções foram encontradas agora. Em vez disso, oferece uma ferramenta poderosa: uma maneira de garantir que, ao pesquisar por novas soluções, você não esteja apenas andando em círculos. Ele transforma a busca de um jogo de "encontrar a mesma coisa novamente" em uma exploração genuína de novos cenários matemáticos, revelando que, para certos problemas, existem infinitas maneiras únicas de multiplicar matrizes de forma eficiente, esperando para serem descobertas, se apenas soubermos como olhar além da simetria.

Resumo Técnico: Substituição e Quociente da Ação do Grupo de Isotropia

Enunciado do Problema
O artigo aborda o desafio de descobrir novos conjuntos de soluções parametrizados não triviais para as equações de Brent, que regem algoritmos de multiplicação de matrizes. Especificamente, os autores focam no sistema $B(m, n, p|r)$ , cujo conjunto de soluções $V(m, n, p|r)$ descreve decomposições tensoriais do tensor de multiplicação de matrizes $\langle m, n, p \rangle$ com posto $r$ .

Um obstáculo primário na exploração desses conjuntos de soluções é a presença de uma ação de grupo de isotropia de dimensão positiva $I(m, n, p|r)$ . Este grupo consiste em quatro componentes: a ação de de Groote (sanduíche), o escalonamento de camadas (layer scaling), a permutação de somandos de posto um e a simetria $S_3$ . Como o conjunto de soluções é invariante sob este grupo, os métodos padrão de fixar soluções parciais e realizar substituição frequentemente resultam em sistemas reduzidos onde as soluções parametrizadas resultantes pertencem à mesma órbita do grupo de isotropia do original. Consequentemente, essas "novas" soluções são meramente cópias de simetria de soluções conhecidas, falhando em fornecer algoritmos genuinamente distintos. Os autores visam desenvolver um método para fixar soluções parciais de tal forma que o conjunto parametrizado resultante intersete órbitas do grupo de isotropia distintas, gerando assim infinitamente muitos algoritmos inequivalentes.

Metodologia
A metodologia proposta integra ferramentas da teoria de grupos de Lie com geometria algébrica numérica. A abordagem central envolve a análise da relação entre o nulclace da matriz Jacobiana e o espaço tangente das órbitas do grupo.

Estrutura Geométrica: Os autores modelam o conjunto de soluções $V(m, n, p|r)$ como uma variedade folheada pelas órbitas do grupo de isotropia $I(m, n, p|r)$ . Fixar uma solução parcial corresponde a interceptar esta variedade com um espaço linear de coordenadas afins $L_I$ .
Matrizes de Base de Nulclace e de Tangente:
- Matriz de Base do Nulclace ( $N(s)$ ): Derivada da matriz Jacobiana $J(s)$ das equações de Brent em uma solução suave $s$ . Seu posto $d$ representa a dimensão local do conjunto de soluções.
- Matriz de Base da Tangente ( $T(s)$ ): Construída usando os geradores infinitesimais da ação do grupo de Lie (especificamente os grupos de de Groote e de escalonamento de camadas). Seu posto $d_T$ representa a dimensão da órbita do grupo que passa por $s$ .
Critério de Seleção: Os autores propõem um critério de primeira ordem para selecionar um subconjunto de variáveis $I$ $I$ para fixar. Eles buscam um conjunto de índices $I$ $I$ tal que:
$\text{posto } N(s) - \text{posto } N_I(s) > \text{posto } T(s) - \text{posto } T_I(s)$
onde $N_I(s)$ $N_{I} (s)$ e $T_I(s)$ $T_{I} (s)$ são submatrizes restritas às linhas indexadas por $I$ $I$ .
- Se a desigualdade for estritamente verdadeira, o sistema reduzido possui direções lineares em $s$ que não são tangentes à órbita do grupo. Isso implica que o conjunto de soluções reduzido intercepta infinitamente muitas órbitas de grupo distintas.
- Se os postos forem iguais, o sistema reduzido provavelmente permanece dentro de uma única órbita (ou uma união finita de órbitas), não gerando novas soluções inequivalentes.
Implementação: O método é implementado em Julia. O processo envolve:
- Verificar a suavidade de uma solução conhecida via sequências de deflação.
- Computar $J(s)$ , $N(s)$ e $T(s)$ .
- Buscar conjuntos de índices $I$ que satisfaçam a condição de lacuna de posto (rank gap).
- Resolver o sistema polinomial reduzido resultante (frequentemente usando bases de Gröbner via Oscar.jl) para obter curvas parametrizadas ou conjuntos de dimensão superior.

Contribuições Principais

Critério Teórico: O artigo estabelece um critério rigoroso de primeira ordem (Equação 3.10) baseado na diferença entre a codimensão das variáveis fixadas no nulclace versus no espaço tangente. Este critério garante que o processo de substituição gere soluções em diferentes órbitas do grupo de isotropia.
Construção Explícita: Os autores fornecem fórmulas explícitas para computar a matriz de base da tangente $T(s)$ para as equações de Brent, contabilizando a estrutura específica das ações de de Groote e de escalonamento de camadas.
Estrutura Algorítmica: Um procedimento prático, passo a passo, é delineado para transformar soluções conhecidas em famílias de soluções inequivalentes, superando as armadilhas de "solução isolada" ou "mesma órbita" de tentativas de substituição anteriores.

Resultados
Os autores aplicaram seu método a várias soluções conhecidas das equações de Brent:

$V(4, 4, 4|48)$ (Solução de Dumas, Pernet e Sedoglavic):
- A solução possui uma dimensão local de 151, enquanto a dimensão da órbita é 141.
- Ao fixar 2082 variáveis, os autores reduziram o sistema para 222 variáveis.
- O conjunto de soluções resultante é uma curva unidimensional contendo infinitos pontos pertencentes a órbitas $I(4, 4, 4|48)$ distintas. Isso fornece infinitos algoritmos inequivalentes para multiplicação de matrizes $4 \times 4$ com 48 multiplicações usando coeficientes racionais.
- Lacunas de posto maiores também foram encontradas, permitindo conjuntos parametrizados de dimensão superior.
$V(4, 4, 4|49)$ (Solução do AlphaTensor):
- A solução possui uma dimensão local de 197 e uma dimensão de órbita de 143.
- Fixar 2344 variáveis reduziu o sistema para 8 variáveis, gerando uma curva parametrizada unidimensional de soluções inequivalentes.
- Fixar 2269 variáveis resultou em um sistema reduzido com 83 variáveis e um conjunto de soluções de dimensão 9, demonstrando a capacidade de gerar famílias de alta dimensão de novos algoritmos.
$V(3, 3, 3|23)$ (Solução de Laderman):
- A solução possui uma dimensão local de 76 e uma dimensão de órbita de 70.
- Fixar 613 variáveis reduziu o sistema para 8 variáveis, produzindo uma curva unidimensional de soluções inequivalentes.
- Fixar 574 variáveis resultou em um conjunto de soluções parametrizadas de dimensão 6.

Significância
O artigo afirma que este método supera com sucesso as limitações das técnicas de substituição anteriores, que frequentemente falhavam em distinguir entre soluções de simetria equivalente e algoritmos genuinamente novos. Ao utilizar a matriz de base da tangente para identificar direções "transversas" em relação à ação do grupo, os autores podem extrair sistematicamente famílias parametrizadas não triviais a partir de soluções conhecidas.

A principal significância reside na capacidade de gerar infinitos algoritmos inequivalentes para multiplicação de matrizes a partir de uma única solução conhecida. Por exemplo, a parametrização da solução racional para multiplicação de matrizes $4 \times 4$ com 48 multiplicações demonstra que não existe apenas um tal algoritmo, mas uma família infinita deles com coeficientes racionais. Isso expande o panorama conhecido dos algoritmos de multiplicação de matrizes e fornece uma ferramenta sistemática para explorar a geometria das equações de Brent. Os autores observam que, embora o método dependa da suposição de interseção transversa, experimentos numéricos confirmam sua eficácia para soluções suaves nos casos testados.

Mais como este