Solmu 2/2015 1
Osittaissummauksella ikävien summien kimppuun
Anne-Maria Ernvall-Hytönen
Matematiikan ja tilastotieteen laitos, Helsingin yliopisto
Kuvitellaan, että pihalla leikkii lapsia, joilla jokaisel- la on yhtä monta palloa kuin ikää vuosina. Naapuriin muuttaa lapsia, joilla ei ole lainkaan palloja. Solidaari- suuden nimissä lapset päättävät antaa naapureille osan palloistaan. Koska olisi kohtuutonta, jos kaikki luopui- sivat yhtä monesta pallosta, kun niitä ei alun perinkään yhtä monta ollut, päätetään, että jokainen lapsi jät- tää itselleen (kokonaislukuun pyöristettynä) sen mää- rän palloja, mikä jää, kun oma alkuperäinen pallomää- rä jaetaan oman iän luonnollisella logaritmilla (paitsi yksi- ja kaksivuotiaiden palloihin ei kosketa). Siispä, jos lapsen ikä on vaikka 5, alun perin hänellä on vii- si palloa, ja lahjoituksen jälkeen ln 55 ≈3,1 ≈3 palloa.
Kuinka monta palloa lapsille karkeasti ottaen jää yh- teensä?
Oletetaan yksinkertaisuuden vuoksi, että pihalla on vain vähintään kolmevuotiaita lapsia. On helppo las- kea, että jos alun perin pallomäärät (eli iät) ovat nouse- vassa järjestyksessäa1, a2, . . . , ak, ja niitä on yhteensä N kappaletta, niin uusi pallomäärä on
a1 lna1
+ a2 lna2
+· · ·+ ak lnak
≥ a1 lnak
+ a2 lnak
+· · ·+ ak lnak
= 1
lnak
(a1+a2+· · ·+ak) = N lnak
, mikäli ei välitetä pyöristyksistä. Samoin saadaan, että pallomäärä on korkeintaanlnNa
1 (jälleen mikäli ei välite- tä pyöristyksistä). Mikäli luvuta1jaak(eli nuorimman
ja vanhimman iät) ovat lähellä toisiaan, on näin saatu varsin hyvät arviot summalle. Jos lukujena1 jaak ero on huomattava, on tuloksessakin heittoa. Esimerkiksi, jos lasten iät ovat 3,4, . . . ,17, niin alun perin palloja on 3 + 4 +· · ·+ 17 = 150, ja 150ln 3 ≈137 ja ln 17150 ≈53.
Näiden tulosten välillä on valtava ero. Kumpi näistä on lähempänä totuutta? Ovatko molemmat päin honkia?
Koska luvut ovat varsin pieniä, voidaan helposti laskea pallojen todellinen määrä. Kolmevuotiaalla on ln 33 ≈ 2,7 ≈ 3 palloa, nelivuotiaalla ln 44 ≈ 3 palloa, ja niin edelleen. Yhteensä 66 palloa. Pienempi raja oli siis sel- västi parempi, ja se ei itse asiassa edes ollut täysin päin honkia, vaikkakaan ei ihan oikeinkaan.
Tällaisten summien käsittelyynosittaussummauson oi- va työkalu. Esitellään seuraavissa luvuissa osittaissum- maus formaalisti ja todistetaan se, käsitellään yhteys osittaisintegrointiin, ja lopuksi käydään läpi muuta- ma esimerkki, mukaan lukien lukuteoreettinen sovel- lus. Mikäli osittaisintegrointi on täysin vierasta, voi jät- tää lukematta sen osan tekstiä, joka liittää osittaissum- mauksen osittaisintegrointiin. Tekstin muun osan ym- märtäminen ei vaadi tämän osan lukemista.
Osittaissummauksen pääperiaate
Esitän osittaissummauksen kuten se Inghamin kirjassa [1] on sivulla 18 esitetty vain hieman notaatiota muut- taen:
2 Solmu 2/2015
Lause.Olkoonλ1, λ2, . . . kasvava jono reaalilukuja, jo- ka lähestyy ääretöntä. Olkoon
A(x) = X
λn≤x
an,
missä luvut an voivat olla reaalisia tai kompleksisia.
Jos X ≥λ1 ja funktiolla f(x) on jatkuva derivaatta.
niin X
λn≤X
anf(λn) =A(X)f(X)− Z X
λ1
A(x)f0(x)dx.
Todistus.Todistus on varsin yksinkertainen, ja se pe- rustuu alkuperäisen summan ja terminA(X)f(X) ero- tukseen:
A(X)f(X)− X
λn≤X
anf(λn)
= X
λn≤X
an(f(X)−f(λn)).
Koska funktiof on jatkuvasti derivoituva, voidaan kir- joittaa
f(X)−f(λn) = Z X
λn
f0(x)dx, jolloin
A(X)f(X)− X
λn≤X
anf(λn)
= X
λn≤X
an
Z X
λn
f0(x)dx,
jolloin integrointi- ja summausjärjestystä vaihtaen (Harjoitustehtävä: piirrä kuva muuttujien suuruuksista tai muutoin vakuuta itsesi, että näin todella on):
X
λn≤X
an
Z X
λn
f0(x)dx= Z X
λ1
X
λn≤x
anf0(x)dx
= Z X
λ1
A(x)f0(x)dx, ja väite on todistettu.
Käytännössä jonoλn on usein esimerkiksi λn = ntai alkuluvuista koostuva jono, mutta lauseen määrittely antaa mahdollisuuden määritellä jonon paljon mieliku- vituksellisemmillakin tavoilla.
Yhteys osittaisintegrointiin
Aluksi varoituksen sananen: hetken päästä puhun su- juvasti epäjatkuvien funktioiden integraaleista. Tällais- ten funktioiden integraalia ei välttämättä pysty mää- rittelemään millään nätillä kaavalla. Silti muutoin riit- tävän siististi käyttäytyvät epäjatkuvat funktiot ovat
usein integroituvia (ehtoja integroituvuudella käsitel- lään yliopiston kursseilla).
Osittaissummaus on osittaisintegroinnin diskreetti vas- tine: Siinä missä positiivisen funktiong integraali mit- taa funktion ja x-akselin väliin jäävän alueen pinta- alaa, summa funktion arvoista mittaa sellaista pinta- alaa, joka saadaan muodostamalla funktion arvojen korkuisia ja ykkösen levyisiä palkkeja. Voi myös ajatel- la niin, että jos funktiog on määritelty kokonaisluku- pisteissä, niin täydennetään siitä kaikilla reaaliluvuilla määritelty funktio siten, että määrätääng(x) =g(bxc).
Näin summauksen ja integroinnin yhteys on ilmeinen.
Osittaisintegrointihan toimii seuraavasti:
Z b
a
g(x)f(x)dx=
b
.
a
G(x)f(x)− Z b
a
G(x)f0(x)dx, missä G0(x) = g(x). Osittaissummauksen tilanteessa funktio f ei muutu mitenkään. Sen sijaan funktio g pitää ajatella kokonaislukupisteissä määriteltynä funk- tiona (tai siitä reaaliluvuille kaavalla g(x) = g(bxc) yleistettynä) ja G(x) puolestaan summafunktiona tai yleistetyn funktion integraalina. Osittaissummaukses- sa alasijoitukset jäävät pois, sillä summa on siellä tyh- jä (eli osittaissummauksessaG(a) = 0).
Kuinka suuri on kertoma?
Luvun n kertoma, jota merkitään n!, on lukujen 1,2, . . . , ntulo, eli
n! = 1·2·3· · ·n= Y
1≤m≤n
m.
Ensimmäinen ajatus tätä lukua tuijottaessa ainakin minulle itselleni alun perin oli, että sen on pakko ol- la tuhottomasti pienempi kuinnn. Alarajan määrittä- minen tuntui paljon hankalammalta. Esimerkiksi arvio n!≥1n = 1 tarjoaisi kyllä alarajan, mutta yleisesti ot- taen tämä alaraja on aivan valtavan huono. Tarkastel- laan nyt tätä lukua tarkemmin. Otetaan aluksi tulosta logaritmi:
lnn! = X
1≤m≤n
lnm.
Tämän summan voi joko arvioida edellisen Solmun nu- meron opeilla integraalien avulla, tai sitten voidaan hyödyntää osittaissummausta.
Osittaissummauksen notaatiota käyttäen am = 1 ja f(x) = lnx. Nyt
X
1≤m≤n
lnm= X
1≤m≤n
amf(m)
=f(n) X
1≤m≤n
am− Z n
1
X
1≤m≤x
am
! f0(x)dx
=nlnn− Z n
1
bxc x dx.
Solmu 2/2015 3
Nyt saadaan helpolla arviolla Z n
1
bxc x dx≤
Z n
1
1dx=n−1< n.
Siispä lnn! ≥nlnn−n, eli n! ≥ nen
, joten oikeas- taannnei ole yhtään hullumpi arvio luvullen!, vaikka se reilusti yläkanttiin onkin.
Lapset jälleen pihamaalla
Palataan nyt alun esimerkkiin ja solidaarisiin lapsiin leikkimässä pihamaalla ja jakamassa pallojaan. Olete- taan, että lasten iät ovat 3,4,5, . . . , n, ja tarkastellaan miten pallojen määrä käyttäytyy, kun n kasvaa. (On ehkä syytä olettaa, että eletään jollain mystisellä pla- neetalla, jolla täysikäisyyden raja on ääretön, eli kaikki ovat lapsia iästä riippumatta.)
Lapsen, jonka ikä onkvuotta, pallomäärä on lnkk pyö- ristettynä kokonaislukuun. Lapsia on allenkappaletta, joten jos unohdetaan pyöristykset ja eletään ikään kuin pallomäärä olisi lnkk, niin virhe on korkeintaan luvunn kokoinen kaikilta lapsilta yhteensä.
Muistetaan vielä, että niiden lasten, joiden ikä on kor- keintaanm, ikien summa on m(m+1)2 −3. Nyt
X
3≤k≤n
k
lnk = n(n+ 1) 2 lnn − 3
lnn
− Z n
3
X
3≤k≤x
k
!
· −1 x(lnx)2dx.
Huomataan ensinnäkin, että n(n+ 1)
2 lnn − 3 lnn
on hyvin tarkasti n(n+1)2 lnn , eli pallojen alkuperäinen määrä jaettuna logaritmilla. Keskitytään nyt integraa- lin arviointiin. Integraalin tarkka määrittäminen olisi viheliäinen tehtävä, joten pelataan likiarvoilla.
Nyt huomataan, että X
3≤k≤x
k≤ x(x+ 1) 2 −3,
kunxon mikä tahansa reaaliluku. Voidaan siis korvata integraali lausekkeella
− Z n
3
X
3≤k≤x
k
!
· −1 x(lnx)2dx
≤ Z n
3
x(x+ 1)
2 −3
· 1 x(lnx)2dx.
Termin Z n
3
3
x(lnx)2dx≤3 Z n
3
1
xdx≤3 lnn
vaikutus on hyvin pieni. Voidaan siis keskittyä inte- graalin
Z n
3
x(x+ 1)
2 · 1
x(lnx)2dx= Z n
3
x+ 1 2(lnx)2dx arviointiin. Koska olemme kiinnostuneita pallojen mää- rän käyttäytymisestä, kun n lähestyy ääretöntä, voi- daan olettaa √
n ≥ 3. Jaetaan integraali kahtia pis- teestä√
n, jolloin saadaan
Z n
3
x+ 1 2(lnx)2dx=
Z
√n
3
x+ 1 2(lnx)2dx+
Z n
√n
x+ 1 2(lnx)2dx.
Ensimmäinen palikka on hyvin helppo arvioida:
Z
√n
3
x+ 1
2(lnx)2dx≤n, koska integroitava on pienempi kuin √
n, kuten myös integraalin pituus. Toinen termi yksinkertaistetaan lo- garitmin avulla. Tässä ei edes menetetä paljon tark- kuutta, sillä logaritmi kasvaa hyvin hitaasti. Siispä
Z n
√n
x+ 1 2(lnx)2dx≤
Z n
√n
x+ 1 2(ln√
n)2dx
= 2
(lnn)2 Z n
√n
(x+ 1)dx
≤ 2
(lnn)2 ·(n+ 2)n
2 = (n+ 2)n (lnn)2 . Luvun nkasvaessa tämä viimeksi saatu termi on suu- rin virhetermeistä. Kuitenkin sekin on selvästi pienem- pi kuin n(n+1)2 lnn , joten pallojen määrä jaettuna suurim- malla logaritmilla osoittautuu varsin hyväksi arvioksi, kun lasten iät ovat peräkkäisiä kokonaislukuja, ja van- hin lapsista on hyvin vanha.
Pienimmän yhteisen jaettavan suuruus- luokka
Tarkastellaan miten suuri on sellainen luku, joka on nensimmäisen positiivisen kokonaisluvun pienin yhtei- nen jaettava, eli joka on pienin positiivinen kokonaislu- ku, joka on jaollinen kaikilla luvuista 1,2, . . . , n. Huo- mataan aluksi (väitteen varmistaminen jätetään har- joitustehtäväksi), että tämän luvun pitää olla muotoa
Y
p≤n, palkuluku
pblogpnc.
Koska blogpnc = 1, kun √
n < p ≤ n, voidaan tulo kirjoittaa tulon
Y
p≤√
n, palkuluku
pblogpnc
4 Solmu 2/2015
ja tulon
Y
√n<p≤n, palkuluku
p
tulona. Aloitetaan tarkastelu jälkimmäisestä termistä.
Tämän käsittely on lähes samanlainen kuin kertoman- kin tapauksessa. Yksinkertaisuuden vuoksi otetaan tu- losta logaritmi, jolloin saadaan se muunnettua sum- maksi:
ln Y
√n<p≤n, palkuluku
p= X
√n<p≤n, palkuluku
lnp.
Alkulukulause on hyvin syvällinen tulos (sitä ei todis- teta tässä, mutta tulos löytyy useista analyyttisen lu- kuteorian kirjoista), joka kertoo, kuinka paljon annet- tua lukua pienempiä alkulukuja on. Sen nojalla lukua xpienempiä alkulukuja on
x
lnx+o x lnx
, missä o lnxx
tarkoittaa, että sitä vastaavan virheter- min ja luvun lnxx osamäärä lähestyy nollaa, kunxlä- hestyy ääretöntä. Lukujen√
nja nvälissä on siis n
lnn+o n lnn
−
√n ln√
n−o √
n ln√ n
= n
lnn+o n lnn
alkulukua. Osittaissummauksen avulla X
√n<p≤n
lnp= lnn· n
lnn+o n lnn
− Z n
√n
x
lnx+o x lnx
x−1dx
=n+o(n)− Z n
√n
1 lnx+o
1 lnx
dx.
Integraalin voi käsitellä usealla tavalla riippuen siitä, mitä tarkkuutta tavoitellaan. Kuitenkin koska pääter- mi onn, ja ensimmäinen virhetermi o(n), olisi turhaa kikkailua käyttää energiaa saadakseen integraalille tar- kan arvon. Voidaan siis helposti arvioida:
Z n
√n
1 lnx+o
1 lnx
dx
≤ Z n
√n
1 ln√
n+o 1
ln√ n
dx
≤ n ln√
n+o n
ln√ n
=o(n).
Olemme nyt saaneet valmiiksi suurten alkulukujen osuuden määrittämisen. Nyt voidaan siirtyä pieniin al- kulukuihin, eli tuloon
Y
p≤√
n, palkuluku
pblogpnc.
Otetaan ensimmäiseksi tästäkin logaritmi:
ln Y
p≤√
n, palkuluku
pblogpnc= X
p≤√
n, palkuluku
blogpnclnp.
Ennen kuin jatketaan pidemmälle, halutaan päästä eroon alaspäinpyöristyksistä. Tämä voidaan tehdä yk- sinkertaisesti seuraavasti:
X
p≤√
n, palkuluku
blogpnclnp
= X
p≤√
n, palkuluku
logpnlnp
− X
p≤√
n, palkuluku
(logpn− blogpnc) lnp.
Viimeisen rivin termistä tulee virhetermi:
X
p≤√
n, palkuluku
(logpn− blogpnc) lnp
≤ X
p≤√
n, palkuluku
lnp,
ja samoin kuin suurten alkulukujen kontribuutiota määritettäessä saadaan
X
p≤√
n, palkuluku
lnp=√
n+o(√
n) =o(n).
Voidaan siirtyä summan X
p≤√
n, palkuluku
logpnlnp
tarkastelemiseen. Huomataan ensin, että logpn=lnn
lnp, jolloin summa sievenee helposti
X
p≤√
n, palkuluku
logpnlnp= lnn X
p≤√
n, palkuluku
1.
Alkulukulauseen nojalla X
p≤√
n, palkuluku
1 =
√n ln√
n+o √
n ln√ n
,
joten
lnn X
p≤√
n, palkuluku
1 =o(n).
Täten pienimmän yhteisen jaettavan luonnollinen loga- ritmi on suuruusluokkaan+o(n), joten pienin yhteinen jaettava kasvaa hyvin karkeasti ottaen yhtä nopeasti kuinen.
Viitteet
[1] A. E. Ingham,The distribution of prime numbers.
Cambridge University Press, 1990.
