DEDEKINDOVE VSOTE IN KVADRATNI RECIPROCITETNI ZAKON REBEKA RENKO ZVER Prva gimnazija Maribor Math. Subj. Class. (2010): 11F20 Predstavili bomo Dedekindove vsote in z njimi povezano reciprocitetno formulo ter pokazali, kako je iz le-te možno izpeljati znani kvadratni reciprocitetni zakon. DEDEKIND SUMS AND THE QUADRATIC RECIPROCITY LAW We will introduce the Dedekind sums with a related reciprocity formula which will lead us to the derivation of the known quadratic reciprocity law. Uvod Dedekindove vsote so pomemben del klasične teorije števil in še danes po- gosto uporabljena tema tudi na drugih področjih matematike. Sestavni del njihove definicije je naslednja funkcija: Definicija 1 (Dvojni oklepaj). ((x)) = { x− [x]− 12 ; če x ni celo število, 0 ; če je x celo število, (1) kjer je [x] največje celo število, ki ne presega x ∈ R. Njen graf je žagaste oblike: Z uporabo dvojnega oklepaja (1) lahko definiramo najpomembneǰsi po- jem tega sestavka: Obzornik mat. fiz. 59 (2012) 6 205 Rebeka Renko Zver Definicija 2 (Dedekindove vsote). s(h, k) = k ∑ j=1 (( j k ))(( hj k )) , h ∈ Z, k ∈ N. (2) Dedekindove vsote so dobile ime po znanem nemškem matematiku Ri- chardu Dedekindu1. Ena njihovih glavnih lastnosti je simetričnost, predstavljena z naslednjo reciprocitetno formulo, ki je veljavna za tuji si naravni števili h, k: 12(s(h, k) + s(k, h)) = −3 + h k + k h + 1 hk . (3) Reciprocitetna formula je pomembna sama po sebi, koristna pa je npr. pri izpeljavi splošnega (Jacobijevega) kvadratnega reciprocitetnega zakona. V zvezi s tem se spomnimo Legendrovega simbola, pri katerem za vsako naravno število n in liho praštevilo p, ki ne deli n, velja ( n p ) = { 1 ; če obstaja tak x, da je x2 ≡ n (mod p), −1 ; sicer. Če pa dovolimo za n tudi negativna cela števila, pa lahko povemo, da velja: ( −1 p ) = { 1 ; če je p ≡ 1 (mod 4), −1 ; če je p ≡ 3 (mod 4). Ob upoštevanju multiplikativnosti Legendrovega simbola v n od tod sledi, da je dovolj poznati vrednosti simbola za naravne n. Vrednost (−1/p) pa je tesno povezana s predstavljivostjo praštevila p kot vsote dveh kvadra- tov naravnih števil. Jacobijev simbol potem definiramo (za poljubno naravno število n in za liho naravno število m, ki si je tuje z n in ima praštevilski razcep m = 1Julius Wilhelm Richard Dedekind (1831–1916) se je rodil v Braunschweigu v Nemčiji, kjer je obiskoval osnovno in srednjo šolo, študiral pa je na univerzi v Göttingenu in Berlinu. Doktoriral je leta 1852 pri Gaussu v Göttingenu kot njegov zadnji študent, habilitacijo pa je opravil leta 1854 v Berlinu istočasno z Riemannom, s katerim sta bila kasneje nekaj časa tudi učiteljska kolega. Vrnil se je v Göttingen, kjer je kot prvi poučeval Galoisovo teorijo. Kasneje je nekaj časa učil v Zürichu in nato do upokojitve 1894 v ro- dnem Braunschweigu. Znan je po svojem delu in rezultatih iz algebre (definicija idealov, algebraični dokaz Riemann-Rochovega izreka za kompaktne Riemannove ploskve), analize (prerezi kot model za realna števila) in teorije množic (definiciji neskončne množice). Na njegove matematične raziskave so največ vplivali Gauss, Dirichlet in Riemann, katerih zbrana dela je urejal. Zbrani in dopolnjeni Riemannovi zapiski so izšli leta 1876 s Hei- nrichom Webrom kot glavnim urednikom. Rokopisa, ki sta obravnavala teorijo eliptičnih modularnih funkcij, pa je uredil sam Dedekind [2]. 206 Obzornik mat. fiz. 59 (2012) 6 Dedekindove vsote in kvadratni reciprocitetni zakon ∏r j=1 pj na ne nujno različne prafaktorje) kot produkt ustreznih Legendrovih simbolov: ( n m ) = r ∏ j=1 ( n pj ) . Splošni kvadratni reciprocitetni zakon pravi, da za tuji si lihi na- ravni števili h in k z Jacobijevima simboloma ( h k ) in ( k h ) velja enakost ( h k )( k h ) = (−1) h−1 2 · k−1 2 . Pred leti je Obzornik že pisal [5] o posebnem primeru tega zakona, ko sta h in k različni lihi praštevili. V nadaljevanju bomo najprej spoznali nekatere elementarne lastnosti Dedekindovih vsot (2) in prek njih izpeljali reciprocitetno formulo (3). Nato bomo (ob privzetku posplošene Gaussove leme) z uporabo reciprocitetne formule dokazali splošni kvadratni reciprocitetni zakon, na koncu pa dodali še nekaj opomb o drugih vidikih Dedekindovih vsot. Dedekindove vsote in reciprocitetna formula Najprej dokažimo, da je funkcija dvojni oklepaj periodična in liha. Trditev 1. Za poljubno celo število n in poljubno realno število x velja: (a) ((x+ n)) = ((x)), (b) ((−x)) = −((x)). Dokaz. (a) Za celo število x je ((x + n)) = 0 = ((x)), sicer pa zaradi [x+ n] = [x] + n velja ((x+ n)) = x+ n− [x+ n]− 12 = x+ n− [x]− n− 1 2 = ((x)). (b) Za x ∈ Z je dokaz trivialen, za x /∈ Z pa rezultat sledi iz enakosti [x] + [−x] = −1. Sedaj se spomnimo pojma, ki ga bomo potrebovali v nadaljevanju. Popolni sistem ostankov po modulu k je taka množica celih števil P = {j1, j2, . . . , jk}, da je ji ≡ i (mod k) za vsak i = 1, 2, ..., k. Pri tem smo upoštevali, da velja k ≡ 0 (mod k), zato bomo posle- dično za popoln sistem ostankov po modulu k venomer uporabljali množico {1, 2, . . . , k}. V primeru, ko je h tuj proti k, je potem tudi hP = {hj1, hj2, ..., hjk} popolni sistem ostankov po modulu k, saj je hji ≡ hi (mod k) in je presli- kava i 7→ hi (mod k) v tem primeru injektivna, torej permutacija množice {1, 2, ..., k}. 205–216 207 Rebeka Renko Zver Trditev 2. Naj bo P poljuben popolni sistem ostankov po modulu k. Tedaj velja: (a) ∑ j∈P (( j k )) = k ∑ j=1 (( j k )) = 0. (b) Če je k naravno, h pa celo število, tuje proti k, je tudi k ∑ j=1 (( hj k )) = 0. (4) Dokaz. (a) Izberimo elemente iz popolnega sistema ostankov P in jih zapi- šimo v obliki: j1 = 1 + k · n1, j2 = 2 + k · n2, . . . jk−1 = (k − 1) + k · nk−1, jk = k · nk, kjer so n1, . . . , nk iz množice celih števil. Tedaj je po trditvi 1 ∑ j∈P (( j k )) = (( 1 k + n1 )) + (( 2 k + n2 )) + . . .+ (( 0 k + nk )) = k−1 ∑ j=1 (( j k )) . To pa je po definiciji 1 in dejstvu [ j k ] = 0 za 1 ≤ j < k naprej enako: k−1 ∑ j=1 (( j k )) = ( 1 k − 1 2 ) + ( 2 k − 1 2 ) + . . .+ ( k − 1 k − 1 2 ) = k(k − 1) 2k − k − 1 2 = 0. (b) Dokaz sledi iz točke (a), saj je tudi hP popolni sistem ostankov po modulu k. Opomba 1. Opazimo, da je zadnji člen v vsoti ∑k j=1 (( j k )) ali ∑k j=1 (( hj k )) enak nič, zato je vseeno, ali v takih vsotah seštevamo do k ali do k − 1. To bomo v nadaljevanju še večkrat upoštevali. 208 Obzornik mat. fiz. 59 (2012) 6 Dedekindove vsote in kvadratni reciprocitetni zakon Dokažimo še nekaj osnovnih lastnosti Dedekindovih vsot. Trditev 3. Imejmo poljuben popolni sistem P = {j1, j2, . . . , jk} ostankov po modulu k. Naj bo h poljubno celo, k pa naravno število, tuje s h. Tedaj velja: s(h, k) = ∑ j∈P (( j k ))(( hj k )) . Trditev pomeni, da je Dedekindova vsota s(h, k) v primeru tujih si števil h, k neodvisna od izbire popolnega sistema ostankov po modulu k. Doka- žemo jo na popolnoma enak način kot trditev 2, če le upoštevamo definicijo popolnega sistema ostankov po modulu k in periodičnost dvojnega oklepaja. V posebnem primeru je od izbire popolnega sistema ostankov P neod- visna tudi vsota s(1, k) = ∑ j∈P (( j k ))(( j k )) = ∑ j∈P (( j k ))2 . (5) Računanje Dedekindovih vsot pa se da še nekoliko poenostaviti; zapi- šemo jih lahko samo z enim dvojnim oklepajem. Trditev 4. Za vsako celo število h in naravno število k, ki si je tuje s h, velja: s(h, k) = k ∑ j=1 j k (( hj k )) . Dokaz. Zadnji člen v vsoti (2) je enak nič, tako da imamo: s(h, k) = k−1 ∑ j=1 (( j k ))(( hj k )) = k−1 ∑ j=1 ( j k − [ j k ] − 1 2 )(( hj k )) . Upoštevajmo, da je [ j k ] = 0, za j < k in enakost (4), pa dobimo: s(h, k) = k−1 ∑ j=1 ( j k − 1 2 )(( hj k )) = k−1 ∑ j=1 j k (( hj k )) = k ∑ j=1 j k (( hj k )) . Najpomembneǰsa lastnost Dedekindovih vsot s(h, k) je reciprocitetna formula. V literaturi zanjo obstaja več dokazov, enega bomo navedli sedaj. 205–216 209 Rebeka Renko Zver Izrek 5 (Reciprocitetna formula). Za poljubni tuji si naravni števili h in k velja naslednja enakost: 12(s(h, k) + s(k, h)) = −3 + h k + k h + 1 hk . (6) Dokaz. Za h = k = 1 je enakost izpolnjena, saj sta obe strani enaki nič. V vseh drugih primerih pa lahko zaradi simetričnosti reciprocitetne formule predpostavimo, da je k > 1. Kot vemo, je zaradi tujosti števil h in k poleg P = {1, 2, ..., k} tudi P ′ = {hj; j ∈ P} popolni sistem ostankov po modulu k, zato zaradi (5) velja: k ∑ j=1 (( hj k ))2 = ∑ i∈P ′ (( i k ))2 = k ∑ j=1 (( j k ))2 . Torej po eni strani dobimo k ∑ j=1 (( hj k ))2 = k ∑ j=1 (( j k ))2 = k−1 ∑ j=1 ( j k − 1 2 )2 = 1 k2 k−1 ∑ j=1 j2 − 1 k k−1 ∑ j=1 j + 1 4 k−1 ∑ j=1 1, (7) po drugi strani pa imamo: k ∑ j=1 (( hj k ))2 = k−1 ∑ j=1 ( hj k − [ hj k ] − 1 2 )2 = = 2h k−1 ∑ j=1 j k ( hj k − [ hj k ] − 1 2 ) + k−1 ∑ j=1 [ hj k ]([ hj k ] + 1 ) − − h2 k2 k ∑ j=1 j2 + 1 4 k−1 ∑ j=1 1 = = 2h k−1 ∑ j=1 j k (( hj k )) + k−1 ∑ j=1 [ hj k ]([ hj k ] + 1 ) − h2 k2 k ∑ j=1 j2 + 1 4 k−1 ∑ j=1 1. (8) Če primerjamo (7) in (8), dobimo 2h k−1 ∑ j=1 j k (( hj k )) + k−1 ∑ j=1 [ hj k ]([ hj k ] + 1 ) − h2 k2 k ∑ j=1 j2 = 1 k2 k−1 ∑ j=1 j2− 1 k k−1 ∑ j=1 j 210 Obzornik mat. fiz. 59 (2012) 6 Dedekindove vsote in kvadratni reciprocitetni zakon in z uporabo trditve 4 najdemo 2hs(h, k) + k−1 ∑ j=1 [ hj k ]([ hj k ] + 1 ) = h2 + 1 k2 k−1 ∑ j=1 j2 − 1 k k−1 ∑ j=1 j. (9) V vsoti na levi strani imamo 0 ≤ [ hj k ] ≤ h − 1. Za lažje računanje označimo [ hj k ] = i− 1, za neki i = 1, 2, . . . , h. (10) Skušajmo ugotoviti, za katere j doseže [ hj k ] vrednost i− 1. Ker hj k ni celo število, je enakost (10) ekvivalentna pogoju i− 1 < hj k < i, zato lahko zapǐsemo k(i− 1) h < j < ki h . Če torej j teče od [ k(i−1) h ] + 1 do vključno [ ki h ] , je za i < h vrednost [ hj k ] enaka i− 1. Če pa je i = h, je ki h = k in [ hj k ] = h− 1 natanko takrat, ko j zavzame vrednosti od [ k(h−1) h ] + 1 do vključno k − 1. Tako dobimo k−1 ∑ j=1 [ hj k ]([ hj k ] + 1 ) = = h−1 ∑ i=1 (i− 1)i {[ ki h ] − [ k(i− 1) h ]} + (h− 1)h { (k − 1)− [ k(h− 1) h ]} = = h−1 ∑ i=1 (i− 1)i [ ki h ] − h ∑ i=1 (i− 1)i [ k(i− 1) h ] + (h− 1)h(k − 1). Druga vsota na koncu je enaka vsoti ∑h−1 i=1 i(i+ 1) [ ki h ] , zato lahko obe vsoti združimo in po kraǰsem računu dobimo: 205–216 211 Rebeka Renko Zver k−1 ∑ j=1 [ hj k ]([ hj k ] + 1 ) = h−1 ∑ i=1 [ ki h ] (i(i− 1)− i(i+ 1)) + (h− 1)h(k − 1) = = −2 h−1 ∑ i=1 i ( ki h − (( ki h )) − 1 2 ) + (h− 1)h(k − 1) = = − 2k h h−1 ∑ i=1 i2 + 2h h−1 ∑ i=1 i h (( ki h )) + h−1 ∑ i=1 i+ (h− 1)h(k − 1) = = 2hs(k, h)− 2k h h−1 ∑ i=1 i2 + h−1 ∑ i=1 i+ (h− 1)h(k − 1). (11) Pri tem smo v zadnji vrstici uporabili trditev 4. Primerjava (9) in (11) nam sedaj pove: 2hs(h, k) + 2hs(k, h) = = h2 + 1 k2 k−1 ∑ j=1 j2 − 1 k k−1 ∑ j=1 j + 2k h h−1 ∑ i=1 i2 − h−1 ∑ i=1 i− (h− 1)h(k − 1) (12) oziroma 2h(s(h, k) + s(k, h)) = h2 + 1 k2 · (k − 1)k(2k − 1) 6 − 1 k · (k − 1)k 2 + + 2k h · (h− 1)h(2h− 1) 6 − (h− 1)h 2 − (h− 1)h(k − 1). Poenostavimo in dobimo: 12(s(h, k) + s(k, h)) = −3 + h k + k h + 1 hk . Kvadratni reciprocitetni zakon Za izpeljavo splošnega kvadratnega reciprocitetnega zakona potrebujemo naslednjo lemo, ki jo navedimo brez dokaza. Lema 6 (Posplošena Gaussova lema). Naj bosta h in k tuji si naravni števili, pri čemer je k liho število. Naj pomeni m število najmanǰsih pozitiv- nih ostankov, večjih od k2 , pri deljenju števil hj, j = 1, 2, . . . , k−1 2 , s številom k. Tedaj velja: ( h k ) = (−1)m. 212 Obzornik mat. fiz. 59 (2012) 6 Dedekindove vsote in kvadratni reciprocitetni zakon Dokaz je možno najti v knjigi [1], str. 144–148. Trditev je posplošitev Gaussove leme, ki je sestavni del dokaza klasičnega Gaussovega kvadratnega reciprocitetnega izreka (glej npr. [5]). Namesto lihega števila k, ki si je tuje s h, tam nastopa liho praštevilo p, ki ne deli h, ter Legendrov simbol namesto Jacobijevega. Tudi naslednjo trditev navedimo brez dokaza. Trditev 7. Za liho naravno število k, naravno število h, ki si je tuje s k, in za Jacobijev simbol ( h k ) velja naslednja modularna enakost 12ks(h, k) ≡ k + 1− 2 ( h k ) (mod 8). (13) Ideja dokaza je naslednja. Najprej lahko brez težav iz trditve 4 izpeljemo enakost 12ks(h, k) = 2h(k − 1)(2k − 1)− 12 k−1 ∑ j=1 j [ hj k ] − 3k(k − 1), (14) nato pa z uporabo posplošene Gaussove leme postopoma reduciramo desno stran po modulu 8 (podrobnosti dokaza glej npr. v [4], str. 30–35 ali v [7], str. 97–99). Na podlagi predhodno zapisanega sedaj dokažimo izrek: Izrek 8 (Kvadratni reciprocitetni zakon). Naj bosta h in k lihi, tuji si celi števili. Tedaj za Jacobijeva simbola ( h k ) in ( k h ) velja: ( h k )( k h ) = (−1) h−1 2 · k−1 2 . Dokaz. Iz enakosti (13) v trditvi 7 sklepamo, da je 12hk(s(h, k) + s(k, h)) ≡ 2hk + h+ k − 2 ( h ( h k ) + k ( k h )) (mod 8). Po drugi strani pa po reciprocitetni formuli (6) velja 12hk(s(h, k) + s(k, h)) = −3kh+ h2 + k2 + 1. Ker pa sta h in k liha, je h2 ≡ 1 (mod 8) in k2 ≡ 1 (mod 8) in zato 12hk(s(h, k) + s(k, h)) ≡ −3kh+ 3 (mod 8). 205–216 213 Rebeka Renko Zver Po primerjavi dobimo: 5hk + h+ k − 3 ≡ 2 ( h ( h k ) + k ( k h )) (mod 8). To kongruenco preoblikujmo v obliko, ki jo zahteva kvadratni reciproci- tetni zakon. Za vrednosti k in h upoštevajmo več možnosti glede deljivosti s številom 4. 1. Naj bo k oblike k = 4m + 1, m ∈ Z. Tako je 5h(4m+1)+h+4m+1−3 ≡ 2 ( h ( h k ) + (4m+ 1) ( k h )) (mod 8), kar lahko preuredimo v (h+ 1)(2m− 1) ≡ h ( h k ) + ( k h ) (mod 4). Ker pa je h lih, je h+ 1 sod in zato 2m(h+ 1) ≡ 0 (mod 4), dobimo −h− 1 ≡ h ( h k ) + ( k h ) (mod 4) oziroma h ( 1 + ( h k )) + ( 1 + ( k h )) ≡ 0 (mod 4). (15) (a) Naj bo še h ≡ 1 (mod 4). Tedaj iz (15) izpeljemo kongruenco ( h k ) + ( k h ) ≡ 2 (mod 4). Ker lahko ( h k ) in ( k h ) zavzameta le vrednosti±1, mora nujno veljati ( h k ) = ( k h ) . (b) Če pa je h ≡ −1 (mod 4), neposredno izpeljemo ( h k ) ≡ ( k h ) (mod 4) oziroma ( h k ) = ( k h ) . 214 Obzornik mat. fiz. 59 (2012) 6 Dedekindove vsote in kvadratni reciprocitetni zakon V obeh primerih je torej ( h k )( k h ) = 1 = (−1) h−1 2 · k−1 2 . 2. Naj bo k oblike k = 4m − 1, m ∈ Z. Tedaj je 5h(4m−1)+h+4m−1−3 ≡ 2 ( h ( h k ) + (4m− 1) ( k h )) (mod 8), kar lahko preuredimo v (h+ 1)(2m− 2) ≡ h ( h k ) − ( k h ) (mod 4). Spet zaradi lihosti števila h velja 2m(h+ 1) ≡ 0 (mod 4) in zato −2h− 2 ≡ h ( h k ) − ( k h ) (mod 4) oziroma h ( 2 + ( h k )) + ( 2− ( k h )) ≡ 0 (mod 4). (16) (a) V primeru h ≡ 1 (mod 4) iz (16) takoj dobimo ( h k ) ≡ ( k h ) (mod 4) oziroma ( h k ) = ( k h ) . (b) Če pa je h ≡ −1 (mod 4), velja ( h k ) + ( k h ) ≡ 0 (mod 4), torej ( h k ) = − ( k h ) . V primeru (a) je rezultat produkta torej enak 1, v (b) pa −1, kar lahko v eni vrstici zapǐsemo kot ( h k )( k h ) = (−1) h−1 2 · k−1 2 . Tako smo dokazali želeno. 205–216 215 Rebeka Renko Zver Sklep Z Dedekindovimi vsotami se je kasneje ukvarjalo še veliko matematikov, ki so osnovno definicijo prilagajali svojim potrebam. Tako lahko Dedekindove vsote, poleg omenjene, zapǐsemo še v več drugih oblikah. Navedimo dva taka možna zapisa, veljavna za tuji si naravni števili h in k (izpeljavo najdemo npr. v [4]): 1. Trigonometrična oblika: s(h, k) = 1 4k k−1 ∑ j=1 cot ( jπ k ) cot ( jhπ k ) . 2. Kompleksna oblika: s(h, k) = − 1 k ∑ ω 1 (1− ωh)(1− ω) + k − 1 4k , kjer seštevamo po vseh k-tih korenih enote ω, različnih od 1. Dedekindove vsote so pomembne same zase kot posebne aritmetične funkcije s številnimi lepimi lastnostmi in prav tako tudi v povezavi z dru- gimi področji matematike, npr. s trigonometričnimi funkcijami, s številom celoštevilskih točk v poliedrih v geometriji števil, z Dedekindovo funkcijo eta v teoriji eliptičnih funkcij, s teorijo enakomerne porazdelitve, s teorijo particij itd. (primerjaj npr. [4]). Raziskovanje Dedekindovih vsot je še da- nes zelo živo, saj v matematični bazi podatkov MathSciNet od leta 2000 naprej obstaja več kot 200 člankov na to temo. Za pomoč pri delu s tem člankom bi se želela zahvaliti dr. Urošu Milu- tinoviću in dr. Milanu Hladniku. LITERATURA [1] P. Bachmann, Die Elemente der Zahlentheorie, Teubner, Leipzig, 1892. [2] R. Dedekind, Erläuterungen zu zwei Fragmenten von Riemann Riemann’s Gesammelte Math. Werke (1892), 466–478, Dedekind’s Gesammelte Math. Werke (1930), 159–173. [3] E. Grosswald, Topics from the Theory of Numbers, Birkhäuser, Boston, 1984. [4] H. Rademacher in E. Grosswald, Dedekind sums, Math. Association of America, 1972. [5] T. Peklar, Varianta dokaza kvadratnega recipročnostnega zakona, Obzornik mat. fiz. 36 (1989), 129–133. [6] B. Riemann, Fragmente über die Grenzfälle der elliptischen Modulfunctionen, Gesam- melte Math. Werke, Dover, New York, 1953. [7] R. Renko, Dedekindove vsote, magistrsko delo, Fakulteta za naravoslovje in matema- tiko Maribor, Univerza v Mariboru, Maribor, 2008. 216 Obzornik mat. fiz. 59 (2012) 6