Randomstrasse101: Open Problems of 2025

Panoramica Generale

Il documento è una raccolta stabile di sedici problemi aperti (di cui otto presentati in dettaglio in questo estratto) pubblicati nel 2025 sul blog Randomstrasse101, gestito da ricercatori del Dipartimento di Matematica dell'ETH Zurigo. L'obiettivo è fornire un riferimento accademico stabile per questioni aperte in Teoria della Probabilità, Computazione, Combinatoria e Statistica. Il testo mantiene un tono informale ma rigoroso, focalizzandosi su congetture e problemi che gli autori ritengono particolarmente intriganti.

Di seguito sono riportati i dettagli tecnici per le sezioni specifiche incluse nel documento (Entry 8-14).

1. Disuguaglianze di Concentrazione per Tensori (Entry 8)

• Problema: Determinare limiti superiori per l'aspettativa della norma iniettiva $\ell_p$ di una somma di tensori simmetrici deterministici pesati da variabili gaussiane standard i.i.d. ($g_i$). La quantità di interesse è $E[\max_{||x||_p \le 1} |\sum g_i \langle T_i, x^{\otimes r} \rangle|]$.
• Contesto: Questo problema si colloca all'intersezione tra teoria dei codici, equazioni differenziali alle derivate parziali dispersive, analisi dei componenti principali tensoriali e geometria degli spazi di Banach.
• Metodologia e Sfide:
  • Per il caso $r=p=2$ (matrici), esistono risultati classici (Tomczak-Jaegermann, Ahlswede-Winter) basati su tecniche di traccia e disuguaglianze di Khintchine non commutative.
  • Per $r, p \ge 2$ generali, l'approssimazione tramite tracce fallisce e la stima delle norme iniettive è NP-difficile.
  • L'approccio proposto utilizza la teoria dei processi gaussiani, specificamente l'integrale di entropia di Dudley, che lega l'aspettativa al numero di copertura $N(B^d_p, D, \epsilon)$ rispetto a una distanza specifica $D$.
• Contributi e Risultati:
  • Viene proposta la Congettura 16: per $p \ge 2$, l'aspettativa è limitata da $\tilde{O}_{r,p}(d^{1/2 - 1/p} \sqrt{\sum ||T_i||_{I_p}^2})$.
  • Il caso $p \ge 2r$ è stato risolto in lavori precedenti ([BGJ+24]), ma per $p < 2r$ sussiste una barriera volumetrica.
  • Vengono discussi lavori recenti che rimuovono fattori logaritmici in casi specifici (es. tensori con entrate indipendenti) utilizzando il Lemma PAC-Bayesiano o tecniche di spazi di Hardy, ma il caso generale rimane aperto.

2. Il Numero di Lovász per Grafi Circulanti Casuali (Entry 9)

• Problema: Caratterizzare l'asintotico del numero di Lovász $\vartheta(G)$ per grafi casuali, in particolare per i grafi circulanti densi.
• Contesto: Il numero di Lovász è un rilassamento SDP (Programmazione Semidefinita) del numero cromatico e fornisce un limite superiore alla capacità di Shannon. Per i grafi di Erdős-Rényi $G(n, 1/2)$, si congettura che $E[\vartheta(G)] \sim \sqrt{n}$.
• Metodologia:
  • I grafi circulanti sono grafi Cayley sul gruppo ciclico $\mathbb{Z}_n$. La loro struttura permette di diagonalizzare le matrici di adiacenza tramite la Trasformata di Fourier Discreta (DFT).
  • Il problema SDP per $\vartheta(G)$ può essere riformulato come un Programma Lineare (LP) sia nel dominio del tempo che della frequenza.
• Contributi e Risultati:
  • Congettura 18: Per un grafo circulante denso casuale, $E[\vartheta(G)] = (1+o(1))\sqrt{n}$.
  • Risultati parziali in [BBD+25] forniscono un limite inferiore preciso e un limite superiore $O(\sqrt{n} \log \log n)$.
  • La tecnica si basa sulla proprietà di isometria ristretta (RIP) della matrice DFT campionata e sullo studio di una versione modificata del LP.

