#11457: Witt Vectors
----------------------------------------------+-------------------------
Reporter: tdupu | Owner: roed
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.12
Component: padics | Resolution:
Keywords: witt vectors, padic, rings | Merged in:
Authors: Taylor Dupuy, David Roe | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
----------------------------------------------+-------------------------
Comment (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+tA[[t]] 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?
--
Ticket URL: <http://trac.sagemath.org/ticket/11457#comment:17>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
