La congettura di Nivat

Che cosa possiamo sapere di un’immagine se possiamo vederne soltanto una piccolissima porzione alla volta? Un’immagine digitale è generalmente rappresentata da una griglia di pixel, ciascuno dotato di un colore. Per essere certi che l’immagine sia abbastanza grande, qui la immagineremo infinita. Sembra allora sorprendente poter dedurre alcunché su questa immagine infinita vedendone soltanto una parte finita alla volta. Eppure, la congettura di Nivat afferma che è possibile prevedere che l’immagine si ripeta se non contiene un numero troppo grande di «piccoli frammenti» diversi.

Una breve digressione lineare ----------------------------

Prima di interessarci al caso di un’immagine infinita (di dimensione 2), può essere utile considerare quello di una riga infinita (di dimensione 1). Sia dunque A un insieme finito (o alfabeto) di colori (o lettere), usato per colorare tutte le caselle di una riga infinita. Una riga di questo tipo è detta periodica e di periodo m se, traslandola di m caselle, si ritrova la stessa riga: si ripete indefinitamente.

Immaginiamo di poter osservare questa riga soltanto attraverso una finestra di larghezza fissata n. Il numero di motivi di dimensione n che compaiono nella riga è chiamato complessità della riga; lo si indica con P(n).

Se una riga è periodica di periodo n, allora P(n) ≤ n. Nel 1938 i matematici statunitensi Harold Calvin Marston Morse (1892-1977) e Gustav Arnold Hedlund (1904-1993) dimostrarono che si tratta in realtà di una caratterizzazione della periodicità: una riga è periodica se e solo se esiste un numero intero n tale che P(n) ≤ n. La dimostrazione del teorema di Morse-Hedlund è piuttosto elementare e permette di rivisitare un classico: il ragionamento per induzione (vedi riquadro).

In due dimensioni ----------------------

Torniamo alla nostra immagine iniziale. Al posto di una riga abbiamo ora una griglia infinita, ancora colorata mediante un certo alfabeto finito A; una colorazione di questo tipo si chiama configurazione. Si parla ora di periodicità rispetto a un vettore $\vec{u}\backslash vec\{u\}$ (e non più rispetto a un semplice numero) quando la configurazione coincide con la propria traslata lungo il vettore $\vec{u}\backslash vec\{u\}$.

Una configurazione periodica rispetto ai vettori (1, 3) e (4, 0).

Un motivo è ora una porzione rettangolare di una configurazione di dimensione m × n, e la complessità di una configurazione è il numero di tali rettangoli diversi che vi si possono osservare attraverso questa «finestra» di dimensione m × n. La complessità si indica con P (m, n). Come nel caso della riga, vorremmo ottenere una caratterizzazione della periodicità di una configurazione in funzione della sua complessità. L’analogo della condizione P (n) ≤ n sarebbe P (m, n) ≤ mn, poiché mn rappresenta l’area del rettangolo osservato.

Purtroppo è impossibile ottenere una caratterizzazione simile a quella di Morse e Hedlund: esiste per esempio una configurazione periodica con complessità P (m, n) = 2 *^m *⁺ *ⁿ *^{+ 1}.

L’altra implicazione della caratterizzazione è oggetto di una congettura, formulata nel 1997 da Maurice Nivat (1937-2017) e che oggi porta il suo nome: ogni configurazione per cui esistono due numeri interi m e n tali che P(m, n) ≤ mn, detta a bassa complessità, deve essere periodica. Questo limite è inoltre ottimale, poiché esistono configurazioni non periodiche di complessità mn + 1.

Ogni finestra di area mn lascia apparire mn motivi diversi con una cella nera in ciascuna delle posizioni del rettangolo, più un motivo interamente bianco, da cui una complessità mn + 1. La configurazione non è periodica: ogni traslazione sposta la cella nera in una posizione diversa.

E in dimensione 3? -----------------------

Un enunciato simile al teorema di Morse-Hedlund è vero in dimensione 1 e congetturato in dimensione 2. E in dimensione 3? È falso!

In 3D, una configurazione è a bassa complessità rispetto a un parallelepipedo di dimensione mnk se la sua complessità P (m, n, k) è minore o uguale a mnk. È allora possibile costruire una configurazione 3D a bassa complessità che non sia periodica: fissiamo un numero intero n e consideriamo la configurazione interamente bianca, eccetto due rette perpendicolari distanti n celle.

Per cominciare, non è periodica, poiché ogni traslazione sposterà almeno una delle due rette. Inoltre, la sua complessità rispetto a un cubo di lato n è P (n, n, n) = 2*n ² + 1, poiché il cubo interseca al massimo una retta. Per n ≥ 3, si ha P(n, n, n) < *n ³, dunque una configurazione a bassa complessità.

L’algebra dei polinomi in soccorso ------------------------------------------

La dimostrazione completa della congettura di Nivat resiste ancora agli assalti dei matematici. Come spesso accade, importanti progressi sono stati compiuti quando questo problema è stato collegato a un altro ambito a priori estraneo: l’algebra polinomiale. Questo legame, tanto sorprendente quanto fecondo, fu messo in evidenza da Jarkko Kari e Michal Szabados nel 2015.

Per capirlo, cominciamo a vedere come un motivo finito possa essere rappresentato da un polinomio. Il primo passo consiste nel considerare un alfabeto A formato da numeri (inclusi, per esempio, nell’insieme degli interi). Un motivo p è una colorazione (un’«etichettatura») di un rettangolo m × n mediante elementi di A; il colore (in realtà il numero) presente nella posizione (i, j) si indica con *p_i*_, *_j*. Il polinomio che rappresenta questo motivo è allora il seguente:

