New lower bounds for constant-weight codes via seeded bit-swap tabu search

Immagina di dover preparare una valigia per un viaggio, ma con una regola molto strana: ogni oggetto che infili deve avere esattamente la stessa dimensione, e nessun due oggetti possono essere troppo simili tra loro. Se sono troppo simili, potrebbero confondersi nel buio, causando il caos. Nel mondo della comunicazione digitale, questa "valigia" è un messaggio, gli "oggetti" sono schemi di zeri e uno (bit), e la "dimensione" è quanti "uno" ci sono nello schema. Questo è l'enigma dei codici a peso costante. Gli scienziati usano questi codici per inviare dati in modo affidabile su canali rumorosi, come il Wi-Fi o la radio nello spazio profondo, assicurando che anche se alcuni bit vengono rimescolati, il ricevente riesca ancora a capire cosa è stato inviato. L'obiettivo è semplice ma incredibilmente difficile: far entrare il maggior numero possibile di oggetti unici e distinti nella valigia senza che si urtino tra loro. Più grande è la valigia (più codici puoi farci stare), più informazioni puoi inviare in una volta sola.

Entra in scena William Echols, che ha deciso di affrontare questo problema di imballaggio con un tocco intelligente. Invece di partire da una valigia vuota e lanciare dentro oggetti a caso, sperando che ci stiano, ha usato un approccio "seminato" (seeded). Pensalo in questo modo: se vuoi costruire un castello Lego migliore, non parti semplicemente da zero e ne costruisci uno nuovo; prendi un castello già esistente e di alta qualità, estrai alcuni mattoncini e scambiali per vedere se puoi renderlo ancora più grande o robusto. Echols ha usato un metodo informatico chiamato ricerca tabu (tabu search), che è come un esploratore molto testardo che si rifiuta di rifare i suoi passi (per evitare di finire in loop) e continua a provare nuovi percorsi. "Seminando" questo esploratore con design di codici esistenti e di alta qualità, lo ha guidato a trovare 124 nuovi, più grandi, arrangiamenti di imballaggio che non erano mai stati scoperti prima. Questi nuovi arrangiamenti migliorano i limiti inferiori di quanti messaggi possiamo inviare e aiutano persino a capire quanti cerchi possono toccare un cerchio centrale in uno spazio ad alta dimensionalità — un concetto noto come "numeri di bacio" (kissing numbers).

L'enigma dell'imballaggio e il seme magico

Nel mondo digitale, i dati sono solo una lunga sequenza di zeri e uno. A volte, per renderli robusti, permettiamo solo sequenze che hanno un numero specifico di "uno". Per esempio, se diciamo che il "peso" è 5, ogni sequenza deve avere esattamente cinque "uno" e il resto zeri. Ora, immagina di avere una collezione di queste sequenze. Per prevenire errori, ogni sequenza nella tua collezione deve essere sufficientemente diversa da tutte le altre. Se due sequenze sono troppo simili, un piccolo disturbo potrebbe trasformare una nell'altra, e il ricevente si confonderebbe. La "distanza" tra loro si misura in base a quanti punti sono diversi.

La grande domanda in questo campo è: Qual è il numero massimo di sequenze che puoi inserire nella tua collezione? Questo numero massimo è chiamato $A(n, d, w)$, dove $n$ è la lunghezza della sequenza, $d$ è la distanza minima richiesta e $w$ è il numero di "uno". Per decenni, matematici e scienziati dell'informatica hanno cercato di trovare le collezioni più grandi per varie impostazioni. Hanno trovato ottime collezioni, ma spesso non sanno se hanno trovato quella assolutamente più grande. Sanno solo che non possono fare meglio di un certo numero.

La strategia "seminata"

I tentativi precedenti di trovare questi numeri massimi usando ricerche informatiche sembravano spesso vagare in una foresta buia. I computer partivano da ipotesi casuali e, sebbene a volte trovassero buoni percorsi, spesso rimanevano bloccati in radure locali che sembravano la cima di una montagna ma non lo erano. Si fermavano lì, pensando di aver trovato il miglior codice possibile, quando un codice molto più grande era proprio oltre la collina successiva.

Echols si rese conto che la chiave era smettere di partire da zero. Usò una tecnica di inizializzazione seminata (seeded initialization). Invece di generare un punto di partenza casuale, prese un codice esistente di alta qualità (un "seme") e lo usò per lanciare la ricerca.

