Eötvös Loránd Tudományegyetem Természettudományi Kar
Fazekas Karen Krisztina
Ramanujan Matematika Bsc szakdolgozat
Témavezet®:
Dr. Freud Róbert Algebra és Számelmélet Tanszék
Budapest, 2015
Köszönetnyilvánítás Szeretném megköszönni témavezet®mnek, Freud Róbertnek, hogy elvállalta a konzulensi teend®ket, mindig rendelkezésemre állt, és megjegyzéseivel a tökéletességre ösztönzött. Köszönettel tartozom még családomnak, barátomnak, barátaimnak a lelki támogatásért, hogy hozzájárultak a munkám sikerességéhez, és f®leg Csanády
A
Bálintnak a L TEX-ban nyújtott segítségéért.
2
Tartalomjegyzék Bevezetés
4
1. Életrajzi összefoglaló
5
2. Partíciószámok
7
2.1.
De níciók és vizsgálati módszerek . . . . . . . . . . . . . . . . . .
2.2.
Konkrét egyenlet megoldása hatványsorokkal
. . . . . . . . . . .
3. Kerek számok
7 13
18
4. Négyzetszámokkal való el®állítás 4.1.
Négyzetszámokkal való el®állítás
4.2.
Waring-problémakör
24 . . . . . . . . . . . . . . . . . .
24
. . . . . . . . . . . . . . . . . . . . . . . . .
28
5. Érdekességek
29
5.1.
Ramanujan kongruenciák
. . . . . . . . . . . . . . . . . . . . . .
29
5.2.
Rogers-Ramanujan azonosságok . . . . . . . . . . . . . . . . . . .
32
Irodalomjegyzék
34
3
Bevezetés Szakdolgozatom kiindulási pontját egy indiai matematikus, Ramanujan munkássága adta, ezen belül is Hardynak a róla szóló el®adásai, a Tizenkét el®adás, aminek a témáját az élete és a munkássága ajánlotta [1] . Dolgozatom célja az volt, hogy Ramanujan érdemekben b®velked® munkásságát és egyedi gondolkodásmódját néhány példán keresztül bemutassam. Az életrajzi összefoglalóban életének olyan elemeit mutattam meg, amelyek szerepet játszhattak a munka[1] [2] módszerének a kialakulásában. Ez Hardy el®adásai és a Prímszámok zenéje alapján készült. A Partíciószámok els® részében a Nagy pillanatok a matematika történetében [3] és a Számelmélet [4] alapján foglaltam össze a partíciószámokkal kapcsolatos alapfogalmakat és vizsgálati módszereket néhány általam megoldott feladat és példa mellett. A második részben a [3] által alkalmazott analízises ötlet felhasználásával oldottam meg egy másik példát, illetve ugyanezt számelméleti eszközökkel is, majd összevetettem a két eredményt. A Kerek számok cím¶ fejezetben Hardy és a
Számelmélet alapján dolgoz-
tam, összevegyítve Hardy leírási módját a valószín¶ségszámítási gondolatokkal, kib®vítve plusz lépésekkel és példákkal. A negyedik fejezetben szintén az el®z® két könyvet használtam, kiegészítve saját megfontolással és feladatmegoldással. Az utolsó fejezetben folytattam a Partíciószámok c. fejezetben elkezdett hat-
p(7m + 5) ≡ 0 (mod 7) kongruenciát. p(5m + 4) ≡ 0 (mod 5) kongruencia bizonyítása szerepelt,
ványsoros irányvonalat, és beláttam a Hardy könyvében a
és ez alapján készítettem el a dolgozatban ismertetettet. A fejezet folytatása némi kitekintés Ramanujan további kongruenciáira és a Rogers-Ramanujan formulák kombinatorikai vonatkozására.
4
1. fejezet
Életrajzi összefoglaló Srinivasa Ramanujan 1887. december 22-én született, egy Erode nev¶ indiai kisvárosban, meglehet®sen szegény családban. Matematikában való tehetsége már 10 évesen megmutatkozott, többek között a trigonometria tanulmányainak kezdetén felfedezte a
eix = cos(x) + i sin(x)
azonosságot. Mélységesen csalódott
volt, amikor megtudta, hogy Euler erre már jóval el®tte rájött. Azonban tizenhat éves koráig semmilyen komolyabb matematikával foglalkozó könyvet nem látott, csak Carl
A tiszta és alkalmazott matematika elemi eredményeinek áttekintése
cím¶ m¶vét. Ennek az lett az egyik következménye, hogy Ramanujan életének egy jelent®s részét tételek újrafelfedezésével töltötte. A másik problémát meg az jelentette, hogy ebben a könyvben a tételek bizonyítás nélkül szerepeltek, így Ramanujan nem kapott pontos képet arról, hogyan kell precízen leírni egy bizonyítást. Élete végéig küzdött azzal a problémával, hogy ® megelégedett annyival, ha valamilyen heurisztikus gondolatsorral önmagát meg tudta gy®zni, és nem tör®dött a részletekkel. Ezen kívül innen eredhet Ramanujan vonzódása a szép formulákhoz, amire remek példát láthatunk a Partíciószámok cím¶ fejezetben. Ösztöndíjjal jutott be egy nagyon jó college-ba (ami a mai középiskolának felel meg), de a nem matematikával foglalkozó tárgyain sorra megbukott, és végül sem ezt, sem egy másik iskolát nem tudott befejezni. Már ekkor is a híressé vált noteszébe jegyezte le felfedezéseit, természetesen magyarázat és bizonyítás nélkül. Mivel 1909-ben megházasodott (felesége ekkor volt 9 éves), ezért állandó állás után kellett néznie. Hosszas keresgélés után végül egy kiköt®ben lett hivatalnok, nem túl nagy zetésért. Sorra küldte a jegyzeteit az indiai professzoroknak, akik nem értettek bel®le egy szót se, többek között a téma újszer¶sége és Ramanujan hiányos leírói stílusa miatt. Mikor kifogyott az indiai matematikusokból, Ramanujan úgy döntött, hogy az angolokkal folytatja. Végül 1913-ban sikerült Hardyhoz eljuttatni egy levelet, melyben kb. 120 képlet volt felsorolva az eredményeir®l, és segítséget kért a publikálásukhoz, ha Hardy lát benne fantáziát. A levélben szerepelt az az állítás is, hogy
1 + 2 + 3 + 4 + ... = −
1 , 12
amir®l egy laikus is rögtön tudja, hogy képtelenség. A vegyes helyesség¶ felhozatal ellenére Hardy rájött, hogy zseniális elmével van dolga, és pár levélváltás után kiharcoltak neki egy zetésemelést, majd kérték, hogy küldje el a formulák bizonyítását is. Miután Ramanujan rávilágított arra, hogy azok meglehet®sen
5
vázlatosak, rá akarták venni, hogy menjen Angliába dolgozni. Ismert viszont, hogy Ramanujan neveltetéséb®l adódóan vallásos volt, így ódzkodott az utazástól, mivel ez a kasztjából való kirekesztést is jelenthette. Vallásossága miatt élete végéig ragaszkodott a vegetáriánus étrendhez, és meggy®z®dése volt, hogy egy Namagiri nev¶ házi istenségt®l kapja az ihletet. Végül ugyanez a házi istenség adott engedélyt arra is, hogy Angliába menjen, ahol már minden adott volt ahhoz, hogy nyugodtan dolgozzon. A napjait az el®adások látogatása, a munka és a Hardyval való eszmecsere töltötte ki. A szerény koszt és az angliai id®járás miatt 1917-ben tüd®vészt kapott, mély depresszió kínozta, így 1919-ben hazautazott. Igyekeztek neki egy indiai professzori állást találni, de 1920-ban felülkerekedett rajta a betegsége. Az újrafelfedezésekkel töltött hosszas id® és korai halála ellenére is nagyon termékeny matematikus volt, kb. 3-4 ezer tétel ®rzi a nevét. Ramanujan intuíciója és a nyugati analízis kombinációja nagyon sikeresnek bizonyult, Hardyval való közös munkáját jól szemlélteti a Kerek számok cím¶ fejezetben említett Hardy-Ramanujan tétel. Angliába jövetele után is csak óvatosan formálták a munkamódszereit, mert attól féltek, hogy elvész az a képessége, ami miatt ilyen jól megsejti a tételeit, azonban pár év elteltével már meg tudta mondani, hogy be tud-e valamit bizonyítani, vagy sem. Hardy állítása szerint ® többet tanult Ramanujantól, mint Ramanujan ®t®le. Ezek alapján talán érthet® a kijelentés, miszerint kortársai Eulerhez és Jacobihoz hasonlították. Littlewood, szintén angol matematikus, azt mondta Ramanujanról, hogy neki minden szám személyes jó barátja. Ezt szemlélteti a következ® történet is, aminek más változata is él a köztudatban. Hardy éppen Ramanujant látogatta meg, amikor betegen feküdt a kórházban, és beszélgetés közben megemlítette, hogy az 1729-es taxival érkezett, ami egy meglehet®sen unalmas szám. Ramanujan erre azt válaszolta, hogy ez egyáltalán nem unalmas, hiszen ez az els® olyan szám, ami felírható mint két-két különböz® köbszám összege:
1729 = 103 + 93 = 13 + 123 . Hardy megkérdezte, tud-e bizonyítást adni arra, hogy tényleg ez a legkisebb, mire Ramanujan azt felelte, hogy nem tud mondani ellenpéldát, és azt gondolja, az els® ilyen tulajdonságú számnak elég nagynak kell lennie. Ezt a megállapítását kés®bb megtalálták egy korábbi feljegyzésében. Azt hihetnénk ezek alapján, hogy Ramanujan jó fejszámoló volt, ellenben beszámolók alapján úgy végezte a m¶veleteket, mint az iskolás gyerekek. Újrafelfedezései között szerepelnek az Érdekességek cím¶ fejezetben említett Rogers-Ramanujan azonosságok, a Prímszámtétel, illetve a Négyzetszámokkal való el®állítás cím¶ fejezetben említett Két-, illetve Három-négyzetszám tétel. Az utóbbinál azonban meg kell jegyeznünk, hogy azt könnyebb megsejteni, mint bizonyítani, és az utóbbival Ramanujan nem rendelkezett. Érdekesség az is, hogy hiányos függvényanalízis tudása ellenére félreismerhetetlenül megtalálható korai jegyzetei között a Riemann-féle zéta függvény is, bár a vele kapcsolatos bizonyítások helytelenek voltak. Hardy szavaival zárnám az életrajzot: "Egy matematikust nem lehet megítélni a hibái vagy az újrafelfedezései alapján, csakis az eredeti és tényleges eredményei szerint", és szerencsénkre Ramanujan ebben b®velkedett.
6
2. fejezet
Partíciószámok 2.1. De níciók és vizsgálati módszerek Ramanujan egyik legnagyobb érdeme az, hogy Hardyval közösen megalkották a partíciószámok képletét. Ez, furcsa módon, egy hibás állítása kapcsán jött létre, amit a Hardynak írt els® levelében említett meg, és végül Angliában sikerült részletesen kitárgyalniuk. Ez a levél, amit már a bevezet®ben is említettem, körülbelül 120 képletet tartalmazott, köztük olyanokat, amelyeket mások már korábban beláttak, olyanokat, amelyeket eddig még senki, és olyanokat, amelyek helytelen voltak. Ez a képlet is az egyik helytelen formula volt, ami mutatja Ramanujan korlátait, de a belátására alkalmazott újszer¶ gondolat alkalmas volt a képlet megalkotására. Ez is remek példa volt arra, hogy Ramanujan ötletei és a fejlett nyugati analízis kombinációja jelent®s eredményekre vezetett. El®ször szükség lesz arra, hogy néhány fogalmat és gondolatot de niáljunk.
2.1.1. De níció. Az n pozitív egész partícióin az n-nek pozitív egészek összegeként történ® különböz® el®állításait értjük, ahol azonosnak tekintjük a csak az összeadandók sorrendjében különböz® el®állításokat. Itt lehet az összeg egytagú is. Az
n
partícióinak számát
p(n)-nel jelöljük. Tehát a 4 partíciói a következ®k:
4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1. Eszerint a példa alapján
p(4) = 5.
Érdemes megjegyezni, hogy a
(2.1)
p(0) = 1
de níció van általánosan érvényben. A partíciószámok vizsgálatát néha érdemes úgy tekinteni, hogy a partíciószámok egy megfelel®en megválasztott egyenlet megoldásai. Ennek a megértéséhez tekintsük az alábbi pénzki zetési problémát: egy
n érték¶ összeget hányfélekép-
pen lehet ki zetni 5, 10, 20, 50, 100 és 200 forintos érmék segítségével. Ha a szükséges érmék számát rendre
x1 , x2 , . . . , x6
jelöli, ahol
xi -k nemnegatív egész
számok, akkor a ki zetések az alábbi egyenlet megoldásai:
5x1 + 10x2 + 20x3 + 50x4 + 100x5 + 200x6 = n Ezt a feladatot általánosíthatjuk adott
b1 , b2 , . . . , bk
(2.2)
különböz®, pozitív egész
számokra a pénzérmék helyett. Ekkor a
b1 x1 + b2 x2 + b3 x3 + ... + bk xk = n 7
(2.3)
egyenletet vizsgáljuk. Tekintsük oldásainak a számát
Pk (n)-nel,
n-t változónak, és jelöljük a fenti egyenlet megbi -kt®l is.
ami természetesen függ a
A feladat egy érdekes átfogalmazása Eulert®l származik Ehhez alkalmaznunk kell a mértani sor összegképletét minden
bi -re:
1 = 1 + x1·bi + x2·bi + ... + xk·bi + ... 1 − xbi ahol
|xbi | <
(2.4)
1. Ekkor
g(x) =
1 (1 − xb1 )(1 − xb2 )...(1 − xbk )
esetén (2.4) alkalmazásával azt kapjuk, hogy
g(x)
(2.5)
el®áll, mint
xb1 x1 +...+bk xk
(2.6)
alakú számok lineáris kombinációja. A szorzást úgy végeztük el, ahogy több tagot több taggal szokás, ami helyes, mert itt abszolút konvergens sorokról van szó. Ez azért átfogalmazása az el®z® példának, mert ha azt nézzük, hogy rögzített
n
mellett hányféleképpen kapunk
xn -t,
akkor a
Pk (n)
számok jó együtthatók
lesznek. Ebb®l következik, hogy
1 + Pk (1)x + Pk (2)x2 + ... + Pk (n)xn + ... = g(x) = A
g(x)
függvényt szokás
1 (1 −
Pk (n) generátorfüggvényének
xb1 )...(1
− xbk )
(2.7)
nevezni. A precíz de-
níció így hangzik:
2.1.2. De níció.
Az
f (x) függvény generátorfüggvényén az F (x) = 1 +
∞ X
f (n) · xn
n=1
hatványsort értjük. A generátorfüggvény nem minden esetben konvergens, és nem minden esetben könny¶ meghatározni, de a pénzki zetési probléma és
|x| <
1 2 esetén
F (x) létezik
és abszolút konvergens. Az el®z® példát nézzük speciálisan a
b1 =1, b2 =2, . . . , bk =k
1 + Pk (1)x + Pk (2)x2 + ... + Pk (n)xn + ... = Ha nem az els®
esetre:
1 (1 − x)(1 − x2 )...(1 − xk )
(2.8)
k egészet engedjük meg, hanem minden pozitív egészet, akkor
a felbontás megegyezik a partíciókkal. (Természetesen továbbra is mindenhol feltesszük, hogy
|x| < 1,
a végtelen szorzatot pedig határértékkel értelmezzük):
1 + p(1)x + p(2)x2 + ... + p(n)xn + ... = Ha
f (n)
jelöli azt, hogy
n-nek
1 (1 − x)(1 − x2 )...(1 − xk )...
(2.9)
hány olyan partíciója van, amelyek csak pá-
ratlan számokból álló összegek, akkor
F (x) = (1 + x + x2 + x3 + ...)(1 + x3 + x6 + ...)... =
8
1 (1 − x)(1 − x3 )(1 − x5 )...
Ha
f (n)
jelöli
n
különböz® számokból álló partícióit, akkor
F (x) = (1 + x)(1 + x2 )(1 + x3 )... n
Ha pedig
különböz®, páratlan számokból álló partícióit keressük, akkor
F (x) = (1 + x)(1 + x3 )(1 + x5 )... Ha az a kérdés, hogy az minden tagja legfeljebb
m,
n−N
F (x) = mivel ha
számnak keressük azokat a partícióit, amelyek
akkor
xN (1 − x)(1 − x2 )...(1 − xm )
n-nek keresnénk ilyen feltételek mellett a partícióit, akkor a generátor-
függvénye
F (x) = xN -nel
lenne, és ezt
1 (1 − x)(1 − x2 )...(1 − xm )
szorozva kapjuk
n − N -nek
a partícióit.
A generátorfüggvény mellett a partíciószámok kezelésében hasznos kombinatorikai eszköz a pontséma, ahol az ábrázoljuk (a
c1 ≥ c2 ≥ ... ≥ ck
n = c1 + c2 + ... + ck
felbontást pontokkal
feltétel mellett), hogy az els® sorában
c2 db stb. 12 = 5 + 3 + 2 + 2
c1
db
pont található, a második sorában Például a lenti ábrán
felbontását látjuk. A de nícióból
egyértelm¶, hogy a sorok hossza föntr®l lefele monoton csökken. Azt a felbontást, amit az oszloponkénti leolvasással kapunk, a példán ez a
12 = 4 + 4 + 2 + 1 + 1
konjugáltjának nevezzük. A lenti
partíciót jelenti. A kétféle leolvasás ötlete
hasznos néhány tétel bizonyításánál.
2.1.1. Tétel.
Ha fr (n) és gr (n) az n olyan partícióinak a száma, ahol az összeadandók száma, illetve a partíciók maximuma r, akkor fr (n) = gr (n).
Bizonyítás: van, tehát
r
Vegyük azokat a pontsémákat, amelyeknek pontosan
kor olyan sémákat kapunk, amelyeknek a maximuma számoljuk, akkor adódik az egyenl®ség.
2.1.2. Tétel. legfeljebb
r
db sora
db összeadandóból állnak. Ha ezeket oszloponként olvassuk le, ak-
r. Ha mindegyik ilyet meg
Az n szám pontosan r tagú partícióinak a száma megegyezik n−r r tagú partícióinak a számával.
9
Bizonyítás: (⇒)
n
Egy kölcsönösen egyértelm¶ megfeleltetésre van szükségünk.
pontosan
r
tagú partíciójának
r
egy olyan partícióját kapjuk, aminek legfeljebb legfeljebb
r
r n−r
sora van, tehát az els® oszlop biztosan
tagú, de lehet, hogy több ilyen is van. Ha kihúzom az els® oszlopot, akkor
r
sora van, és ez
n − r-nek
egy
tagú partíciója.
(⇐) Vesszük
n − r-nek egy legfeljebb r tagból álló partícióját és elé írunk egy rn-nek kapjuk egy pontosan r tagú partícióját, mivel nagyobb r hosszúságú pedig van.
es oszlopot, és így nem lehet,
2.1.3. Tétel.
Jelölje s(n), illetve t(n) az n pozitív egész azon partícióinak a számát, ahol minden összeadandó különböz®, és a tagok száma páros, illetve páratlan. Ekkor
( s(n) − t(n) =
Bizonyítás:
(−1)k 0
ha
n = 21 (3k 2 ± k);
(2.10)
különben.
Jó lenne kölcsönösen egyértelm¶ megfeleltetést létrehozni
n
páros
és páratlan sok különböz® tagból álló partíciói között, de a tétel kimondásából is látszik, hogy ez csak abban az esetekben lehetséges, amikor
s(n)=t(n).
Tehát
létre kell hozni egy majdnem kölcsönösen egyértelm¶ megfeleltetést. Ha
n csupa különböz® komponensb®l álló felbontását vesszük, az olyan sémá-
kat eredményez, amelynél a sorokban szerepl® pontok száma szigorúan csökken. Például a lenti ábrán a
23 = 8 + 7 + 5 + 3
felbontást láthatjuk
A séma élének nevezzük a séma jobb fels® sarkából induló, maximális, 45 fokos szögben haladó, ÉK-DNY irányú pontsort. A fenti ábrán ez a pontsor 2 db pontból áll. Legyen
A
az a transzformáció, amely egy séma élét áthelyezi
a séma alá új sornak, azzal a feltétellel, hogy ez a m¶velet nem rontja el a séma alakját (tehát hogy csupa különböz® összeadandókból áll, és hogy monoton csökkennek a sorok hosszai). De niáljuk a
B
transzformációt olyanformán, hogy
az utolsó sort a séma éle mellé rakja, ha az nem rontja el a séma alakját.
Az el®bbi példánkon elvégezve az végezhet® el. Általában
A
és
B
A-t, a fenti sémát kapjuk, azonban a B nem
közül pontosan az egyik végezhet® el, néhány
kivételt®l eltekintve, amikor egyik sem. Ezt a következ®ekben látjuk be. Legyen a a séma utolsó sorának elemszáma, b pedig az él elemszáma. Ha a ≤ b, akkor A nem végezhet® el, és B igen, kivéve ha a = b és az él és az utolsó sor összeér, mint az az alábbi ábrán is látszik.
10
Ha
a > b,
B
akkor
nem végezhet® el, és
A
igen, kivéve ha
a=b+1
és az él
és az utolsó sor összeér.
A
Természetes, hogy
és
B
egymás inverzei, hiszen egymás után elvégezve
®ket az eredeti állapotot nyerjük vissza. Igaz az is, hogy
A
és
B
eggyel növeli,
illetve csökkenti a sorok számát, így a keletkez® partícióban az összeadandók paritása ellentétes lesz a kezd®állapothoz képest. Ebb®l a kett®b®l következik, hogy
A
B
és
kölcsönösen egyértelm¶ megfeleltetést létesít a páros és páratlan
számú összeadandókból álló partíciók között, kivéve a két kivételes esetet. Ebb®l következik, hogy
s(n) − t(n) = 0,
kivéve a két kivételes esetet, amikor
a kivételes partícióban az összeadandók száma páros, és Ha az els® kivételes esetben a rossz partíció
k
k
−1,
±1
(1, ha
a másik esetben).
db összeadandóból áll (azaz
db sorból áll), akkor
n = (2k − 1) + (2k − 2) + ... + k =
(3k − 1)k 2
(2.11)
Hasonlóan a második kivételes esetben, ha a rossz partíció itt is
k
db
összeadandóból áll, akkor
n = 2k + (2k − 1) + ... + (k + 1) =
(3k + 1)k 2
(2.12)
Be kell még látni, hogy egy számnak csak egy rossz partíciója lehet. Adott
n-re
(2.11) és (2.12) egyszerre ugyanazzal az indexszel nem teljesülhet, de kü-
lönböz®vel se, mivel
Azonban abban az
(3k − 1)k (3k + 1)k < 2 2 esetben, ha a bal oldalt k helyett k + 1-re
(2.13) vesszük, akkor
az egyenl®tlenség megfordul, tehát az egyenl®ség egyetlen pozitív egész teljesülhet.
k -ra sem
Ennek a tételnek van következménye a partíciószámokra nézve is. Ehhez alkalmazunk kell a fejezet elején említett, (2.9)-cel jelölt formulát, majd vezessük be a
Q(x)
jelölést.
1 + p(1)x + p(2)x2 + ... + p(n)xn + ... = A továbbiakban ezt a
Q(x)
1 1 = 2 k (1 − x)(1 − x )...(1 − x )... Q(x)
függvényt akarjuk hatványsor alakra hozni, azaz:
Q(x) = 1 + a1 x + a2 x2 + ... + ak xk + ... 11
(2.14)
megfelel® együtthatókkal. Ha
Q(x)
helyett el®ször az
(1 + x)(1 + x2 )...(1 + xk )... hatványsorba fejtését vizsgálnánk, akkor azt kapnánk, hogy annyiszor 1, ahányszor el®állítható
n
Ha ezzel a gondolatmenettel vizsgáljuk Itt
s(n)
(illetve
t(n))
n
együtthatója
mint különböz® pozitív egészek összege.
Q(x)-et, akkor an := a(n) = s(n) − t(n). t(n) negatív
ugyanaz jelenti, amit az el®z® tételben. A
el®jele a páratlan db negatív szám szorzata miatt adódik. A bizonyítás következményeként adódik az Euler azonosság ezen alakja
Q(x) = (1 − x)(1 − x2 )(1 − x3 )... =
∞ X
(−1)k x
3k2 +k 2
.
(2.15)
k=−∞ Ekkor a legutóbb bizonyított tétel miatt az
an -ek
a legtöbb helyen
0-k,
a
kivételes esetekt®l eltekintve. A (2.9) és (2.14) formulákból következik, hogy
(1+a1 x+a2 x2 +...+an xn +...)(1+p(1)x+p(2)x2 +...+p(n)xn +...) = 1. Az
n≥1
esetre a jobb oldalon
xn
együtthatója
0,
(2.16)
a bal oldalon viszont
p(n) + p(n − 1)a1 + p(n − 2)a2 + ... + p(1)an−1 + an . Mivel a hatványsorbafejtés egyértelm¶, a két érték megegyezik. Átrendezve pedig egy rekurzív képletet kapunk
p(n)-re, ami nagyon jól használható, an -ek nagy része 0.
mert
sokkal kevesebb a m¶veletigénye, hiszen az
p(n) = −p(n − 1)a1 − p(n − 2)a2 + ... − p(1)an−1 − an = = p(n − 1) + p(n − 2) − p(n − 5) + p(n − 7) + ... Ennek a képletnek a segítségével számolták ki
p(200)-t,
ami akkoriban ha-
talmas eredménynek számított, de a mai korban sem kell lebecsülni ennek a képletnek a hasznosságát.
p(200) = 3 972 999 029 388. A fenti tétel például olyan kérdésekre is választ ad, hogy melyek azok a számok, amelyek páratlan sokféleképpen állnak el® különböz® pozitív egészek összegeként. Ez a kérdés átfogalmazható arra, hogy melyek azok a számok, amelyeknek páratlan az olyan partíciószáma, ahol a partíciók különböz® tagokból állnak (jelöljük ezt
f (n)-nel).
Ha az
s(n) = t(n)
eset áll fenn, akkor
f (n) = s(n) + t(n) = 2s(n), tehát ekkor ez a partíciószám páros. Ha az
n = 21 (3k 2 ± k )),
s(n) = t(n) ± 1
eset áll fenn (azaz
akkor
f (n) = s(n) + t(n) = 2s(n) ± 1, ami mindig páratlan. Tehát a válasz, hogy ez a típusú partíciószám.
12
n = 21 (3k 2 ± k)
esetén lesz páratlan
2.2. Konkrét egyenlet megoldása hatványsorokkal Érdemes fontolóra venni azt a kérdést, mennyire hasznos a feladat Euler-féle átfogalmazása, azaz mennyit nyerünk vele. Ennek a megvizsgálásához vegyük a
(2.3)
diofantikus egyenletet a
k = 3, esetben. Ekkor
(2.3)
és
b1 = 2,
(2.7)
b2 = 3,
b3 = 4
a következ®re módosul
2x1 + 3x2 + 4x3 = n, 1+
∞ X
P3 (n)xn =
n=1
(2.17)
1 (1 − x2 )(1 − x3 )(1 − x4 )
A parciális törtekre bontást Maple-lel elvégezve kapjuk, hogy
(1 − +
x2 )(1
1 1 1−x 1 1 = · + · + 3 4 2 − x )(1 − x ) 8 1+x 16 (1 + x)2
(2.18)
1 1 1 59 1 7 1 1 2+x 1 · + · + · + · + · , 24 (1 − x)3 8 (1 − x)2 288 1 − x 32 1 + x 9 1 + x + x2
amelyeknek könnyen megalkotható a hatványsora. Mivel az
|x| < 1 eset áll fenn,
ezért alkalmazhatjuk a mértani sor összegképletét, miszerint:
1 = 1 + x + x2 + ... + xk + ... 1−x Mivel
|x| < 1, x
(2.19)
helyett (−x)-et véve is érvényes a feltétel, ezért alkalmaz-
hatjuk a képletet, tehát:
1 = 1 − x + x2 − x3 + ... + (−1)k xk + ... 1+x Továbbra is
(2.20)
(2.19)-b®l kiindulva, és úgy végezve a szorzást, ahogy több tagot
több taggal szokás (ami az abszolút konvergencia miatt megtehet®), levezethet®, hogy
1 = 1 + 2x + 3x2 + ... + (k + 1)xk + ... (1 − x)2
(2.21)
Binomiális együtthatókra átírva kapjuk azt az eredményt, hogy
1 = (1 − x)2
1 2 3 2 k+1 k + x+ x + ... + x + ... 1 1 1 1
(2.22)
Hasonlóan kijön az az eredmény, hogy
1 = (1 − x)3 A (2.21) képletet
x
2 3 k+2 k + x + ... + x + ... 2 2 2
helyett
−x-et
(2.23)
alkalmazva azt kapjuk, hogy
1 1 = = 1 − 2x + 3x2 + ... + (−1)k (k + 1)xk + ... 2 (1 + x) (1 − (−x))2 13
(2.24)
A (2.18) bizonyításához szükségünk van még a
2+x 1 + x + x2 1 + x + x2
hatványsorára. Ehhez meghatározzuk
két gyökét, amik komplexek,
majd elvégezzük a parciális törtekre bontást. Mindkét törtet, hogy alkalmazhassuk a mértani sor összegképletét, egyszer¶sítjük a nevez®vel.
2+x = 1 + x + x2 (x + 1 2
=
√
+
x+ Mivel
|x| < 1
1 2
3i 2√
3i 2
+
1 2
+
x+
√
1 2
+
2+x
3i 2 )(x
+
1 2
√
3i 2 )
−
=
√
− 1 2
3i 2√
3i 2
−
1
=
+
x√ 3i 1 2+ 2
1+
1 x√
1+
1 2−
3i 2
és
v 2 1 √3i u 1 u + =t ± 2 2 2
√ !2 r 3 1 3 + = 1, ± = 2 4 4
(2.25)
ebb®l következik, hogy
1 x 1 √3i < = 1, ± 1 2 2 tehát használhatjuk a mértani sor összegképletét (esetünkben praktikusabb a (2.20)). Azaz
∞
X 2+x (−1)k = 2 1+x+x k=0
!k
x 1 2
+
√
+
3i 2
∞ X
(−1)
k=0
!k
x
k 1 2
√
−
3i 2
=
A könnyebb számolás miatt gyöktelenítve a nevez®t, összevonva a két szummát, majd
=
(−1)k -nal
∞ X
(−1)
k
beszorozva kapjuk azt az eredményt, hogy
x·
k=0
√ !!k ∞ X 1 3i (−1)k − + 2 2 k=0
=
∞ X
√ !k 3i k k 1 (−1) · x · − + 2 2
k=0
=
∞ X k=0
√ !k 1 3i k x · − + + 2 2
x·
√ !!k 1 3i + = 2 2
√ !k 3i 1 + = 2 2
√ !k 1 3i − − . 2 2
(2.26)
A hatványozás elvégzéséhez szükségünk van a számok trigonometrikus alakjára (felhasználva (2.25)-öt)
√ 1 3 2π 2π − +i· = cos( ) + i · sin( ) 2 2 3 3
és
14
−
√ 1 3 4π 4π −i· = cos( ) + i · sin( ), 2 2 3 3
majd a Moivre formulát használjuk fel. Visszahelyettesítve (2.26)-ba azt kapjuk, hogy
∞ X k=0
2π 4π 4π 2π ) + i · sin(k · ) + cos(k · ) + i · sin(k · ) . xk · cos(k · 3 3 3 3
Kihasználva, hogy
sin(x)
(−2π)/3 = 4π/3 (mod 2π),
és az, hogy a
cos(x)
páros, a
pedig páratlan függvény, kapjuk azt az eredményt, hogy
∞
X 2π 2π 2+x 2π = 2 · xk · cos(k · ) = 2 · cos(0 · ) + 2 · cos(1 · ) · x + ... 2 1+x+x 3 3 3
(2.27)
k=0
Az utolsó hiányzó hatványsor a (2.18)-hoz az
1−x 1 −x = + 1 + x2 1 + x2 1 + x2 A
(2.20)
egyenletb®l kiindulva, és
x
helyett
x2 -et
helyettesítve kapjuk, hogy
1 = 1 − x2 + x4 − x6 + ... + (−1)k x2k + ... 1 + x2 A
(2.28)-at −x-szel
(2.28)
megszorozva:
−x = −x + x3 − x5 + x7 + ... + (−1)k+1 x2k+1 + ... 1 + x2
(2.29)
A fenti két egyenletet összegezve azt kapjuk, hogy k+1 1−x = 1 − x − x2 + x3 + x4 − ... + (−1)b 2 c xk + ... 2 1+x
Ezzel
(2.18)
tás miatt és a
(2.30)
minden komponensének hatványsora megvan. Az összegre bon-
(2.19), (2.20), (2.22), (2.23), (2.24), (2.27), (2.30)
egyenleteket
felhasználva kapjuk, hogy
P3 (n) = +
n+1 1 1 · (−1)b 2 c + · (−1)n (n + 1)+ 8 16
n+2 59 7(−1)n 2 2nπ 1 1 · + + · cos( ). + · (n + 1) + 24 2 8 288 32 9 3
Mivel el®z®leg megállapítottuk, hogy
(2.31)
P3 (n)-ek is megfelel® együtthatók, ezért
a hatványsorbafejtés egyértelm¶sége miatt a két érték megegyezik, ami egy meglehet®sen meglep® eredmény, mert például az sem triviális, hogy a jobb oldal miért mindig egész szám. Ez is egy jó példa a Ramanujan-szer¶en szép formulára, f®leg hogy van benne egy periodikus tag is. Általában azonban az ilyen feladatokat nem így szokás megoldani. Adott
n-re
(2.17)-et, mint egy diofantikus egyenletet, aminek xi -kre a megoldásait. Kezdetben foglalkozzunk a
tekinthetjük
nemnegatív
2x1 + 4x3 = k,
x1 , x3 ≥ 0,
x1 , x3 ∈ Z,
keressük a
(2.32)
k mellett. Könny¶ meggondolni, hogy csak k páros szám, és minden nemnegatív, páros k ra létezik megoldás (például ha k/2 db 2-est veszünk, és 0 darab 4-est). Innent®l
egyenlet megoldásaival, rögzített
akkor létezik ennek megoldása, ha
15
feltesszük, hogy
k
rögzített és páros. Az átláthatóság kedvéért a megoldásokat
rendezett párba írjuk, tehát
(a1 , b1 )
a1 , b1 ≥ 0,
2a1 + 4b1 = k, k
Ha tudjuk
sainak egy része ha
k+2
azt jelenti, hogy
megoldásait (jelöljük ezeket
(ai + 1, bi )
(ai , bi )-vel),
akkor
k+2
megoldá-
alakú. Csak akkor keletkezhet másféle megoldás,
osztható 4-gyel, hiszen ekkor
következik, hogy
a1 , b1 ∈ Z,
k -ról k + 2-re
(0, (k + 2)/4)
is megoldás lesz. Ebb®l
lépve vagy 1-gyel n® a megoldások száma, vagy
ugyanannyi marad.
k = 0-ra és k = 2-re a megoldások száma 1, onnantól pedig 4-esével n® k -ra a (2.32) egyenlet megoldásainak (jelöljük ezt dk -val) ( k 4 + 1 ha k páros; dk := 0 különben.
Mivel
1-gyel, ezért megállapítható, hogy adott száma
Átrendezve a
(2.17)
egyenletet, azt kapjuk, hogy
2x1 + 4x3 = n − 3x2 , ahol bármely
x2 -re
tudjuk a megoldást. Mivel a jobb oldalon nem szeretnénk
negatív számot kapni, ezért
x2 -nek
0 és
bn/3c között kell lennie. x2 -re a megoldások számát,
Ez alapján vegyük az összes lehetséges ket összegezve kapjuk az eredeti
(2.17)
és eze-
egyenlet megoldásainak számát, ami a
következ®:
bn/3c
X
bn/3c
dn−3x2 =
x2 =0 ahol
χ
X
x2 =0
n − 3x2 + 1 · χ {ha n − 3x2 4
páros} ,
(2.33)
a karakterisztikus függvényt jelöli (ami 1-et vesz fel, ha igaz az állítás,
és 0-t, ha nem). Ezt a formulát lehet tovább folytatni aszerint, hogy 4-gyel osztva. Például
n = 4s + 1
n
milyen maradékot ad
esetben a szummában 0-tól
sorozattól eltekintve minden szám szerepel. Jelöljük az els®
s-ig egy számtani s szám összegét
S -sel. Ebben az esetben a hiányzó részsorozat az
jnk 4 Ennek a karakterizációja, ha
a1 =
jnk 4
− 2,
m
− 2,
jnk 4
− 5, ...
a sorozat elemszámát jelöli:
d = −3,
m=
la m 1
3
=
bn/4c − 2 3
Az összege
Sm =
l a m 3 l a m2 3 l a m [2a1 + (m − 1)d]m 1 1 1 = a1 · − + 2 3 2 3 2 3
Tehát a sorozat összege
S − Sm
l a m 3 l a m2 3 l a m (a1 + 2)(a1 + 3) 1 1 1 = − a1 · − + 2 3 2 3 2 3 16
Ezt nagyságrendileg becsülve (tehát nem tör®dve a fels® és alsó egészrészekkel és
a1 -et n/4-ként
kezelve) kapjuk, hogy
S − Sm
= ahol
f ∼g
a2 5a1 ≈ 1+ +3− 2 2
a21 a2 a1 − 1+ 3 6 2
=
1 n2 n n2 a21 + 2 · a1 + 3 = · + +3∼ , 3 3 16 2 48
az aszimptotikus egyenl®séget jelöli. Nagyságrendileg tényleg m¶kö-
dik a formula, hiszen a különbségünk a következ®képp állt el®:
n
n/4 X
n/12
i−3
i=1
X i=1
1 1 n 2 3 n 2 1 n2 2 − · =n i∼ · − = 2 4 2 12 32 96 48
Ehhez hasonlóan megalkotható a formula a többi maradékosztályra is, de ett®l itt most eltekintünk.
(2.33) jelent®s mértékben más formula, de ugyanazt az eredményt adja, (2.31). Ezt most egy konkrét példára le is ellen®rizzük. Legyen ebben az esetben n = 13. Ekkor a fenti formula alapján A
mint a
4 X 13 − 3x2 + 1 · χ {ha 13 − 3x2 4 x =0
páros}
=
2
= A
(2.31)
13 − 3 · 1 13 − 3 · 3 +1 + + 1 = 2 + 1 + 1 + 1 = 5. 4 4
formula pedig szintén ezt az eredményt adja, hiszen
1 13 + 2 1 1 1 b 13+1 13 c 2 · (−1) (13 + 1) + · + · (13 + 1)+ P3 (13) = · (−1) + 8 16 24 2 8 +
59 7(−1)13 2 13 · 2π 1 7 105 14 59 7 1 + + · cos( )=− − + + + − − = 5. 288 32 9 3 8 8 24 8 288 32 9
Azonban érdemes megjegyezni, hogy nagyobb számokra a hatványsoros módszerrel adott képlet jóval kevesebb m¶veletigénnyel rendelkezik.
17
3. fejezet
Kerek számok Ebben a témakörben Hardy és Ramanujan egy nevezetes tételét szeretnénk kimondani. Ez a tétel a kerek számok témakörébe tartozik, és Turán Pál adott rá egy egyszer¶ bizonyítást. Ehhez szükséges azonban néhány el®készület, amit a következ®kben teszünk meg. Általában egy számot
kereknek
nevezhetünk, ha a prímfelbontásában a prí-
720 = 24 · 32 · 5 egy 1024 = 210 még nála is kere-
mek a nagyságához képest kicsi számok. Példának okáért a kerek szám, és köznyelvi megfogalmazás alapján az
kebb. Hardyt és Ramanujant is érdekelte, hogy mi a matematikai magyarázata annak, hogy a kerek számok meglehet®sen ritkák. Els®re ez a kijelentés kicsit ellentmondásosnak t¶nhet, hiszen a számok fele osztható kett®vel, a harmada hárommal, az ötöde öttel stb., és mégis az teljesül, hogy egy számnak vannak nagy prímosztói. Két olyan függvényt vezetünk most be, amelyek valamilyen mértékben azt jellemzik, hogy egy szám mennyire tekinthet® összetettnek. Be fogjuk látni, hogy esetünkben ezek között nincs nagy különbség. Vegyük adott tását:
n = pa1 1 · ... · paν ν =
ν Y
n-re
a prímfelbon-
pai i ,
i=1 ahol
p1 < ... < pν
prímtényez®k. Ekkor legyen
ω(n) := ν ,
tehát
n
különböz®
prímfaktorainak a száma. Hasonlóképpen de niálhatjuk a másik függvényt:
Ω(n) :=
ν X
ai ,
i=1 tehát
Ω(n)-nel jelöljük azz n prímfelbontásában a prímek számát multiplicitással n, amire ω(n) = ν , éppen
számolva. Egyértelm¶, hogy a legkisebb
n = 2 · 3 · ... · pν , ahol
pν
a
ν -edik
prímszámot jelöli. Még egy alapde nícióra szükségünk van a
továbbiakban.
3.0.1. De níció.
Legyen f egy számelméleti függvény (azaz pozitív egészeken értelmezett komplex érték¶ függvény) és F (n) := f (1) + f (2) + ... + f (n). Az f függvény átlagértékfüggvényén (vagy középértékfüggvényén) az F (n)/n függvényt értjük.
18
Azt fogjuk belátni, hogy
ω(n) és Ω(n) átlagértéke log log(n). El®ször az ω(n)
függvénnyel foglalkozunk.
X
ω(k) =
k≤n Az els® egyenl®ség az
XX
1=
1
p≤n pm≤n
k≤n p|k
ω(k)
X X
de níciója miatt teljesül, majd a két szummát
p olyan prím és m olyan pozitív egész, k -ra (ahol k ≤ n) néztük meg a prímosztóit, és ez ugyanaz, mintha adott p ≤ n prímre néznénk meg, hogy hány olyan m van, amire pm ≤ n. A fenti feltételt átalakíthatjuk úgy, hogy ne legyen szükségünk m-re, ugyanis ha minden megfelel® m és p pár ér 1-et, akkor egy adott p-re pontosan n/p alsó egészrész db jó m található. X1 X X n X n X n n = − − =n + O(n). (3.1) ω(k) = p p p p p
felcserélve kapjuk a fenti eredményt, ahol
amelyek kielégítik az egyenl®tlenséget. Hiszen el®ször adott
p≤n
k≤n
p≤n
p≤n
p≤n
0 ≤ a − bac < 1 minden a-ra, így az alsó egészrész elhagyásával maximum n tag van. A továbbiakban a hibát O(n)-nel jelöljük. Jelen esetben ez azt jelenti, hogy a hiba nagyságrendje n-es, azaz n-nel elosztva az értéke korlátos. Ismert tétel, hogy X1 = log log(n) + O(1). (3.2) p Mivel
1 hiba keletkezik, a szummában pedig maximum
p≤n
Ebb®l következik, hogy
X
ω(k) = n · log log(n) + O(n).
(3.3)
k≤n Beírva a de níciót, majd összevonva a két szummát
Ω(k)
esetében is, arra
jutunk, hogy
X
Ω(k) =
XX
1=
k≤n pa |k
k≤n
X
1.
pa m≤n
Majd ugyanazokat a megfontolásokat téve, mint az el®bb, kapjuk azt az eredményt, hogy
X k≤n
X n X n n n Ω(k) = + 2 + 3 + ... = pa p p p a p ≤n
p≤n
Itt viszont kicsit módosul a gondolatmenet. Ha a magasabb rend¶ tagok nem lennének ott, akkor visszakapnánk az
ω(k)-ra
tett becslésünket, ezért belátjuk,
hogy a maradék nagysága nem túl nagy. A második lépésben felhasználva a
O(n)-nél nagyobb |p| > 1 minden p-re, így |1/p| < 1 biztosan teljesül. X n n X 1 X 1 1 + + ... < n · + + ... =n· = O(n). 2 3 2 3 p p p p p(p − 1)
mértani sor összegképletét megkapjuk, hogy nem keletkezik hiba. Felhasználható, hiszen
p≤n
p≤n
p≤n
1/(p2 − p) < 1/n2 < ∞ tagonként, tehát konvergens, így n-szer megszorozva O(n)-es hibát kapunk. Erre a függvényre is kijött az, hogy X X n X n n Ω(k) = + + 3 + ... = n · log log(n) + O(n). p p2 p Tudjuk, hogy
k≤n
P
p≤n
P
p≤n
19
Tehát bebizonyítottuk azt, hogy
X
X
ω(k) ∼ n · log log(n),
k≤n ahol
f ∼ g
Ω(k) ∼ n · log log(n),
k≤n
azt jelenti, hogy
f /g
tart 1-hez, azaz aszimptotikusan egyenl®ek.
Szükségünk van arra az állításra, hogy
log log(2) + ... + log log(n) ∼ n · log log(n),
(3.4)
ami ekvivalens azzal, hogy
Pn
i=2 log log(i) = 1. n · log log(n)
lim
n→∞
A fenti állítást rend®relvvel fogjuk igazolni. Fels® becslést könny¶ adni, ha minden tagot
log log(n)-et,
log log(n)-nel
fölülr®l becsülünk, és hozzáadunk még egyszer
mivel a számlálóban csak
n−1
db tag van, a tört 1-et ad. Az alsó
becsléshez felhasználjuk majd, hogy
√ 1 1 log log( n) = log( · log(n)) = log( ) + log log(n) = log log(n) − log(2). (3.5) 2 2 √ √ A szummában a b nc utáni tagokat log log(n) − log(2)-vel, a b nc el®tti tagokat pedig 0-val becsüljük. Ezt követ®en átalakítjuk a szummát, elhagyjuk az alsó egészrészt, és leosztunk tagonként.
Pn
i=2 log log(i) ≥ n · log log(n)
Pn
√ i=b nc
Pn
log log(i)
√ i=b nc (log log(n)
≥
− log(2))
n · log log(n) n · log log(n) √ (n − b nc)(log log(n) − log(2)) = ≥ n · log log(n) √ √ n · log log(n) − n · log log(n) − n log(2) + n log(2) ≥ = n · log log(n)
1 log(2) log(2) =1− √ − +√ →1 log log(n) n n · log log(n) Így
(3.4)
ságrendje is
log log(n)
n → ∞.
alapján természetes azt mondani, hogy ω(n) és Ω(n) átlagos nagylog log(n). Ez még nem jelenti azt, hogy ω(n) (vagy Ω(n)) feltétlenül
körüli értéket vesz fel. Vegyünk erre egy szemléletes példát. Legyen
( n g(n) := 0 Ekkor
G(n) :=
n X
ha
mivel az els®
k
köbszám;
g(i) =
X j≤
√ 3
j3 ∼
n
G(n)
átlagértéke
legtöbbször pedig 0.
20
n4/3 , 4
k -adik háromszögszám négyn1/3 -os nagyságrend¶. A g(n)
darab köbszám összege egyenl® a
zetével. Ebb®l következik hogy
n,
n
különben.
i=1
id®nként
ha
=
Hardy és Ramanujan tétele azt fejezi ki, hogy ezzel az extrém példával szemben
ω(n)
Ω(n)
és
majdnem mindig
log log(n)
körül értéket vesz fel. Belátható,
hogy ebb®l a szempontból sincs nagy különbség a két függvény között, ezért ezentúl a könnyebbség miatt
ω(n)-et
fogjuk vizsgálni. Mi a tétel egy lokális
k -ra nem a ω(k) és ω(k) − log log(n)-et. Ezt megtehet-
változatát fogjuk bizonyítani, ami azt jelenti, hogy adott
log log(k)
különbségét vizsgáljuk, hanem a
jük, mert a
log log(n)
egy nagyon lassan növ® függvény, és ez nem jelent sok
hibát. Precízen a tétel a következ®képp szól:
3.0.1. Tétel (Hardy-Ramanujan).
Bármely > 0-hoz létezik olyan (az -tól C , hogy tetsz®leges n ≥ 3 esetén az 1, 2, ... , n számok között legalább (1 − )n darab olyan k található, amelyre p |ω(k) − log log(n)| < C log log(n).
függ®)
Ennek a tételnek valószín¶ségszámítási tartalma is van, hiszen tekinthe-
ω -ra, mint valószín¶ségi változóra, ami egyenl® valószín¶séggel vesz ω(1), ..., ω(n) értékeket. Ekkor az eddigi meggondolásaink alapján ennek a várható értéke kb. log log(n). A leírás könnyebbítése miatt vezessük be a µ = log log(n) jelölést. Valószín¶ségszámítási fogalmakkal kifejezve azt kell vizsgálnunk, hogy az ω valószín¶ségi változó milyen valószín¶séggel tér el a várható értékét®l (azaz µ-t®l), majd belátjuk, hogy ez az eltérés nem lehet túl nagy, tünk úgy fel
azaz kicsi a szórása. Ezek alapján a továbbiakban a szórásnégyzet nagyságát akarjuk meghatározni, azaz a
X
{ω(k) − µ}2
k≤n kifejezés átlagértékét. Valószín¶ségi szempontból az
n · D(n)2 -nek
felelne meg.
Elvégezve a négyzetre emelést azt kapjuk, hogy
X
{ω(k) − µ}2 =
k≤n
X
{ω(k)}2 − 2 · µ ·
k≤n
X
ω(k) + µ2 ·
k≤n
X
1,
(3.6)
k≤n
amiben az utolsó két tagra vannak már becsléseink. Tehát a tétel bizonyításához szükségünk van még a:
X
{ω(k)}2
k≤n becslésére is. Ehhez írjuk be kétszer az aszerint, hogy a
X
p
és
{ω(k)}2 =
k≤n
q
ω(k)
de nícióját, majd alakítsuk át
prímek egyenl®ek-e
X
X X X X 1 1 = 1+
k≤n
p|k
q|k
k≤n
Ennek a kettébontásnak az is el®nye, hogy a
p 6= q esetben q|k , akkor pq|k , tehát
p|k
p=q
X
1 =
pq|k, p6=q esetben keletkez® szum-
mára már van becslésünk. A
pedig azt kell megfontolni, hogy
k -ra ha p|k és pql = k . Megcserélve
létezik egy pozitív egész
adott
kapjuk azt, hogy
=
XX k≤n p|k
1+
l,
hogy
a két szummát, azaz felcserélve az összegzés sorrendjét,
X
X
k≤n pq|k, p6=q
1=
X X p≤n pm≤n
21
1+
X
X
pq≤n, p6=q pql≤n
1=
m, l olyan pozitív egészek, amelyek kielégítik az egyenl®tlenséget. Az összes l-re 1-et számolva kapjuk a fenti átfogalmazást. Majd felhasználjuk azt a sokszor alkalmazott gondolatot, hogy ilyen jó l-b®l (illetve m-b®l) pont n/pq (illetve n/p) alsó egészrész db van. X n X n = + p pq ahol
jó
p≤n
pq≤n, q6=p
Összefoglalva
X
X
{ω(k)}2 =
k≤n
(3.7)
p≤n
pq≤n, q6=p
Most meg szeretnénk becsülni
X n n + . pq p
(3.7) nagyságrendjét. Az ehhez hiányzó szum-
ma becslésénél megállapítható, hogy
X pq≤n, q6=p
n pq
=n·
X pq≤n, q6=p
X 1 1 + O(n) = n · + O(n). pq pq pq≤n
Az els® egyenl®ség azért teljesül, mert az alsó egészrész elhagyásával maximum
n
1 hiba keletkezik, és a szummában legfeljebb
tag van. A
q 6= p
feltételt el-
hagyhatjuk, mert a prímek négyzetének reciprok összege konvergens, ugyanis
∞ X 1 π2 = <∞ k2 6
∞ ∞ X X 1 1 ≤ 2 2 p k p=2
és
k=1
k=1 tagonként. A
P
1/pq
tagot azonban alulról és felülr®l is tudjuk becsülni
2 X X 1 X 1 ≤ ≤ pq √ p
Az els® egyenl®tlenség azért igaz, mert ha következik, hogy
pq ≤ n.
p≤n
teljesül.
A
q ≤ n is (3.2) miatt és
p≤n
pq≤n
p≤ n
p≤
√
n
2 1 p
és
q≤
√
n,
A második pedig azért igaz, mert ha
akkor abból az
pq ≤ n,
akkor
a jobb széls®r®l tudjuk, hogy
{log log(n) + O(1)}2 = {log log(n)}2 + O(log log(n)), nagyságrend¶, de a
(3.5)-ös
megállapítás miatt ugyanez igaz a bal széls®re is.
Emiatt a középs® kifejezés is szükségszer¶en
{log log(n)}2 + O(log log(n)) nagy-
ságrend¶. Ebb®l következik, hogy
X pq≤n, q6=p Behelyettesítve
X
n pq
= n · {log log(n)}2 + O(n · log log(n)).
(3.7)-be (3.3)-at
és
(3.8)-at
kapjuk, hogy
{ω(k)}2 = n · {log log(n)}2 + O(n log log(n)) = n · {µ}2 + O(nµ),
k≤n
22
(3.8)
(3.9)
(3.7)-es képlet becslését. (3.6)-os képlet becslését (felhasználva (3.9)-et
és ezzel befejeztük a Összefoglalva a
és
(3.3)-at),
a
következ® végeredményhez jutunk:
X
{ω(k) − µ}2 = n · {µ2 + O(µ)} − 2 · µ · n{µ + O(1)} + µ2 {n + O(1)} = O(nµ)
k≤n (3.10) Visszatérve a valószín¶ségszámítási gondolathoz, a fenti képlet egy becslés a szórásnégyzet nagyságára. Most jön az az elején említett gondolat, hogy nem lehet túl sok olyan tag, ami túl nagy, azaz esetünkben kívül esne a szórás konstansszorosán. Ennek belátásához tegyük fel, hogy van kisebb
n-nél
δn
db olyan
k,
ami
és
|ω(k) − µ| > χ(n). Ebb®l az következne, hogy
X
{ω(k) − µ}2 = δnχ(n)2 ,
k≤n ami ellentmond
(3.10)-nek,
ha
χ(n) > c ·
√
µ,
alkalmas
c-vel.
Ebb®l következik,
hogy nem lehet túlságosan sok tag, ami eltér az átlagértékt®l, ami bizonyítja a tételünket. A bizonyítás eredeti szerz®je Turán Pál, akit ezen bizonyítása miatt a valószín¶ségi számelmélet elindítójánaként tartanak számon. Ennek az az oka, hogy a bizonyítás módja megegyezik a Csebisev egyenl®tlenség bizonyításának a gondolatával, annak ellenére, hogy ezt csak kés®bb elemezték ki.
23
4. fejezet
Négyzetszámokkal való el®állítás Ebben a fejezetben azt vizsgáljuk meg, hogy egy adott pen állítható el® mint adott
rk (n)-nel.
k
n
szám hányfélekép-
darab négyzetszám összege. Jelöljük ezt a számot
Ramanujan szintén alkotott ebben a témakörben, és ebben az eset-
ben is felmerül az a kérdés, hogy Ramanujan Angliában szerzett-e ismereteket a témáról, vagy magától fedezte fel ®ket. Akárhogy is történt, Ramanujan tételei így is, úgy is helytállóak. Egyszer¶bb esetekre már Ramanujan el®tt is léteztek eredmények, Jacobi oldotta meg ezeket a
k = 2, 4, 6, 8 esetre. Legel®ször a k = 2 bizonyítását nézzük,
azaz annak a diofantikus egyenlet megoldásainak a számát akarjuk megadni, hogy
x2 + y 2 = n,
x, y ∈ Z,
(4.1)
ahol számít sorrend és az el®jel is. Ehhez a témához azonban szükséges még néhány de níció.
4.1.1. De níció. Gauss-egésznek azt a ahol a és b egészek.
z = a + bi komplex számot nevezzük,
A Gauss-egészek struktúrája nagyon szép, a komplex számok összeadására és szorzására nézve kommutatív, egységelemes, nullosztómentes gy¶r¶t alkotnak. Az összes egység az
1,
a
−1,
az
i
és a
−i.
Az is teljesül, hogy egy Gauss-
egész pontosan akkor Gauss-prím, ha Gauss-felbonthatatlan, valamint a Gaussegészek körében is igaz a számelmélet alaptétele.
4.1.1. Tétel (A számelmélet alaptétele). Minden 0-tól és egységekt®l különböz® Gauss-egész felbontható véges sok Gauss-prím szorzatára, és ez a felbontás a tényez®k sorrendjét®l és egységszeresekt®l eltekintve egyértelm¶. A következ® tételre is szükségünk lesz:
4.1.2. Tétel.
Minden Gauss-prím a következ® módon áll el® ( tetsz®leges egy-
ség)
• (1 + i); • q, ahol q pozitív 4k − l alakú prímszám; 24
• u, ahol |u|2 egy 4k + 1 alakú prímszám. Minden ilyen prímszámhoz egységszerest®l eltekintve két Gauss-prím tartozik, amelyek egymás konjugáltjai, de nem egymás egységszeresei. Adott
n
egész számra általában a kanonikus alakot úgy is felírhatjuk, hogy
n = 2a · pb11 · ... · pbkk · q1c1 · ... · qlcl , ahol
pi -k 4k + 1,
a
qj -k
pedig
4k − 1
(4.2)
alakú prímek, a kitev®k pedig nemne-
gatív egészek. A Gauss-egészek körében is létezik kanonikus alak fogalom, ami
4.1.2
egységt®l és sorrendt®l eltekintve egyértelm¶. A
Tétel miatt
n
egyik ilyen
kanonikus alakja
n = (−i)a (1 + i)2a · z1b1 z1 b1 · ... · zkbk zk bk · q1c1 · ... · qlcl , mivel
−i · (1 + i)2 = −i · (1 + 2i − 1) = 2
és
zi zj = pj ,
ahol
zj
(4.3)
Gauss-prím. Ez
praktikus lesz a következ® tétel bizonyításánál.
4.1.3. Tétel (Két-négyzetszám tétel). oldható meg, ha (4.2)-ben
A (4.1) egyenlet akkor és csak akkor
∀i-re ci páros, és k Y
r2 (n) = 4
(bj + 1).
j=1
Bizonyítás:
A bizonyítás alapötlete az, hogy a (4.1)-et
(x + iy)(x − iy) = n x+iy és x−iy is Gauss-egész, amelyek egymás konjugáltjai. n és x + iy kanonikus alakját (felhasználjuk, hogy x + iy osztja n-et) konjugáljuk, összeszorozzuk x + iy -t és x − iy -t, és megnézzük milyen feltételek mellett jöhet ki n. Az eredmény pedig az lesz,
alakba hozzuk, ahol
A gondolatmenet a következ®: felírjuk
mint amit kimondtunk a tételben. A bizonyítás alatt végig feltesszük, hogy egyik prím sem egységszerese a másiknak. Mivel
x + iy
Gauss-egészekre), ezért
osztója
x + iy
n-nek
(felhasználva a számelmélet alaptételét
kanonikus alakja a következ®képpen néz ki: 0
b0
b0
00
00
c0
c0
x + iy = (1 + i)a · z11 z1 b1 · ... · zkk zk bk · q11 · ... · ql l , ahol
egység, és minden kitev® legfeljebb akkora, mint (4.3)-ban. Ezt konjugálva
kapjuk azt az eredményt, hogy 0
b00
b00
0
0
c0
c0
x − iy = (1 − i)a · z11 z1 b1 · ... · zkk zk bk · q11 · ... · ql l , Az utóbbit még tudjuk átalakítani, mivel
i)
a0
0
0
, és így kanonikus alakba hoztuk. Összeszorozva a két fenti számot kapjuk azt, hogy 0
0
n = (x + ix)(x − iy) = (−i)a (1 + i)2a · b0 +b00 1
·z11
00
0
b0 +b00 k
z1 b1 +b1 · ... · zkk
00
0
2c01
zk bk +bk · q1
2c0l
· ... · ql
és ennek az eredménynek kell egyenl®nek lennie a (4.3)-beli felbontással.
25
0
(1 − i)a = ((−i)(i + 1))a = (−i)a (1 +
Ebb®l következik, hogy ez csak az
a0 = a, b0j + b00j = bj
és a
cj
mellett teljesülhet. Ez pontosan azt jelenti, hogy minden a tétel els® állítása. A
, b0j -k
b00j -k
és
2c0j = cj
feltételek
kitev® páros, ami
azonban szabad paraméterek, amik a
megoldások számát befolyásolják.
megválasztására 4 opció van, b0j a 0, ..., bj értékek között mozog, b00j 0 pedig bj kiválasztása után egyértelm¶, ezért az egyenlet megoldásainak a száma Qk 4· j=1 (bj + 1)-gyel egyenl®. Mivel
Létezik másik bizonyítás is ugyanerre a tételre, ami hasonlít a Partíciószámok cím¶ fejezetben használt hatványsoros el®állításokra. Ez a bizonyítás felhasználja a Jacobi-theta függvényt:
ϑ(x) = 1 + 2x + 2x4 + ... =
∞ X
xm
2
m=−∞ Ekkor
ϑ(x)2 -r®l
belátható, hogy el®áll mint:
ϑ(x)2 = (1+2x+2x4 +...)(1+2x+2x4 +...) = 1+4x+4x2 +4x4 +8x5 +4x8 +... = x x3 x5 = 1 + 4(x + x2 + x4 + ...) = 1 + 4 − + − ... (4.4) 1 − x 1 − x3 1 − x5 De
ϑ(x)2 -re
el®állítható
igaz az is, hogy
n,
xn
együtthatója pontosan annyi, ahányféleképpen
mint két négyzetszám összege. A fenti formulát átírhatjuk úgy,
hogy
ϑ(x)2 = 1 + 4
∞ X
(−1)i
i=0 ∞ X
=1+4
∞ X
∞ ∞ X X x2i+1 (−1)i x(2i+1)j = = 1 + 4 1 − x2i+1 i=0 j=1
(−1)
d−1 2
xdj = 1 +
∞ X n=1
d=1, 2-d j=1
X
4
(−1)
d−1 2
xn .
d|n, 2-d
Az utolsó el®tti egyenl®ségnél átírtuk úgy a szummát, hogy
d csak a páratlan
számokat fussa be, az utolsó egyenl®ségnél pedig megfordítottuk az összegzés sorrendjét. A legutolsó formulából már látszik, hogy
n 6= 0),
xn
együtthatója (ahol
azaz a (4.1)-es feladat megoldásainak a száma
r2 (n) = 4
X
(−1)
d−1 2
= 4 · (d4m+1 − d4m−1 ),
d|n, 2-d ahol
d4m+1
(illetve
d4m−1 ) n-nek
a
4m + 1
(illetve
4m − 1)
alakú osztóinak a
számát jelenti. Ez ugyanaz az eredmény, mint amit az el®z®leg kaptunk. Legyenek ugyanis
n kanonikus alakjában pi -k 4k + 1, a qj -k pedig 4k − 1 alakú prímek, és minden qi páros hatványon szerepel. Ahhoz az osztóhoz, amiben a q1 a 2s − 1-ediken szerepel, hozzápárosítjuk azt, amiben a q1 a 2s-ediken szerepel. Ezután minden olyan osztóhoz, amiben q2 a páratlan hatványon szerepel, q1 pedig nincs benne, rendeljük hozzá azt az osztót, ami csak abban különbözik, hogy q2 az eggyel nagyobb hatványon szerepel. Hasonlóan folytatjuk minden qi -re. Ekkor minden 4k + 1 alakú osztóhoz hozzárendeltünk egy 4k − 1 alakú osztót. Ezért a fenti 26
különbségben azok az osztók maradnak, amikben nem szerepel
4k − 1
alakú
prím, ezeknek a száma pedig a Két-négyzetszám tételben kapott eredmény. Ramanujan egyik nagy eredménye az volt, hogy elemi bizonyítást talált a (4.4)-es formulára. A
k = 3, k = 4
esetre is léteznek tételeink:
4.1.4. Tétel (Három-négyzetszám tétel). Egy kor áll el® három négyzetszám összegeként, ha nem
n pozitív egész pontosan akn = 4k (8m + 7) alakú.
4.1.5. Tétel (Négy-négyzetszám tétel). Minden négyzetszám összegeként, a megoldások száma pedig: ( P 8 d|n d r4 (n) = P 24 d|n, 2-d d
ha ha
n n
páratlan; páros.
Ebb®l következik, hogy minden 4-nél magasabb mint
k
n pozitív egész el®áll négy
k -ra
is igaz, hogy
n
el®áll,
db négyzetszám összege, azonban a megoldások száma azonban még
k = 4
mindig érdekes kérdés. A
esetre létezik a 2-höz hasonló hatványsoros
el®állítás is, ahol a Jacobi-theta függvény 4. hatványának segítségével dolgozunk.
(4.1) kapcsán, hogy mennyi az r2 (n) függvény át-
Érdekes kérdés lehet még a
lagértéke. Ehhez egy geometriai megoldást adunk, ahol úgy tekintünk az egyenletre, mint egy Ekkor
√
r2 (n)
n
sugarú, origó középpontú körre.
megadja azt is, hogy
hány rácspont (azaz egész koordinátájú pont) található a rön. Ekkor
√
Pn
i=1 r2 (i)
n
sugarú kö-
becsülhet® az
összes olyan rácspont számával, ami a körön belül található, azaz olyan et és
y -t
x2 + y 2 ≤ n, A
x-
keresünk, amire
rácspontok
x, y ∈ Z.
számát
úgy
becsül-
jük, hogy egységnégyzetet rajzolunk a pontok köré, és az így kialakult síkidom területét becsüljük. Ez körülbelül akkora, mint a
√
n
sugarú kör területe, a hibák nagysága pedig a
√ √ [ n − 0, 5; n + 0, 5]
sugarú
körgy¶r¶ területe, hiszen ez a köré- és
4.1. ábra.
belé írható kör különbsége.
Az n=16 eset
√ √ √ √ π · (( n + 0, 5)2 − ( n − 0, 5)2 ) = 2π n = O( n) Ebb®l következik, hogy
n X
√ r2 (i) = π · n + O( n).
i=1 Azaz megkaptuk az átlagértékre azt, hogy
Pn
i=1 r2 (i)
n
1 = π + O( √ ) =⇒ n 27
Pn
i=1 r2 (i)
n
∼ π.
4.2. Waring-problémakör Waring-problémakörnek nevezzük azt az általa megfogalmazott sejtést, hogy ha
k tetsz®leges pozitív egész, akkor létezik hozzá egy g = g(k) szám, amire teljesül, hogy minden n el®áll, mint g db nemnegatív egész k -adik hatványa. Azaz létezik x1 , ..., xg ∈ N, hogy n = xk1 + xk2 + ... + xkg . Természetesen
g(k)
nem függ
n-t®l.
Az el®bbiek alapján
g(2) = 4.
Waringnak
a sejtését ugyan Hilbert igazolta 1909-ben, de megoldatlan probléma maradt a
g(k)
pontos értéke. Ebben a témakörben alkotott Ramanujan, Hardy és Litt-
lewood segítségével. Itt is nagyon jól megmutatkozik, hogy Ramanujan újszer¶ gondolkozásmódja hatásosnak volt klasszikus számelméleti problémákkal szemben. A hatványsoros el®állításoknál sokszor használt gondolatot alkalmazva, vették a következ® függvényt k
k
k
h(x) = 1 + x1 + x2 + ... + xm , majd a
h(x)b -t,
ahol
b
tetsz®leges pozitív egész. Ekkor ha
h(x)b
minden együtt-
hatója pozitív, az pontosan azt jelenti, hogy minden szám el®áll, mint
k -adik
hatvány összege. Ebb®l következik, hogy
g(k) ≤ b.
b
db
Itt alkalmazták Ra-
manujan ötletét, és ezzel nyerték az els® explicit korlátot, tehát azt, hogy elég nagy
n
esetén
g(k) ≤ (k − 2) · 2k−1 + 5, ∀k ≥ 2. A másik irányban könnyen adódik a következ® tétel:
4.2.1. Tétel.
$ % k 3 −2 g(k) ≥ 2k + 2
Bizonyítás:
A bizonyításhoz minden k -hoz találni fogunk egy olyan k -tól függ® n-et, amihez pont ennyi k -hatvány szükséges. Legyen n a legnagyobb olyan c2k − 1 szám, ami kisebb, mint 3k . Megállapítható, hogy ekkor c nem lehet k nagyobb, mint b(3/2) c. k k Ekkor n el®állításhoz csak az 1 és 2 tagok használhatóak. Az olyan összek k állítás, ami a lehet® legkevesebb tagot használja fel, az c − 1 db 2 és 2 − 1 db 1-es összegéb®l áll, azaz
n = c · 2k − 1 = (c − 1)2k + 2k − 1. Mivel
c − 1 + 2k − 1 = 2k + c − 2,
ezért ebb®l következik, hogy
g(k) ≥ 2k + c − 2. Beírva
c
becslését, kapjuk azt, hogy
$ % k 3 g(k) ≥ 2k + − 2. 2 Ennek az egyenl®tlenségnek az a különlegessége, hogy általában egyenl®ség teljesül, és csaknem biztos, hogy nincsenek kivételek. Például megkapjuk a korábban említett 4 eredményt.
28
k
helyére 2-t írva
5. fejezet
Érdekességek 5.1. Ramanujan kongruenciák Ramanujan korában még nagyon keveset tudtak a partíciószámokról, például az is nyitott kérdés volt, hogy a
p(n) mikor páros, vagy mikor páratlan. Akko-
riban a partíciószámok táblázata a 200. tagig bezárólag készült el egy bizonyos McMahon ®rnagynak köszönhet®en. Ezt a táblázatot szemlélve, Ramanujantól megszokott módon, intuitívan sejtette meg a következ® tételben szerepl® kongruenciákat. Ezek is olyan tételek voltak, amelyeknek a f® nehézsége a kitalálásuk volt, de a bizonyításuk is sok meggondolást igényelt. Legel®ször a következ® kongruenciákat publikálta:
Tehát az
p(5m + 4) ≡ 0
(mod 5)
(5.1)
p(7m + 5) ≡ 0
(mod 7)
(5.2)
p(11m + 6) ≡ 0
(mod 11)
(5.3)
5m + 4, 7m + 6
és
11m + 6
alakú számok partíciója osztható 5-
tel, 7-tel, illetve 11-gyel. El®ször vegyük az (5.2)-es formula bizonyítását. Hardy Ramanujanról szóló el®adásában az (5.1)-es formula levezetése szerepel, ami alapján készítettem el a szakdolgozatomban ismertetett bizonxítást.
Bizonyítás:
Már korábban megállapítottuk, hogy a partíciószámok generátor-
függvénye
1 + p(1)x + p(2)x2 + ... + p(k)xk + ... = Mi ebben a hatványsorban vizsgáljuk a a bizonyítás szempontjából egyszer¶bb az
x2 -tel
1 (1 − x)(1 − x2 )...(1 − xk )...
(5.4)
7m + 5 alakú számok partícióját, de x7m+7 alakú számokkal dolgozni. Ha
végig szorozunk, kapjuk, hogy
F (x) = x2 + p(1)x3 + p(2)x4 + ... + p(k)xk+2 + ... = ahol az
x7m+7
együtthatója
p(7m + 5).
Az
F (x)-et
x2 (1 − x)...(1 − xk )...
(5.5)
tovább alakítjuk a vizsgá-
lat könnyítése végett két (Ramanujan zsenialitását sejtet®) ötlettel. El®ször is elvégezzük az alábbi átalakítást:
x2 x2 k 6 = ((1 − x)...(1 − x )...) (1 − x)...(1 − xk )... ((1 − x)...(1 − xk )...)7 29
(5.6)
Majd az alábbi három szorzatra bontjuk:
(1 − x7 )(1 − x14 )... 1 · k 7 7 ((1 − x)...(1 − x )...) (1 − x )(1 − x14 )...
x2 ((1 − x)...(1 − xk )...)6 ·
(5.7)
Ezt a három tényez®t vizsgáljuk a következ®kben, legel®ször a második szor-
(1 − x)−n függvény binomiális sorát megkapjuk úgy, hogy ∞ ∞ X X −n (−n)(−n − 1) · ... · (−n − k + 1) · (−1)k xk = (−x)k = k! k
zótényez®t. Az
k=0
k=0
=
∞ X n+k−1 k ·x = x . k
∞ X (n)(n + 1) · ... · (n + k − 1)
k
k!
k=0
k=0
n = 7-re alkalmazva megkapjuk azt, hogy ∞ ∞ ∞ X 1 6 + k k X 6 + k k X (6 + k) · ... · (1 + k) k = x ·x . = x = (1 − x)7 k 6! 6
Ezért ezt
k=0
k=0
k=0
(5.8) Itt minden együttható osztható 7-tel, kivéve az
1, x7 , x14 , ...
alakúakat, amik 1
maradékot adnak. A nevez®ben ugyanis hat egymást követ® szám szorzata van, ami a
k = 7i esetekben nem tartalmaz 7-tel osztható számot, viszont a 0-n kívül
minden más maradékosztályt igen. Ez alapján
1 1 ≡ (1 − x)7 1 − x7
(mod 7)
Tehát a két hatványsor tagonként megegyezik mértani sor
x7
Z7
(5.9)
felett, mivel a jobb oldal egy
kvócienssel. Átszorzással kapjuk azt az eredményt, hogy
1 − x7 ≡1 (1 − x)7 Ezt alkalmazva
x-re, x2 -re, x3 -re
(mod 7)
(5.10)
stb. kapjuk azt, hogy
(1 − x7 )(1 − x14 )... (1 − x7 )...(1 − x7k )... = ≡1 k 7 ((1 − x)...(1 − x )...) (1 − x)7 ...(1 − xk )7 ...
(mod 7)
(5.11)
Végezetül vizsgáljuk meg a legutolsó szorzótényez®t. Err®l megállapíthatjuk, hogy
∞ X 1 7 14 14 28 = (1 + x + x + ...)(1 + x + x + ...)... = p(n)x7n , (1 − x7 )(1 − x14 )... n=1 (5.12) mert a bal oldal azt az re, hogy
f (m) függvényt generálja, amely azt fejezi ki egy adott m-
m hányféleképpen fejezhet® ki 7-tel osztható számok összegeként. Mivel
csak 7-tel osztható számok állíthatók el® 7-tel osztható számok összegeként, ezért
7n = m
esetén
n
egész, és
x7n
együtthatója
p(n). G(x).
Most vizsgáljuk az els® szorzótényez®t, ami legyen
Ehhez szükségünk
lesz a Jacobi formulára, aminek a bizonyítását most nem részletezzük.
{(1 − x)(1 − x2 )(1 − x3 )...}3 =
∞ k2 +k 1 X (−1)k (2k + 1)x 2 2 k=−∞
30
(5.13)
Átalakítva a
G(x)-et
és felhasználva a Jacobi formulát a következ® ered-
ményhez jutunk:
G(x) = x2 {(1 − x)(1 − x2 )...}6 = x2 ({(1 − x)(1 − x2 )...}3 )2 = ∞ ∞ j 2 +j i2 +i 1 X X = (−1)i+j (2j + 1)(2i + 1)x2+ 2 + 2 4 i=−∞ j=−∞ Az (5.14) egyenletben az
x7m+7
(5.14)
alakú tagok együtthatóit kell vizsgálnunk,
x7k
ugyanis a második szorzótényez® 1, a harmadik pedig csak
alakú számokból
áll, tehát ahhoz, hogy a szorzatban a 7-tel osztható kitev®j¶ számokat kapjuk, itt is olyanokat kell venni. Feltettük tehát, hogy
2+
i2 + i j 2 + j + 2 2
osztható 7-tel. Szorozva 8-cal, és elvégezve a teljes négyzetté alakítást, kapjuk azt, hogy
i2 + i j 2 + j + − 14. (2j + 1)2 + (2i + 1)2 = 8 2 + 2 2 Mivel a jobb oldal oszható 7-tel, ezért a bal oldal is. Felhasználva azt, hogy
(2i + 1)2 ≡ 0, 1, 2, 4
(mod 7),
két ilyen szám összegeként csak úgy jöhet ki 7-tel osztható, ha mindkett® osztható 7-tel (azaz mindkett® 0-val kongruens (mod 7)). Ekkor az (5.14) egyenletben
(2i + 1)(2j + 1)
is osztható 7-tel (s®t 49-cel is), ami az
x7m+7
alakú számok
együtthatója. A három szorzótényez® ismeretében az számoknál (az
m-hez
megfelel®
i-re
és
F (x)
együtthatója az
x7m+7
alakú
j -re)
(−1)i+j (2j + 1)(2i + 1) · 1 · p(m + 1). Az els® tényez®r®l most állapítottuk meg, hogy osztható 7-tel. A legelején tett megfontolás alapján ha az tója osztható 7-tel, akkor
F (x) függvényben p(7m + 5) is.
az
x7m+7
alakú számok együttha-
Ramanujan kés®bb kimondott ennél kicsit többet is. Az
52 és 72 modulusokra
bebizonyította, hogy
p(25m + 24) ≡ 0 p(49m + 47) ≡ 0
(mod 52 )
(5.15)
2
(mod 7 )
Ramanujan azt sejtette, hogy valami hasonló m¶ködik
(5.16)
5a , 7b
és
11c
mo-
dulusokra is, ez azonban vegyes eredményeket hozott. A sejtése az volt, hogy
δ =5a · 7b · 11c
és
24n ≡ 1
(mod δ)
esetén
p(δ · m + n) ≡ 0 minden
(mod δ)
m-re. Ez tartalmazza az (5.1)-es, (5.2)-es, (5.3)-as, (5.15)-ös és az (5.16)(5.1)-es esetében δ =5, n=4, ekkor
os kongruenciákat is. Például az
24 · 4 = 96 ≡ 1 31
(mod 5)
is teljesül. Kés®bb már
δ =73
esetén találtak ellenpéldát. Ugyanakkor Krecmar
belátta, hogy
p(125m + 99) ≡ 0
(mod 53 )
és Watson is bizonyított egy állítást általános
5a
modulusra.
Ugyanabban a publikációban, ahol a kongruenciákról ír, Ramanujan közölt két azonosságot is, bizonyítás nélkül.
p(4) + p(9)x + p(14)x2 + ... = 5 ·
{(1 − x5 )(1 − x10 )(1 − x15 )...}5 {(1 − x)(1 − x2 )(1 − x3 )...}6
p(5) + p(12)x + p(19)x2 + ... = 7 · + 49x ·
(5.17)
{(1 − x7 )(1 − x14 )(1 − x21 )...}3 + {(1 − x)(1 − x2 )(1 − x3 )...}4
{(1 − x7 )(1 − x14 )(1 − x21 )...}6 {(1 − x)(1 − x2 )(1 − x3 )...}7
(5.18)
Ha ezekre az azonosságokra gondolunk, akkor képünk lehet arról, hogy Ramanujan hogyan sejthette meg intuitívan az
(5.17)
és
(5.18)
(5.1)
és
(5.2)
kongruenciákat. Az
egyenlet bizonyítását Ramanujan kés®bb sem közölte, kés®bb
Mordell és Darling belátta ®ket.
5.2. Rogers-Ramanujan azonosságok Ramanujan munkássága kapcsán említésre méltók még a Rogers-Ramanujan azonosságok. Ezeket eredetileg a Leonard James Rogers névre hallgató matematikus publikálta és bizonyította be 1894-ben, ám ez nem sok gyelmet kapott. Kés®bb Ramanujan maga is felfedezte ®ket 1913-ban, de bizonyítása nem volt rá. Amikor 1917-ben régi matematikai kiadványok között kutatott, akkor talált rá Rogers munkájára, majd közös munkába kezdtek, és sikerült egy egyszer¶bb bizonyítást találniuk. Ugyanekkor Schur is elkezdett foglalkozni az azonosságokkal, miután felfedezte ezeknek egy egyszer¶ kombinatorikai interpretációját. Jelenleg több bizonyítás is létezik, de egyik sem egyszer¶, és újszer¶ ötleteken alapszik. A két azonosság a következ®képpen néz ki: 2
1+
x x4 xm + + ... + + ... = 2 1 − x (1 − x)(1 − x ) (1 − x)(1 − x2 )...(1 − xm )
1 (1 − x)(1 − x6 )...(1 − x5m+1 )...(1 − x4 )(1 − x9 )...(1 − x5m+4 )...
(5.19)
és
1+
x2 x6 xm(m+1) + + ... + + ... = 1 − x (1 − x)(1 − x2 ) (1 − x)(1 − x2 )...(1 − xm ) 1
(1 −
x2 )(1
−
x7 )...(1
−
x5m+2 )...(1
− x3 )(1 − x8 )...(1 − x5m+3 )...
Ezek is Ramanujan-szer¶en szép formulák, hiszen az azonosságok egyáltalán nem triviálisak. A bal oldal és a jobb oldal viszonya is érdekes, hiszen a jobb oldal annak az
f (n)-nek
a generálófüggvénye, ami minden
32
n-re
megadja azt,
n-nek hány olyan partíciója 5m + 3) alakú számokból áll.
hogy
van, ami
5m + 1
és
5m + 4
(illetve
Az (5.19) formula bal oldala pedig azt adja meg, hogy adott
5m + 2
és
n-re hány olyan
partíció van, amelynek a tagjai között a minimális különbség 2. Ennek vizsgálatához el®ször tekintsük az 2
xm (1 − x)(1 − x2 )...(1 − xm ) kifejezést. Ez megadja azt, hogy minden tagja legfeljebb
m.
n − m2 -nek
hány olyan partíciója van, aminek
Ismeretes, hogy minden
m2 -re
igaz, hogy
m2 = 1 + 3 + 5 + ... + (2m − 1). Vegyük ezért
n − m2 -nek
egy olyan partícióját, ami legfeljebb
és a pontsémájához soronként illesszük hozzá
m2
m
tagból áll,
felbontásából a tagokat, mint
ahogy az alábbi ábrán látszik.
Ekkor
n-nek
egy olyan felbontását, kapjuk, aminek a tagjai között a mini-
mális különbség 2. Ha az összes lehetséges
m-re
vesszük az ilyen partíciókat,
akkor az (5.19) egyenlet jobb oldalát kapjuk, tehát
n-nek
az összes olyan partí-
cióját, aminek a tagjai között a minimális különbség 2. Ez tehát egy kölcsönösen egyértelm¶ megfeleltetés.
33
Irodalomjegyzék [1] G. H. Hardy,
Twelve lectures on subjects suggested by his life and work,
Cambridge university press, 1940. [2] Marcus du Sautoy,
A prímszámok zenéje, Park Könyvkiadó, 2014.
Egy különös életút, Ramanujan, 7. fejezet, In: Freud Róbert Nagy pillanatok a matematika történetében, Gondolat Kiadó, 1981.
[3] Turán Pál, (szerk.),
[4] Freud Róbert-Gyarmati Edit,
Számelmélet, Nemzeti Tankönyvkiadó, 2000.
34
