###################################################################### ##lattices: Save this file as lattices. To use # ##it, stay in the same directory, get into Maple (by typing: maple # ## ) # ##and then type: read lattices : # ##Then follow the instructions given there # ## # ##Written by Alejandro Ginory, Rutgers University , # ##aginory@math.rutgers.edu. # ###################################################################### #This is a package that aids in lattice related computations. #For a list of the included programs, enter `Help();'. For help on a specific program, #enter `Help(program_name);' (do not include the argmuent, for example, enter #`Help(LatticeSumBasis);'). #We will use the following conventions. #A lattice L of rank R with bilinear form is given by a pair L=[basis, bilfor] #where basis=[e1,e2,...,eR] is a list of row vectors (lists) and bilfor=[[...],...] is a #matrix (in list form) representing the bilinear form. If there is no special bilinear form, #then simply use the identity matrix, i.e., the standard inner product. ############################################ with(linalg): with(ArrayTools): with(LinearAlgebra): with(ArrayTools): with(ListTools): with(combinat): interface(rtablesize=50): ############################################ Help:=proc(): if args=NULL then lprint(`The following programs are included in this package:`): lprint(`trivlatbas(r), evabilfor(a,b,B), tolist(M), DualLattice(L), colvec(vec), rowvec(vec),`): lprint(`lcmset(S), gcdset(S), SpanToBase(spanset), LatticeSumBasis(L1,L2), LatticeIntersectBasis(L1,L2),`): lprint(` `): fi: if nops([args])=1 and op(1,[args])=trivlatbas then lprint(`trivlatbas(r): gives the "trivial lattice" of rank R, i.e, the lattice of the form`): lprint(`[ identity matrix , identity matrix ] where identity matrix is given in list form.`): fi: if nops([args])=1 and op(1,[args])=evabilfor then lprint(`evabilfor(a,b,B): evaluates the bilinear form (a,b) with respect to the bilinear form `): lprint(`matrix B where a and b are (row) vectors expressed as lists w.r.t. the ordered basis that `): lprint(`produced B. `): fi: if nops([args])=1 and op(1,[args])=tolist then lprint(`tolist(M): converts matrix to list form`): fi: if nops([args])=1 and op(1,[args])=DualLattice then lprint(`DualLattice(L): input a lattice L=[base,bilfor] of any rank r[ [ seq([0\$(ii-1),1,0\$(r-ii)],ii=1..r) ],[ seq([0\$(ii-1),1,0\$(r-ii)],ii=1..r) ]]: ############################################ #evabilfor(a,b,B): evaluates the bilinear form (a,b) with respect to the bilinear form #matrix B where a and b are (row) vectors expressed as lists w.r.t. the ordered basis that #produced B. evabilfor:=proc(a,b,B): multiply(a,multiply(B,[seq([b[ii]],ii=1..nops(b))]))[1]: end: ############################################ #Converts matrix to list form tolist:=(M)->[seq([seq(M[ii,jj],jj=1..Size(M)[2])],ii=1..Size(M)[1])]: ############################################ #DualLattice(L): input a lattice L=[base,bilfor] of any rank rrank(MM0) then MM0:=[ op(MM0) , [0\$(i-1),1,0\$(n-i)] ]: fi: od: fi: MM:=Multiply( Matrix(L[2]) , Matrix(transpose(MM0)) ): #if r[seq([vec[ii]],ii=1..nops(vec))]: ############################################ #rowvec(vec): converts column vector in list form to row vector in list form rowvec:=(vec)->[seq(vec[ii][1],ii=1..nops(vec))]: ############################################ #lcmset(S): input a set of integers S, the output is the least common multiple. lcmset:=(S)->`if`(nops(S)=1,S[1],`if`(nops(S)=2,lcm(S[1],S[2]),lcm(S[1],lcmset(S[2..nops(S)]) ) ) ): ############################################ #gcdset(S): input a set of integers S, the output is the greatest common divisor. gcdset:=(S)->`if`(nops(S)=1,S[1],`if`(nops(S)=2,gcd(S[1],S[2]),gcd(S[1],gcdset(S[2..nops(S)]) ) ) ): ############################################ #SpanToBase(spanset): input a list of row vectors of length n (in list form) that span #a sublattice M of a lattice L. The entries MUST BE real numbers. #Outputs a base of M generated by spanset. In fact, this algorithm gives a basis in row #echelon form. SpanToBase:=proc(spanset) local n,m,i,SS,r,LL,LLinf,minLL,minind,gg: n:=nops(spanset[1]): m:=nops(spanset): #First, we check if the vectors are all of the same length. if {seq(nops(spanset[ii]),ii=1..nops(spanset))}<>{nops(spanset[1])} then RETURN(`The vectors must be of the same length.`): fi: #Second, we check if the first entries are all 0. If n=1 and all entries are 0, #then we return the empty list. Otherwise, we apply SpanToBase on the vectors with the #first entry truncated. if {seq(spanset[ii][1] ,ii=1..m )}={0} then if n>1 then LL:=SpanToBase([seq(spanset[ii][2..n],ii=1..m)]): RETURN([seq( [0,op(LL[ii])] ,ii=1..nops(LL)) ]): else RETURN([]): fi: fi: #Since at least 1 of the initial entries is nonzero, we switch signs to make them #positive and find the smallest one. We then subtract the smallest from the remaining ones #and repeat, until there is a single remaining nonzero initial entry. SS:=spanset: SS:=[seq(sign(SS[ii][1])*SS[ii],ii=1..m)]: r:=0: for i from 1 to 1000000000 while r<>1 do LL:=[seq(SS[ii][1],ii=1..m)]: LLinf:=[seq(`if`(LL[ii]=0,infinity,LL[ii]),ii=1..m)]: minLL:=min(LLinf): minind:=Search(minLL,LL): SS:=[ seq( SS[ii]-floor(LL[ii]/minLL)*SS[minind] ,ii=1..minind-1) , SS[minind] , seq( SS[ii]-floor(LL[ii]/minLL)*SS[minind] ,ii=minind+1..m) ]: if [seq(SS[ii][1],ii=1..m)]=[0\$(minind-1),minLL,0\$(m-minind)] then r:=1: fi: od: #Now, we move the nonzero initial entry vector to the front of the list. SS:=[SS[minind], seq( SS[ii] ,ii=1..minind-1) , seq( SS[ii] ,ii=minind+1..m) ]: #lprint(1,SS): #We then apply SpanToBase to the remaining vectors (minus the first). If n=1, then we are #done and so we return [ SS[1] ] if n>1 then LL:=SpanToBase([seq(SS[ii][2..n],ii=2..m)]): else RETURN([ SS[1] ]): fi: #print(2,LL): [SS[1], seq( [0,op(LL[ii])] ,ii=1..nops(LL)) ]: end: ############################################ #LatticeSumBasis(L1,L2): input two lattices L1, L2 whose bases are given in a common basis of some #ambient module (or vector space) M. #Output is a basis of the sum of these lattices in M. LatticeSumBasis:=(L1,L2)->SpanToBase([op(L1[1]),op(L2[1])]): ############################################ #LatticeIntersectBasis(L1,L2): input two lattices L1, L2 whose bases are given in a common #basis of some ambient module (or vector space) M. #Output is a basis of the intersection of these lattices in M. LatticeIntersectBasis:=proc(L1,L2) local L0,M1,M2,Lsum: if nops(L1[1])=0 then RETURN(L2): fi: if nops(L2[1])=0 then RETURN(L1): fi: if nops(L1[1][1])<>nops(L2[1][1]) then RETURN(`The vectors involved must have the same length.`): fi: #We create a trivial lattice simply to use the identity matrix L0[2]. L0:=trivlatbas(nops(L1[1][1])): #We take the dual lattices of L1 and L2 under the standard inner product. M1:=DualLattice([L1[1],L0[2]]): M2:=DualLattice([L2[1],L0[2]]): #Then we take the sum L1*+L2*. Lsum:=[LatticeSumBasis(M1,M2),L0[2]]: #print(Lsum): #Finally, we take the dual of the sum (L1*+L2*)*=L1 \cap L2. DualLattice(Lsum)[1]: end: ############################################ ################################################################################