Lo fece in due modi giocosi:

1. Semina Diretta: Prese un codice esistente e aggiunse una parola extra alla sua collezione, scelta con cura per causare il minor numero di "problemi" (deficit di distanza). Questo creò un punto di partenza leggermente più grande e leggermente disordinato.
2. Semina di Vicinato: Guardò i codici per problemi leggermente diversi. Ad esempio, se voleva un codice di lunghezza 30, poteva prendere un ottimo codice di lunghezza 29, aggiungere uno zero a ogni parola per renderle di lunghezza 30, e poi usarlo come punto di partenza. Oppure, poteva prendere un codice di lunghezza 31, tagliare via uno zero e usarlo.

Una volta ottenuti questi punti di partenza "seminati", avviò la sua ricerca tabu di scambio di bit (bit-swap tabu search). Immagina questa ricerca come un gioco di sedie musicali dove le sedie sono le posizioni degli "uno" nelle sequenze. L'algoritmo scambia i bit, cercando di rendere le sequenze più distinte. La parte "tabu" significa che l'algoritmo tiene memoria delle mosse appena fatte e si rifiuta di annullarle immediatamente, costringendolo a esplorare nuovi territori invece di girare in tondo.

I Risultati: 124 Nuove Scoperte

Usando questa intelligente strategia di semina, Echols ha trovato 124 nuove costruzioni che hanno superato i precedenti record noti. Non si tratta di piccoli miglioramenti; alcuni sono salti enormi.

Per esempio:

• Per un codice di lunghezza 39 con vincoli specifici, il precedente record era di 1.014 parole. Il nuovo metodo ne ha trovate 1.118. Un guadagno di 104!
• Per la lunghezza 40, il record è passato da 1.170 a 1.230.
• Per la lunghezza 56, il numero è passato da 2.414 a 2.477.

Questi numeri rappresentano il numero massimo di messaggi unici che possiamo ora garantire di inviare senza confusione per quelle specifiche impostazioni. L'articolo non sostiene che questi siano i limiti massimi assoluti (il vero limite matematico), ma dimostra che possiamo certamente fare meglio di quanto pensassimo. Spinge il "limite inferiore" più in alto, il che significa che sappiamo con certezza di poter far entrare almeno questo numero di oggetti nella valigia.

Numeri di Bacio: Un Effetto Collaterale Sorprendente

Ecco dove la storia diventa ancora più interessante. L'articolo tocca anche un concetto chiamato numeri di bacio (kissing numbers). Immagina di avere una grande palla al centro di una stanza. Quante altre palle della stessa dimensione puoi posizionare intorno ad essa in modo che tocchino la palla centrale senza sovrapporsi tra loro? Nello spazio 3D, la risposta è 12. Ma in dimensioni superiori (come 32 o 33 dimensioni), la risposta è molto più difficile da trovare.

La matematica di questi numeri di bacio è profondamente collegata ai codi a peso costante che Echols ha trovato. Poiché ha migliorato i codici per parametri specifici (nello specifico $A(n, 8, 8)$), ha automaticamente migliorato i limiti inferiori per i numeri di bacio nelle dimensioni 32, 33, 34 e 37.

Per esempio, per la dimensione 32 ($\tau_{32}$), la stima precedente era che almeno 345.408 palle potessero toccare la palla centrale. Con i nuovi codici, quel numero sale a 346.432. È un piccolo aumento percentuale, ma nel mondo della geometria ad alta dimensione, trovare anche solo una pallina in più che entra è una vittoria significativa.

Conclusione

William Echols non ha solo trovato alcuni codici migliori; ha dimostrato che, essendo intelligenti su come si inizia la ricerca — ovvero usando i "semi" dalle conoscenze esistenti invece di partire alla cieca — si possono trovare soluzioni molto migliori. L'articolo dimostra che 124 miglioramenti specifici sono possibili e fornisce un nuovo, più alto pavimento per quanto dato possiamo impacchettare in modo affidabile in queste stringhe digitali. È un promemoria del fatto che, a volte, il modo migliore per andare avanti è stare sulle spalle di ciò che già conosciamo, piuttosto che cercare di costruire tutto da zero.