Witt Vectors

[tdupu]

An implementation of the ring of witt vectors and their elements for any commutative ring

Component: padics

Keywords: witt vectors, rings

Author: Jacob Dennerlein

Branch/Commit: u/gh-nielrenned/witt_vectors @ d195667

Issue created by migration from https://trac.sagemath.org/ticket/11457

[tdupu]

Attachment: witt.patch.gz

[tdupu]

Attachment: witt.2.patch.gz

[tdupu]

Attachment: witt.3.patch.gz

[tdupu]

Attachment: witt.4.patch.gz

[tdupu]

Attachment: witt.5.patch.gz

[tdupu]

comment:1

Attachment: witt.6.patch.gz

This is what it can do right now

sage: W = Big
Big_Witt_Ring    Big_Witt_Vector  
sage: W = Big_Witt_Ring(ZZ)
sage: x = [1 for i in range(10)]
sage: w = W(x)
sage: w+w
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/usr/local/sage-4.7/devel/sage-sandbox/<ipython console> in <module>()

TypeError: unsupported operand type(s) for +: 'Big_Witt_Vector' and 'Big_Witt_Vector'

[kcrisman]

comment:2

Attachment: witt.7.patch.gz

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.

[tdupu]

comment:3

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

[tdupu]

This was made during sage days 44. It runs. Unless I someone messed up when I uploaded this which is a real possibility.

[tdupu]

Attachment: witt.8.patch.gz

Attachment: witt.9.patch.gz

[tdupu]

comment:4

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.

[tdupu]

Attachment: pwittvectors.patch.gz

Hopefully I'm using mercurial right...

[roed314]

comment:5

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?

[tdupu]

comment:6

Replying to @roed314:

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.

[roed314]

comment:7

Replying to @tdupu:

Replying to @roed314:

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.

Weird. I have no idea what's going on there. Perhaps you should e-mail sage-devel?

[darijgr]

comment:8

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").

[kcrisman]

comment:9

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.

@darijgr: 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.

[darijgr]

comment:10

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.

[tdupu]

comment:11

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.

[tdupu]

comment:12

Replying to @darijgr:

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.

[tdupu]

comment:13

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?

[darijgr]

comment:14

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

[tdupu]

comment:15

Replying to @darijgr:

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.

[tdupu]

comment:17

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 #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+tATrac macro t given by
(x_1, x_2,...) maps to prod_i (1-x_i tⁱ⁾{-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ⁱ⁾{-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?

[nielrenned]

comment:21

I have been working an implementation of Witt vectors using Luis Finotti's work in this paper. I'd like to take over this ticket and begin merging this work, but I want to be careful about credit. Also, I'm new to the Trac server, and don't want to make changes hastily.

If/when I accept this ticket, should I change the "Authors" field to just my name? Or my name and the previous authors? I'm not really building on the previous work (as I've just discovered it).

[kcrisman]

comment:22

Good questions! Two thoughts.

• First, the "Author" field really is about who writes the final version that goes in. So the author can change over time, and if you end up starting from scratch, then maybe you'd be sole author. For now we can even just leave it blank, obviously this ticket has languished.
• Second, there is a likely coming move to Github. So you may wish to put a temporary branch here for anyone to try out whatever functionality you do have, but with the recognition that it would (potentially) be migrated to GH in the near-to-mid-term future. You can certainly feel free to suggest a different branch, though, as that history is still here (for now, there is a plan on how to migrate).

[nielrenned]

comment:23

Replying to Karl-Dieter Crisman:

Good questions! Two thoughts.

• First, the "Author" field really is about who writes the final version that goes in. So the author can change over time, and if you end up starting from scratch, then maybe you'd be sole author. For now we can even just leave it blank, obviously this ticket has languished.
• Second, there is a likely coming move to Github. So you may wish to put a temporary branch here for anyone to try out whatever functionality you do have, but with the recognition that it would (potentially) be migrated to GH in the near-to-mid-term future. You can certainly feel free to suggest a different branch, though, as that history is still here (for now, there is a plan on how to migrate).

Thanks for your prompt reply! Crazy timing on my part, seeing as that vote started yesterday. Looks like the new plan is the (typical?) fork-then-pull-request structure. Does this mean it would perhaps be better to go ahead and fork? Or should I also create a temporary branch, as you suggested? The code is (mostly) functional, so the temp branch could be useful, but it's not clear to me what happens after the move to GitHub. Would I scrap the branch and then make a PR marked as Draft?

[roed314]

comment:24

I've deleted Taylor and my names from Authors; once you have a branch on here that's ready for review feel free to replace it with your own.

As for Github, the plan is to convert branches on trac tickets into branches on the sagetrac-mirror, together with PRs from there. If you want to work on this project before the transition, you should do so here on trac (there's no way that's yet supported to develop Sage on github). Of course, you can also wait and create a fork and PR once Sage transitions, but we don't have an explicit timeline for when that will be (aside from definitely more than two weeks from now, since that's when the voting ends).

[roed314]

Changed author from Taylor Dupuy, David Roe to none

[nielrenned]

comment:25

Okay, great. Thanks for your clear answers! Code to come soon.

[nielrenned]

Branch: u/gh-nielrenned/witt_vectors

[nielrenned]

Last 10 new commits:

be75b3c	Implement the 'standard' sum and product methods.
accbd22	Implement negation.
b7ab2de	Change how the 'algorithm' keyword behaves.
128fea6	Implement Witt Vector inversion and division.
056f4c5	Implement the Finotti method for Witt vector operations.
52d30db	Better error message
3091a8f	Refactor WittVector class
b0380e7	Implement computation of sum/prod when p is a unit.
15b39dd	Implement faster integer coercion for p-typical Witt Rings
a574ddc	Implement Zq isomorphism algorithm

[nielrenned]

Author: Jacob Dennerlein

[nielrenned]

Commit: a574ddc

[sagetrac-git]

Changed commit from a574ddc to 87ef62b

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

cc1382a	Implement cardinality and iterability.
5a5751f	Fix characteristic method.
b9f815d	Add hashing to Witt Vector
d9f25ff	Update representation string for non-p-typicals
86d802f	Correct negation for p=2
9cb7992	Fix finite field coercion.
87ef62b	Fix _fcppow

[sagetrac-git]

Changed commit from 87ef62b to 7f068e2

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7f068e2

Fix error in Witt vector inversion.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

d195667

Remove all E1 errors.

[sagetrac-git]

Changed commit from 7f068e2 to d195667