Diofantin

Diophantinské adjektivum ( / d j o . F ɑ̃ . T j ɛ̃ / ) (od jména Diophantus Alexandrijský ) se vztahuje na všechno, co se týká polynomiálních rovnic s celočíselnými koeficienty, nazývaných také Diophantine rovnice . K překonání desátého problému Hilberta byly vyvinuty následující koncepty . Jde o to vědět, jestli existuje obecný algoritmus umožňující říci, zda existuje řešení diofantické rovnice. Matiyasevich to teorém dokazuje nemožnost existence takového algoritmu.

Diophantine set

O podmnožině M o ℕ n se říká, že je diofantická, pokud existuje polynom D s proměnnými n + p s relativními celočíselnými koeficienty, jako například:

a ∈ M ⇔ existuje x prvek ℕ p tak, že D ( a , x ) = 0

Příklad

Sada sudých čísel je Diophantine, protože:

i ⇔ existuje x tak, že - 2 x = 0

Sada non-prvočísel je Diophantine, protože:

a není prvočíslo ⇔ existuje ( x , y ) takové, že a - ( x +2) ( y +2) = 0

Sada kladných hodnot polynomu

Jednoduchý trik způsobený Hilary Putnamovou nám umožňuje ukázat, že pokud je množina M nenulových přirozených celých čísel diofantická, jedná se o sadu přísně kladných hodnot polynomu s celočíselnými koeficienty, pro kladné hodnoty proměnných .

Opětovným převzetím definice v případě, že n = 1. Existuje polynom D s proměnnými p + 1 a relativními celočíselnými koeficienty takový, že

a ∈ M ⇔ ∃ x ∈ ℕ p , D ( a , x ) = 0.

Poté zavedeme polynom (1 - D ( y , x ) 2 ), jehož hodnoty jsou menší nebo rovny 1.

Zejména je dosaženo pouze kladné hodnoty 1 tehdy, když D ( y , x ) je nula, takže tehdy, když y ∈ M .

Sada M je tedy množina přísně kladných hodnot polynomu y (1 - D ( y , x ) 2 ):

M = ℕ * ∩ { y (1 - D ( y , x ) 2 ) | x ∈ ℕ p a y ∈ ℕ}

Například sada Fibonacciho čísel se skládá z kladných hodnot polynomu y (2 - ( x 2 + xy - y 2 ) 2 ).

Parametry x byly vybrány kladně, ale jakékoli přirozené číslo, které je součtem 4 čtverců , je možné úpravou polynomu převzít parametry v ℤ.

Setkání a průnik diofantických sad

Je snadné ukázat, že spojení nebo průnik dvou diofantinových množin je diofantin. Ve skutečnosti, jestliže M 1 a M 2 jsou Diophantine, zastoupené v tomto pořadí podle rovnice D 1 a D 2 , pak:

a ∈ M 1 ∪ M 2 ⇔ existuje ( x , y ) takové, že D 1 ( a , x ) D 2 ( a , y ) = 0.

M 1 ∪ M 2 je proto diofantin, představovaný D ( a , x , y ) = D 1 ( a , x ) D 2 ( a , y ).

Podobně, M 1 ∩ M 2 je Diophantine, zastoupená D ( , x , y ) = D 1 ( a , x ) 2 + D 2 ( , y ) 2 .

Na druhou stranu, doplněk sady Diophantine není vždy Diophantine.

Diophantine vlastnost

Vlastnost P je považována za diofantinovou, pokud existuje polynom D takový, že

P ( a ) ⇔ existuje x takové, že D ( a , x ) = 0

což představuje říká, že množina splňující vlastnost P je Diophantine set. Spojení nebo disjunkce diofantinových vlastností je diofantin. Na druhou stranu negace nebo implikace nezachovává diofantický charakter.

Postupně definujeme stále složitější diofantické vlastnosti, například skutečnost, že celé číslo je prvočíslo.

Diophantinová funkce

Funkce F v , nebo obecněji v , je Diophantine, pokud její graf je Diophantine. Jinými slovy : ${\ mathbb N}$ ${\ mathbb N}$ $\ mathbb {N} ^ {n}$ ${\ mathbb N} ^ {m}$

a = F ( b ) ⇔ existuje x, D (a, b, x) = 0

Polynomiální mapy jsou zjevně diofantické. Ale také ukazujeme, že exponenciál je Diophantine, jinými slovy, existuje polynom D, který:

a = b n ⇔ existuje x , D ( a , b , n , x ) = 0

Zdůrazňujeme, že levý výraz a = b n má tři proměnné a , b a n, a je tedy exponenciálním vztahem, a nikoli jednoduchým polynomiálním vztahem, takže a = b 3 , kde n byla stanovena hodnota 3. Je absolutně pozoruhodné, že exponenciální výraz lze charakterizovat pouze polynomiálními vztahy. Tato vlastnost, svědčí Matiyasevich , je klíčovým bodem negativní odpověď na 10 th problém Hilbert. K tomu můžeme použít skutečnost, že sekvence řešení diofantických rovnic mohou růst exponenciálně. Tedy, b n je téměř rovno a n, kde ( a n ) je sekvence definovaná:

a 0 = 0, a 1 = 1, a n +2 = ba n +1 - a n

a :

existuje n , x = n a y = s n + 1 ⇔ x 2 - bxy + y 2 = 1

Nebo pomocí kódování procházejícího řešeními Pell-Fermatových rovnic ukážeme, že existuje ekvivalence mezi a = b n a:

