Biquadratic SOS Rank and Double Zarankiewicz Number

Este artigo introduz o conceito de número de Zarankiewicz duplo ($z_2$) para bipartidos com arestas simples e duplas, estabelecendo que ele fornece um limite inferior mais preciso para o posto de soma de quadrados (SOS) de formas biquadráticas e determinando seus valores exatos para diversos casos pequenos, como $z_2(4,3)=8$, superando assim as fronteiras anteriores conhecidas.

O essencial

Imagine que você está organizando uma grande festa com dois grupos de convidados: Grupo X (com $m$ pessoas) e Grupo Y (com $n$ pessoas).

O objetivo da festa é criar o maior número possível de parcerias (ou "conexões") entre alguém do Grupo X e alguém do Grupo Y, mas com uma regra estrita: ninguém pode formar um quadrado perfeito.

O Problema do "Quadrado Proibido" (O Círculo de 4)

Na linguagem da matemática, esse "quadrado" é chamado de $C_4$. Imagine quatro pessoas: duas do Grupo X (digamos, Ana e Bia) e duas do Grupo Y (Carlos e Daniel). Se Ana se conecta com Carlos, Ana com Daniel, Bia com Carlos e Bia com Daniel, você formou um quadrado fechado. A regra da festa diz: isso é proibido.

O número clássico de Zarankiewicz ($z(m, n)$) é simplesmente a resposta para a pergunta: "Qual é o número máximo de parcerias que posso fazer sem criar nenhum desses quadrados proibidos?"

A Grande Descoberta: O "Super-Par"

Até recentemente, os matemáticos achavam que essa era a única maneira de contar. Mas, em um caso específico (4 pessoas de um lado, 3 do outro), eles descobriram uma brecha.

Eles perceberam que, em vez de apenas fazer conexões simples (uma linha entre duas pessoas), você pode criar um "Super-Par".

• Conexão Simples (1-edge): Uma linha direta entre Ana e Carlos.
• Super-Par (2-edge): Uma conexão especial que envolve duas pessoas de cada lado ao mesmo tempo, como se fosse um "casamento duplo" ou um "tiro duplo". Na matemática, isso é representado como o quadrado de uma soma: $(Ana \cdot Carlos + Bia \cdot Daniel)^2$.

Essa "Super-Par" conta como duas conexões na contagem final, mas ocupa um espaço diferente no "tabuleiro" da festa.

O que é o "Número Duplo de Zarankiewicz"?

Os autores deste artigo (Qi, Cui e Xu) criaram uma nova métrica chamada Número Duplo de Zarankiewicz ($z_2(m, n)$).

Pense assim:

1. O Problema Antigo: Quantas linhas simples posso desenhar num papel quadriculado sem formar um quadrado?
2. O Novo Problema: Quantas linhas simples E quantos "Super-Pares" (que ocupam dois cantos do quadrado de uma vez) posso colocar sem formar um quadrado proibido?

A grande revelação do artigo é que, ao permitir esses "Super-Pares", você consegue colocar mais conexões do que o limite antigo permitia, sem violar a regra do quadrado.

Os Resultados Práticos (A Festa em Números)

Os matemáticos calcularam exatamente quantas conexões são possíveis em festas pequenas:

• Festa 4x3:

  • Regra antiga: O máximo era 7 conexões.
  • Nova regra: Com os "Super-Pares", conseguimos 8 conexões.
  • Analogia: Era como se você tivesse 7 cadeiras em uma mesa. De repente, descobriu-se que pode empilhar duas cadeiras em uma base especial, permitindo colocar 8 pessoas no mesmo espaço sem quebrar a mesa.

• Festa 5x3:

  • Regra antiga: O máximo era 8.
  • Nova regra: Conseguimos 9.

• Festa 4x4 (O Mistério):

  • Regra antiga: O máximo era 9.
  • Nova regra: Conseguimos provar que dá para chegar a 10.
  • O que falta saber: Será que dá para chegar a 11? Os autores dizem que 10 é possível, mas 11 é um mistério. Eles apostam que 10 é o limite real, mas ainda não conseguiram provar matematicamente que 11 é impossível.

