Autore originario é Marcelo Escudeiro Hernandes.
Per il famoso “Teorema dei quattro colori”, abbiamo bisogno solo di quattro colori per colorare una mappa in modo che nessuna delle regioni confinanti abbia lo stesso colore. Usando equazioni polinomiali e basi di Gröbner possiamo determinare se tre colori sono sufficienti per una mappa specifica.
1. Colorazione di mappe
Il famoso Teorema dei Quattro Colori [1] afferma che tutte le mappe, siano esse in un piano o su una sfera, possono essere colorate con quattro colori senza che regioni confinanti siano dello stesso colore. È molto facile produrre esempi di mappe che non possono essere colorate con tre colori e di altre per le quali ciò è possibile. Un modo per decidere se tre colori sono sufficienti per colorare una particolare mappa, è quello di analizzare un sistema polinomiale associato alla mappa. Ogni colore è rappresentato da una radice cubica complessa dell’unità e ogni regione da una variabile che può assumere solo uno di tre valori, cioè, uno dei tre colori. Abbiamo quindi per ciascuna regione.
Per regioni e abbiamo . Se e sono regioni confinanti e, come regioni confinanti, non possono avere lo stesso colore, allora , cioè, . In questo modo, una mappa con n regioni può essere colorata con tre colori se e soltanto se il seguente sistema di equazioni polinomiali ammette almeno una soluzione
(1)
dove e e rappresentano regioni adiacenti.
Esempio 1.
Consideriamo la mappa:
Può essere colorata con tre colori?
Per rispondere a questa domanda dobbiamo verificare se si può risolvere il sistema polinomiale (1), con e
2. Sistemi di equazioni polinomiali
La risposta a molti problemi in matematica è dovuta alla soluzione di sistemi di equazioni polinomiali, che non è sempre semplice. Se il sistema è composto da equazioni lineari, mediante eliminazione gaussiana, possiamo sostituire il sistema con un altro ad esso equivalente la cui soluzione è più semplice. Nel caso di sistemi polinomiali, si ha a disposizione un metodo analogo che descriviamo sotto.
Denoteremo con l’insieme dei polinomi a coefficienti complessi con variabili . Dato un insieme di polinomi in , determiniamo l’ideale generato da essi:
Un teorema dovuto al matematico David [2], chiamato Nullstellensatz di Hilbert, afferma che il sistema ammette una soluzione (complessa) se e soltanto se . Ma come si può verificare quest’ultima condizione?
È molto semplice verificare che due sistemi di equazioni e , dove soddisfano alla condizione
(2)
hanno la stessa soluzione.
Quindi, la strategia per risolvere un sistema consiste nel trovare polinomi che soddisfano alla condizione (2) e con cui è possibile verificare se un dato appartiene o meno all’ideale e la cui soluzione comune è più semplice da calcolare rispetto a quella del sistema originario.
L’esistenza di tale era stata scoperta dal punto di vista teorico nella prima metà del secolo scorso dal matematico Wolfgang Gröbner. Alcuni anni dopo, il suo studente Bruno Buchberger ha creato un algoritmo per calcolarlo. Questi insiemi sono chiamati Basi di Gröbner e l’algoritmo di Buchberger per calcolarle è uno degli strumenti più importanti del calcolo algebrico.
Se l’ideale è della forma , abbiamo se e solo se , vale a dire, è divisibile per . Analogamente, se e solo se , il che suggerisce qualcosa di simile per la divisione di per . In effetti, possiamo dividere un polinomio in diverse variabili mediante un insieme finito di polinomi, a condizione che i monomi siano ordinati in un qualche modo.
3. Basi di Gröbner
Un monomio di è un elemento della forma , dove
sono interi non negativi. Il monomio sarà denotato con . Tra gli ordini tra i monomi di , quelli che soddisfano e ogni volta che sono quelli che permettono di applicare l’algoritmo della divisione.
Un esempio è l’ ordine lessicografico , dove , se esiste tale che e per tutti .
Fissato un ordine tra i monomi, il massimo monomio di un polinomio f è chiamato il termine portante di ed è denotato con .
Una base di Gröbner di un ideale rispetto ad un dato ordine tra monomi, è, per definizione, un qualunque insieme di elementi di tale che il termine portante di un qualunque elemento di sia divisibile per il termine portante di qualche elemento di . Possiamo mostrare che una qualunque base di Gröbner di è un insieme che soddisfa la condizione (2).
Quindi, se e soltanto se esiste una base di Gröbner di che contiene una costante non nulla, poichè , per ogni monomio di .
Per esempio, è una base di Gröbner di rispetto ad un qualsiasi ordine tra monomi, mentre non è una base di Gröbner di rispetto all’ordine lessicografico, perchè non è divisibile per .
Per ottenere una base di Gröbner di un ideale, rispetto all’ordine tra monomi scelto, si può applicare l’algoritmo di BuchBerger [3]. Troviamo algoritmi per calcolare le basi di Gröbner nella maggior parte dei CAS (computer algebra systems).
Per esempio, una base di Gröbner per l’ideale , rispetto all’ordine lessicografico è .
4. Soluzione del problema ed altre applicazioni
Il sistema dato nell’Esempio 1. ha al più un numero finito di soluzioni (nove variabili, di cui ognuna può assumere uno dei tre valori). Il problema è determinare se il sistema ammette una qualche soluzione, e in tal caso, trovarla.
Applicando l’algoritmo di BuchBerger al sistema dell’Esempio 1., otteniamo la seguente base di Gröbner , rispetto all’ordine lessicografico:
Quindi, e di conseguenza il sistema ammette soluzioni. Le equazioni
descrivono quanto segue: possiamo usare un qualunque colore per , , e .
Poiché i colori sono rappresentati dalle radici cubiche complesse dell’unità , l’unica soluzione per , e è attribuire valori (colori) distinti per , e e così . Infine,
ci dà due possibilità : o , vale a dire, , e assumono colori distinti oppure . In tal modo, troviamo, a meno di permutazioni di colori, tutte le possibili soluzioni:
Le basi di Gröbner possono anche essere usate per operare con gli ideali, convertendo equazioni parametriche in forma implicita (ad esempio, alcune superfici e curve) in equazioni non parametriche, per calcolare il polinomio minimo di numeri algebrici, per verificare teoremi di geometria euclidea, per validare costruzioni con gli Origami e per risolvere puzzle Sudoku (si veda [4], [5] e [6]).
Riferimenti bibliografici
[1] http://www.ipv.pt/millenium/Millenium24/12.pdf
[2] http://www.mat.uniroma1.it/people/manetti/dispense/nullstellen.pdf
[3] https://www.risc.jku.at/people/buchberg/papers/1970-00-00-A.english.pdf
[4] Adams, W. and Loustaunau, P., An Introduction to Gröbner Basis, AMS, Providence RI (1994).
[5] Cox, D; Little, J. and O’Shea, D., Ideals, Varieties and Algorithms, 2nd edition, Springer-Verlag, New York, (1996).
[6] Hernandes, M. E., Um Primeiro Contato com Bases de Gröbner, 28°. Colóquio Brasileiro de Matemática, IMPA, Rio de Janeiro, (2011).
Questo post è disponibile in: Inglese, Francese, Tedesco, Arabo, Khmer