3. Iniettività e Stabilità nel Phase Retrieval (Entry 10)

• Problema: Determinare le condizioni necessarie e sufficienti per l'iniettività e la stabilità della ricostruzione di un vettore $x$ dai moduli delle sue misure lineari $|Ax|$.
• Contesto: Il problema è fondamentale in fisica e ingegneria. Per $K=\mathbb{C}$, si sa che $N \ge 4M-4$ è necessario, ma la congettura originale è stata smentita (esistono set di 11 misure per $M=4$).
• Metodologia:
  • Analisi della proprietà di complemento: un insieme di misure è iniettivo se ogni partizione delle righe di $A$ in due insiemi lascia almeno uno che genera $\mathbb{R}^M$.
  • Introduzione della quantità $\omega(A)$, legata al minimo valore singolare di sotto-matrici che generano lo spazio, come misura di stabilità.
• Contributi e Risultati:
  • Congettura 19: Per $N=4M-5$ e $A$ casuale, la probabilità di iniettività è strettamente minore di 1 e tende a 0 per $M \to \infty$.
  • Congettura 20 (Balan-Wang): Esiste una relazione di stabilità $\omega(A) \le C \max ||A_k||^\beta M$.
  • Problema Aperto 21: Determinare il valore esatto di $\omega(A)$ per matrici gaussiane e verificare la congettura di Balan-Wang.

4. Basi Mutamente Incondizionate (MUB), ETF e Congettura di Zauner (Entry 11)

• Problema: Esistenza e numero massimo di basi mutuamente incondizionate (MUB) in spazi complessi $\mathbb{C}^d$ e la costruzione di Frame Equiangolari Stretti (ETF).
• Contesto: Le MUB sono cruciali in fisica quantistica. Per $d$ potenza di un primo, il numero massimo è $d+1$. Per $d=6$, il problema è aperto.
• Contributi e Risultati:
  • Congettura 22: $MUB(6) < 7$.
  • Problema Aperto 23: Esiste una prova di grado 4 tramite "Sum-of-Squares" (SoS) che non esistono 7 MUB in $\mathbb{C}^6$?
  • Congettura 24 (Zauner): Per ogni dimensione $d$, esiste un ETF con $n=d^2$ vettori (SIC-POVM).
  • Vengono discussi recenti progressi condizionali basati su congetture di teoria dei numeri (Congetture di Stark) che implicano la congettura di Zauner, ma una prova incondizionata manca.

5. Numero di Clique del Grafo di Paley (Entry 12)

• Problema: Stimare il numero di clique $\omega(G_p)$ per i grafi di Paley (definiti su campi finiti, dove gli archi corrispondono a residui quadratici).
• Contesto: I grafi di Paley sono deterministici ma si comportano come grafi casuali. Si congettura che $\omega(G_p)$ sia polilogaritmico, mentre i limiti attuali sono dell'ordine di $\sqrt{p}$.
• Metodologia:
  • Uso di rilassamenti convessi come il numero di Lovász $\vartheta$ e le rilassazioni Sum-of-Squares (SoS) di grado superiore.
  • Analisi delle "localizzazioni" del grafo (sotto-grafi indotti dai vicini di un nodo).
• Contributi e Risultati:
  • Congettura 25: $\omega(G_p) = O(\text{polylog}(p))$.
  • Congetture 26-27: Stime migliori ottenute tramite localizzazione e rilassamenti SDP su sotto-grafi locali ($\vartheta(G_{p,2}) \le \frac{2}{3}\sqrt{p}$).
  • Congettura 28: Il rilassamento SoS di grado 4 può migliorare il limite superiore a $O(p^{1/2 - \epsilon})$.
  • Congettura 29: La costruzione ETF di Paley soddisfa la Proprietà di Isometria Ristretta (RIP) oltre il "collo di bottiglia della radice quadrata".

