Opened 10 years ago
Last modified 7 years ago
#11457 new enhancement
Witt Vectors
Reported by: | tdupu | Owned by: | roed |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | padics | Keywords: | witt vectors, padic, rings |
Cc: | Merged in: | ||
Authors: | Taylor Dupuy, David Roe | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
An implementation of the ring of witt vectors and their elements for any commutative ring
Attachments (10)
Change History (30)
Changed 10 years ago by
Changed 10 years ago by
Changed 10 years ago by
Changed 10 years ago by
Changed 10 years ago by
Changed 10 years ago by
comment:1 Changed 10 years ago by
Changed 10 years ago by
comment:2 Changed 10 years ago by
- Component changed from PLEASE CHANGE to padics
- Owner changed from tbd to roed
Witt Vectors! Yes! That would be awesome. I will stay tuned.
By the way, you should feel free to "Replace existing attachment of the same name" so that you aren't attaching a million files. It could get sizeable after a while.
comment:3 Changed 10 years ago by
roed314: the coercion system catches other problems and doesn't forward them all on your real problem is: 100 return x[0]
101 if n>0:
--> 102 divs = divisors(n)
103 dict = {} 104 wn = 0
NameError?: global name 'divisors' is not defined you need to import divisors from sage.rings.arith me: so you have to do like nn=Integer(n) nn.divisors()
roed314: that would work too then you have to import Integer from sage.rings.integer
Changed 8 years ago by
This was made during sage days 44. It runs. Unless I someone messed up when I uploaded this which is a real possibility.
Changed 8 years ago by
comment:4 Changed 8 years ago by
There is a problem in the division by p in characteristic p.
sage: a = pWittElement({0:GF(3)(1), 1:GF(3)(2), 2:GF(3)(2)}, Wp) sage: Wp=pWittVectors(GF(3),3) sage: a = pWittElement({0:GF(3)(1), 1:GF(3)(2), 2:GF(3)(2)}, Wp) sage: a^2 + a --------------------------------------------------------------------------- ZeroDivisionError Traceback (most recent call last) /home/tdupu/sage-5.6/devel/sage-oms/<ipython console> in <module>() /home/tdupu/sage-5.6/local/lib/python2.7/site-packages/sage/structure/element.so in sage.structure.element.RingElement.__pow__ (sage/structure/element.c:14627)() /home/tdupu/sage-5.6/local/lib/python2.7/site-packages/sage/structure/element.so in sage.structure.element.generic_power_c (sage/structure/element.c:26200)() /home/tdupu/sage-5.6/local/lib/python2.7/site-packages/sage/structure/element.so in sage.structure.element.RingElement.__mul__ (sage/structure/element.c:14096)() /home/tdupu/sage-5.6/local/lib/python2.7/site-packages/sage/structure/element.so in sage.structure.element.RingElement._mul_ (sage/structure/element.c:14222)() /home/tdupu/sage-5.6/local/lib/python2.7/site-packages/sage/rings/padics/witt.pyc in _mul_(self, other) 219 a = self.dict 220 b = other.dict --> 221 return C(wittprod(self.p,a,b), self.parent() ) 222 223 def frob(self): /home/tdupu/sage-5.6/local/lib/python2.7/site-packages/sage/rings/padics/witt.pyc in wittprod(p, x, y) 116 prod[0] = x[0]*y[0] 117 for j in range(1,m): --> 118 prod[j] = ( witt(p,j,x)*witt(p,j,y) - witt(p,j-1,frob(p,prod)) )/p**j 119 return prod 120 /home/tdupu/sage-5.6/local/lib/python2.7/site-packages/sage/structure/element.so in sage.structure.element.RingElement.__div__ (sage/structure/element.c:14855)() /home/tdupu/sage-5.6/local/lib/python2.7/site-packages/sage/structure/coerce.so in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:6832)() /home/tdupu/sage-5.6/local/lib/python2.7/site-packages/sage/structure/element.so in sage.structure.element.RingElement.__div__ (sage/structure/element.c:14834)() /home/tdupu/sage-5.6/local/lib/python2.7/site-packages/sage/rings/finite_rings/integer_mod.so in sage.rings.finite_rings.integer_mod.IntegerMod_int._div_ (sage/rings/finite_rings/integer_mod.c:21514)() ZeroDivisionError: Inverse does not exist.
comment:5 follow-up: ↓ 6 Changed 8 years ago by
It looks like the newest patch is formatted fine.
Does coercion from the integers into a ring of Witt Vectors work right? What is the image of p?
comment:6 in reply to: ↑ 5 ; follow-up: ↓ 7 Changed 8 years ago by
Replying to roed:
It looks like the newest patch is formatted fine.
Does coercion from the integers into a ring of Witt Vectors work right? What is the image of p?
Coercion is not implemented. I'd also like to implement coercions for padics but I first need to deal with this division by p thing.
Also, I have some modifications that It won't let me refresh. I'm having trouble with these "phases". It's not letting me refresh the patch
(sage-sh) tdupu@tdupu-Gazelle-Professional:sage-oms$ hg qrefresh abort: cannot refresh immutable revision (see "hg help phases" for details)
I tried modifying my .hg/hgrc in my working branch of sage ~/sage-whatever like so
[phases] publish = False
this isn't working.
comment:7 in reply to: ↑ 6 Changed 8 years ago by
Replying to tdupu:
Replying to roed:
It looks like the newest patch is formatted fine.
Does coercion from the integers into a ring of Witt Vectors work right? What is the image of p?
Coercion is not implemented. I'd also like to implement coercions for padics but I first need to deal with this division by p thing.
Also, I have some modifications that It won't let me refresh. I'm having trouble with these "phases". It's not letting me refresh the patch
(sage-sh) tdupu@tdupu-Gazelle-Professional:sage-oms$ hg qrefresh abort: cannot refresh immutable revision (see "hg help phases" for details)I tried modifying my .hg/hgrc in my working branch of sage ~/sage-whatever like so
[phases] publish = Falsethis isn't working.
Weird. I have no idea what's going on there. Perhaps you should e-mail sage-devel?
comment:8 follow-up: ↓ 12 Changed 8 years ago by
There are at least two issues with this implementation of Witt vectors:
1) The Frobenius map on the Witt vectors doesn't just take the p-th power of every coordinate. This is only true if p = 0 in the base ring.
2) The definition of Witt vector addition and multiplication through the ghost components don't work over a ring where p isn't invertible (or at least a non-zero divisor). This is why every time this definition is used to actually define the Witt vectors, it is accompanied by a functoriality condition.
I fear that fixing the issues requires rewriting the methods from scratch.
I am also wondering whether anything speaks against implementing Witt vectors for general nests as well (including the nest of all positive integers, leading to "big Witt vectors").
comment:9 Changed 8 years ago by
On an unrelated note, it would be helpful to know which (all? just the last two?) patches here are to be applied, and perhaps to make one big "master" patch as well, if relevant.
@darij: would it be possible to "fix" the issues you raise by appropriate documentation about allowable base rings (or even try/except or assert for inappropriate ones)? I do agree that whatever infrastructure is here should be robust enough to eventually support at least the big Witt vectors, if not even other sets. Maybe a placeholder class to inherit from...
Another thought - is there really any reason to have the functions wittsum
etc. as separate functions?
Finally, there are various formatting issues, but that's not worth fixing until a more final patch, likely.
comment:10 Changed 8 years ago by
Restricting the base ring? I don't think so. If we wanted to fix both issues at the same time this way, we'd have to restrict R to the zero ring, which is definitely not the intention ;) but even restricting to char-p or char-coprime-to-p only makes Witt vectors a lot less powerful.
comment:11 Changed 8 years ago by
The reply button doesn't seem to be working.
Re Darij's Comments: 1) Do you mean p is the characteristic of the base ring? Yeah, this is an issue. I mentioned this before but still haven't fixed it. 2) The function also only works for p-typical witt vectors. There should be a slicker way of implementing this. The hard part is computing the witt polynomials.
Re: kcrisman's comments: -One could add change the flow of the code: Here is a quick-fix the characteristic of the base is zero then do this. If not they raise a NotImplementedError?.
-Also, the big witt vectors can not be implemented using what i did since I used that w_{n-1}(a^{p) + p}n a_n = w_n(a) in the recurrence.
-The witt sums and witt additions should be excluded because they may be used for Greenberg transforms (which will have applications to say lifting J-invariants). I have talked a little bit to Luis Finotti about this.
There are snippets of big witt vectors code in the original patches (not the pWittVectors patch) that can be used but the indexing is off in that code I think.
I will try and make a list of other issues soon. It might be better to make something on github.
comment:12 in reply to: ↑ 8 Changed 8 years ago by
Replying to darij:
There are at least two issues with this implementation of Witt vectors:
1) The Frobenius map on the Witt vectors doesn't just take the p-th power of every coordinate. This is only true if p = 0 in the base ring.
darij actually means in characteristic p base ring. The correct form of the p-frobenius has the ghost component equation
w_{n}(f_p) = w_{n+1}
See Hazewinkel (5.27).
2) The definition of Witt vector addition and multiplication through the ghost components don't work over a ring where p isn't invertible (or at least a non-zero divisor). This is why every time this definition is used to actually define the Witt vectors, it is accompanied by a functoriality condition.
I fear that fixing the issues requires rewriting the methods from scratch.
The following two suggestions have been made:
1) Implementing a division by p^n
function. This is just a morphism of modules from p^{n} R
to R/ann(p^{n} )
.
2) Implementing a lifting function. If R has the form A/p^n A
then we would like a function which takes elements of A to elements in A/p^{n+1} A
.
I am also wondering whether anything speaks against implementing Witt vectors for general nests as well (including the nest of all positive integers, leading to "big Witt vectors").
I'm not sure what you mean here. Could you explain more or provide a link? Suggestions for implementations of Witt-Burnside functors are also welcome.
comment:13 Changed 8 years ago by
The fix I mentioned to darij's comments also has the drawback of not being able to implement Greenberg transforms. We would like to be able to take a polynomial and simple take a Greenberg transform of them (i.e. just the computation written out in witt components). It would be nice to be able to do this "abstractly" i.e. without specifying a particular p. Do people have opinions on this? Should we just implement this for a particular p? Should we make this a whole other ticket?
comment:14 follow-up: ↓ 15 Changed 8 years ago by
Hi Taylor,
1) Implementing a division by p^{n function. This is just a morphism of modules from p}{n} R to R/ann(p^{{n} ) . }
2) Implementing a lifting function. If R has the form A/p^{n A then we would like a function which takes elements of A to elements in A/p}{n+1} A .
I don't think any of these would help compute Witt vector addition over an arbitrary commutative ring. When you take ghost components over a ring in which p is a zero-divisor, you lose information; you can't gain it back by lifting as far as I know.
What I meant by "big Witt vectors" are Witt vectors that are not p-typical (Section 9 of Hazewinkel). We should be able to use some of the extensive symmetric functions implementation we have in Sage (including Witt coordinates since #14775). While I'd love to play around with Witt-Burnside, too, I don't know enough about this generalization to implement it well (though I can learn).
When you say "specifying a particular p", does p mean the polynomial or the prime? It might be interesting to do it on a generic polynomial, though I wasn't thinking of that; having addition, negation and multiplication would already be a wonderful start.
Best regards,
Darij
comment:15 in reply to: ↑ 14 Changed 8 years ago by
Replying to darij:
Hi Taylor,
1) Implementing a division by p^{n function. This is just a morphism of modules from p}{n} R to R/ann(p^{{n} ) . }
2) Implementing a lifting function. If R has the form A/p^{n A then we would like a function which takes elements of A to elements in A/p}{n+1} A .
I don't think any of these would help compute Witt vector addition over an arbitrary commutative ring. When you take ghost components over a ring in which p is a zero-divisor, you lose information; you can't gain it back by lifting as far as I know.
I need to think if something like this can be well-defined. This isn't clear to me right now.
What I meant by "big Witt vectors" are Witt vectors that are not p-typical (Section 9 of Hazewinkel). We should be able to use some of the extensive symmetric functions implementation we have in Sage (including Witt coordinates since #14775). While I'd love to play around with Witt-Burnside, too, I don't know enough about this generalization to implement it well (though I can learn).
oooh, I didn't know about this. I need to take a look at this. Do you have any suggestions? I'm not too familiar with what has been done there.
When you say "specifying a particular p", does p mean the polynomial or the prime? It might be interesting to do it on a generic polynomial, though I wasn't thinking of that; having addition, negation and multiplication would already be a wonderful start.
I means p as a prime. I would like to be able to leave p unspecialized (so you can see formulas with the symbol 'p' rather than an actual prime). I vaguely recall mathematica being able to do things like this. It is probably too much to ask.
comment:16 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:17 Changed 8 years ago by
Here are some suggested that I'm copy-pasting from the emails to fix the division problems. The formatting is a little weird, but I think people can read it if they need to. Here is the link to the symmetric polynomials patch that darij wrote http://trac.sagemath.org/ticket/14775
FIRST IMPLEMENTATION: Try the "lifting and dividing" procedure. I have broken it up into subcases. Are there other objects we could consider?
Here are the cases we could consider:
A) finitely generated rings over ZZ (may not be implemented). This could be maybe broken into two subcases, 1) Rings in which p is a zero divisor (may not be implemented) i) Rings for which p is nilpotent (these are just finitely generated algebras over ZZ/p^n, and we can do computations with lifts as it is well defined.) ii) Ring for which p is not nilpotent (this may be hard, I need to think about this too) 2) Rings in which p is a non-zero divisor B) Finite Fields. (could be coerced into case A?) C) p-Adic Rings. (we could probably use case A here but I'm not too familiar with this. ) D) Domains.
TODO:
*Implement the control flow suggested above. *Implement the frobenius correction. *Re A.1.ii) Rings where p is a zero divisor but not nilpotent could be tricky too since division by p could be really messed up. For example division by powers of p in the ring ZZ[x,p]/(p^5 x) or lifts of it could be totally nasty. *Re A.1.i) We need to check that two functions are implemented. --A lifting function which lifts an element of a ring mod p^n to an element of a ring mod p^{m} where m>n --A division function which is a map from an element of p^n A to A/ann(p^n). *We should also clarify where these functions should be implemented within sage. For example, the lifting procedure would probably be useful outside of the witt vectors code. *Is sage coercion to finitely generated ZZ algebras working? For example, if we implemented to code on the level of finitely generated ZZ-algebras, then ran it on GF(4)[x]/(x^4+x) would it work? Should we care? *Can sage test for nilpotence of elements in finitely generated ZZ-algebras? *Can sage test if an element is a zero divisor in a finitely generated ZZ-algebra? Can it compute its annihilator ideal? *Are there classes implemented already that would give computational advantages that we are not considering?
SECOND IMPLEMENTATION: I thought about it and I like the symmetric polynomials/generating function identities approach to Witt sum and multiplication polynomials/rules. I think working with just the big Witt vectors is a good first step for the applications we have in mind.
Recall:
{{ -There is an injective functorial group homomorphism from the Ring of big Witt vectors (viewed as tuples in the usual way) to the ring of power series 1+tAt? given by (x_1, x_2,...) maps to prod_i (1-x_i t^{i)}{-1}. Recall that the multiplication structure on the power series is induced from the rule (1-xt)^{{-1}*(1-yt)}{-1} = (1-xyt)^{{-1} Together with the identity Prod (1- x_i t}i)^{{-1} = Prod (1-y_i t)}{-1} That is, we views the x_i's as symmetric polynomials in y_i's and derive the rule by rewriting the final product in terms of elementary symmetric polynomials. The addition rule is just usual power series multiplication. }}
At any rate, I think the suggestion of Darij is as follows: use the isomorphism between power series functor and the big Witt functor to derive the sum and addition polynomials. I outline it the idea for the multiplication polynomials
1) the isomorphism between the big Witt vectors and power series tells is that the image of (x_1,x_2,...)*(y_1,y_2,...)=(m_1,m_2,...) under the homomorphism will be Prod(1-m_it^i)^{-1}. We can expand this out to get 1 + c_1(m) t + c_2(m) t^2 + .... where m = (m_1,m_2,....) are the witt multiplication polynomials and c_j(m) is a simple polynomial we can write down (and have a simple closed form expression of --- it is the sum of terms m_1^{j_1} m_2^{j_2} ... where j_1 + 2j_2 + ... = j ) 2) If we consider the x_i's and y_i's as elementary symmetric polynomials in auxiliary variables z_i and w_i so that prod_i 1/(1-x_i t^i) = \prod_i 1/(1-w_i t) \prod_i 1/(1-y_i t^i) = \prod_i 1/(1-z_i t) then the product \prod 1/(1-w_iz_i t) can be expanded and then since it is symmetric the coefficients of the expansion can be written as a symmetric functions in w_i and z_i (ie polyns in x_i and y_i): prod_i 1/(1-x_it^i) prod_i 1/(1-y_i t^i) = 1 + M_1(x,y) t + M_2(x,y)t^2 +.... where M_1,M_2, ... are explicitly computable. 3) I think what darij proposed is to use the identities c_i(m) = M_i(x,y) to solve for m_1, m_2, ...
Am I stating this correct? Are there simplifications that one can make in doing this? I haven't tried to do this in sage so I don't know if solving these equations is actually faster than solving for the witt addition and multiplication polynomials "by hand". Is there a simpler way of factoring these power series?
comment:18 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:19 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:20 Changed 7 years ago by
- Milestone changed from sage-6.3 to sage-6.4
This is what it can do right now