Asymptotic tensor rank is characterized by polynomials

Sintesi Tecnica: Il Rango Tensoriale Asintotico è Caratterizzato da Polinomi

Contesto del Problema
Il rango tensoriale asintotico, indicato con $\tilde{R}(T)$, è un parametro fondamentale nella teoria della complessità algebrica, definito come il limite $\lim_{n \to \infty} R(T^{\boxtimes n})^{1/n}$, dove $R$ è il rango tensoriale standard e $\boxtimes$ è il prodotto di Kronecker. Questo parametro è centrale per determinare l'esponente della moltiplicazione di matrici $\omega$, poiché $2\omega = \tilde{R}(\langle 2, 2, 2 \rangle)$. Nonostante la sua importanza, le proprietà computazionali e strutturali del rango asintotico sono scarsamente comprese. Un importante problema aperto è se $\tilde{R}(T)$ sia computabile. Inoltre, la congettura di Strassen sul rango asintotico postula che $\tilde{R}(T)$ sia uguale al più grande rango di appiattimento (flattening rank) di $T$, implicando che sia sempre un intero ed sia facile da calcolare. Sebbene lavori recenti abbiano stabilito proprietà di discretezza per i parametri asintotici su campi finiti, il comportamento su campi infiniti (come i numeri complessi) rimaneva in gran parte sconosciuto.

Metodologia
Gli autori approcciano il problema analizzando la struttura geometrica dei sotto-livelli dei ranghi asintotici e dei funzionali correlati. Introducono il concetto di "funzionali ammissibili", una classe di funzioni sulle potenze tensoriali che soddisfano proprietà specifiche (subadditività, submoltiplicatività, invarianza per permutazione, ecc.), che include il rango asintotico e tutti i punti dello spettro asintotico di Strassen.

L'innovazione metodologica principale consiste nel dimostrare che, per ogni funzionale ammissibile $\mathcal{F}$ e per ogni numero reale $r$, il sotto-livello $\{T : \tilde{\mathcal{F}}(T) \leq r\}$ è Zariski-chiuso. Ciò viene ottenuto attraverso un argomento di decomposizione che mostra come il supremo del funzionale sulla chiusura di Zariski di un insieme $A$ sia uguale al supremo su $A$ stesso. Questo si basa sull'espressione degli elementi nella chiusura come combinazioni lineari di potenze tensoriali di elementi in $A$ e sull'utilizzo di un'analisi di doppio blocco asintotico.

Per estendere questi risultati dai formati tensoriali fissi all'insieme di tutti i tensori (dimensioni arbitrarie), gli autori sviluppano nuovi limiti inferiori sulle trasformazioni da tensore a matrice (specificamente, quantità $Q_{i,j}(T)$ che rappresentano il massimo rango di matrice ottenibile su specifiche gambe tramite restrizione). Essi dimostrano una disuguaglianza che mette in relazione il prodotto di questi ranghi di trasformazione con il rango di appiattimento $R_I(T)$, generalizzando i risultati precedenti per $k=3$.

Contributi Chiave e Risultati

1. Caratterizzazione Polinomiale e Computabilità dall'Alto:
   Il documento dimostra che il rango tensoriale asintotico è "computabile dall'alto". Per ogni campo computabile $F$ e per ogni limite reale $r$, esiste un algoritmo che, dato un tensore $T$, decide se $\tilde{R}(T) \leq r$. Questo algoritmo si basa sul fatto che il sotto-livello è Zariski-chiuso, il che significa che è definito dalla scomparsa di una lista finita di polinomi. Sebbene il documento non costruisca esplicitamente questi polinomi, la loro esistenza è garantita.

2. Sotto-livelli Zariski-chiusi:
   Il Teorema 1.2 stabilisce che per ogni campo $F$, ordine $k$ e limite $r$, l'insieme $\{T : \tilde{R}(T) \leq r\}$ è Zariski-chiuso. Di conseguenza, il rango asintotico è semicontinuo inferiore nella topologia euclidea su $\mathbb{C}$. Ciò implica che se una sequenza di tensori converge a un tensore limite, e tutti i tensori nella sequenza hanno un rango asintotico al massimo $r$, allora anche il tensore limite ha un rango asintotico al massimo $r$.

3. Discretezza dall'Alto (Ben Ordinamento):
   Il Teorema 1.3 dimostra che l'insieme dei valori $\mathcal{R} = \{\tilde{R}(T) : T \in F^{d_1} \otimes \dots \otimes F^{d_k}, d_i \in \mathbb{Z}_{\geq 1}\}$ è ben ordinato. Ciò significa che qualsiasi sequenza non crescente di ranghi asintotici deve eventualmente stabilizzarsi.

   • Implicazione per la Moltiplicazione di Matrici: Esiste una costante $\epsilon > 0$ tale che nessun tensore abbia un rango asintotico strettamente compreso tra $2\omega$ e $2\omega + \epsilon$. Qualsiasi sequenza di limiti superiori su $\omega$ che si avvicina ad esso dall'alto deve eventualmente "scattare" al valore reale.
   • Questo risultato si generalizza a tutte le funzioni dello spettro asintotico di Strassen (Teorema 1.5).

4. Chiusezza Euclidea su $\mathbb{C}$:
   I Teoremi 1.4 e 4.1 mostrano che, quando il campo base è $\mathbb{C}$, l'insieme dei valori assunti dal rango asintotico è chiuso nella topologia euclidea. Ciò significa che il limite di qualsiasi sequenza convergente di ranghi asintotici è esso stesso il rango asintotico di qualche tensore.

5. Generalizzazione allo Spettro Asintotico:
   Gli autori estendono questi risultati strutturali all'intero spettro asintotico dei tensori $\Delta(F, k)$. Dimostrano che per ogni $F \in \Delta(F, k)$, l'insieme dei valori assunti è ben ordinato. Ciò viene ottenuto tramite la dualità di Strassen e un "argomento di crescita" che coinvolge i nuovi limiti inferiori tensore-matrice derivati (Teorema 3.2).

Significato e Rivendicazioni
Il documento sostiene che questi risultati forniscono una comprensione strutturale fondamentale del rango tensoriale asintotico che era precedentemente mancante, in particolare su campi infiniti.

• Implicazioni Computazionali: La proprietà di essere "computabile dall'alto" suggerisce che, sebbene calcolare il rango esatto possa essere difficile, verificare un limite superiore è algoritmicamente fattibile tramite la valutazione polinomiale.
• Implicazioni Strutturali: Il ben ordinamento (discretezza dall'alto) esclude la possibilità che i ranghi asintotici si accumulino arbitrariamente vicino a un valore dall'alto senza raggiungerlo. Questo fornisce evidenza a supporto della congettura di Strassen, che implicherebbe che l'insieme dei valori sia semplicemente i numeri naturali $\mathbb{N}$.
• Problemi Aperti: Gli autori dichiarano esplicitamente di non aver dimostrato la discretezza dal basso (ovvero se le sequenze crescenti di ranghi debbano stabilizzarsi). Notano che la congettura di Strassen implicherebbe questo, ma rimane una questione aperta. Lasciano inoltre aperto il problema dell'irreducibilità dei sotto-livelli per $k \geq 3$.

Il lavoro unisce la geometria algebrica (topologia di Zariski) e la teoria della complessità, offrendo nuovi strumenti per analizzare l'esponente della moltiplicazione di matrici e la struttura dei parametri tensoriali senza risolvere direttamente la congettura del rango asintotico.