Minimum transformation representations of diagram monoids

1. Il Problema

L'articolo affronta il problema fondamentale della teoria dei semigruppi e dei monoidi: determinare il grado di trasformazione minimo (denotato come $\deg(M)$) per una data famiglia di monoidi finiti.
Il grado di trasformazione minimo di un monoide $M$ è il più piccolo intero $n$ tale che $M$ possa essere immerso (embedding) nel monoide delle trasformazioni totali $T_n$ (l'insieme di tutte le funzioni da $\{1, \dots, n\}$ a se stesso).
Sebbene il teorema di Cayley garantisca che ogni monoide finito $M$ si immerge in $T_{|M|}$, il calcolo del grado minimo esatto è notoriamente difficile, anche per strutture algebriche relativamente semplici. Il paper si concentra specificamente sulle monoidi diagrammatici, una classe di strutture che includono il monoide delle partizioni ($P_n$), il monoide di Brauer ($B_n$), il monoide di Temperley-Lieb ($TL_n$) e altri, ampiamente studiati in algebra, combinatoria e fisica teorica (ad esempio, nella teoria dei nodi e nella meccanica statistica).

Prima di questo lavoro, per molti di questi monoidi (in particolare $P_n$), non esistevano limiti superiori significativi oltre alla banale $|M|$, e non erano note formule esatte per il grado minimo.

2. Metodologia

Gli autori combinano tecniche teoriche avanzate con esperimenti computazionali per derivare formule esatte. La metodologia si articola in tre fasi principali:

• Approccio Computazionale e Induttivo: Utilizzando il pacchetto Semigroups per GAP, gli autori hanno calcolato i gradi minimi per piccoli valori di $n$ (fino a $n=7$ per $P_n$). Questo ha permesso di identificare pattern numerici e formulare congetture basate su sequenze di numeri famosi (numeri di Bell, Catalan, Motzkin, ecc.).
• Teoria delle Congruenze e Azioni: Il cuore della metodologia teorica si basa sulla relazione tra rappresentazioni fedeli e congruenze destre. Un'azione fedele di un monoide su un insieme $X$ corrisponde a una congruenza destra $\sigma$ tale che il nucleo dell'azione sia banale. Gli autori costruiscono esplicitamente congruenze destre minime o quasi-minime per separare le classi di Green ($L, R, J$) e distinguere gli elementi del monoide.
• Azioni Parziali su Proiezioni: Una delle innovazioni chiave è l'uso delle proiezioni (idempotenti fissati dall'involuzione, $p^2=p=p^*$) in un contesto di regular ∗-semigroups. Gli autori costruiscono azioni (spesso parziali) dell'intero monoide sull'insieme delle sue proiezioni $P(M)$ o su sottoinsiemi specifici di queste (basati sul rango).
  • Per i monoidi $P_n, PB_n, PP_n, Mn$, dimostrano che un'azione su un insieme di proiezioni di basso rango (rango $\le 2$) è fedele.
  • Per il monoide di Brauer $B_n$, la situazione è più complessa (specialmente per $n$ pari), richiedendo la costruzione di azioni come "push-out" di azioni più piccole e l'uso di sottogruppi di permutazioni (come il gruppo simmetrico o prodotti di wreath) per gestire le classi di Green.
• Dimostrazione dei Limiti Inferiori: Per provare che i limiti superiori ottenuti sono ottimali, gli autori utilizzano argomenti combinatori che mostrano come qualsiasi azione fedele debba necessariamente contenere un numero di elementi almeno pari a quello delle proiezioni di basso rango selezionate, separando coppie critiche di elementi (generatori delle congruenze minime).

3. Contributi Chiave

Il contributo principale del paper è la risoluzione completa del problema del grado di trasformazione minimo per le famiglie più studiate di monoidi diagrammatici, fornendo formule chiuse esatte.

1. Formule Esatte per $P_n$ e varianti:
   Gli autori dimostrano che per il monoide delle partizioni $P_n$ (e per i suoi sottomonoidi planari e parziali), il grado minimo è dato da:
   $$\deg(P_n) = 1 + \frac{B(n+2) - B(n+1) + B(n)}{2}$$
   dove $B(n)$ è l'$n$-esimo numero di Bell. Il grado di trasformazione parziale minimo è $\deg'(P_n) = \deg(P_n) - 1$.
   Risultati analoghi sono ottenuti per il monoide di partizioni parziali ($PB_n$), il monoide di partizioni planari ($PP_n$) e il monoide di Motzkin ($M_n$), esprimendo i gradi in termini di numeri di involuzione, Catalan e Motzkin.

