Hilbert tizedik problémája

Csirmaz László

David Hilbert a századforulón a párizsi Nemzetközi Matematikai Kongresszuson 23 problémát sorolt fel, melyek megoldását az eljövendő századtól várta. Ezek közül a tizedik a következő volt: adjunk meg olyan eljárást (algoritmust), amely minden egész együtthatós (többváltozós) polinomról eldönti, van-e a polinomnak nem-negatív egészekből álló gyökrendszere. Ebben a jegyzetben azt mutatjuk meg, hogy Hilbert várakozásával ellentétben ilyen algoritmus nem létezik.

Tekintsünk egy n+m-változós, egész együtthatós p(\overline{x}, \overline{y}) polinomot. Az \overline{y} változókat paramétereknek tekintjük, és ezek rögzitése után megnézzük, hogy a polinomnak az \overline{x} változókban van-e nem-negatív egészekből álló megoldása. Álljon R_{p} pontosan azokból az \overline{y} paraméterekből, melyekre ilyen megoldás létezik. Ezzel R_{p} egy természetes számok m-eseiből álló halmaz, vagyis egy reláció lesz. Az ilyen típusú relációkat diphantikus relációknak nevezzük, s ezek vizsgálata vezetett végül is a fenti eredményhez.

Egy természetes számokon értelmezett és természetes számot felvevő függvény rekurzív, ha kiszámítható, azaz ha létezik olyan Turing-gép, ami minden inputra megáll és éppen a függvény értékét számítja ki. A rekurzív függvények sok más ekvivalens definíciója közül mi a következőt fogjuk használni.

Definíció Rekurzív függvények az ω^{n} → ω^{m} függvények legszűkebb részosztálya, mely egyrész tartalmazza a következő függvényeket:

