INSOLUBILITA’ DEL XPROBLEMA DI

HILBERT

Tania Notarantonio

Luglio 2002

Il problema diofanteoIl problema diofanteo Un’equazione diofantea è

un’equazione della forma: E0(x1,…,xn) = E1(x1,…,xn) dove E0 , E1 sono poly(nomi) a coefficienti interi positivi.

poly::=monom| |

monom+monom monom::=NAT|VAR| |monom.monom NAT::=(1|2|…|9)(0|1|2|…|9)*

VAR::=x|y|z|u|v|w|VAR NAT

Un’equazione diofantea esponenziale è una equazione della forma: E0(x1,…,xn) = E1(x1,…,xn) dove E0, E1 sono polinomi esponenziali (polyexp) a coefficienti interi positivi. polyexp::=monom| |monom+monom monom::=NAT|VAR|

|monom.monom| |monommonom

-1 0-3

Esempio

Data l’equazione: (x+2)2 = 1 + 7y2

il cui grafico è il seguente:

Sue soluzioni intere sono: (-1,0),(-3,0).

Ci chiediamo se esistono soluzioni sui naturali: una breve ricerca rivela che (6,3) è soluzione intera positiva per l’equazione data.

Cercare soluzioni intere / naturali sono sottoproblemi del cercare soluzioni reali ma non per questo risulta essere più banale.

ALGORITMO DI

DECISIONE

Il X problema di Hilbert era: trovare un metodo per determinare se una equazione diofantea data ha soluzioni su ℤ.

E0, E1

si

no

(u+1)2+

(w+1)2 z2

:questo problema specifica le terne pitagoriche:

x2 + y2= z2, dove x,y,z > 1

(u+1)w+3 +(v+1)w+3 zw+3

:grazie al grande teorema di Fermat dimostrato nel 1995

L’enigma di Fermat

L’Ultimo teorema di Fermat o “enigma” di Fermat afferma che non esistono numeri interi positivi legati dalla relazione:

xn + yn = zn con n > 2

INDICE

» casi decidibili emblematici

» riduzione del X a ℕ

» idea chiave della dimostrazione di insolubilità:

› insiemi diofantei;

› insiemi diofantei esponenziali;

› insiemi r.e. ( listabili ).

» insolubilità del X ( gödelizzazione, argom. diagonale )

» questioni aperte

› limitazione alla forma normale di Davis

› ampliamento del X a ℚ

D D

E E

R R

?

?

Sottoproblemi classici (risolti) del X.

equazioni lineari:

ax + by = c con a, b, c > 0

equazioni di Pell:

x2 - (b2 - 1) y2 = 1 con b > 0

C.N.S. per la risolubilità di è che M.C.D(a,b) | c ;

ha sempre infinite soluzioni.

ricade come caso particolare nella decidibilità dell’aritmetica additiva (Presburger, 1929).

Sia che ricadono nella decidibilità di equazioni di 2° grado.

Riduzione di altri problemi al diofanteo

A. Ogni istanza D(x1,…,xn)=0del X problema di Hilbert sipuò ridurre al problema disoddisfare una congiunzionedi letterali insiemistici delleforme: y z = ø x = y zx y |x| = |y| x = y z|x| |y|

B. Se disponiamo di unrisolutore sugli interi, grazieal teorema di Lagrange(1772) possiamo adattarloai naturali sostituendo ogniincognita xi con la somma: x²i1 + x²i2 + x²i3 + x²i4 .

Congettura di Martin Davis (1953)

Def.: (rappresentazione diofantea di un insieme S)

Si dice diofanteo un insieme S associato a un polinomio parametrico diofanteo D come segue:

(a1, … , an) S

x1, … , xm D(a1, … , an, x1, … , xm) = 0

(n si chiama dimensione di S)

Congettura:

le nozioni diofanteo si equival-

di insieme ricorsivamente enumerabile gono

Dalla dimostrazione di questa discese, nel 1970, l’insolubilità del X problema di Hilbert.

CRESCITA ESPONENZIALEParadigma di ricorrenza: b(0) = 1

b(n+1)=b . b(n) a=bc a = b(c)

Varianti:

b(n) = b(n) = n per n = 0,1

b(n+2) = b(n+1) + b . b(n)

b(n+2) = b(n+1) - b . b(n)

n = 1(n) [seq. Fibonacci]

La diofantinità di a = bc discende da quella di una delle segg. relazioni:

v = 2u (1970); a = b(c) (1970); a = b(c) (1993)

Ecco il modo in cui Davis (1973) rappresenta

la relazione m = nk con m,n,k > 0:

pell(c,x,y) Def x2 - (c2 - 1) . y2 = 1

pell(a,x,y) pell(a,u,v) pell(b,s,t) b > a > 1 y k > 0 b > 4y 4y | b - 1v > 0 y2 | v u | b - a s > x u | s - x t k 4y | t- k ( x - y . (a - n) - m)2 = f2 . (2a . n - n2 - 1)2

2a . n - n2 - 1 > m > 0 pell(w,a,(w - 1) . (g + 1)) w > n > 0 w > k

Corollari della diofantinità di m = nk

r.e secondo Turing

Gli insiemi diofantei esponenziali coincidono

. . . diofantei

Per altra via:

• gli insiemi diofantei sono chiusi rispetto

