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:

Status badges

Description

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

Attachments (10)

witt.patch (6.9 KB) - added by tdupu 10 years ago.
witt.2.patch (6.6 KB) - added by tdupu 10 years ago.
witt.3.patch (6.9 KB) - added by tdupu 10 years ago.
witt.4.patch (7.3 KB) - added by tdupu 10 years ago.
witt.5.patch (7.4 KB) - added by tdupu 10 years ago.
witt.6.patch (7.9 KB) - added by tdupu 10 years ago.
witt.7.patch (7.9 KB) - added by tdupu 10 years ago.
witt.8.patch (212 bytes) - added by tdupu 8 years ago.
This was made during sage days 44. It runs. Unless I someone messed up when I uploaded this which is a real possibility.
witt.9.patch (4.9 KB) - added by tdupu 8 years ago.
pwittvectors.patch (4.3 KB) - added by tdupu 8 years ago.
Hopefully I'm using mercurial right…

Download all attachments as: .zip

Change History (30)

Changed 10 years ago by tdupu

Changed 10 years ago by tdupu

Changed 10 years ago by tdupu

Changed 10 years ago by tdupu

Changed 10 years ago by tdupu

Changed 10 years ago by tdupu

comment:1 Changed 10 years ago by tdupu

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'

Changed 10 years ago by tdupu

comment:2 Changed 10 years ago by kcrisman

  • 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 tdupu

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 tdupu

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 tdupu

comment:4 Changed 8 years ago by tdupu

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.

Changed 8 years ago by tdupu

Hopefully I'm using mercurial right...

comment:5 follow-up: Changed 8 years ago by 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?

comment:6 in reply to: ↑ 5 ; follow-up: Changed 8 years ago by 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 = False

this isn't working.

comment:7 in reply to: ↑ 6 Changed 8 years ago by roed

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 = False

this isn't working.

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

comment:8 follow-up: Changed 8 years ago by 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.

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

Last edited 8 years ago by darij (previous) (diff)

comment:9 Changed 8 years ago by kcrisman

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 darij

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 tdupu

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}(ap) + pn 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 tdupu

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 tdupu

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: Changed 8 years ago by darij

Hi Taylor,

1) Implementing a division by pn 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/pn 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 tdupu

Replying to darij:

Hi Taylor,

1) Implementing a division by pn 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/pn 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 jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:17 Changed 8 years ago by tdupu

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 ti){-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 ti){-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 vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:19 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:20 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.