f(x, y) = x + y  összeadás
f(x, y) = x · y  szorzás
f(x_{1}, …, x_{n}) = x_{i}  projekciófüggvények
f(x, y) = \{ \begin{matrix}1 & ha x ≥ y, \\ 0 & egyébként \end{matrix}  a ≥ karakterisztikus függvénye

másrészt zárt a kompozícióra és a μ-operációra, azaz ha f(\overline{x}, u) egy (n + 1)-változós rekurzív függvény úgy hogy minden \overline{x}-hez van olyan u amivel f(\overline{x}, u) = 0, akkor

g(\overline{x}) = μu(f(\overline{x}, u) = 0) {def \atop =} min\{u ∈ ω : f(\overline{x}, u) = 0\}

szintén rekurzív.

Csakúgy mint itt, a későbbiekben is ω jelöli a természetes számok halmazát. Egy ω^{n}-en értelmezett R reláció rekurzív, ha karakterisztikus függvénye, azaz χ_{R}(\overline{x}) = 1 ha \overline{x} ∈ R és χ_{R}(\overline{x}) = 0 ha \overline{x} ∉ R, rekurzív. R rekurzívan felsorolható, ha R éppen egy rekurzív függvény értékkészlete. Megjegyezzük, hogy minden rekurzív reláció egyúttal rekurzívan felsorolható is, de fordítva nem: van ω-nak rekurzívan felsorolható, de nem rekurzív részhalmaza.

Egy függvény parciálisan rekurzív, ha értelmezési tartománya ω^{n} valamely részhalmaza, és előáll egy rekurzív függvényből a μ-operáció alkalmazásával, ahol is nem követeljük meg, hogy minden \overline{x} inputra létezzen megfelelő u érték.

A nevezetes Church-tézis azt mondja ki, hogy minden (elvben) kiszámítható függvény rekurzív. A tézis számos következménye közül az egyik legnevezetesebb, hogy nincs algoritmus (vagyis kiszámítási eljárás), ami minden Turing-gépre megmondaná, hogy az véges sok lépésen belül megáll-e vagy sem (megállási probléma).

Visszatérve Hilbert 10. problémájához, az 50-es évek elejére Julia Robinson bizonyította, hogy amennyiben az f(n, k) = n^{k} kétváltozós függvény diophantikus, akkor minden rekurzív függvény is az. Ebből viszont már következik, hogy a Hibert által keresett algoritmus nem létezik — amit úgy szokás kifejezni, hogy Hilbert tizedik problémája megoldhatatlan (lásd 7. Következmény). Annak igazolása, hogy n^{k} valóban diophantikus, további 20 évet váratott magára, ez J. Matijasevics tétele.

A bizonyításhoz elsőként néhány definíciót vezetünk be, majd pár egyszerű állítást igazolunk.

Definíció Az R ⊂ ω^{n} reláció diophantikus, ha van olyan n + m-változós egész együtthatós p(\overline{x}, \overline{z}) polinom, hogy minden x_{1}, …, x_{n} nem-negatív egész számra \overline{x} = ⟨x_{1}, …, x_{n}⟩ ∈ R akkor és csak akkor, ha vannak olyan nem-negatív egész z_{1}, …, z_{m} számok, hogy p(\overline{x}, \overline{z}) = 0.

Definíció Az f : ω^{n} → ω függvény diophantikus, ha az \{⟨\overline{x}, y⟩ ∈ ω^{n+1} : f(\overline{x}) = y\} reláció diophantikus.

1. ÁllításAz =, ≠, ≤, < diophantikus relációk, a +, ·, id diophantikus függvények.

Bizonyítás. Az alábbi átírások alkalmazásával:

\begin{aligned}x = y & ⇔ x − y = 0 \\ x ≤ y & ⇔ (∃z ≥ 0) x + z − y = 0 \\ x ≠ y & ⇔ (∃z ≥ 0) (x − y)^{2} − 1 − z = 0 \\ x < y & ⇔ (∃z ≥ 0) x + z + 1 − y = 0 \\ x + y = z & ⇔ x + y − z = 0 \\ x·y = z & ⇔ x·y − z = 0. \end{aligned}

2. ÁllításHa R_{1} ⊂ ω^{n} és R_{2} ⊂ ω^{n} diophantikus relációk, akkor R_{1} ∨ R_{2} ( = R_{1} ∪ R_{1}) valamint R_{1} ∧ R_{2} ( = R_{1} ∩ R_{2}) is azok.

Bizonyítás. Legyen \overline{x} ∈ R_{1} ⇔ (∃\overline{z} ≥ 0) p(\overline{x}, \overline{z}) = 0 valamint \overline{x} ∈ R_{2} ⇔ (∃\overline{u} ≥ 0) q(\overline{x}, \overline{u}) = 0. Ekkor

\begin{aligned}\overline{x} ∈ R_{1} ∪ R_{1} & ⇔ (∃\overline{z} ≥ 0)(∃\overline{u} ≥ 0) p(\overline{x}, \overline{z})·q(\overline{x}, \overline{u}) = 0, \\ \overline{x} ∈ R_{1} ∩ R_{1} & ⇔ (∃\overline{z} ≥ 0)(∃\overline{u} ≥ 0) p^{2}(\overline{x}, \overline{z}) + q^{2}(\overline{x}, \overline{u}) = 0. \end{aligned}

Ezek alapján az állítás közvetlenül adódik.

3. ÁllításHa f_{1} és f_{2} diophantikus függvények, akkor f_{1} + f_{2}, f_{1}·f_{2} és f_{1} ∘ f_{2} (kompozíció) is azok.

Bizonyítás. Definíció szerint (f_{1}+f_{2})(\overline{x}) = y ⇔ ∃y_{1} ≥ 0∃y_{2} ≥ 0(f_{1}(\overline{x}) = y_{1}∧f_{2}(\overline{x}) = y_{2}∧y_{1}+y_{2} = y). A feltétel szerint a zárójelben diophantikus relációk állnak, így azok metszete is diophantikus. Hasonlóan bizonyítható a többi eset is.

Világos, hogy minden diophantikus fügvény egyúttal parciálisan rekurzív is, és hogy a diophantikus relációk rekurzívan felsorolhatók. Láttuk, hogy az alapfüggvények, melyekből a (parciálisan) rekurzív függvényeket felépíthetjük, diophantikusak, továbbá hogy a diophantikus függvények köréből az összeg, szorzat és kompozícióképzés nem vezet ki. Így annak igazolásához, hogy minden parciálisan rekurzív függvény egyúttal diophantikus is, elegendő az alábbi tételt igazolnunk:

4. TételHa az f : ω^{n+1} → ω függvény diophantikus, akkor a g(\overline{x}) = μu(f(\overline{x}, u) = 0) szintén diophantikus.

Mielőtt a tétel bizonyítására rátérnénk, nézzük néhány következményét. Elsőként az előbb megfogalmazott ekvivalenciát mondjuk ki.

5. KövetkezményEgy függvény akkor és csak akkor parciálisan rekurzív, ha diophantikus.

Bizonyítás. A függvény felépítésére vonatkozó indukcióval.

Kleene első normálforma tétele azt mondja ki, hogy minden n-re létezik univerzális rekurzíve felsorolható reláció, azaz olyan U_{n} ⊂ ω^{n+1}, hogy minden rekurzív R ⊂ ω^{n}-re található olyan r ∈ ω, hogy R = \{\overline{x} ∈ ω^{n} : ⟨\overline{x}, r⟩ ∈ U_{n}\}.

6. Következmény (Univerzalitási tétel)Van olyan p(x, r, \overline{z}) egész együtthatós polinom, hogy minden rekurzíve felsorolható R ⊂ ω relációhoz található r ∈ ω, hogy x ∈ R ⇔ (∃\overline{z} ≥ 0)p(x, r, \overline{z}) = 0.

7. Következmény (Hilbert tizedik porblémájának megoldhatatlansága)Legyen p(x, r, \overline{z}) egy univerzális polinom. Ekkor nem létezik olyan algoritmus, amely minden r ∈ ω-ra eldöntené, hogy a p(r, r, \overline{z}) = 0 diophantikus egyenletnek van-e megoldása a nem-negatív egész számok körében.

Bizonyítás. Ha mégis volna ilyen algoritmus, akkor a Chuch-tézis értelmében az

R = \{r ∈ ω : a p(r, r, \overline{z}) = 0 nem oldható meg \overline{z} ≥ 0-val \}

halmaz szintén rekurzív volna, így a p univerzalitása miatt volna r ∈ ω, hogy

x ∈ R ⇔ p(x, r, \overline{z}) = 0 megoldható \overline{z}-ben.

Itt x = r-et téve kapjuk, hogy

p(r, r, \overline{z}) = 0 megoldható ⇔ p(r, r, \overline{z}) = 0 nem olható meg,

ami nyilván ellentmondás.

Nem nehéz belátni (lásd a feladatokat), hogy van negyedfokú univerzális polinom. Így Hilbert tizedik problémája már negyedfokú polinomokra sem oldható meg. Ugyanakkor ismeretes algoritmus, mely tetszőleges első- és másodfokú polinom esetén megmondja, van-e a polinomnak egész gyöke vagy sem (ez C. L. Siegel 1972-es eredménye). Harmadfokú polinomokra a kérdés nyitva van.

Más oldalról az univerzális polinomok változóinak számát vizsgálhatjuk. Jól ismert, hogy egy egyváltozós egész együtthatós polinom egész gyöke (ha van) osztója a konstans tagnak, így egyváltozós polinomokra is létezik eldöntő algoritmus. J. Robinson és J. Matijasevics konstruált 13 ismeretlenes univerzális polinomot, ennek fokszáma azonban igen magas, nagyobb mint 10^{10^{10}}. A következő fokszám– változószám párok mellett ismert univerzális polinom: (4,153), (6,129), (8,108), (10,107), (20,86), (44,83), (1952,80). Az ismert legkisebb lehetséges változószám kilenc: 9-változós polinomok olyan sorozatát lehet megadni, melyekre nem létezik eldöntő algoritmus. A hiányzó 2, 3, …, 8 esetekre szinte semmi sem ismert.

Az univerzális polinom létezésének egyik meglepő következménye, hogy elegendően nagy q-ra (például q ≥ 14 megteszi) a legalább q tényezős szorzatra felbontható számok halmaza, vagyis az

{x ∈ ω : ∃z_{1} ≥ 0 … ∃z_{q} ≥ 0 x = (z_{1} + 2)·(z_{2} + 2)· · · · ·(z_{q} + 2)}

reláció definiálható q-nál kevesebb paraméterrel is.

Az 5. következmény bizonyítása – könnyen látható módon – formalizálható a Peano axiómarendszerben. Mivel egy reláció akkor és csak akkor rekurzíve felsorolható, ha van azt definiáló Σ_{1} formula, azonnal adódik az alábbi

8. KövetkezményMinden φ(\overline{x}) Σ_{1} Peano formulához található olyan ψ(\overline{x}, \overline{z}) kvantormentes (prím) formula, hogy P A |− φ(\overline{x}) ↔ ∃z_{1} … ∃z_{m}ψ(\overline{x}, \overline{z}).

Más szavakkal a Σ_{1} formulák ekvivalensek az ún. egzisztenciális formulákkal, melyekben egyátalán nem szerepel korlátos kvantor. Az aritmetikai hierarchia felépítésében így a Σ_{n}, Π_{n} formulákban n ≥ 1-re feltehetjük, hogy nem szerepel korlátos kvantor.

Most rátérünk a 4. tétel bizonyítására. Legyen tehát a p(\overline{x}, u, y, \overline{z}) egész együtthatós polinom olyan, hogy minden \overline{x} ∈ ω^{n}, u, y ∈ ω mellett

f(\overline{x}, u) = y akkor és csak akkor, ha (∃\overline{z} ≥ 0)p(\overline{x}, u, y, \overline{z}) = 0.

Legyen g(\overline{x}) = μu(f(\overline{x}, u) = 0). A μ operáció definíciója alapján adott \overline{x} ∈ ω^{n} és u ∈ ω esetén g(\overline{x}) = u pontosan akkor áll fenn, ha f(\overline{x}, u) = 0, továbbá minden 0 ≤ v < u esetén f(\overline{x}, v) definiálva van és 0-tól különböző, azaz értéke y + 1 valamilyen y ≥ 0-ra. Így g(\overline{x}) = u pontosan akkor, ha

(∃\overline{z} ≥ 0)p(\overline{x}, u, 0, \overline{z}) = 0 ∧ (∀v < u)(∃\overline{z} ≥ 0)(∃y ≥ 0)p(\overline{x}, v, y + 1, \overline{z}) = 0.

Ahhoz, hogy g valóban diophantikus függvény legyen, elegendő az itt szereplő diszjunkció második tagjáról megmutatni, hogy diophantikus reláció. A jelölések egyszerűsítése érdekében az y változót a \overline{z} paraméterek közé soroljuk, és a szereplő (most már) n + 1 + m-változós polinomot P -vel jelöljük. Így azt kell igazolnunk, hogy a következő n + 1-változós reláció diophantikus:

R = \{⟨\overline{x}, u⟩ ∈ ω^{n+1} : (∀v < u)(∃\overline{z} ≥ 0)P (\overline{x}, v, \overline{z}) = 0\}.

Legyen ⟨\overline{x}, u⟩ ∈ R tetszőleges de rögzített. Ekkor persze minden 0 ≤ v < u-hoz van olyan \overline{z} ∈ ω^{m}, melyre P (\overline{x}, v, \overline{z}) = 0, jelöljük az egyik ilyet \overline{z}^{(v)}-vel, és legyen z az összes \overline{z}^{(v)}-ben szereplő természetes szám mindegyikénél nagyobb. Vegyük ω^{m}-nek mindazokat a \overline{t} elemeit, melyekre \overline{t} < z, azaz \overline{t}-nak mind az m eleme kisebb z-nél, és legyen M olyan nagy, hogy v < u és \overline{t} < z esetén

|P (\overline{x}, v, \overline{t})| < M,

továbbá u < M és z < M is teljesül.

Ha most b_{0}, b_{1}, …, b_{u−1} páronként relatív prím, M-nél nagyobb egész, akkor a kínai maradéktétel értelmében van olyan c > 0 egész, melyre

c ≡ v (mod b_{v}) v = 0, 1, …, u − 1.

Továbbá ha \overline{z}^{(v)} elemeit z_{1}^{(v)}, z_{2}^{(v)}, …, z_{m}^{(v)} jelöli, akkor vannak olyan a_{1}, …, a_{m} pozitív számok is, hogy

a_{1} ≡ z_{1}^{(v)} (mod b_{v})  v = 0, 1, …, u − 1
…
a_{m} ≡ z_{m}^{(v)} (mod b_{v})  v = 0, 1, …, u − 1.

Ekkor természetesen P (\overline{x}, c, \overline{a}) ≡ P (\overline{x}, v, \overline{z}^{(v)} = 0 (mod b_{v}), ahol \overline{a} = ⟨a_{1}, …, a_{m}⟩, tehát a b_{0}·b_{1}· . . . ·b_{u−1} szorzatot s-sel jelölve

P (\overline{x}, c, \overline{a}) ≡ 0 (mod s).

Az a_{j} − z_{j}^{(v)} különbség osztható b_{v}-vel, a z_{1}(v), …, z_{m}^{(v)} mindegyike kisebb z-nél, ezért a ∏_{i<z}(a_{j} − i) szorzat osztható a relatív prím b_{v}-k szorzatával, s-sel is. Ezzel igazoltuk a következő lemma első felét:

9. Lemma⟨\overline{x}, u⟩ ∈ R akkor és csak akkor, ha vannak olyan M, z, s, c és a_{1}, …, a_{m} nem-negatív egészek, melyekre

(i)minden v < u és \overline{t} < z esetén |P (\overline{x}, v, \overline{t})| < M, továbbá 2u + 3 < M és z < M;

(ii)s felbontható u darab páronként relatív prím szám, b_{0}, …, b_{u−1} szorzatára úgy, hogy mindegyik tényezőnek van M-nél nagyobb prímosztója, továbbá minden v < u-ra c ≡ v (mod b_{v});

(iii)minden j = 1, …, m-re ∏_{i<z}(a_{j} − i) osztható s-sel;

(iv)P (\overline{x}, c, \overline{a}) ≡ 0 (mod s).

Bizonyítás. A fentebb mondottak értelmében elegendő a megfordítást igazolni. Legyen 0 ≤ v < u esetén p_{v} a b_{v}-nek M-nél nagyobb ((ii) szerint létező) prímosztója, és j = 1, 2, …, m-re z_{j}^{(v)} éppen a_{j}-nek p_{v}-vel való osztásakor adódó maradék, végül \overline{z}^{(v)} = ⟨z_{1}^{(v)}, …, z_{m}^{(v)}⟩. Ekkor (iv) alapján

P (\overline{x}, v, \overline{z}^{(v)}) ≡ 0 (mod p_{v})

hiszen p_{v} osztója s-nek és c ≡ v (mod b_{v}), ezért ez a kongruencia mod p_{v} is fennáll. (iii) szerint ∏_{i<z}(a_{j} − i) osztható b_{v}-vel, ezért p_{v}-vel is, tehát a_{j}-nek p_{v}-vel való osztásakor a maradék csak 0, 1, …, z − 1 közül kerülhet ki, vagyis z_{j}^{(v)} < z. Így (i) miatt

|P (\overline{x}, v, \overline{z}^{(v)})| < M < p_{v},

következésképp P (\overline{x}, v, \overline{z}^{(v)}) értéke csak nulla lehet.

Minden v < u-ra találtunk tehát olyan \overline{z} ≥ 0-t, amire P (\overline{x}, v, \overline{z}) = 0, így (\overline{x}, u) ∈ R, ahogyan kívántuk.

Könnyű olyan Q(\overline{x}, u, z) polinomot találni, hogy adott \overline{x} ∈ ω^{n}, u, z ∈ ω mellett minden 0 ≤ v < u és \overline{t} ∈ ω^{n}, \overline{t} < z esetén

|P (\overline{x}, v, \overline{t})| ≤ Q(\overline{x}, u, z)

legyen. Egyszerűen P -ben az összes együtthatót az abszolút értékével helyettesítjük, továbbá az utolsó m darab z_{1}, …, z_{m} változó mindegyikének a helyébe z-t írunk. Ekkor a lemma (i) feltétele az M = Q(\overline{x}, u, z) + 2u + z + 1 választással nyilván teljesül. (iv)-ről könyen látható, hogy diophantikus reláció, így elegendő (ii)-vel és (iii)-vel foglalkoznunk.

Az, hogy az (iii) alatti m darab reláció mindegyike diophantikus, azonnal következik abból, hogy az f(x) = x! faktoriális függvény diophantikus. Valóban, ∏_{i<z}(a − i) pontosan akkor osztható s-sel, ha (az (i) és (ii) szerint) pozitív tényezőkből álló

∏_{i<z}(a + s − i) = \frac{(a + s)!}{(a + s − z)!}

szorzat osztható s-sel, azaz ha van olyan q_{a} ≥ 0 egész, hogy

(a + s)! = q_{a}·s·(a + s − z)!.

Ez valóban diophantikus, ha x! az.

Végül (ii)-ben s-et és c-t is meg tudjuk diophantikus függvénnyel adni, ugyanilyen feltétel mellett. A

b_{v} = \frac{M! − v − 1}{v + 1} v = 0, …, u − 1

választással ugyanis a b_{v}-k szorzata

s = \frac{M! − 1}{1}·\frac{M! − 2}{2}· · · · ·\frac{M! − u}{u} = \binom{M! − 1}{u} = \frac{(M! − 1)!}{u!(M! − 1 − u)!}

és még b_{u−1} > M is teljesül, ha M > u + 3. Ha pedig

c = M! − 1

akkor c − v = M! − 1 − v valóban osztható b_{v}-vel. Így csak azt kell ellenőriznünk, hogy a b_{v} számok páronként relatív prímek, és mindegyiknek van M-nél nagyobb prímosztója. Legyen 0 ≤ i < j < u. Ha egy p prímszám osztója lenne b_{i}-nek és b_{j}-nek, akkor

p | b_{i} − b_{j} = \frac{M!(j − i)}{ij},

tehát M > u > j − i miatt p mindenképpen osztója lenne M!-nak is. Ezért p | b_{i} = \frac{M!}{i + 1} − 1 csak úgy lehet, ha p egyúttal (i + 1)-nek is osztója. De i + 1 ≤ u és 2u < M esetén p biztosan osztója lesz \frac{M!}{i + 1}-nek, tehát nem lehet osztója az ennél eggyel kisebb számnak, b_{i}-nek.

A fenti okoskodás egyúttal azt is adja, hogy b_{i}-nek egyátalán nincs M-nél kisebb prímosztója, tehát p_{i}-nek b_{i} tetszőleges prímosztója megfelelő.

10. LemmaHa az f(x) = x! függvény diophantikus, akkor az R reláció is az.

Bizonyítás. Az előzőek alapján ⟨\overline{x}, u⟩ ∈ R akkor és csak akkor, ha vannak olyan M, z, x, c ∈ ω és \overline{a} ∈ ω^{m} egészek, melyekre

(i)M = Q(\overline{x}, u, z) + 2u + z + 4;

(ii)s = \binom{M! − 1}{u} = \frac{(M! − 1)!}{u!(M! − 1 − u)!}, c = M! − 1;

(iii)minden j = 1, 2, …, m-re s | \frac{(a_{j} + s)!}{(a_{j} + s − z)!};

(iv)P (\overline{x}, c, \overline{a}) ≡ 0 (mod s).

Mivel ezen relációk mindegyike diophantikus a mondott feltétel mellett, a lemma állítását beláttuk.

Ezek után elegendő egyetlen függvényről, nevezetesen az x! függvényről igazolnuk, hogy diophantikus, ebből már következik, hogy minden parciálisan rekurzív függvény is az. Ehhez először igazoljuk, hogy ha a g(x, y) = x^{y} hatványfüggvény diophantikus, akkor a faktoriális függvény is az, majd egy speciális típusú Pell-egyenlet vizsgálata után a hatványfüggvényről is belátjuk, hogy diophantikus.

11. LemmaHa a hatványfüggvény diophantikus, akkor a faktoriális függvény is az.

Bizonyítás. Állítjuk, hogy y = k! akkor és csak akkor, ha vagy k = 0 és y = 1, vagy ha vannak olyan n, u, a és b ∈ ω értékek, hogy

k ≥ 1, n = k^{2}·(2k)^{k} +1, u = 2^{n} +1;
a·y ≤ n^{k} < a·(y + 1)  (azaz y = [\frac{n^{k}}{a}]);
b·u^{k} ≤ (u + 1)^{n} < (b + 1)·u^{k}  (azaz b = [\frac{(u + 1)^{n}}{u^{k}}]);
a < u, u | b − a

(azaz b-nek u-val való osztásakor adódó maradék éppen a).

Ezek a relációk nyilván mind diophantikusak, ha a g(x, y) = x^{y} az.

Mivel k értéke egyértelműen meghatározza n-et és az u-t, továbbá ezek b-t, b és u a-t, végül n, k, és a értéke y-t, azért ezeket a feltételeket pontosan egy y elégíti ki. Elegendő tehát megmutatnunk, hogy y = k!-ra a feltételek kielégíthetők.

Először is a binomiális tétel alapján

\frac{(u + 1)^{n}}{u^{k}} = ∑_{i>k} \binom{n}{i}u^{i−k} + \binom{n}{k} + ∑_{i<k} \binom{n}{i}u^{i−k}.

Az u = 2^{n} + 1 > 2^{n} feltételből azonnal adódik, hogy az összeg harmadik tagja 1-nél kisebb, az első szumma mindegyik tagja osztható u-val és u > 2^{n} ≥ \binom{n}{k}, ezért (u + 1)^{n}/u^{k} egész részét u-val osztva a maradék éppen \binom{n}{k}, tehát a = \binom{n}{k}. Így elegendő megmutatnunk, hogy n = k^{2}·(2k)^{k} + 1 > k^{2}·(2k)^{k} esetén

k! = [\frac{n^{k}}{\binom{n}{k}}].

Ennek bizonyításához először megjegyezzük, hogy 0 < α < 1 és k ≥ 1 esetén (1 − α)^{k} ≥ 1 − k·α, tehát

(1 − \frac{k}{n})^{k} ≥ 1 − \frac{k^{2}}{n} > 1 − \frac{1}{(2k)^{k}} = 1 − (\frac{1}{k} − \frac{1}{2k} )^{k} > 1 − (\frac{1}{k} − \frac{1}{n})^{k},

és így

1 < (1 − \frac{k}{n})^{k} + (\frac{1}{k} − \frac{1}{n})^{k} = (1 − \frac{k}{n})^{k}(1 + \frac{1}{k^{k}} ).

Ezek után

k! ≤ k!\frac{n^{k}}{n(n − 1) … (n − k + 1)} = \frac{n^{k}}{\binom{n}{k}} < k!(\frac{n}{n − k} )^{k} = k!\frac{1}{(1 − \frac{k}{n})^{k}} < k!(1 + \frac{1}{k^{k}} ) ≤ k! + 1

ahogyan állítottuk.

A hátralevő részben azt bizonyítjuk be, hogy a hatványfüggvény diophantikus. Ezt egy speciális típusú Pell-egyenlet vizsgálatával kezdjük.

Legyen a egynél nagyobb egész, és d = a^{2} − 1. (a + \sqrt{d})(a − \sqrt{d}) = 1 miatt (a + \sqrt{d})^{n} = (a − \sqrt{d})^{−n}, így minden n egész számra egyértelműen találhatók olyan x_{a}(n) és y_{a}(n) egész számok, hogy

(a + \sqrt{d})^{n} = x_{a}(n) + y_{a}(n)\sqrt{d}, (1)

és ekkor persze (a − \sqrt{d})^{n} = x_{a}(n) − y_{a}(n)\sqrt{d}. (2)

Speciálisan x_{a}(0) = 1, y_{a}(0) = 0, x_{a}(1) = a, y_{a}(1) = 1, továbbá n > 0 esetén x_{a}(n) és y_{a}(n) pozitívak, x_{a}(n) = x_{a}(−n) valamint y_{a}(n) = −y_{a}(−n). Mivel (a + \sqrt{d})^{n+m} = (a + \sqrt{d})^{n}·(a + \sqrt{d})^{m}, (1)-ből azonnal adódik, hogy

\begin{matrix}x_{a}(n + m) = & x_{a}(m)x_{a}(n) + d·y_{a}(m)y_{a}(n) \\ y_{a}(n + m) = & x_{a}(m)y_{a}(n) + x_{a}(n)y_{a}(m). \end{matrix} (3)

Ezeket m = ±1-re felírva és páronként összeadva

\begin{matrix}x_{a}(n + 1) + x_{a}(n − 1) = 2ax_{a}(n) \\ y_{a}(n + 1) + y_{a}(n − 1) = 2ay_{a}(n), \end{matrix} (4)

tehát az {x_{a}(n)} és {y_{a}(n)} sorozatok kielégítik az

r_{n+1} = 2ar_{n} − r_{n−1}

rekurziót. (3)-ban m = 1-et téve

\begin{matrix}x_{a}(n + 1) = & ax_{a}(n) + dy_{a}(n) \\ y_{a}(n + 1) = & ay_{a}(n) + x_{a}(n) \end{matrix}

adódik. Így n ≥ 0-ra mind x_{a}(n) mind y_{a}(n) n-ben szigorúan monoton nő, továbbá n ≥ 1-re

\begin{matrix}\frac{(2a − 1)^{n}}{2} < & x_{a}(n) ≤ \frac{(2a)^{n}}{2} , \\ (2a − 1)^{n−1} ≤ & y_{a}(n) ≤ (2a)^{n−1}, \end{matrix} (5)

ez szimultán rekurzióval egyszerűen látható.

12. TételAz x^{2}−dy^{2} = 1 Pell-egyenlet nem-negatív megoldásai pontosan az ⟨x_{a}(n), y_{a}(n)⟩ párok n ≥ 0ra.

Bizonyítás. Az (1) és (2) összefüggéseket összeszorozva

x_{a}(n)^{2} − d·y_{a}(n)^{2} = 1,

vagyis ⟨x_{a}(n), y_{a}(n)⟩ valóban megoldás. Legyen most ⟨x, y⟩ a Pell egyenletnek ezektől különböző, nemnegatív egészekből álló megoldása, továbbá legyen n ≥ 0 olyan, hogy

(a + \sqrt{d})^{n} ≤ x + y\sqrt{d} < (a + \sqrt{d})^{n+1}.

Itt egyenlőség nem állhat, mert akkor x = x_{a}(n) és y = y_{a}(n) volna. Legyenek x′ és y′ olyan egészek, hogy

x′ + y′\sqrt{d} = \frac{x + y\sqrt{d}}{(a + \sqrt{d})^{n}} = (x + y\sqrt{d})(a + \sqrt{d})^{−n} = (x + y\sqrt{d})(x_{a}(n) − y_{a}(n)\sqrt{d}).

Ekkor 1 < x′ + y′\sqrt{d} < a + \sqrt{d}, és könnyen ellenőrizhető, hogy x^{′2} − dy^{′2} = 1. Megmutatjuk, hogy ez lehetetlen. Valóban,

(x′ + y′\sqrt{d})(x′ − y′\sqrt{d}) = 1,

és itt mindkét tényező pozitív (hiszen az első még 1-nél is nagyobb), tehát a reciprokokat véve 1 > x′ − y′\sqrt{d} > (a + \sqrt{d})^{−1} = a − \sqrt{d}, azaz

−1 < −x′ + y′\sqrt{d} < −a + \sqrt{d}.

Ezt a fenti 1 < x′ + y′\sqrt{d} < a + \sqrt{d} egyenlőtlenséghez hozzáadva 0 < 2y′\sqrt{d} < 2\sqrt{d}, azaz 0 < y′ < 1 adódik, ami lehetetlen, hiszen y′ egész.

A továbbiakban a megoldások oszthatósági viszonyait vizsgáljuk. Először is megállapítjuk, hogy x_{a}(n) és y_{a}(n) relatív prímek minden n-re, hiszen ha b osztója mindkettőnek, akkor osztója x_{a}(n)^{2} − dy_{a}(n)^{2} = 1-nek is, tehát b = 1.

13. Lemmay_{a}(m) | y_{a}(n) akkor és csak akkor, ha m | n.

Bizonyítás. (3) alapján

y_{a}(n − m) = x_{a}(m)y_{a}(n) − x_{a}(n)y_{a}(m),

ezért y_{a}(m) és y_{a}(n) legnagyobb közös osztója egyúttal osztója y_{a}(n − m)-nek is. Másrészt y_{a}(m) és x_{a}(m) relatív prímek, így az y_{a}(n − m) és y_{a}(m) legnagyobb közös osztója osztója y_{a}(n)-nek, tehát

lnko(y_{a}(m), y_{a}(n)) = lnko(y_{a}(n − m), y_{a}(n)).

Innen az euklídeszi algoritmus alapján y_{a}(0) = 0 miatt

lnko(y_{a}(m), y_{a}(n)) = y_{a}(lnko(m, n)),

amiből a lemma állítása következik.

14. Lemmay_{a}(i)^{2} | y_{a}(i·k) akkor és csak akkor, ha y_{a}(i) | k.

Bizonyítás. Először is megjegyezzük, hogy

x_{a}(i·k) + y_{a}(i·k)\sqrt{d} = (a + \sqrt{d})^{i·k} = (x_{a}(i) + y_{a}(i)\sqrt{d})^{k}.

Ennek alapján a binomiális tételből

y_{a}(i·k) = \binom{k}{1}y_{a}(i)x_{a}(i)^{k−1} + \binom{k}{3}d·y_{a}(i)^{3}x_{a}(i)^{k−3} + …,

és így

y_{a}(i·k) ≡ k·y_{a}(i)x_{a}(i)^{k−1} (mod y_{a}(i)^{3}).

Innen a lemma “csak akkor” része közvetlenül adódik.

A fordított irányú implikáció bizonyításához tegyük fel, hogy y_{a}(i)^{2} | y_{a}(i·k). A fenti kongruencia alapján ekkor k·y_{a}(i)x_{a}(i)^{k−1} is osztható y_{a}(i)^{2}-tel, ami x_{a}(i) és y_{a}(i) relatív prím volta miatt az jelenti, hogy y_{a}(i) osztója k-nak.

15. LemmaTegyük fel, hogy x_{a}(i) ≡ x_{a}(j) (mod x_{a}(n)). Ekkor vagy i ≡ j (mod 4n), vagy i ≡ −j (mod 4n).

Bizonyítás. A (3) összefüggés szerint

x_{a}(m + n) + x_{a}(m − n) = 2x_{a}(n)x_{a}(m),

hiszen x_{a}(n) = x_{a}(−n) és y_{a}(n) = −y_{a}(−n). Ennek alapján

x_{a}(j) = x_{a}((j − n) + n) ≡ −x_{a}((j − n) − n) = −x_{a}(j − 2n) (mod x_{a}(n)),

és így

x_{a}(j) ≡ −x_{a}(j − 2n) ≡ x_{a}(j − 4n) (mod x_{a}(n)).

Feltehetjük tehát, hogy 0 ≤ i, j < 4n. Továbbá ugyancsak a fentiek miatt

x_{a}(i) ≡ −x_{a}(2n − i) ≡ −x_{a}(2n + i) ≡ x_{a}(4n − i) (mod x_{a}(n)),

továbbá

x_{a}(0) ≡ 1, x_{a}(n) ≡ 0, x_{a}(2n) ≡ −1, x_{a}(3n) ≡ 0 (mod x_{a}(n)).

Ha most még azt is tudjuk, hogy x_{a}(n − 1) < \frac{1}{2}x_{a}(n), akkor készen vagyunk. Az x_{a}(n) sorozat ugyanis szigorúan monoton nő n ≥ 0-ra, és így

1 = x_{a}(0) < x_{a}(1) < … < x_{a}(n − 1) < \frac{1}{2}x_{a}(n) < x_{a}(n) − x_{a}(n − 1) < … < x_{a}(n) − x_{a}(0) < x_{a}(n),

tehát az x_{a}(0), …, x_{a}(2n) számok mind különböző maradékot adnak x_{a}(n)-nel osztva. Következésképp a 0 ≤ j < 4n intervallumon az 1-et és −1-et kivéve minden maradék pontosan kétszer fordul elő: egyszer j-re, másszor 4n − j-re. Így ha 0 ≤ i, j < 4n, továbbá x_{a}(i) ≡ x_{a}(j) (mod x_{a}(n)), akkor vagy i = j vagy i = 4n − j, ahogyan állítottuk.

A (3) összefüggés szerint

x_{a}(n) = a·x_{a}(n − 1) + d·y_{a}(n − 1),

ezért

\frac{1}{2}x_{a}(n) ≥ \frac{1}{a}x_{a}(n) = x_{a}(n − 1) + \frac{d}{a}y_{a}(n − 1) > x_{a}(n − 1),

hiszen n ≥ 2 és ezért y_{a}(n − 1) > 0. Ezzel a lemmát beláttuk.

16. LemmaLegyenek a, b egynél nagyobb egészek, és a ≡ b (mod c) Ekkor x_{a}(n) ≡ x_{b}(n) (mod c) minden n ≥ 0-ra.

Bizonyítás. Az állítás igazsága n = 0-ra és n = 1-re közvetlenül ellenőrizhető. Nagyobb n-ekre a (4)-ből adódó

x_{a}(n + 1) = 2ax_{a}(n) − x_{a}(n − 1)

rekurzív összefüggés alapján teljes indukcióval bizonyítható.

17. Lemmay_{a}(n) ≡ n (mod a − 1).

Bizonyítás. Az y_{a}(n + 1) = 2ay_{a}(n) − y_{a}(n − 1) = (2a − 2)y_{a}(n) + 2y_{a}(n) − y_{a}(n − 1) összefüggés alapján teljes inducióval.

18. TételAz y_{a}(k) kétváltozós függvény diophantikus.

Bizonyítás. Megmutatjuk, hogy a ≥ 1 és k ≥ 1 esetén y = y_{a}(k) akkor és csak akkor igaz, ha vannak olyan b, u, v, s, t és x nem-negatív egész számok, melyekre a következő tizenegy diophantikus reláció mindegyike teljesül:

(i)x^{2} − (a^{2} − 1)y^{2} = 1, u^{2} − (a^{2} − 1)v^{2} = 1, s^{2} − (b^{2} − 1)t^{2} = 1;

(ii)0 ≤ v, k ≤ y, 1 < b;

(iii)4y | b − 1, y^{2} | v;

(iv)a ≡ b (mod u), x ≡ s (mod u), t ≡ k (mod b − 1).

Ezzel az állítást nyilván beláttuk, hiszen a hiányzó a ≤ 1 illetve k = 0 esetekben a függvényt könnyű diophantikus relációkkal definiálni.

Elsőként tegyük fel, hogy y = y_{a}(k), és keressünk olyan b, u, v, a, t és x értékeket, amikre az összes reláció fennáll.

Legyen n = 2ky_{a}(k), továbbá x = x_{a}(k), u = x_{a}(n), v = y_{a}(n), a = x_{b}(k), t = y_{b}(k). Ezekkel a választásokkal (i) mindhárom egyenlőtlensége teljesül. Feltételünk szerint k ≥ 1, ezért n ≥ 2, tehát 0 < y_{a}(n) = v, és k = y_{a}(k) = y is teljesül. Mivel y_{a}(k) | n, azért a 14. lemma alapján y_{a}(k)^{2} | y_{a}(n), tehát y^{2} | v.

A b-t úgy kell megválasztanunk, hogy egyrészt b ≡ 1 (mod 4y), másrészt b ≡ a (mod u) legyen. Ilyen b biztosan van (mégpedig akármilyen nagy is), ha 4y és u relatív prímek. De egyrészt y_{a}(n) páros, hiszen n páros, és (3) alapján

y_{a}(2m) = 2y_{a}(m)x_{a}(m);

másrészt k | n és így az 13. lemma miatt y_{a}(k) | y_{a}(n). Ezért 4y = 4y_{a}(k) minden prímosztója osztója y_{a}(n)-nek is, y_{a}(n) és x_{a}(n) = u relatív prímek, tehát 4y-nak és u-nak nincs közös prímosztója — valóban relatív prímek. Miután b > 1-et így megválasztottuk, a 16. lemma alapján x_{a}(k) ≡ x_{b}(k) (mod u), vagyis x ≡ s (mod u), amivel (iv) második kongruenciáját is beláttuk. Végül az 17. lemma alapján t = y_{b}(k) ≡ k (mod b − 1).

Fordítva, tegyük fel, hogy a > 1, k ≥ 1, és vannak a (i)–(iv) relációkat kielégítő b, u, v, s, t, x és y természetes számok, azt akarjuk belátni, hogy y = y_{a}(k).

Mivel a, b > 1, az ⟨x, y⟩, ⟨u, v⟩ és ⟨s, t⟩ párok megoldásai egy–egy Pell-egyenletnek, tehát vannak olyan i, j és n nem-negatív egészek, hogy

x = x_{a}(i), y = y_{a}(i), u = x_{a}(n), v = y_{a}(n), s = x_{b}(j), t = y_{b}(j),

és azt szeretnénk belátni, hogy i = k. A k ≤ y feltétel miatt y = y_{a}(i) ≠ 0, így i > 0, továbbá v = y_{a}(n) > 0 és ezért n > 0 is áll. y^{2} | v, ahonnan v ≠ 0 miatt y ≤ v. Ha most n = 1, akkor v = y_{a}(1) = 1 és k ≤ y − y_{a}(i) ≤ v alapján k = i = 1. Így feltehetjük, hogy n ≥ 2, amikor is v = y_{a}(n) > 2. Ekkor az y^{2} | v feltételből y = y_{a}(i) < v = y_{a}(n), tehát i < n.

Tudjuk, hogy a ≡ b (mod u), így alkalmazhatjuk a 16. lemmát:

x_{a}(j) ≡ x_{b}(j) = s ≡ x − x_{a}(i) (mod u).

Most u = x_{a}(n), 0 < i < n, tehát a 15. lemma alapján

j ≡ ±i (mod 4n)

valamelyik előjellel. Tudjuk azt is, hogy y^{2} = y_{a}(i)^{2} osztója v = y_{a}(n)-nek, ezért a 14. lemma szerint y | n, tehát

j ≡ ±i (mod 4y)

valamilyen előjellel.

Az 17. lemma és (iv) harmadik kongruenciája szerint

k ≡ t = y_{b}(j) ≡ j (mod b − 1)

és mivel 4y | b − 1, azért

k ≡ j (mod 4y).

Végül is azt kaptuk, hogy k ≡ ±i (mod 4y) valamilyen előjellel, i ≤ y_{a}(i) = y, továbbá a (ii) feltétel miatt k ≤ y, így ez a kongruencia csak úgy állhat fönn, ha k = i és ezt akartuk bizonyítani.

Lényegében elérkeztünk célunkhoz: minden rendelkezésünkre áll ahhoz, hogy igazoljuk: a hatványfüggvény diophantikus.

19. TételAz n^{k} kétváltozós függvény diophantikus.

Bizonyítás. Elegendő azzal az esettel foglalkoznunk, mikor n és k is legalább kettő. Állítjuk, hogy ilyen feltételek mellett y = n^{k} akkor és csak akkor, ha vannak olyan i, p, q természetes számok, hogy

i = 1 + 2k·y_{n}(k + 1),

p = y_{i·n}(k + 1),
q = y_{i}(k + 1),
4(p − yq)^{2} < q^{2}  (azaz |y − \frac{p}{q}| < \frac{1}{2}).

Az előző tétel szerint ezek mind diophantikus relációk, így ha ezt igazoljuk, készen vagyunk.

Az n és k értékek egyértelműen meghatározzák i, p és q értékét, és legfeljebb egy olyan y van, amire |y − \frac{p}{q}| < \frac{1}{2}. Következésképp elég megmutatni, hogy az y = n^{k} teljesíti ezt a feltételt.

Korábban (5) alatt láttuk, hogy minden k ≥ 0-ra

(2a − 1)^{k} ≤ y_{a}(k + 1) ≤ (2a)^{k}.

Ezért egyrészt

\frac{p}{q} ≤ \frac{(2in)^{k}}{(2i − 1)^{k}} = n^{k}(1 − \frac{1}{2i})^{−k} ≤ n^{k}(1 − \frac{k}{2i})^{−1} = n^{k}(1 + \frac{k}{2i − k} ) < n^{k} + \frac{kn^{k}}{i} .

Itt felhasználtuk, hogy 0 < α < 1 és k ≥ 1 esetén (1 − α)^{k} ≥ 1 − αk, valamint hogy i ≥ 1 + k. Másrészt

\frac{p}{q} ≥ \frac{(2in − 1)^{k}}{(2i)^{k}} = n^{k}(1 − \frac{1}{2in})^{k} ≥ n^{k}(1 − \frac{k}{2in}) = n^{k} − \frac{kn^{k}}{2in} .

Így

−\frac{kn^{k}}{i} < n^{k} − \frac{p}{q} ≤ \frac{kn^{k}}{2in} .

Ám i definíciója alapján i = 1 + 2k·y_{n}(k + 1) ≥ 1 + 2k·(2n − 1)^{k} > 2kn^{k}, tehát a bal és jobb oldalak abszolút értéke egyaránt kisebb 1/2-nél:

|n^{k} − \frac{p}{q}| < \frac{1}{2},

amit bizonyítani akartunk.

Feladatok 1.Bizonyítsuk be, hogy egy R reláció akkor és csak akkor rekurzíve felsorolható, ha van olyan p polinom, melynek az egész helyeken felvett értékei közül a nem-negatívak éppen R elemeit adják ki. Speciálisan van olyan polinom, melynek a pozitív értékei éppen a prímek. 2.Mutassuk meg, hogy olyan eljárás sincs, mely tetszőleges egész együtthatós polinomról eldöntené, hogy van-e egészekből álló megoldása. 3.Bizonyítsuk be, hogy van olyan polinom, melynek akkor és csak akkor nincs egész megoldása, ha a Fermat-sejtés igaz. (Ugyanez a Rieman sejtésre.) 4.Igazoljuk, hogy minden n ≥ 4-re van n-edfokú univerzális polinom. 5.Igazoljuk, hogy nincs olyan algoritmus, ami eldöntené, hogy egy polinomnak van-e legalább 100 egész megoldása. 6.Van-e olyan polinom, aminek nincs egészekből álló megoldása, de ezt a tényt nem tudjuk igazolni?