6. La Congettura KLS e Implicazioni (Entry 13)

• Problema: La Congettura di Kannan-Lovász-Simonovits (KLS) riguarda il limite inferiore della costante isoperimetrica per misure log-convesse in spazi ad alta dimensione.
• Contesto: Per misure gaussiane, la costante è indipendente dalla dimensione. KLS congettura che ciò valga (a meno di una costante universale) per tutte le distribuzioni log-convesse.
• Metodologia e Progressi:
  • Storicamente, il limite era $O(n^{-1/2})$.
  • Eldan (2013) ha introdotto la "localizzazione stocastica", migliorando il limite a $O(n^{-1/3})$.
  • Chen (2021) ha rotto la barriera polinomiale con un limite quasi costante.
  • Klartag (2023) ha ottenuto il miglior limite attuale: $\psi_n \ge C (\log n)^{-1/2}$.
• Risultati Recenti (2025):
  • La congettura del "Thin Shell" (guscio sottile) è stata dimostrata da Klartag e Lehec ([KL25b]), implicando il limite attuale per KLS.
  • Il problema del "Slicing" di Bourgain è stato risolto da Klartag e Lehec ([KL25a]), mostrando profonde connessioni tra questi problemi di geometria convessa.

7. Limiti Precisi per le Matrici di Grafo (Entry 14)

• Problema: Stabilire limiti superiori e inferiori precisi (inclusi i fattori logaritmici) per la norma spettrale delle "matrici di grafo" ($M_\alpha$), che appaiono nell'analisi della gerarchia Sum-of-Squares (SoS).
• Contesto: Le matrici di grafo sono matrici casuali i cui elementi sono polinomi di variabili di Rademacher. Sono fondamentali per dimostrare limiti inferiori per algoritmi SoS (es. problema della clique piantata).
• Metodologia:
  • Le matrici di grafo sono un caso particolare di "Matrix Chaos" (caos di matrici).
  • L'approccio standard usa il metodo dei momenti, ma spesso lascia fattori logaritmici non ottimali.
  • Si propone l'uso di disuguaglianze di concentrazione per matrici (NCK) iterate.
• Contributi e Risultati:
  • Congettura 31: La norma attesa di una matrice di grafo associata a una forma $\alpha$ è $\Theta(n^{f(\alpha)} (\log n)^{g(\alpha)})$, dove $f$ e $g$ dipendono solo dalla forma.
  • L'obiettivo è rimuovere i fattori logaritmici superflui per ottenere limiti inferiori più stretti per la gerarchia SoS e comprendere meglio l'euristica di "pseudo-calibrazione".

Significato e Impatto Complessivo

Questo manoscritto funge da mappa aggiornata per la ricerca di frontiera in diverse aree della matematica applicata e teorica.

1. Interdisciplinarità: Collega problemi apparentemente distanti (es. geometria dei tensori, teoria dei grafi, fisica quantistica, ottimizzazione convessa) attraverso strumenti comuni come le disuguaglianze di concentrazione, i rilassamenti SDP e la teoria dei processi stocastici.
2. Progressi Recenti: Documenta breakthrough significativi avvenuti nel 2024-2025 (risoluzione del problema del Thin Shell e dello Slicing), che hanno impatti diretti su congetture aperte come KLS.
3. Guida per la Ricerca: Le congetture presentate (es. su MUB(6), limiti per matrici di grafo, e il comportamento dei grafi di Paley) offrono obiettivi chiari per la comunità matematica, suggerendo direzioni specifiche (come l'uso di prove SoS di grado superiore o tecniche di localizzazione stocastica) per risolvere problemi decennali.
4. Riferimento Stabile: Fornisce una versione "stabile" e citabile dei problemi del blog, facilitando la comunicazione accademica e la verifica dei risultati futuri.