Possiamo ora studiare i motivi da un punto di vista puramente algebrico, analizzando questi polinomi!

Le posizioni dei diversi monomi in un motivo 3 × 2.

Il motivo rappresentato da 3xy + xy ² + 2x ² y + 3x ² y ² + x ³ y + 2x ² y ².

Generalizzando questa idea, si possono rappresentare le configurazioni come «polinomi infiniti» (chiamati serie formali), i cui coefficienti sono i numeri presenti nelle celle della configurazione. Kari e Szabados hanno mostrato che i polinomi il cui prodotto con una serie dà 0 sono particolarmente importanti; sono chiamati polinomi annullatori (vedi riquadro).

Comprendendo meglio quale forma possano assumere i polinomi annullatori, Kari e Szabados riescono a dimostrare diversi nuovi risultati.

Anzitutto, ogni configurazione c di bassa complessità può essere scritta come somma di configurazioni periodiche c₁, c₂… *c_r , che possono tuttavia avere un alfabeto infinito: c = c*₁ + c₂ +… + *c_r *.

Riescono inoltre a dimostrare una versione asintotica della congettura di Nivat: se P(m, n) ≤ mn per un’infinità di numeri interi m e n, allora la configurazione è periodica.

Infine, combinando il loro approccio algebrico con strumenti sviluppati da Van Cyr e Bryna Kra, riescono a dimostrare che, se una configurazione è somma di sole due configurazioni periodiche, allora soddisfa la congettura di Nivat.

Nella tesi Autour du problème du domino – Structures combinatoires et outils algébriques, questi strumenti algebrici sono ulteriormente sviluppati per ottenere nuovi risultati che si avvicinano alla congettura di Nivat. Una parte del lavoro si è concentrata sulle configurazioni uniformemente ricorrenti, ossia quelle che non contengono motivi isolati.

Eliminare le direzioni problematiche --------------------------------------

Le tecniche sviluppate da Cyr e Kra si basano sulla nozione di determinismo di un insieme X di configurazioni. X si dice deterministico nella direzione $\overrightarrow{u}\in {\mathbb{Z}}^2\backslash overrightarrow\{u\}\; \backslash in\; \backslash mathbb\{Z\}^2$ se, quando due configurazioni di X coincidono su un semipiano in tale direzione, coincidono ovunque.

In altre parole, il valore assunto dalle configurazioni su un semipiano nella direzione $\vec{u}\backslash vec\{u\}$ determina interamente ciascuna configurazione.

Un semipiano di direzione $\vec{u}\backslash vec\{u\}$ = (–1,2). Se esiste al più una configurazione di X con un valore dato su questo semipiano, allora X è deterministico nella direzione $\vec{u}\backslash vec\{u\}$.

Maurice Paul Nivat (1937–2017).

Ogni direzione è dunque deterministica oppure non deterministica. L’ultimo caso rimasto aperto dopo i lavori di Cyr e Kra è quello delle direzioni $\vec{u}\backslash vec\{u\}$ per le quali X è deterministico nella direzione $\vec{u}\backslash vec\{u\}$ ma non deterministico nella direzione $-\vec{u}-\backslash vec\{u\}$. Uno dei risultati più importanti della tesi mostra che, nel caso delle configurazioni uniformemente ricorrenti, queste direzioni problematiche possono in realtà essere «eliminate». Ciò permette di dimostrare che la congettura di Nivat è vera per le configurazioni uniformemente ricorrenti.

Uniformemente che cosa? -----------------------

A partire da una configurazione c, si può costruire la sua orbita O (c), che contiene le traslazioni di c per ogni vettore $\vec{u}\backslash vec\{u\}$ di ${\mathbb{Z}}^2\backslash mathbb\{Z\}^2$. Prendendo poi la chiusura $\overline{O(c)}\backslash overline\{O(c)\}$ dell’orbita, si ottiene un insieme che contiene tutte le traslazioni di c, nonché le configurazioni limite di tali traslazioni. Una configurazione è uniformemente ricorrente se, per ogni configurazione c’ in $\overline{O(c)}\backslash overline\{O(c)\}$, si ha $\overline{O(c^{\mathrm{\prime }})}=\overline{O(c)}\mathrm{.}\backslash overline\{O(c\text{'})\}\; =\; \backslash overline\{O(c)\}\; .$ In altre parole, non si possono «cancellare» motivi di c traslandola, neppure all’infinito.

Il risultato preciso ottenuto nella tesi con Jarkko Kari mostra che, per ogni configurazione di bassa complessità, $\overline{O(c)}\backslash overline\{O(c)\}$ contiene una configurazione periodica d. Si noti che, se la congettura di Nivat è vera, allora ogni configurazione di $\overline{O(c)}\backslash overline\{O(c)\}$ è periodica.

Poiché d è periodica, $\overline{O(d)}\backslash overline\{O(d)\}$ contiene soltanto configurazioni periodiche. Ora, poiché c è uniformemente ricorrente, $\overline{O(d)}=\overline{O(c)},\backslash overline\{O(d)\}\; =\; \backslash overline\{O(c)\},$ tutte le configurazioni di $\overline{O(c)}\backslash overline\{O(c)\}$ sono dunque periodiche, compresa c stessa.

L’ultima cosa da fare per dimostrare la congettura di Nivat è dunque studiare il caso delle configurazioni non uniformemente ricorrenti. Tuttavia, sono ancora poco comprese, e per il momento la congettura resta inaccessibile.