L'aggettivo diofhantino ( / d j o . F ɑ̃ . T j ɛ̃ / ) (dal nome di Diofanto di Alessandria ) si applica a tutto ciò che riguarda le equazioni polinomiali a coefficienti interi, dette anche equazioni diofantine . I seguenti concetti sono stati sviluppati per superare il decimo problema di Hilbert . Si tratta di sapere se esiste un algoritmo generale che consenta di dire se esiste o meno una soluzione a un'equazione diofantina. Il teorema di Matiyasevich dimostra l'impossibilità dell'esistenza di un tale algoritmo.
Si dice che un sottoinsieme M di ℕ n sia diofhantino se esiste un polinomio D con n + p variabili con coefficienti interi relativi come:
a ∈ M ⇔ esiste x elemento di ℕ p tale che D ( a , x ) = 0Un semplice trucco dovuto a Hilary Putnam ci permette di dimostrare che se un insieme M di interi naturali diversi da zero è diofantina, è l'insieme di valori strettamente positivi di un polinomio a coefficienti interi, per valori positivi delle variabili .
Riprendendo la definizione nel caso in cui n = 1. Esiste un polinomio D con variabili p + 1 e relativi coefficienti interi tali che
a ∈ M ⇔ ∃ x ∈ ℕ p , D ( a , x ) = 0.Introduciamo quindi il polinomio (1 - D ( y , x ) 2 ) i cui valori sono minori o uguali a 1.
In particolare, l'unico valore positivo 1 viene raggiunto se e solo se D ( y , x ) è zero e quindi se e solo se y ∈ M .
L'insieme M è quindi l'insieme dei valori strettamente positivi del polinomio y (1 - D ( y , x ) 2 ):
M = ℕ * ∩ { y (1 - D ( y , x ) 2 ) | x ∈ ℕ p e y ∈ ℕ}Ad esempio, l'insieme dei numeri di Fibonacci è costituito dai valori positivi del polinomio y (2 - ( x 2 + xy - y 2 ) 2 ).
I parametri x sono stati scelti positivi, ma, essendo qualsiasi numero naturale la somma di 4 quadrati , è possibile, modificando il polinomio, assumere parametri in ℤ.
È facilmente dimostrato che l'unione o l'intersezione di due insiemi diofantini è diofantina. Infatti, se M 1 e M 2 sono diofantine, rappresentate rispettivamente dalle equazioni D 1 e D 2 , allora:
a ∈ M 1 ∪ M 2 ⇔ esiste ( x , y ) tale che D 1 ( a , x ) D 2 ( a , y ) = 0.M 1 ∪ M 2 è quindi diofantina, rappresentato da D ( a , x , y ) = D 1 ( a , x ) D 2 ( a , y ).
Allo stesso modo, M 1 ∩ M 2 è diofantina, rappresentato da D ( a , x , y ) = D 1 ( a , x ) 2 + D 2 ( a , y ) 2 .
D'altra parte, il complemento di un set diofantino non è sempre diofantino.
Una proprietà P si dice diofhantina se esiste un polinomio D tale che
P ( a ) ⇔ esiste x tale che D ( a , x ) = 0il che equivale a dire che l'insieme di a soddisfacente la proprietà P è un insieme diofantino. La congiunzione o disgiunzione delle proprietà diofantine è diofantina. D'altra parte, la negazione o l'implicazione non preserva il carattere diofantino.
Definiamo gradualmente proprietà diofantine sempre più complesse, ad esempio il fatto che un intero sia un numero primo.
Una funzione F di in , o più in generale di in , è Diofantina se il suo grafo è Diofantina. In altre parole :
a = F ( b ) ⇔ c'è x, D (a, b, x) = 0Le mappe polinomiali sono ovviamente diofantine. Ma mostriamo anche che l'esponenziale è diofhantino, in altre parole, esiste un polinomio D tale che:
a = b n ⇔ c'è x , D ( a , b , n , x ) = 0Si specifica che l'espressione sinistra un = b n ha tre variabili a , b ed n ed è quindi una relazione esponenziale, e non una semplice relazione polinomiale tale che un = b 3 , dove n è stato fissato il valore 3. E ' assolutamente notevole che un'espressione esponenziale possa essere caratterizzata solo da relazioni polinomiali. Questa struttura, dimostrato da Matiyasevich , è un punto chiave della risposta negativa data al 10 ° problema di Hilbert. Possiamo usare per questo il fatto che le sequenze di soluzioni di equazioni diofantine possono crescere in modo esponenziale. Pertanto, b n è quasi uguale ad a n dove ( a n ) è la sequenza definita da:
a 0 = 0, a 1 = 1, a n +2 = ba n +1 - a ne :
esistono n , x = a n e y = a n + 1 ⇔ x 2 - bxy + y 2 = 1Oppure, utilizzando una codifica che passa per soluzioni di equazioni di Pell-Fermat , mostriamo che c'è equivalenza tra a = b n e:
esistono ( f , g , h , k , l , m , s , t , u , v , w , x , y , z ) interi strettamente positivi come: m 2 - ( w 2 - 1) ( w - 1) 2 z 2 = 1 w = b + h = n + l un + g = 2 mb - b 2 - 1 ( X - y ( mb ) - un ) 2 = ( f - 1) 2 (2 mb - b 2 - 1) 2 x 2 - ( m 2 - 1) y 2 = 1 u 2 - ( m 2 - 1) v 2 = 1 s 2 - ( k 2 - 1) t 2 = 1 v = ry 2 k = 1 + 4 py = m + qu s = x + cu t = n + 4 ( d - 1) y y = n + e - 1Mostriamo che i coefficienti binomiali sono diofantini considerandoli come coefficienti in una base b abbastanza grande di ( b +1) n . È lo stesso per fattoriali e numeri primi.
Il decimo problema di Hilbert è definire un algoritmo che accetti come parametro l'equazione diofantina D e dando una risposta che facesse sì che D ammetta o meno soluzioni. Nel 1970, Matiyasevic ha dimostrato che era impossibile l'esistenza di un tale algoritmo.
Mostriamo infatti che c'è equivalenza tra gli insiemi diofantini e gli insiemi riconoscibili da una macchina di Turing (insiemi chiamati anche ricorsivamente enumerabili o semi-computabili). Una macchina di Turing modella un determinato programma su un computer universale senza limitazioni di memoria. Un insieme ricorsivamente enumerabile E è un insieme per il quale esiste un algoritmo tale che, se diamo come parametro all'algoritmo un elemento a di E, allora l'algoritmo smette di dare una risposta positiva, mentre se diamo come parametro un elemento a non appartenendo a E, o l'algoritmo smette di dare una risposta negativa, o esegue un ciclo indefinito. Un insieme ricorsivamente enumerabile è un insieme i cui elementi possono essere elencati uno per uno. Potrebbe essere impossibile elencare gli elementi del suo complementare.
È facile mostrare che un insieme diofantino E definito da un'equazione D è enumerabile ricorsivamente. L'algoritmo che lo riconosce è il seguente:
Questo algoritmo viene fornito nel caso in cui x descrive . Se x deve descrivere , l'enumerazione degli elementi di dovrebbe essere sostituita da un'enumerazione degli elementi di .
Se a è un elemento di E, esisterà una x tale che D ( a , x ) = 0. L'algoritmo precedente alla fine lo troverà e si fermerà su questo valore di x . D'altra parte, se a non è un elemento di E, nessuna x è adatta e l'algoritmo eseguirà un ciclo indefinito. E è quindi enumerabile ricorsivamente.
Il contrario è estremamente delicato e costituisce il punto cruciale del teorema di Matiyasevich. Un modo per dimostrarlo è mostrare che la funzione che associa la seguente configurazione ad una configurazione di una macchina di Turing, quella ottenuta dopo una fase di calcolo, è una funzione diofantina, le configurazioni essendo codificate da numeri interi. Se p è un numero che codifica una configurazione di una macchina di Turing, esiste un polinomio D tale che D ( p , x 1 , ..., x n ) ha una soluzione se e solo se la macchina di Turing che inizia con la configurazione p si ferma . Il riconoscimento degli insiemi diofantini è quindi equivalente a quello degli insiemi ricorsivamente enumerabili.
Il metodo precedente consente esplicitamente di associare un polinomio a un algoritmo che definisce un insieme ricorsivamente enumerabile. Così, Jones, Sato, Wada e Wiens hanno esplicitato nel 1976 un polinomio di variabili di grado 25 e 26 il cui insieme di valori strettamente positivi, quando le variabili attraversano interi naturali, coincide con l'insieme dei numeri primi. Il polinomio è costruito dalla rappresentazione diofantea dell'insieme di numeri primi usando il trucco di Putnam sopra .
La teoria della computabilità ha mostrato che esistono insiemi enumerabili ricorsivamente il cui complemento non è enumerabile ricorsivamente.
Più precisamente, per qualsiasi equazione diofantea D senza parametri, definiamo la carta (D) come il cardinale del suo insieme di soluzioni (possibilmente infinite). Allora l'insieme E = {D | La carta (D) ≥ 1} è enumerabile ricorsivamente. Perché se D appartiene a un tale insieme, è sufficiente enumerare le x una dopo l'altra e verificare se D ( x ) è zero per trovarne uno, il che consente di dire che D appartiene a E. Se D lo fa non ammette una soluzione, l'algoritmo precedente si ripete indefinitamente. E precisamente, dimostriamo che {D | Card (D) = 0} non è enumerabile ricorsivamente. Ciò significa che esiste effettivamente un algoritmo generale che consente di dire se un'equazione diofantina D ammette una soluzione, ma nessun algoritmo che consente di dire se D non ne ammette alcuna.
Il decimo problema di Hilbert quindi non ammette alcuna soluzione. La risoluzione generale delle equazioni diofantine è un problema indecidibile.
Youri Matiiassevitch, Il decimo problema di Hilbert , Masson 1995.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">