Containments of Tensor Network Varieties

Sintesi Tecnica: Contenimenti di Varietà di Reti Tensoriali

Definizione del Problema
Il documento affronta la questione fondamentale del contenimento tra varietà di reti tensoriali. Dato due formati tensoriali codificati da alberi binari, gli autori indagano se l'insieme di tutti i tensori rappresentabili da una rete (la varietà) sia contenuto nell'insieme rappresentabile da un'altra. Questo problema generalizza la "Congettura di Hackbusch", precedentemente risolta per coppie specifiche di alberi (alberi gerarchici e alberi train track) da Buczyńska et al. [BBM15]. Gli autori mirano a stabilire un quadro generale per confrontare arbitrari alberi binari, trascurando gli embedding planari, e a quantificare il "costo" del contenimento. Nello specifico, cercano di determinare quanto debbano essere scalati i parametri dimensionali (il "boost") di una rete rispetto a un'altra affinché il contenimento sia garantito.

Metodologia
Gli autori impiegano un approccio combinatorio radicato nella struttura degli alberi binari radicati completi e nelle proprietà dei relativi stati di reti tensoriali (TNS).

1. Definizioni e Quadro Teorico:

   • Reti Tensoriali: Definite come una terna $(T, \mathcal{V}, f)$, dove $T$ è un albero binario completo, $\mathcal{V}$ è una famiglia di spazi vettoriali alle foglie, e $f$ è un vettore di dimensioni che assegna le dimensioni ai sottospazi in ogni vertice.
   • Varietà: La varietà $TNS(T)$ è il locus di tensori che soddisfano vincoli di rango in ogni vertice, definito tramite sottospazi lineari $U_v$ tali che $U_v \subseteq U_{v_1} \otimes U_{v_2}$.
   • Descrizione Esterna: Gli autori utilizzano le contrazioni tensoriali per caratterizzare la varietà tramite condizioni di rango sulle mappe di "appiattimento" (flattening). Un tensore appartiene a $TNS(T)$ se il rango della sua contrazione attraverso ogni split $(\downarrow v | \uparrow v)$ è limitato da $f(v)$.
   • Insiemi Doad: Uno strumento combinatorio cruciale introdotto è l'insieme "doad" (foglie discendenti o anti-discendenti), denotato con $DOAD(T)$. Questi sono sottoinsiemi di foglie $S$ tali che $S = \downarrow v$ o $S = \uparrow v$ per qualche vertice $v$.

2. Criteri di Contenimento:

   • Contenimento Triviale: Una rete $T$ è trivialmente contenuta in $T'$ se ogni insieme doad di $T'$ può essere coperto da insiemi doad di $T$ tali che il prodotto dei parametri dimensionali degli insiemi di copertura in $T$ sia minore o uguale al parametro in $T'$.
   • Contenimento Asintotico (Lemma 2.11): Gli autori stabiliscono che se ogni insieme doad (o il suo complemento) di $T'$ può essere coperto da al massimo $c_0$ insiemi doad di $T$, allora per un fattore di scala $r$ sufficientemente grande, $TNS(rT) \subseteq TNS(r^{c_0}T')$. Ciò porta alla definizione di esponente di contenimento.

3. L'Esponente di Contenimento:

   • Definito come il più piccolo numero $E$ tale che per tutti i vettori di dimensioni e per $r$ sufficientemente grande, $TNS(rT) \subseteq TNS(r^c T')$ vale per ogni $c > E$.
   • Limiti Combinatori: Gli autori derivano limiti basati sulla struttura di posetto degli alberi. Il Teorema 3.3 fornisce una formula per un esponente basato sul numero di elementi massimali in specifici sotto-posetti derivati dalle strutture degli alberi.
   • Alberi Planari: Per gli alberi planari (dove le foglie sono ordinate), gli autori sfruttano il fatto che gli insiemi doad corrispondono a intervalli. Introducono l'altezza e l'altezza duale dei vertici per derivare limiti specifici per il contenimento rispetto all'albero train track ($TT_n$) e tra arbitrari alberi planari (Teorema 4.4, Corollario 4.7).

4. Approccio Computazionale:

   • Gli autori hanno implementato un algoritmo per calcolare questi esponenti per un piccolo numero di foglie ($n \le 8$).
   • Hanno utilizzato il pacchetto SageMath BinaryTree per generare tutti gli alberi binari completi.
   • Per $n$ più grandi, dove la ricerca esaustiva delle coperture degli insiemi doad diventa impraticabile, hanno formulato un Programma Lineare Intero (ILP) per minimizzare il numero di insiemi doad necessari per coprire gli split dell'albero target.

Contributi Chiave e Risultati

• Generalizzazione della Congettura di Hackbusch: Il documento estende l'analisi di contenimento dalle coppie specifiche di alberi (gerarchico vs. train track) a qualsiasi coppia di alberi binari.
• Esistenza e Definizione degli Esponenti di Contenimento: Gli autori provano l'esistenza di un esponente di contenimento finito per ogni coppia di alberi e lo definiscono come una misura della scalatura del parametro necessaria per il contenimento.
• Limiti Combinatori:
  • Viene fornito un limite superiore generale di $\lfloor n/2 \rfloor$ (Proposizione 3.2).
  • Un limite più stretto basato sulla struttura di posetto degli alberi è presentato nel Teorema 3.3.
  • Limiti specifici per gli alberi planari sono derivati utilizzando le altezze dei vertici, mostrando che l'esponente per un albero $T$ nell'albero train track $TT_n$ è correlato al massimo di $\min\{h_\ell, h^*_{\ell+1}\}$ (Corollario 4.5).
• Implementazione Algoritmica: Gli autori forniscono un algoritmo e una formulazione ILP per calcolare questi esponenti. Riportano una ricerca esaustiva per alberi con fino a $n=8$ foglie, con risultati dettagliati raccolti in un dataset separato [GM25].
• Non-Strettezza dei Limiti: Il documento dimostra, attraverso esempi (ad esempio, Figura 6), che i limiti combinatori derivati non sono necessariamente stretti. In alcuni casi, il reale esponente di contenimento è significativamente inferiore al limite superiore teorico fornito dalle formule basate su posetto o altezza.

Significato e Rivendicazioni
Gli autori pongono questo lavoro come un "primo passo" verso una migliore comprensione dei contenimenti di reti tensoriali. Essi affermano di aver:

1. Proposto un quadro generale per la questione del contenimento che si applica ad arbitrari alberi binari di forma diversa.
2. Introdotto una nuova misura, l'esponente di contenimento, che quantifica la relazione tra diversi formati di reti tensoriali.
3. Fornito sia limiti teorici (tramite strutture di posetto e programmazione intera) che dati sperimentali per piccoli $n$.

Il documento si conclude con modestia, osservando che, sebbene i limiti siano utili, non sono sempre stretti. Gli autori identificano domande aperte riguardanti se i limiti superiori derivati dal Lemma 2.11 siano sempre stretti e se le soluzioni duali della rilassazione lineare possano essere utilizzate per costruire tensori che forniscano limiti inferiori per gli esponenti. Suggeriscono che l'esponente di contenimento offra una nuova misura di distanza non simmetrica per gli alberi, che merita ulteriori confronti con le metriche di albero esistenti nella letteratura.