################################################################## ## File contatining a Sage code for computing BP Power Operations ## ## 14 February, 2010 ## ## Niles Johnson and Justin Noel ## http://arxiv.org/abs/0910.3187 ## ################################################################## class BPPowerOps(): """ Use formal group laws to compute power operations on CP^n. This leads to a computation of McClure's obstructions for H-infty structure on BP. This code is used in the paper "For Complex Orientations Preserving Power Operations, p-Typicality is Atypical" by Niles Johnson and Justin Noel, available at http://arxiv.org/abs/0910.3187 In the output, t is a dummy power series variable, and we use the variable y in places where xi was used in the paper. USAGE: sage: B = BPPowerOps(3,30) sage: B.exp_BP() t - L1*t^3 + 3*L1^2*t^5 - 12*L1^3*t^7 + (55*L1^4 - L2)*t^9 + (-273*L1^5 + 12*L1*L2)*t^11 + (1428*L1^6 - 105*L1^2*L2)*t^13 + (-7752*L1^7 + 816*L1^3*L2)*t^15 + (43263*L1^8 - 5985*L1^4*L2 + 9*L2^2)*t^17 + (-246675*L1^9 + 42504*L1^5*L2 - 210*L1*L2^2)*t^19 + (1430715*L1^10 - 296010*L1^6*L2 + 3036*L1^2*L2^2)*t^21 + (-8414640*L1^11 + 2035800*L1^7*L2 - 35100*L1^3*L2^2)*t^23 + (50067108*L1^12 - 13884156*L1^8*L2 + 356265*L1^4*L2^2 - 117*L2^3)*t^25 + (-300830572*L1^13 + 94143280*L1^9*L2 - 3322704*L1^5*L2^2 + 4060*L1*L2^3 - L3)*t^27 + (1822766520*L1^14 - 635745396*L1^10*L2 + 29216880*L1^6*L2^2 - 81840*L1^2*L2^3 + 30*L1*L3)*t^29 + O(t^30) sage: B.McClure(2,"formal") a0^2*v1 - 3*a0*a2 sage: B.McClure(4,"formal") -5*a0^3*a2*v1 + 15*a0^2*a2^2 - 5*a0^3*a4 sage: B.McClure(2) y^8*v1^3*t^8 + 2*y^10*v2*t^10 + (y^12*v1^5 + y^12*v1*v2)*t^12 + 2*y^14*v1^2*v2*t^14 + 2*y^16*v1^7*t^16 + (2*y^18*v1^8 + y^18*v2^2)*t^18 + (y^20*v1^5*v2 + y^20*v1*v2^2)*t^20 + (2*y^22*v1^10 + 2*y^22*v1^6*v2 + y^22*v1^2*v2^2)*t^22 + (y^24*v1^11 + y^24*v1^7*v2)*t^24 + (2*y^26*v1^12 + 2*y^26*v1^8*v2 + y^26*v1^4*v2^2)*t^26 + (2*y^28*v1^13 + 2*y^28*v1^9*v2 + 2*y^28*v1*v2^3 + 2*y^28*v3)*t^28 + O(t^29) sage: B.McClure(4) 2*y^22*v1^9*t^22 + 2*y^24*v1^10*t^24 + 2*y^26*v1^7*v2*t^26 + (2*y^28*v1^8*v2 + y^28*v1^4*v2^2)*t^28 + (2*y^30*v1^13 + 2*y^30*v1^9*v2 + 2*y^30*v1^5*v2^2 + 2*y^30*v1*v2^3 + y^30*v3)*t^30 + O(t^31) this code (especially the documentation) is in a rough, but working state """ def __init__(self, p, ps_prec): """ Initialize the class with a given prime number p and specified power series precision ps_prec. INPUT: p -- a prime number ps_prec -- an integer greater than or equal to p^2 EXAMPLES: coming soon """ if is_prime(p): self.__prime = p else: raise TypeError("first argument must be prime") if ps_prec < p**2: raise NotImplementedError("second argument must be at least p^2, or construction of ground ring BPQ breaks") self.__prec = ps_prec ## Set the logarithmic precision n = ps_prec log_prec = floor(log(ps_prec, p)) self.__log_prec = log_prec ## shorthand self.pVal = p self.nVal = ps_prec self.BPQ = PolynomialRing(QQ,['L%s'%n for n in [1..log_prec]],order="deglex") self.BP = PolynomialRing(QQ,['v%s'%n for n in [1..log_prec]],order="deglex") self.BPQxyTilde = PolynomialRing(QQ,['x','y']+['L%s'%n for n in [1..log_prec]],order="deglex") (self.x,self.y) = (self.BPQxyTilde.gens()[0],self.BPQxyTilde.gens()[1]) BPQxyIdl = (self.BPQxyTilde.ideal([self.BPQxyTilde.gens()[0]**self.nVal,self.BPQxyTilde.gens()[1]**self.nVal])) self.BPxyTilde = PolynomialRing(QQ,['x','y']+['v%s'%n for n in [1..log_prec]],order="deglex") BPxyIdl = (self.BPxyTilde.ideal([self.BPxyTilde.gens()[0]**self.nVal,self.BPxyTilde.gens()[1]**self.nVal])) self.BPQxy = QuotientRing(self.BPQxyTilde,BPQxyIdl) self.BPxy = QuotientRing(self.BPxyTilde,BPxyIdl) self.BPQxyt = PowerSeriesRing(self.BPQxyTilde,'t') self.BPxyt = PowerSeriesRing(self.BPxyTilde,'t') ## trying power series self.BPQt = PowerSeriesRing(self.BPQ,'t') self.BPt = PowerSeriesRing(self.BP,'t') self.L = (1,)+self.BPQxyTilde.gens()[2:] self.v = (self.pVal,)+self.BPxyTilde.gens()[2:] self.t = self.BPQt.gen() self.logBP = sum([self.L[i]*self.t**self.pVal**i for i in [0..self.__log_prec]]) + O(self.t**self.nVal) self.vnRules = self.vn_rules("Hazewinkel") #self.vnRules = self.vn_rules("Araki") #self.expBP = self.ps_inverse_Lagrange(self.logBP) self.expBP = None self.redpSeries = None self.formalSumU = None self.cyclicPowerOp = None self.cyclicPowerOpU = None self.FirstCheck = None self.GenMultInv = None return None def test(self): self.tmp = self.power_tuple(self.logBP) return self.logBP.coefficient({self.__y:0}) def todo(self): """ progress so far: expBP, formal_sum, cyclic_powerop, red_p_series, a_class, reduction by reduced p-series, MCn implemented with power series TO DO: broken things: BPQ breaks if there is only L1, but no higher Li """ return self.tmp def __repr__(self): """ Print the class. """ print "prime = "+str(self.pVal) print "power series precision: ps_prec = "+str(self.nVal-1) print "in output, t is a dummy power series variable to keep track of precision, \n and we use y instead of xi \n" return "more details could be added here . . ." def vn_rules(self,name): """ return rules for vn substitutions; takes "Hazewinkel" or "Araki" as input """ vee = [self.pVal] for i in [1..self.__log_prec]: vee.append(var('vee%s'%i)) vee = self.v ell = [1]+[var('ell%s'%i) for i in [1..self.__log_prec]] if name == "Hazewinkel": vn_solns = flatten( solve([ vee[0]*ell[m] == sum( ell[i]*vee[m-i]^(self.pVal^i) for i in range(0,max(m,1))) for m in range(0,self.__log_prec+1) ],[ell[i] for i in range(1,self.__log_prec+1)]) ) elif name == "Araki": vn_solns = flatten( solve([ vee[0]*ell[m] == sum( ell[i]*vee[m-i]^(self.pVal^i) for i in range(0,m+1)) for m in range(0,self.__log_prec+1) ],[ell[i] for i in range(1,self.__log_prec+1)]) ) else: raise NotImplementedError("name must be Hazewinkel or Araki") ellmap = {} for m in [1..self.__log_prec]: ellmap[ell[m]] = self.L[m] veemap = {} for m in [1..self.__log_prec]: veemap[vee[m]] = self.BPxyt(self.v[m]) vn_rules = {} for c in vn_solns: vn_rules[ellmap[c.left()]] = c.right() return vn_rules def exp_BP(self): """ compute BP exponential using Lagrange inversion """ if self.expBP != None: #print "already defined" return self.expBP self.expBP = self.ps_inverse_Lagrange(self.logBP) return self.expBP def formal_sum(self,ivalB=1): """ alternate implementation (slower) """ var1 = self.x var2 = self.y vart = self.t logBPx = self.logBP.substitute(t = var1*vart) logBPy = self.logBP.substitute(t = var2*vart) outBPQ = self.expBP.substitute(t = (ivalB*logBPy + logBPx)) outBPcoeffs = [self.BPxyt(self.BPxyTilde(symbolic_expression(w).substitute(self.vnRules))) for w in outBPQ.padded_list(self.nVal)] output = sum([outBPcoeffs[i]*self.BPxyt(self.t)**i for i in range(0,self.nVal)])+O(self.BPxyt(self.t)**self.nVal) return output def formal_sum_u_big(self,ivalB = 1): """ formal sum [u]y +_BP x implemented as a single function """ BPQu = PolynomialRing(QQ,['x','y','u']+['L%s'%n for n in [1..self.__log_prec]],order="deglex") u = BPQu.gens()[2] BPu = PolynomialRing(QQ,['x','y','u']+['v%s'%n for n in [1..self.__log_prec]],order="deglex") BPQut = PowerSeriesRing(BPQu,'t') BPut = PowerSeriesRing(BPu,'t') self.BPut = BPut self.u = self.BPut.base_ring().gens()[2] var1 = self.x var2 = self.y vart = self.t if self.formalSumU == None: logBPx = BPQut(self.logBP.substitute(t = var1*vart)) logBPy = BPQut(self.logBP.substitute(t = var2*vart)) expBPu = BPQut(self.expBP) self.formalSumU = expBPu.substitute(t = (u*logBPy + logBPx)) outBPcoeffs = [self.BPxyt(self.BPxyTilde(symbolic_expression(w).substitute(self.vnRules).substitute(u = ivalB))) for w in self.formalSumU.padded_list(self.nVal)] output = sum([outBPcoeffs[i]*self.BPxyt(self.t)**i for i in range(0,self.nVal)])+O(self.BPxyt(self.t)**self.nVal) return output def formal_sum_u_Pa_old(self,ivalB = 1): """ part a--older slower version """ BPQu = PolynomialRing(QQ,['x','y','u']+['L%s'%n for n in [1..self.__log_prec]],order="deglex") u = BPQu.gens()[2] self.BPu = PolynomialRing(QQ,['x','y','u']+['v%s'%n for n in [1..self.__log_prec]],order="deglex") BPQut = PowerSeriesRing(BPQu,'t') BPut = PowerSeriesRing(self.BPu,'t') self.BPut = BPut self.u = self.BPut.base_ring().gens()[2] var1 = self.x var2 = self.y vart = self.t if self.formalSumU == None: logBPx = BPQut(self.logBP.substitute(t = var1*vart)) logBPy = BPQut(self.logBP.substitute(t = var2*vart)) expBPu = BPQut(self.expBP) self.formalSumU = expBPu.substitute(t = (u*logBPy + logBPx)) return self.formalSumU def formal_sum_u_Pa(self,ivalB = 1): """ part a--faster version """ self.exp_BP() BPQu = PolynomialRing(QQ,['x','y','u']+['L%s'%n for n in [1..self.__log_prec]],order="deglex") u = BPQu.gens()[2] self.BPu = PolynomialRing(QQ,['x','y','u']+['v%s'%n for n in [1..self.__log_prec]],order="deglex") BPQut = PowerSeriesRing(BPQu,'t') BPut = PowerSeriesRing(self.BPu,'t') self.BPut = BPut self.u = self.BPut.base_ring().gens()[2] var1 = self.x var2 = self.y vart = self.t if self.formalSumU == None: logBPx = BPQut(self.logBP.substitute(t = var1*vart)) logBPy = BPQut(self.logBP.substitute(t = var2*vart)) expBPu = BPQut(self.expBP) parts = [self.nVal - self.pVal**j + 1 for j in [0..self.__log_prec]] #print str(parts) etrunc = [expBPu.truncate(N) for N in parts] etrunc.reverse() #print str(etrunc) esplit = [etrunc[0]]+[etrunc[j] - etrunc[j-1] for j in range(1,len(etrunc))] #print str(esplit) esplitser = [BPQut(e).add_bigoh(self.nVal) for e in esplit] #print str(esplitser) bounds = [self.pVal**i for i in [1..self.__log_prec+1]] bounds .reverse() #print str(bounds) fstmp = esplitser[0].subs(t = (u*logBPy + logBPx)) for q in range(1,len(esplitser)): fstmp += esplitser[q].substitute( t = (u*logBPy.add_bigoh(bounds[q]) + logBPx.add_bigoh(bounds[q])) ) self.formalSumU = fstmp return self.formalSumU def formal_sum_u_Pb(self): """ part b """ fsBPQ = self.formal_sum_u_Pa() fsBPQ_coeffs = fsBPQ.padded_list(fsBPQ.prec()) fsBP_coeffs = [self.BPu(symbolic_expression(T).subs(self.vnRules)) for T in fsBPQ_coeffs] return fsBP_coeffs def formal_sum_u_Pc(self,ivalB=1): """ part c """ fsBP_coeffs = self.formal_sum_u_Pb() output = [w.subs(u = ivalB) for w in fsBP_coeffs] return output def formal_sum_u(self,ivalB=1): """ formal sum [u]y +_BP x implemented in several different functions part a takes by far the majority of the time this is the formal sum function we actually use """ coeffs = self.formal_sum_u_Pc(ivalB) i_series = sum([self.BPxyt(coeffs[j])*self.BPxyt(self.t)**j for j in range(0,len(coeffs))])+O(self.BPxyt(self.t)**self.expBP.prec()) return i_series def red_p_series(self): """ reduced p-series """ if self.redpSeries != None: #print "already defined:" return self.redpSeries self.exp_BP() out = (self.expBP.substitute(t=(self.pVal*self.logBP))/self.t) outsubbed = [self.BPxyt(self.BPxyTilde(symbolic_expression(w).substitute(self.vnRules))) for w in out.padded_list(out.prec())] self.redpSeries = sum([outsubbed[i]*self.BPxyt(self.y)**i*self.BPxyt(self.t)**i for i in range(0,out.prec())])+O(self.BPxyt(self.t)**out.prec()) return self.redpSeries def cyclic_powerop(self,verbosity=None): """ the cyclic power operation """ if self.cyclicPowerOp != None: #print "already defined:" return self.cyclicPowerOp var1 = self.BPxyt(self.x) var2 = self.BPxyt(self.y) vart = self.BPxyt(self.t) if verbosity == None: parts = [var1*vart]+[self.formal_sum(ivalB=j) for j in range(1,self.pVal)] else: parts = [var1*vart] for j in range(1,self.pVal): print " part "+str(j) time parts.append(self.formal_sum(ivalB=j)) self.cyclicPowerOp = prod(parts) return self.cyclicPowerOp def cyclic_powerop_u(self,verbosity=None): """ the cyclic power operation """ if self.cyclicPowerOpU != None: #print "already defined:" return self.cyclicPowerOpU var1 = self.BPxyt(self.x) var2 = self.BPxyt(self.y) vart = self.BPxyt(self.t) if verbosity == None: parts = [var1*vart]+[self.reduce(self.formal_sum_u(j)) for j in range(1,self.pVal)] else: parts = [var1*vart] for j in range(1,self.pVal): print " part "+str(j) time parts.append(self.reduce(self.formal_sum_u(j))) self.cyclicPowerOpU = prod(parts) return self.cyclicPowerOpU def a_class(self,r): """ the a-classes; a_class(r) is the coefficient of x^{r+1} in cyclicPowerOp """ self.formal_sum_u() self.cyclic_powerop_u() var1 = self.BPxyt(self.x) vart = self.BPxyt(self.t) coeff_list = self.cyclicPowerOpU.padded_list(self.nVal) return sum([coeff_list[j].coefficient({var1:r+1})*vart**(j-r-1) for j in range(r+1,len(coeff_list))])+O(vart**(len(coeff_list)-r-1)) def reduce(self,ser): """ reduce a series modulo red_p_series: 1. make padded list for series 2. for each term in padded list, get list of monomials 3. for each monomial, get numerator of rational coefficient and determine divisibility by pVal 4. multiply red_p_series by necessary factor, and subtract from input series 5. return to step 1 """ self.red_p_series() tmp_ser = ser tmp_ser_2 = self.reduce_first_unreduced_term(tmp_ser) while tmp_ser_2 != tmp_ser: tmp_ser = tmp_ser_2 tmp_ser_2 = self.reduce_first_unreduced_term(tmp_ser) return tmp_ser_2 def reduce_first_unreduced_term(self,ser): term_list = ser.padded_list(ser.prec()) #print str(ser) for j in range(0,len(term_list)): term = term_list[j] #print "term: "+str(term) rtm = self.reduce_term_multiplier(term)*self.BPxyt(self.t)**j #print "rtm: "+str(rtm) if rtm != 0: out_ser = ser - rtm*self.redpSeries return out_ser return ser def reduce_term_multiplier(self,term): """ returns multiplier for red_p_series by which to reduce input term """ monomial_list = term.monomials() multiplier = 0 for mon in monomial_list: Coeff = QQ(term.monomial_coefficient(mon)) d = Coeff.numerator().quo_rem(self.pVal)[0] multiplier += d/Coeff.denominator()*mon return self.BPxyt(multiplier) def a_class_red(self,r): """ return reduced a_class """ return self.reduce(self.a_class(r)) def first_check(self): """ check first possible obstruction; MC_{2(p-1)}/[(2p-1)*a_0^{2p-4}] """ if self.FirstCheck != None: print "already computed this" return self.FirstCheck import time print "starting at "+str(time.localtime()) self.__repr__() print "computing expBP.." self.exp_BP() print "..finished at: "+str(time.localtime()) print " -- " print "computing reduced p-series.." self.red_p_series() print "..finished at: "+str(time.localtime()) print " -- " print "computing [u]y +_BP x.." self.formal_sum_u() print "..finished at: "+str(time.localtime()) print " -- " print "computing cyclic power operation.." self.cyclic_powerop_u("verbose") C0 = self.a_class_red(0) C1 = self.a_class_red(self.pVal-1) C2 = self.a_class_red(2*(self.pVal - 1)) print " -- " print " C0:" print str(C0) print " C1:" print str(C1) print " C2:" print str(C2) fc_unred = -1*self.BPxyt(self.v[1])*C0*C1 - C0*C2 + self.pVal*C1**2 fc = self.reduce(fc_unred) print "ended at: "+str(time.localtime()) print "____first possible obstruction____" print str(fc) print "" print "" self.FirstCheck = fc return fc def MC2pm1(self): out_unred = (2*self.pVal - 1)*self.a_class_red(0)**(2*self.pVal - 4) * self.first_check() return self.reduce(out_unred) def gen_mult_inv(self,r=None): """ returns general multiplicative inverse, through specified range r (default range is self.nVal) """ if r == None: r = self.nVal Apoly = PolynomialRing(QQ,['u']+['a%s'%((self.pVal-1)*n) for n in range(1,ceil(r/(self.pVal-1)))]) u = Apoly.gens()[0] A = (1,)+Apoly.gens()[1:] Aps = PowerSeriesRing(Apoly,'w') w = Aps.gen() # think of u as 1/a0 # then a0*g is the thing we really want to invert g = 1+sum([u*A[i]*w**(i*(self.pVal-1)) for i in range(1,ceil(r/(self.pVal-1)))])+O(w**r) tmp = (1/g) # testing: #print str(g*tmp) return tmp def McClure(self,en=None,what_to_return = None): """ do MC_n calculation default value of n is 2(p-1) to get formal version, set second variable to "formal" to get unreduced version , set second variable to "unred" """ if en == None: en = 2*(self.pVal - 1) coeff_ser = self.gen_mult_inv(en+1)**(en+1) summand_list = coeff_ser.padded_list(en+1) rCP_list = [] for k in [0..en]: lognum = log(en-k+1,self.pVal) if floor(lognum) == lognum: tmp_term = self.L[lognum]*(en-k+1) tmp_term = symbolic_expression(tmp_term).subs(self.vnRules) else: tmp_term = 0 rCP_list.append(tmp_term) Apolyt = PolynomialRing(QQ,['u']+['a%s'%((self.pVal-1)*j) for j in range(0,ceil((en+1)/(self.pVal-1)))]+list(self.v[1:])) At = Apolyt.gens()[1:ceil((en+1)/(self.pVal-1))+1] ut = Apolyt.gens()[0] Avt = Apolyt.gens()[ceil((en+1)/(self.pVal-1))+1:] Idl = Apolyt.ideal([ut*At[0] - 1]) #print str(At) #print str(Avt) Aquot = QuotientRing(Apolyt,Idl) #u's and a0's : MCn_ua0 = At[0]^(en)*sum([a*b for (a,b) in zip(rCP_list,summand_list)]) #push to quotient: MCnbar = Aquot(MCn_ua0) #lift: MCnformal = MCnbar.lift() if what_to_return == "formal": return MCnformal #now substitute a_class_red's P = PolynomialRing(QQ,[self.y]+list(At)+list(self.v[1:])) T = PowerSeriesRing(P,[self.t]) Taclasses = [T(self.a_class_red(m*(self.pVal-1))) for m in range(0,ceil((en+1)/(self.pVal-1)))] PAt = [P(al) for al in At] di = dict(zip(PAt,Taclasses)) # parent includes ai's MCnUnredA = P(MCnformal).subs(di) precision = MCnUnredA.prec() mp = MCnUnredA.polynomial() cl = [self.BPxyTilde(SR(coeff)) for coeff in mp.padded_list(precision)] MCnUnred = sum([cl[j]*self.BPxyt(self.t)**j for j in range(0,len(cl))])+O(self.BPxyt(self.t)^precision) #now parent is self.BPxyt if what_to_return == "unred": return MCnUnred MCn = self.reduce(MCnUnred) return MCn def flatten(x): """flatten(sequence) -> list Returns a single, flat list which contains all elements retrieved from the sequence and all recursively contained sub-sequences (iterables). Examples: >>> [1, 2, [3,4], (5,6)] [1, 2, [3, 4], (5, 6)] >>> flatten([[[1,2,3], (42,None)], [4,5], [6], 7, MyVector(8,9,10)]) [1, 2, 3, 42, None, 4, 5, 6, 7, 8, 9, 10]""" result = [] for el in x: #if isinstance(el, (list, tuple)): if hasattr(el, "__iter__") and not isinstance(el, basestring): result.extend(flatten(el)) else: result.append(el) return result def ps_inverse_Lagrange(self,f): """ computes inverse of power series, using Lagrange inversion """ if f.valuation() != 1: raise ValueError, "series must have valuation one for reversion" if f.prec() is infinity: raise ValueError, "series must have finite precision for reversion" t = parent(f).gen() h = t/f k = 1 g = 0 for i in range(1, f.prec()): k *= h g += (1/i)*k.padded_list(i)[i - 1]*t^i g += O(t^f.prec()) return g #B = BPPowerOps(5,30)