Por que isso importa? (A Conexão com o Mundo Real)

Você pode estar se perguntando: "E daí? É só um jogo de conectar pontos?"

Na verdade, isso tem a ver com otimização e inteligência artificial.

• Os "parceiros" são variáveis em equações complexas.
• O "quadrado proibido" representa um erro ou uma ineficiência no sistema.
• O "número de conexões" representa a complexidade ou o esforço necessário para resolver um problema.

Ao descobrir que podemos usar "Super-Pares" para aumentar o número de conexões, os autores estão dizendo aos engenheiros e cientistas de dados: "Ei, vocês podem resolver problemas mais complexos (ou representá-los de forma mais eficiente) do que pensávamos antes, usando uma estrutura matemática que ninguém estava olhando."

Resumo em uma frase

Este artigo mostra que, ao permitir "casamentos duplos" (Super-Pares) em vez de apenas "namoros simples" (conexões diretas), conseguimos organizar festas matemáticas muito maiores e mais complexas sem criar os quadrados proibidos que antes limitavam nosso crescimento. Isso abre novas portas para entender como resolver problemas difíceis de otimização.

Resumo técnico

Resumo Técnico: Rank SOS Biquadrático e Número de Zarankiewicz Duplo

Autores: Liqun Qi, Chunfeng Cui e Yi Xu.
Data: Março de 2026.

1. Problema e Motivação

O artigo aborda o problema de determinar o rank máximo de soma de quadrados (SOS) de formas biquadráticas $m \times n$, denotado por $BSR(m, n)$. Uma forma biquadrática $P(x, y)$ é SOS se puder ser escrita como uma soma finita de quadrados de formas bilineares. O rank SOS é o menor número de termos necessários para essa representação.

Recentemente, foi estabelecido que $BSR(m, n) \geq z(m, n)$, onde $z(m, n)$ é o número de Zarankiewicz clássico (o número máximo de arestas em um grafo bipartido $m \times n$ que não contém um ciclo $C_4$ completo, ou seja, $K_{2,2}$). No entanto, uma lacuna foi descoberta no caso $4 \times 3$:

• $z(4, 3) = 7$ (limite clássico).
• $BSR(4, 3) \geq 8$.
  A discrepância surgiu da construção de uma forma biquadrática que adiciona o quadrado de uma forma bilinear com dois termos, $(x_4y_2 + x_1y_3)^2$, a uma forma simples baseada em um grafo livre de $C_4$. Isso sugeriu que o limite clássico de Zarankiewicz não capturava totalmente a complexidade dos ranks SOS quando se permitem termos cruzados (quadrados de somas).

O objetivo deste trabalho é formalizar essa lacuna introduzindo uma nova estrutura combinatória e um novo parâmetro numérico.

2. Metodologia e Definições Fundamentais

Os autores introduzem o conceito de Número de Zarankiewicz Duplo, denotado por $z_2(m, n)$, baseado em uma nova classe de grafos bipartidos generalizados.

• Grafos com Arestas Duplas (2-arestas):

  • 1-arestas ($E_1$): Arestas ordinárias do tipo $(i, j)$, correspondendo a termos $x_i^2 y_j^2$.
  • 2-arestas ($E_2$): Arestas do tipo $(i, j; k, l)$, correspondendo a quadrados de formas bilineares de dois termos: $(x_i y_j + x_k y_l)^2$.
  • Uma forma biquadrática associada a tal grafo $G$ é definida como:
    $$P_G(x, y) = \sum_{(i,j) \in E_1} x_i^2 y_j^2 + \sum_{(i,j;k,l) \in E_2} (x_i y_j + x_k y_l)^2$$
  • Se $P_G$ for irredutível, seu rank SOS é exatamente $|E_1| + |E_2|$.