existují ( f , g , h , k , l , m , s , t , u , v , w , x , y , z ) přísně kladná celá čísla, jako například: m 2 - ( w 2 - 1) ( w - 1) 2 z 2 = 1 w = b + h = n + l a + g = 2 mb - b 2 - 1 ( x - y ( m - b ) - a ) 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 - 1

Ukazujeme, že binomické koeficienty jsou diofantické, protože je považujeme za koeficienty v dostatečně velké základně b ( b +1) n . Totéž platí pro faktoriály a prvočísla.

Hilbertův desátý problém

Na desátý problém Hilbertova je definovat algoritmus akceptuje jako parametr Diophantine rovnice D a dát odpověď, která dělala D připouští nebo ne řešení. V roce 1970 Matijasevič ukázal, že je nemožné, aby takový algoritmus existoval.

Skutečně ukazujeme, že existuje ekvivalence mezi Diophantinovými množinami a množinami rozpoznatelnými Turingovým strojem (nazývané také rekurzivně vyčíslitelné nebo polopočitatelné množiny ). Turingův stroj modeluje daný program na univerzálním počítači bez omezení paměti. Rekurzivně vyčíslitelná množina E je množina, pro kterou existuje algoritmus takový, že pokud dáme jako parametr algoritmu prvek a z E, pak algoritmus přestane dávat kladnou odpověď, zatímco pokud dáme jako parametr prvek a nepatřící do E, buď algoritmus přestane dávat zápornou odpověď, nebo se bude opakovat na neurčito. Rekurzivně vyčíslitelná sada je sada, jejíž prvky lze vypisovat jeden po druhém. Je možné, že nebude možné vyjmenovat prvky jeho doplňkového obsahu.

Jakákoli Diophantine sada je rekurzivně spočetná

Je snadné ukázat, že diofantická množina E definovaná rovnicí D je rekurzivně spočetná. Rozpoznávaný algoritmus je následující:

načíst hodnotu parametru a jako vstup
dát x hodnotu 0
zatímco D ( a , x ) se liší od 0, zvyšte x o 1 konec while

Tento algoritmus je uveden v případě, že x popisuje . Pokud má x popisovat , měl by být výčet prvků z nahrazen výčtem prvků z . ${\ mathbb N}$ ${\ mathbb N} ^ {p}$ ${\ mathbb N}$ ${\ mathbb N} ^ {p}$

Pokud je prvek E, bude existovat x tak, že D ( , x ) = 0. předchozí algoritmus nakonec najít a zastavení této hodnoty x . Na druhou stranu, pokud a není prvkem E, není vhodné žádné x a algoritmus bude smyčku neurčitě. E je proto rekurzivně spočetné.

Jakákoli rekurzivně vyčíslitelná sada je Diophantine

Konverzace je extrémně delikátní a představuje jádro Matijasevičovy věty. Jedním ze způsobů, jak to dokázat, je ukázat, že funkce, která spojuje následující konfiguraci s konfigurací Turingova stroje, která byla získána po kroku výpočtu, je Diophantine funkce, konfigurace jsou kódovány celými čísly. Pokud p je číslo kódující konfiguraci Turingova stroje, existuje polynom D tak, že D ( p , x 1 , ..., x n ) má řešení právě tehdy, když se Turingův stroj začínající konfigurací p zastaví . Rozpoznávání diofantických sad je tedy ekvivalentní rozpoznávání rekurzivně vyčíslitelných sad.

Předchozí metoda výslovně umožňuje přidružení polynomu k algoritmu definujícímu rekurzivně vyčíslitelnou množinu. Jones, Sato, Wada a Wiens tedy v roce 1976 výslovně uvedli polynom proměnných stupně 25 a 26, jejichž množina přísně kladných hodnot, když proměnné procházejí přirozenými celými čísly, se shoduje se sadou prvočísel. Polynom je sestaven z diofantické reprezentace množiny prvočísel pomocí výše uvedeného triku Putnam .

Nemožnost desátého problému Hilberta

Teorie vyčíslitelnosti ukázala, že existují rekurzivně spočetné množiny, jejichž doplněk není rekurzivně spočetný.

Přesněji řečeno, k libovolné diofantické rovnici D bez parametrů definujme Card (D) jako kardinál její sady řešení (možná nekonečný). Pak množina E = {D | Karta (D) ≥ 1} je rekurzivně spočetná. Protože pokud D patří do takové množiny, stačí vyjmenovat x jeden po druhém a otestovat, zda D ( x ) je nula, aby skončil s vyhledávacím, což umožňuje říci, že D patří E. Pokud D dělá nepřipustit řešení, předchozí algoritmus se opakuje na neurčito. A přesně ukážeme, že {D | Karta (D) = 0} nelze rekurzivně spočítat. To znamená, že skutečně existuje obecný algoritmus, který umožňuje říci, zda diofantická rovnice D připouští řešení, ale žádný algoritmus, který umožňuje říci, pokud D nepřijímá žádné.

Hilbertův desátý problém proto nepřipouští žádné řešení. Obecné rozlišení diophantinových rovnic je nerozhodnutelným problémem.

Poznámky a odkazy

Hilary Putnam (1960), Neřešitelný problém v teorii čísel , Journal of Symbolic Logic, Vol. 25, č. 3, září 1960.
James P. Jones , „ Universal Diophantine Equation, “ The Journal of Symbolic Logic , sv. 47, n o 3,1982, str. 549-571 ( ISSN 0022-4812 , DOI 10.2307 / 2273588 , číst online , přistupováno 14. května 2020 )

Youri Matiiassevitch, Desátý problém Hilberta , Masson 1995.