Resumo Técnico: Randomstrasse101: Open Problems of 2025

Autores: Afonso S. Bandeira, Daniil Dmitriev, Kevin Lucca, Petar Nizic-Nikolac, Almut Rödder (e colaboradores do blog).
Data: Abril de 2026 (registrando problemas de 2025).
Contexto: O documento compila 16 problemas abertos (destacados aqui os das entradas 8 a 14) focados em Teoria da Probabilidade, Computação, Combinatória e Estatística. O objetivo é servir como um registro estável para referência acadêmica de conjecturas e questões abertas consideradas intrigantes pela comunidade do Departamento de Matemática do ETH Zurique.

Abaixo, detalhamos os problemas e contribuições técnicas apresentados nas entradas selecionadas do documento.

---

1. Desigualdades de Concentração para Tensores (Entry 8)

Problema: Determinar limites superiores para a norma injetiva $\ell_p$ de uma soma ponderada por variáveis gaussianas de tensores determinísticos simétricos. Formalmente, busca-se limitar $\mathbb{E}[\|\sum g_i T_i\|_{I_p}]$.
Contexto e Metodologia:

• O problema conecta teoria de códigos, EDPs dispersivas, PCA de tensores e geometria de espaços de Banach.
• Para matrizes ($r=p=2$), a desigualdade é bem compreendida (desigualdade de Khintchine não comutativa), onde o comportamento assemelha-se ao caso escalar com um fator logarítmico.
• Para tensores gerais ($r, p \ge 2$), a aproximação via traços (usada para matrizes) falha, pois calcular normas injetivas é NP-difícil.
• A abordagem utiliza o controle do processo gaussiano via a integral de entropia de Dudley, que depende do número de cobertura $N(B^d_p, D, \epsilon)$.
  Contribuições e Resultados:
• Conjectura 16: Propõe que a esperança da norma é limitada por $\tilde{O}_{r,p}(d^{1/2 - 1/p} \sqrt{\sum \|T_i\|^2_{I_p}})$.
• Resultados parciais foram obtidos para $p \ge 2r$ usando técnicas de cobertura, mas existe uma barreira volumétrica para $p < 2r$.
• Trabalhos recentes (Aden-Ali, Boedihardjo) removeram fatores logarítmicos em casos específicos (entradas independentes), mas o caso geral permanece aberto.

2. O Número de Lovász de Grafos Circulantes Aleatórios (Entry 9)

Problema: Caracterizar o comportamento assintótico do número de Lovász ($\vartheta(G)$) para grafos circulantes aleatórios densos.
Contexto e Metodologia:

• O número de Lovász fornece um limite superior computável para o número cromático e um limite inferior para a capacidade de Shannon.
• Para grafos de Erdős-Rényi $G(n, 1/2)$, conjectura-se que $\mathbb{E}[\vartheta(G)] \sim \sqrt{n}$.
• Grafos circulantes são definidos sobre o grupo cíclico $\mathbb{Z}_n$, permitindo que suas matrizes de adjacência sejam diagonalizadas pela Transformada Discreta de Fourier (DFT).
• A formulação do problema é transformada em um Programa Linear (LP) nos domínios do "tempo" e da "frequência".
  Contribuições e Resultados:
• Conjectura 18: Estende a conjectura de $\sqrt{n}$ para grafos circulantes aleatórios densos.
• Resultado Parcial (BBD+25): Fornece um limite inferior preciso e um limite superior de $O(\sqrt{n} \log \log n)$.
• A técnica utiliza a Propriedade de Isometria Restrita (RIP) da matriz DFT amostrada para analisar o programa linear dual.

3. Injetividade e Estabilidade na Recuperação de Fase (Entry 10)

Problema: Determinar as condições necessárias e suficientes para a injetividade e estabilidade da recuperação de um vetor $x$ a partir de medições de módulo $|Ax|$.
Contexto e Metodologia:

• No caso complexo, a conjectura original de que $N \ge 4M-4$ medições são necessárias foi refutada (contra-exemplo com 11 medições em $\mathbb{C}^4$).
• A questão agora foca na probabilidade de injetividade para $N = 4M-5$.
• Para a estabilidade, o problema é ligado à propriedade de complementaridade e ao número de condição de subconjuntos de linhas da matriz $A$.
  Contribuições e Resultados:
• Conjectura 19: Propõe que para $N=4M-5$, a probabilidade de injetividade é estritamente menor que 1 e tende a 0 quando $M \to \infty$.
• Conjectura 20 (Balan-Wang): Relaciona a estabilidade $\omega(A)$ ao máximo das normas das linhas de $A$, sugerindo uma dependência de potência $\beta$.
• Problema Aberto 21: Determinar o valor exato de $\omega(A)$ para matrizes gaussianas e verificar a validade da conjectura de Balan-Wang.

4. Bases Mutuamente Inviáveis (MUBs), ETFs e a Conjectura de Zauner (Entry 11)

Problema: Investigar a existência e o número máximo de Bases Mutuamente Inviáveis (MUBs) e Frames Equiangulares Apertados (ETFs).
Contexto e Metodologia:

• MUBs: Dois bases ortonormais são mutuamente inviáveis se o produto interno entre qualquer par de vetores de bases diferentes tem módulo $1/\sqrt{d}$. Sabe-se que $MUB(d) \le d+1$.
• ETFs: Frames onde todos os vetores têm norma unitária e produtos internos constantes. ETFs com $n=d^2$ vetores são chamados de SIC-POVMs.
• A abordagem utiliza Provas de Soma de Quadrados (Sum-of-Squares - SoS) para provar a inexistência de certas configurações.
  Contribuições e Resultados:
• Conjectura 22: $MUB(6) < 7$ (o caso $d=6$ é o menor aberto e mais famoso).
• Problema Aberto 23: Existe uma prova SoS de grau 4 para a inexistência de 7 MUBs em $\mathbb{C}^6$?
• Conjectura 24 (Zauner): ETFs existem para toda dimensão $d$. Progressos recentes (AFK25) provaram condicionalmente a existência baseada em conjecturas de teoria dos números (Conjecturas de Stark), mas uma prova incondicional permanece ausente.

5. Número de Clique do Grafo de Paley (Entry 12)

Problema: Estabelecer limites superiores para o número de clique $\omega(G_p)$ do grafo de Paley (grafos pseudo-aleatórios definidos por resíduos quadráticos).
Contexto e Metodologia:

• O grafo de Paley é isomorfo ao seu complemento, então $\omega(G_p) = \alpha(G_p)$.
• Limites clássicos usam o número de Lovász ($\vartheta$) ou métodos espectrais, resultando em $\omega(G_p) \le \sqrt{p}$.
• A pesquisa investiga se relaxações convexas (como SoS de grau 4) podem melhorar significativamente este limite, possivelmente para polilogarítmico.
  Contribuições e Resultados:
• Conjectura 25: $\omega(G_p) = O(\text{polylog}(p))$.
• Conjectura 26 & 27: Analisam localizações do grafo (subgrafos induzidos por vizinhanças) e sugerem que $\vartheta(G_{p,2})$ pode ser limitado por $2/3 \sqrt{p}$.
• Conjectura 28: Relaxações SoS de grau 4 podem fornecer limites $O(p^{1/2 - \epsilon})$.
• Conjectura 29: A construção do ETF de Paley satisfaz a Propriedade de Isometria Restrita (RIP) além do "gargalo da raiz quadrada".

6. A Conjectura KLS e Implicações (Entry 13)

Problema: Determinar se a constante isoperimétrica de medidas log-côncavas é limitada inferiormente por uma constante universal independente da dimensão.
Contexto e Metodologia:

• A conjectura KLS (Kannan-Lovász-Simonovits, 1995) afirma que, para medidas log-côncavas, o "gargalo" (bottleneck) é minimizado por semi-espaços, similar ao caso Gaussiano.
• Isso tem implicações diretas em desigualdades de Poincaré, concentração de Lipschitz e tempos de mistura de cadeias de Markov (Ball Walk).
• A evolução histórica inclui métodos de localização, localização estocástica (Eldan) e bootstrapping.
  Contribuições e Resultados:
• Estado da Arte: O limite inferior melhor conhecido é $\psi_n \ge C (\log n)^{-1/2}$ (Klartag, 2023).
• Conexões Recentes: A resolução da Conjectura da Casca Fina (Thin Shell Conjecture) por Klartag e Lehec (2025) implica o limite atual para KLS.
• Problema de Slicing de Bourgain: Também resolvido recentemente (2024/2025), está intimamente ligado a KLS via transformada de Laplace logarítmica. A prova de KLS implica a solução do problema de Slicing.

7. Limites Precisos para Matrizes de Grafos (Entry 14)

Problema: Estabelecer limites de norma espectral precisos (sem fatores logarítmicos desnecessários) para matrizes de grafos usadas na análise da hierarquia Sum-of-Squares (SoS).
Contexto e Metodologia:

• As matrizes de grafos ($M_\alpha$) são usadas para construir pseudo-expectações em problemas de otimização polinomial aleatória (ex: Planted Clique).
• O método de momentos clássico fornece limites com fatores logarítmicos $O(n^{f(\alpha)} (\log n)^{g(\alpha)})$.
• A abordagem recente utiliza "Matrix Chaoses" e desigualdades de concentração de matrizes iteradas.
  Contribuições e Resultados:
• Conjectura 31: Propõe que a norma esperada é exatamente $\Theta(n^{f(\alpha)} (\log n)^{g(\alpha)})$, onde $f$ e $g$ dependem apenas da forma $\alpha$.
• O objetivo é eliminar os fatores logarítmicos desnecessários ($g(\alpha)=0$) quando possível, o que levaria a limites inferiores mais fortes para a hierarquia SoS.
• A compreensão espectral dessas matrizes é crucial para validar o heurístico de "pseudo-calibração".

---

Significado Geral e Impacto

Este manuscrito não apresenta uma única prova, mas sim um mapa estratégico das fronteiras atuais em matemática aplicada e teórica.

1. Interdisciplinaridade: Os problemas conectam áreas distantes, como geometria de Banach, teoria dos números (resíduos quadráticos), física quântica (MUBs/SIC-POVMs) e ciência da computação teórica (limites inferiores de algoritmos SoS).
2. Ferramentas Unificadoras: Há um forte foco no uso de relaxações convexas (SDP, Sum-of-Squares) e concentração de medida (desigualdades de concentração, localização estocástica) como ferramentas centrais para atacar problemas de combinatória e otimização.
3. Progresso Recente: O documento destaca que o campo está em um momento de aceleração, citando resoluções recentes de conjecturas de décadas (KLS, Slicing, Thin Shell) e propondo novos desafios baseados nessas descobertas.
4. Aplicabilidade: A resolução desses problemas teria impactos diretos no desenvolvimento de algoritmos de aprendizado de máquina (PCA robusto, recuperação de fase), criptografia (segurança baseada em grafos pseudo-aleatórios) e fundamentos da mecânica quântica.

Em suma, o documento serve como um guia essencial para pesquisadores que desejam contribuir com os problemas mais desafiadores e promissores da matemática contemporânea nas áreas de probabilidade e combinatória.