alla quantificazione limitata (y)yx

• le funzioni diofantee sono tutte e sole

le ricorsive.

poly(N,P) :- natural(N), !, M is N mod 3, (M==0 -> M1=3; M1=M), I is (N-M1) //3,

(N==0 -> P=1; M==1 -> name(I,S), [X] = "x", name(P,[X|S])

; cantor(L,R,I), poly(L,PL), poly(R,PR), ( M==2 -> P=PL+PR; P=PL*PR )).

poly(0,1).poly(N,Xi) :- atom(Xi), name(Xi,[X|S]), [X]="x", name(I,S), N is 3*I+1. poly(N,P+Q) :- poly(L,P),poly(R,Q), cantor(L,R,C), N is 3*C+2.poly(N,P*Q) :- poly(L,P),poly(R,Q), cantor(L,R,C),

N is 3*C+3.

Gödelizzazione di polinomi - I

Gödelizzazione di polinomi - II

% l'N-simo numero triangolare e`...triang(N,T) :- natural(N), !, T is (N*(N+1)) // 2. %…la somma T= 0+1+2+...+N triang(0,0).triang(Np1,TT) :- triang(N,T), Np1 is N+1, TT is T+Np1.

cantor(L,R,C) :- natural(L), !, LpR is L+R, triang(LpR,T), C is T+R.cantor(L,R,C) :- triang(N,T),

(T==C -> L=N,R=0; T>C -> R is C-T+N, L is N-1-R), !.

Indicheremo con L(n), R(n) le projez. associate alla funzione di abbinamento, i.e., cantor(L(n), R(n) , n)

Argomento diagonale contro la risolubilità del XOra sappiamo gödelizzare i poly involgenti la solacostante 1 e, come variabili, le x0 , x1 , x2 ,... :

n | Pn (x0 , x)

Di qui una enumerazione effettiva D0 , D1 , D2 ,…di tutti i sottinsiemi diofantei di ℕ :

Dn = { x0 | x PL(n) (x0 , x)= PR(n) (x0 , x)}

Possiamo trovare polynomi PL(n*) (x0 , x) , PR(n*) (x0 , x)anche per l’insieme, che si dimostra diofanteo,

{ k | R(k) DL(k) } (=Dn* )mentre è, evidentemente, non diofanteo il

= { h | h Dh }-->-->-->

Argomento diagonale contro la risolubilità del X-->-->-->

Se per assurdo potessimo risolvere il X, alloraavremmo modo di verificare seR(k) DL(k) , ossia x PL(n*) (x0 , x) = PR(n*) (x0 , x)o no; sarebbero dunque ricorsive la funzione

Dh (x)

(di h ed x) e la

1- Dx (x)

funzione caratteristica di , che dunque sarebbediofanteo, contraddizione.

TEOREMA: indecidibilità forte del X problema

Esistono un polinomio diofanteo V(x0, x1, … ,xm) e una funzione calcolabile tot. a tali che nessun algoritmo A dia risposta corretta circa la risolubilità su ℕ dell’equazione V(a(⌈A ⌉) , x1, … ,xm) = 0 :

A(a(⌈A⌉ )) ‘SI’

x1, … ,xm ℕ V(a(⌈A⌉) , x1, … ,xm) = 0

Già la famiglia

V(b, x1, … ,xm) = 0, con bℕ

di equazioni diofantee è dunque indecidibile. Compromesso fra il grado d di V e il numero massimo m di incognite: l’uno può essere reso più piccolo a costo di accrescere l’altro. Ecco alcuni record:

(d,m) = (4, 58), (8, 38), ….. , (1.6 . 1045, 9)

Limitazione alla FORMA NORMALE di Davis

La chiusura dei diofantei rispetto ad (y)yx, derivabile dalla diofantinità di m = nk , era stata individuata come possibile chiave per rispondere negativamente al X, grazie alla scoperta di una rappresentazione degli r.e., nota come forma normale di Davis:

z (y)yzx1, … , xh P(y,z, x1, … , xh) = 0

Grazie alla diofantinità di m = nk , oggi sappiamo che h2.

Può essere fissato h=1 ?

X in ambienti numerici diversi da ℕRisolvere una equazione:

D(X1,…..,Xm) = 0

nelle X1,…..,Xm su ℚ è equivalente a risolvere l’equazione:

D((x1-y1)/(z+1),….., (xm-ym)/(z+1)) = 0

nelle incognite x1, y1,…..,,xm, ym, z su ℤ+.

Quest’ultima equazione è equivalente alla seguente equazione omogenea:

(z+1)dD((x1-y1)/(z+1),….., (xm-ym)/(z+1)) = 0

dove d è il grado del polinomio D.

Due problemi interriducibili:

stabilire se una equazione diofantea ha soluzione in ℚ;

stabilire se una equazione diofantea omogenea ha solu-

zioni non-banali in ℤ.

Le equazioni sono una sottoclasse delle equazioni diofantee ed è pertanto possibile che questa sottoclasse ridotta sia decidibile.

Inteso in senso largo il X problema di Hilbert rimane ancora aperto.

In senso stretto, così come è stato letteralmente formulato, risulta chiuso grazie ai contributi di Martin Davis, Hilary Putnam, Julia Robinson e Yuri Matiyasevič.