2. Risoluzione per il Monoide di Brauer ($B_n$):
   Il caso del monoide di Brauer è trattato separatamente a causa della sua struttura più complessa. Gli autori derivano formule distinte per $n$ dispari e $n$ pari:

   • Se $n$ è dispari: $\deg'(B_n) = \frac{n+1}{2} \cdot n!!$
   • Se $n$ è pari: $\deg'(B_n) = \frac{(n+4)(n+2)}{8} \cdot (n-1)!!$
     (Dove $m!!$ è il fattoriale doppio).
     È notato che per $n$ pari, il grado di trasformazione minimo è strettamente inferiore al grado della congruenza destra minima ($\deg(B_n) < \deg_{rc}(B_n)$), un fenomeno non presente negli altri monoidi trattati.

3. Costruzioni Esplicite:
   Non si limitano a fornire i numeri, ma costruiscono esplicitamente le rappresentazioni fedeli di grado minimo. Queste rappresentazioni sono spesso realizzate come azioni (parziali) su insiemi di proiezioni di basso rango, offrendo una comprensione strutturale profonda di come questi monoidi agiscono su spazi di dimensione ridotta.

4. Collegamento con Sequenze Combinatorie:
   Il lavoro stabilisce un ponte diretto tra la teoria dei semigruppi e le sequenze di numeri combinatori classici (OEIS), mostrando che i gradi minimi sono combinazioni lineari di numeri di Bell, Catalan e Motzkin.

4. Risultati Principali

I risultati sono sintetizzati nelle tabelle e nei teoremi del paper:

• Teorema 4.1: Stabilisce che per $P_n, PB_n, PP_n, Mn$, il grado minimo è $1 + |Q|$, dove $Q$ è l'insieme delle proiezioni con rango $\le 2$.
• Teorema 5.1: Estende il risultato al monoide di Temperley-Lieb $TL_n$, distinguendo tra casi pari e dispari.
• Teorema 6.1: Fornisce la formula completa per il monoide di Brauer $B_n$, dimostrando che il metodo delle proiezioni di basso rango deve essere modificato (inclusione di gruppi di permutazione e azioni non monogene per $n$ pari).
• Tabella 1 e 2: Forniscono le formule combinatorie esplicite e i valori calcolati per $n$ fino a 10, mappandoli alle sequenze note dell'OEIS (es. A087649 per $P_n$).

5. Significato e Impatto

Questo lavoro è significativo per diversi motivi:

• Chiusura di Problemi Aperti: Risolve problemi aperti da decenni (o almeno non affrontati in letteratura con tali dettagli) sui gradi di trasformazione di monoidi fondamentali. Ad esempio, prima di questo lavoro, non si conosceva il grado esatto di $P_3$ (che è 22), ma solo limiti molto larghi.
• Nuove Tecniche: Introduce e formalizza l'uso sistematico delle azioni su proiezioni per i regular ∗-semigroups, estendendo la teoria semilocale dei semigruppi finiti. Questo approccio potrebbe essere applicato ad altre classi di semigruppi.
• Implicazioni Computazionali: Le formule ottenute permettono di calcolare istantaneamente il grado minimo per qualsiasi $n$, evitando la necessità di costosi calcoli computazionali o di costruire rappresentazioni "alla cieca".
• Interdisciplinarità: Rafforza i legami tra l'algebra dei semigruppi, la combinatoria enumerativa e la teoria delle rappresentazioni, fornendo nuovi strumenti per lo studio delle algebre di diagrammi (come le algebre di Temperley-Lieb e di Brauer) che hanno applicazioni in fisica matematica e teoria dei nodi.

In sintesi, il paper fornisce una soluzione completa ed elegante a un problema classico di rappresentazione, trasformando una questione di calcolo computazionale in una serie di formule combinatorie eleganti e dimostrandone l'ottimalità attraverso costruzioni algebriche rigorose.