###################################################################### ##MARVIN: Save this file as MARVIN # ## To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read MARVIN # ##Then follow the instructions given there # ## # ##Written by Doron Zeilberger, Rutgers University , # #zeilberg at math dot rutgers dot edu # ###################################################################### #Created: Dec. 29, 2011 with(numtheory): print(`Created: Dec. 29, 2011`): print(` This is MARVIN `): print(`A Maple package written in fond memory of`): print(`my dear friend, Marvin Isadore Knopp (1933-Dec. 24, 2011)`): print(`to study Dedekind Sums, dear to his heart, and in particular`): print(`the Knopp-Petersson identity.`): print(``): print(`Please report bugs to zeilberg at math dot rutgers dot edu`): print(``): print(`The most current version of this package and paper`): print(` are available from`): print(`http://www.math.rutgers.edu/~zeilberg/ .`): print(`For a list of the procedures type ezra();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): with(combinat): ezra1:=proc() if args=NULL then print(` The supporting procedures are: `): print(` GuessPol`): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`The main procedures are: `): print(`Pab, ProveA, shk, Shk, VerifyKnopp, VerifyKnoppKN, VerifySubrah `): elif nops([args])=1 and op(1,[args])=GuessPol then print(`GuessPol(L,n,s0): guesses a polynomial of degree d in n for`): print(` the list L, such that L[i]=P[i] for i>=s0 for example, try: `): print(`GuessPol([seq(i,i=1..10)],n,1);`): elif nops([args])=1 and op(1,[args])=Pab then print(`Pab(a,b,k): the polynomial (a*k+b)*s(a,a*k+b) for `): print(`numeric a and b with 1<=b1, gcd(a,b)=1 and ALL k`): print(`For example, try:`): print(`ProveA(10);`): elif nops([args])=1 and op(1,[args])=shk then print(`shk(h,k): The Dedekind sum Eq. (1) in the Rademacher/Grosswald`): print(`book: "Dedekind Sums", using the definition`): print(`For example, try:`): print(`shk(11,5);`): print(``): elif nops([args])=1 and op(1,[args])=Shk then print(`Shk(h,k): The Dedekind sum s(h,k)`): print(`using the Reciprocity Theorem, Eq. (4) (p.4) in the `): print(`book: "Dedekind Sums", by Hans Rademacher and Emil Grosswald`): print(`For example, try:`): print(`Shk(11,5);`): print(``): elif nops([args])=1 and op(1,[args])=VerifyKnopp then print(`VerifyKnopp(h,k,n): verifies Marvin Knopp's identity (1.2)`): print(`of Marvin Knopp's lovely article "Hecke Operators and an Identity`): print(`for the Dedekind Sums", J. of Number Theory 12(1980), 2-9.`): print(`For example, try:`): print(`VerifyKnopp(2,3,10);`): elif nops([args])=1 and op(1,[args])=VerifyKnoppKN then print(`VerifyKnoppKN(K,N): verifies Knopp's identity for all`): print(`h<=k gcd(h,k)=1 and n<=N. For example, try:`): print(`VerifyKnoppKN(10,50);`): elif nops([args])=1 and op(1,[args])=VerifySubrah then print(`VerifySubrah(h,k,d): verifies P. Subrahmanyam's identity`): print(`VerifySubrah(2,3,5);`): else print(`There is no ezra for`,args): fi: end: ###start GuessPol #GuessPol1(L,d,n,s0): guesses a polynomial of degree d in n for # the list L, such that L[i]=P[i] for i>=s0 for example, try: #GuessPol1([(seq(i,i=1..10),1,n,1); GuessPol1:=proc(L,d,n,s0) local P,i,a,eq,var: if d>=nops(L)-s0-2 then ERROR(`the list is too small`): fi: P:=add(a[i]*n^i,i=0..d): var:={seq(a[i],i=0..d)}: eq:={seq(subs(n=i,P)-L[i],i=s0..s0+d+3)}: var:=solve(eq,var): if var=NULL then RETURN(FAIL): fi: subs(var,P): end: #GuessPol(L,n,s0): guesses a polynomial of degree d in n for # the list L, such that L[i]=P[i] for i>=s0 for example, try: #GuessPol([seq(i,i=1..10)],n,1); GuessPol:=proc(L,n,s0) local d,gu: for d from 0 to nops(L)-s0-3 do gu:=GuessPol1(L,d,n,s0): if gu<>FAIL then RETURN(gu): fi: od: FAIL: end: ###end Guess Pol##### #shk(h,k): The Dedekind sum Eq. (1) in the Rademacher/Grosswalk book #"Dedekind Sums", straight from the definition #For example, try: #shk(11,5); shk:=proc(h,k) local m: #if gcd(h,k)<>1 then # RETURN(FAIL): #fi: add((m/k-trunc(m/k)-1/2)*(h*m/k-trunc(h*m/k)-1/2),m=1..k-1): end: #Shk(h,k): The Dedekind sum s(h,k) using The reciporicity identity #For example, try: #Shk(11,5); Shk:=proc(h,k) option remember: if gcd(h,k)<>1 then RETURN(Shk(h/gcd(h,k),k/gcd(h,k))): fi: if h=1 and k=1 then RETURN(0): fi: if k=1 then RETURN(0): fi: if h=1 then RETURN( -1/4+(2/k+k)/12): fi: if h>k then Shk(h mod k,k): else -1/4+(h/k+k/h+1/h/k)/12-Shk(k,h): fi: end: #Pab(a,b,k): the polynomial (a*k+b)^2*s(a,a*k+b) for #numeric a and b with 1<=b=1 and b>=1 and b1, gcd(a,b)=1 and ALL k #For example, try: #ProveA(10); ProveA:=proc(A) local b,a: for a from 2 to A do for b from 1 to a-1 do if gcd(a,b)=1 then if not Proveab(a,b) then RETURN(false): fi: fi: od: od: true: end: #VerifyKnopp(h,k,n): verifies Marvin Knopp's identity (1.2) #of Marvin Knopp's lovely article "Hecke Operators and an Identity # for the Dedekind Sums", J. of Number Theory 12(1980), 2-9. #For example, try: #VerifyKnopp(2,3,10); VerifyKnopp:=proc(h,k,n) local a,d,b,gu,mu: if not gcd(h,k)=1 then RETURN(FAIL): fi: gu:=0: mu:=divisors(n): for d in mu do a:=n/d: for b from 1 to d do gu:=gu+shk(a*h+b*k,d*k): od: od: evalb(gu=sigma(n)*shk(h,k)): end: #VerifyKnoppf(h,k,n): verifies Marvin Knopp's identity (1.2) #of Marvin Knopp's lovely article "Hecke Operators and an Identity # for the Dedekind Sums", J. of Number Theory 12(1980), 2-9. #For example, try: #VerifyKnoppf(2,3,10); VerifyKnoppf:=proc(h,k,n) local a,d,b,gu,mu: if not gcd(h,k)=1 then RETURN(FAIL): fi: gu:=0: mu:=divisors(n): for d in mu do a:=n/d: for b from 1 to d do gu:=gu+Shk(a*h+b*k,d*k): od: od: evalb(gu=sigma(n)*Shk(h,k)): end: #VerifyKnoppKN(K,N): verifies Knopp's identity for all #h<=k gcd(h,k)=1 and n<=N. For example, try: #VerifyKnoppKN(10,50); VerifyKnoppKN:=proc(K,N) local h,k,n: for n from 1 to N do for k from 2 to K do for h from 1 to k do if gcd(h,k)=1 then if not VerifyKnoppf(h,k,n) then RETURN(false): fi: fi: od: od: od: true: end: #VerifyKnoppKNf(K,N): verifies Knopp's identity for all #using Shk(h,k) rather than shk(h,k) #h<=k gcd(h,k)=1 and n<=N. For example, try: #VerifyKnoppKNf(10,50); VerifyKnoppKNf:=proc(K,N) local h,k,n: for n from 1 to N do for k from 2 to K do for h from 1 to k do if gcd(h,k)=1 then if not VerifyKnopp(h,k,n) then RETURN(false): fi: fi: od: od: od: true: end: #VerifySubrah(h,k,d): verifies P. Subrahmanyam's identity #VerifySubrah(2,3,5); VerifySubrah:=proc(h,k,d) local b,gu1,gu2,mu,c: if not gcd(h,k)=1 then RETURN(FAIL): fi: mu:=divisors(d): gu2:=add(mobius(c)*shk(h*c,k)*sigma(d/c), c in mu): gu1:=add(shk(h+b*k,d*k),b=1..d): evalb(gu1=gu2): end: