""" Find all sublists of length m of a list G """ def findsublists(G,m): if m<0: return [] n=len(G) if m==n: return [G] elif m>n: return [] else: L1=findsublists(G[1:],m) L2=findsublists(G[:len(G)-1],m) for a in L2: if not a in L1: L1=L1+[a] return L1 """ Example: findsublists([1,0,1],2) [[1,0],[0,1]] #note that [1,1] is not considered as sublist """ #Same for tuples def findsubtuples(G,m): L=findsublists(list(G),m) re=[] for a in L: re=re+[tuple(a)] return re def lring(p,a): """ Laurentpolynomials in the variable y over the p-adic numbers with precision a. For us: y(0)=-1, y(1)=0. """ return LaurentSeriesRing(Qp(p,a,'capped-rel'), "y") #return LaurentSeriesRing(Qp(p,a), "y") def coef(f,n): """ Fetching the coefficient of a Laurent Polynomial. """ if n not in f.exponents(): return 0 else: return f.coefficients()[f.exponents().index(n)] def lfrobpoly(p,a): """ Returns the Laurent polynomial representation of p(y+1)^(p-1)/((y+1)^p-1) up to precision a. """ S=lring(p,a) y=S.gen(0) x=y+1 g=(1+y^(-1))^p-y^(-p)-1 h=S(0) for k in range(a): h=h+S((-1)**k)*(g**k) return S(p)*(x**(p-1))*(y^(-p))*h def ldividebyx(f,S): """ Divide a Laurent polynomial f by y+1. """ y=S.gen(0) if not f(-1)==0: return "Does not vanish at -1." else: if not f.exponents()==[]: min=f.exponents()[0]-1 else: min=0 max=f.degree()-1 b=0 g=0 for i in range(max,min-1,-1): b=coef(f,i+1)-b g=g+b*y^i return g def lstepone(E,G,p,a,S): """ Given a dictionary of solutions G for the morphism constructed in the proposition, and a tuple E, it computes the solution for E. Therefore all proper subtuples of E have to be contained as indices in G. The argument a is the precision and S is the base ring we work with. """ f=lfrobpoly(p,a) y=S.gen(0) # trivial case if E==(): return {E:[S(0),S(1)]} #Compute the main term (from the proposition), #which we need to integrate after modification #in order to kill the residues mterm=S(0) if not E==(0,): for i in range(1,len(E)): mterm=mterm+G[E[:i]][1]*G[E[i:]][0]*y^(-1) if E[len(E)-1]==0: mterm=mterm+S(p)*ldividebyx(G[E[:len(E)-1]][1],S) if E[0]==0: mterm=mterm-S(p)*ldividebyx(G[E[1:]][1],S) if E[0]==1: mterm=mterm-G[E[1:]][1]*f #Take residues T=-mterm.residue() #Modify and integrate + subtract the value at #y=-1 (x=0) so that the primitive vanishes at 0 L=(T*y^(-1)+mterm).integral()-(T*y^(-1)+mterm).integral()(-1) return {E:[T,L]} # # Computation of theta # def ltheta(E,p,a): """ Computes our solution for all subtuples of the first argument. The second argument is a prime, the third argument is the precision. The result is a dictionary. The firt argument of an entry is the coefficient of tau(e_1), the second argument is the coefficient of L. EXAMPLES: sage: ltheta((1,0),3,2) {(1, 0): [0, (2*3^3 + O(3^4))*y^-4 + (2*3^2 + O(3^3))*y^-3 + (2*3^3 + O(3^4))*y^-2 + (3^2 + O(3^4))*y^-1], (): [0, (1 + O(3^2))], (1,): [3 + O(3^3), (2*3^2 + O(3^3))*y^-4 + O(3^2)*y^-3 + (2*3 + 3^2 + O(3^3))*y^-2 + (2*3 + 2*3^2 + O(3^3))*y^-1], (0,): [0, 0]} sage: for i in ltheta((1,0,0,1,0,0,1),2,10): if not ltheta((1,0,0,1,0,0,1),2,10)[i][0]==0: print i, ":", ltheta((1,0,0,1,0,0,1),2,10)[i][0] (0, 0, 1, 0, 0, 1) : 2^4 + 2^5 + O(2^7) (1,) : 2 + O(2^11) (1, 0, 0, 1, 0, 0) : 2^4 + 2^6 + O(2^7) sage: for i in ltheta((1,0,0,1,0,0,1),2,8): if not ltheta((1,0,0,1,0,0,1),2,8)[i][0]==0: print i, ":", ltheta((1,0,0,1,0,0,1),2,8)[i][0] (0, 1) : 2^7 + O(2^9) (0, 0, 1, 0, 0, 1) : 2^4 + 2^5 + 2^7 + O(2^8) (1,) : 2 + O(2^9) (1, 0, 0) : 2^6 + 2^7 + O(2^8) (0, 0, 1) : 2^6 + 2^7 + O(2^8) (0, 1, 0, 0, 1) : 2^6 + O(2^8) (0, 0, 1, 0, 0) : 2^7 + O(2^8) (1, 0) : 2^7 + 2^8 + O(2^9) (1, 0, 0, 1, 0) : 2^6 + O(2^8) (0, 1, 0) : 2^7 + O(2^8) (1, 0, 0, 1, 0, 0) : 2^4 + 2^6 + O(2^8) """ #fixes issue with python tuple if E==(0): E=(0,) if E==(1): E=(1,) #setup S=lring(p,a) G={():[S(0),S(1)]} for i in range(1,len(E)+1): for el in findsubtuples(E,i): G.update(lstepone(el,G,p,a,S)) return G # #Check the output of theta # def lchecktheta(E,p,a): S=lring(p,a) f=lfrobpoly(p,a) y=S.gen(0) L=ltheta(E,p,a) checkdict={():S(0)} for i in range(1,len(E)+1): for el in findsubtuples(E,i): rel=L[el][1].derivative() if not el==(0,): for j in range(len(el)+1): rel=rel-L[el[:j]][1]*L[el[j:]][0]*(y^(-1)) if el[len(el)-1]==0: rel=rel-S(p)*ldividebyx(L[el[:len(el)-1]][1],S) if el[0]==0: rel=rel+S(p)*ldividebyx(L[el[1:]][1],S) if el[0]==1: rel=rel+L[el[1:]][1]*f checkdict.update({el:rel}) return checkdict def norms(E,p,a): for i in ltheta(E,p,a): if not ltheta(E,p,a)[i][0]==0: print i, ":", ltheta(E,p,a)[i][0].abs() def RightFactors(word): n=len(word) dummy = [()] for k in range(n): dummy = dummy +[tuple(word[n-1-k:n])] return dummy # Find all contiguous sublists # including self def contiguous_sublists(G): dummy = [] for m in range(len(G)+1): dummy = dummy+ findsublists(G,m) return dummy # Example: # Me: contiguous_sublists((0,1,0,0,1)) # Sage: [(0, 1, 0, 0, 1), (), (1,), (0,), (0, 1), # (0, 0), (1, 0), (0, 0, 1), (1, 0, 0), (0, 1, 0), # (1, 0, 0, 1), (0, 1, 0, 0)] # Retrieve coefficient of \tau(a)(e1) from 'L_tau_dict' # Input 'V' a tuple of 0's and 1's def tau_e1_coeff(W, L_tau_dict): if W == (): return 0 else: return L_tau_dict[W][0] # L_point_coeff # Retreive coefficient of L(point) = \theta(e_I)(point) # from 'L_tau_dict' def L_point_coeff(Wpr, point, L_tau_dict): return L_tau_dict[Wpr][1](point-1) # eval # Dict extended by zero def eval(dict, key): if dict.has_key(key): return dict[key] else: return 0 # prod # Product of elements of subword algebra of X def prod(Dp, Dpp, Cont_Subwords_X, K): D = dict() for W in Cont_Subwords_X: c_W = K(0) for i in range(len(W)+1): Wp = W[0:i] a_Wp = eval(Dp, Wp) Wpp = W[i:len(W)+1] b_Wpp = eval(Dpp, Wpp) c_W = c_W + a_Wp*b_Wpp D.update({W:c_W}) return D def tau_dict(word, prime, padic_prec, L_tau_dict, Cont_Subwords_X): X = word Xlen = len(X) p = prime K = Qp(p, padic_prec, 'capped-rel') # Construct the part of \tau(point)(e1) corresponding # to contiguous subwords of X. CS = Cont_Subwords_X tau_e1 = dict() for W in CS: tau_e1.update({W:tau_e1_coeff(W, L_tau_dict)}) td = {():({():1}), (0,): ({(0,):K(p)}), (1,): (tau_e1)} for nl in range(2, Xlen+1): csf = findsublists(X, nl) for V in csf: td.update({V :prod(td[V[0:1]] ,td[V[1:nl+1]] , Cont_Subwords_X, K ) }) return td def L_dict(word, point, prime, padic_prec, L_tau_dict, Cont_Subwords_X): D = dict() for Wpr in Cont_Subwords_X: D.update({Wpr :L_point_coeff(Wpr, point, L_tau_dict) }) return D def theta_data(word, point, prime, padic_prec): X = word p = prime L_tau_dict=ltheta(X,p, padic_prec) Cont_Subwords_X= contiguous_sublists(X) L = L_dict(word, point, prime, padic_prec,\ L_tau_dict, Cont_Subwords_X) tau = tau_dict(word, prime, padic_prec, \ L_tau_dict, Cont_Subwords_X) return [L,tau]