• Ciclo $C_4$ Generalizado:
  Para garantir a irredutibilidade (e, portanto, que o rank seja igual ao número de arestas), os autores definem uma condição de proibição de "Ciclo $C_4$ Generalizado". Um grafo contém tal ciclo se:

  1. Condição Combinatória (i): Em qualquer submatriz $2 \times 2$(duas linhas distintas e duas colunas distintas), o número total de arestas "ordinárias" (contando 1-arestas como 1 e 2-arestas completas dentro do bloco como 2) seja$\geq 4$.
  2. Condição Algébrica (ii): Existe uma combinação linear não trivial dos vetores de base associados às arestas dentro de um bloco $2 \times 2$ que se anula. Isso garante a independência linear necessária para a irredutibilidade.

• Definição de $z_2(m, n)$: É o número máximo total de arestas ($|E_1| + |E_2|$) em um grafo bipartido $m \times n$ que não contém um ciclo $C_4$ generalizado.

3. Contribuições Principais e Resultados

O artigo estabelece a relação fundamental $BSR(m, n) \geq z_2(m, n)$ e determina valores exatos ou limites para vários casos pequenos.

• Teorema Fundamental (2.4): Para quaisquer $m, n \geq 2$, $BSR(m, n) \geq z_2(m, n)$. Isso é provado mostrando que qualquer grafo que atinja $z_2(m, n)$ gera uma forma biquadrática irredutível com rank igual ao número de arestas.

• Valores Exatos Determinados:

  • Casos Triviais/Lineares:
    • $z_2(m, 2) = m + 1$
    • $z_2(2, n) = n + 1$
    • (Coincide com o caso clássico $z(m, 2)$ e $z(2, n)$).
  • Caso $3 \times 3$:
    • $z_2(3, 3) = 6$ (Igual a $z(3, 3)$).
  • Caso $4 \times 3$ (Resolvendo a lacuna):
    • $z_2(4, 3) = 8$.
    • Isso confirma que $BSR(4, 3) \geq 8$, superando o limite clássico $z(4, 3) = 7$. A construção ótima utiliza 7 arestas simples e 1 aresta dupla.
  • Caso $5 \times 3$:
    • $z_2(5, 3) = 9$.
    • Melhora o limite clássico $z(5, 3) = 8$.

• Caso $4 \times 4$ (Problema em Aberto):

  • Os autores estabelecem os limites: $10 \leq z_2(4, 4) \leq 11$.
  • Limite Inferior (10): Uma construção explícita com 8 arestas simples e 2 arestas duplas que evita ciclos generalizados.
  • Limite Superior (11): Derivado de argumentos de contagem em submatrizes $2 \times 2$.
  • O valor exato permanece como um problema aberto, embora os autores conjecturem que seja 10.

4. Significado e Implicações

• Ponte entre Teoria dos Grafos e Álgebra: O trabalho cria uma ligação rigorosa entre a teoria de grafos extremal (problema de Zarankiewicz) e a representação de soma de quadrados (SOS) de formas polinomiais.
• Refinamento de Limites Inferiores: Demonstra que o limite clássico de Zarankiewicz é insuficiente para capturar o comportamento máximo do rank SOS em certas dimensões. A introdução de "arestas duplas" (quadrados de formas bilineares mistas) permite construir formas com ranks mais altos do que o previsto apenas por grafos livres de $C_4$ simples.
• Novas Direções de Pesquisa:
  • Determinar o valor exato de $z_2(4, 4)$.
  • Investigar o comportamento assintótico de $z_2(m, n)$ para $m, n$ grandes (a melhoria é linear ou quadrática em relação a $z(m, n)$?).
  • Explorar se toda forma SOS extremal pode ser representada por um grafo de Zarankiewicz duplo (a recíproca do teorema principal).
  • Desenvolver algoritmos eficientes para verificar a condição de ciclo generalizado e calcular $z_2(m, n)$.

Em conclusão, o artigo redefine os limites inferiores conhecidos para o rank SOS de formas biquadráticas, introduzindo um novo invariante combinatório ($z_2$) que é estritamente maior que o número de Zarankiewicz clássico em casos específicos ($4 \times 3$,$5 \times 3$), oferecendo uma ferramenta mais precisa para a análise de irredutibilidade em otimização e álgebra real.