Introduction#
Thanks to Xavier Caruso and David Lubicz, Magma now contains an implementation of linear algebra over \({\bf Z}_p[[u]]\) and related rings [Caurso and Lubicz, 2012]. This is a first step in various calculations with \(p\)-adic Hodge theory, to be able to compute with modules over suitable approximations in these rings.
The package deliberately builds a wrapper level through user-defined types in Magma. While one could alternatively just do everything in terms of power (and Laurent) series rings over the \(p\)-adics directly, this extra layer is hoped to make it easier to use the functionality in a coherent way. Some of the common functions applicable to power series, matrices, and modules have been copied over, but not all of them. The underlying attributes can be accessed directly in the cases where there is no equivalent on the types described here. Most notably, vectors and matrices that are user-defined types do not seem yet to be accessible via \(v[i]\) or \(M[i,j]\).
The package has seen limited testing, with not every possibility of precision bounds (in both the \(p\)-adic and power series aspects) being considered in all cases, nor has much work been done for base rings that are extensions of \({\bf Z}_p\).
Background#
Let \(R\) be a discrete valuation ring with residue field of characteristic \(p\), and let \(\nu\) be real. Recall that \(f(u)=\sum_i a_iu^i\) where \(a_i\in{\rm Frac}(R)\) converges for \(|u|<1/p^\nu\) if and only if \(\inf_i v_R(i)+i\nu\) is bounded.
When \(\nu\) is rational, this infinimum is attained. It is called the Gauss valuation, denoted by \(v_\nu(f)\), and the Weierstrass degree \(d_\nu(f)\) is the minimal \(i\) that realises this (by convention, the Weierstrass degree of the zero element is \(-\infty\)). An element is distinguished if its Gauss valuation is 0. We have that \(v_\nu(fg)=v_\nu(f)+v_\nu(g)\) and \(v_\nu(f+g)\ge\min\bigl(v_\nu(f),v_\nu(g)\bigr)\), while \(d_\nu(fg)=d_\nu(f)d_\nu(g)\).
As it is not particularly clear how to represent elements of a convergent series ring in finite form, so we instead work with the “slope” ring of elements of nonnegative Gauss valuation for which \(v_\nu(f)\ge 0\), namely
For instance, when \(\nu=0\), this ring is just the power series ring over \(R\).
There are two related rings of interest. The first extends the coefficients to allow them to have negative valuation in \({\rm Frac}(R)\), namely \(S_p^\nu(R)=S^\nu[1/\pi]\) where \(\pi\) uniformises \(R\). The second is a type of Laurent extension, namely writing \(\nu=a/b\) in lowest terms, we have \(S_u^\nu(R)=S^\nu[\pi^a/u^b]\).
For instance, the polynomial \(u^2/p\) is in \(S^{1/2}({\bf Q}_p)\) and \(S^\nu({\bf Q}_p)\) for all \(\nu\), and inverting it gives us \(p/u^2\in S^{1/2}_u({\bf Q}_p)\). Note that as a power series \(u^2/p\) clearly has infinite radius of convergence, even though it is in not in the slope ring \(S^0({\bf Q}_p)\).
Another example, \(p+u\) has Gauss valuation \(\min(1,\nu)\), and thus the Weierstrass degree is \(0\) for \(\nu\ge 1\) but degree \(1\) for \(\nu<1\).
Both of these “completion” rings are Euclidean, which allows us to construct a module theory over them. While internally Magma has generic code for handling modules over Euclidean rings, with these user-defined types the component parts are all taken from boilerplate package-level implementations.
Basic Operations#
Here are the basic creations and operations for \(S^\nu\) rings and elements. All of these have a direct analogue for \(S_p^\nu\) and \(S_u^\nu\) rings.
Creation Intrinsics#
- SnuRing(F, nu): FldPad, FldRatElt -> SnuRng#
- SpRing(F, nu): FldPad, FldRatElt -> SpRng#
- SuRing(F, nu): FldPad, FldRatElt -> SuRng#
Precision: RngIntElt Default: Infinity()
Given a p-adic field (or ring) \(F\) and a slope \(\nu\) (which can be rational or integral), create the slope ring (or the \(S_p^\nu\) or \(S_u^\nu\) ring). The precision refers to that of the power series ring.
- SnuRing(F): FldPad -> SnuRng#
- SpRing(F): FldPad -> SpRng#
- SuRing(F): FldPad -> SuRng#
- SnuRing(p, e): RngIntElt, RngIntElt -> SnuRng#
- SnuRing(p): RngIntElt -> SnuRng#
- SpRing(p, e): RngIntElt, RngIntElt -> SpRng#
- SpRing(p): RngIntElt -> SpRng#
- SuRing(p, e): RngIntElt, RngIntElt -> SuRng#
- SuRing(p): RngIntElt -> SuRng#
nu : FldRatElt Default: 0 Precision: RngIntElt Default: Infinity()
The first three are the same as above, but with \(\nu\) as a parameter. The others create the slope ring over \({\bf Q}_p\), with \(e\) being the precision of the \(p\)-adic ring in this case.
- SnuRing(S, nu): RngSerPow, FldRatElt -> SnuRng#
- SpRing(S, nu): RngSerPow, FldRatElt -> SpRng#
- SuRing(S, nu): RngSerLaur, FldRatElt -> SuRng#
Given a power-series ring over a \(p\)-adic ring or field and a rational number (or integer), create the slope ring. For the \(S^\nu_u\) ring, one gives a Laurent series ring.
Access Functions#
- R eq S: SnuRng, SnuRng -> BoolElt#
- R ne S: SnuRng, SnuRng -> BoolElt#
- R eq S: SpRng, SpRng -> BoolElt#
- R ne S: SpRng, SpRng -> BoolElt#
- R eq S: SuRng, SuRng -> BoolElt#
- R ne S: SuRng, SuRng -> BoolElt#
Two slope rings are equal if their underlying \(p\)-adic power series rings are the same (including precisions), and the slopes \(\nu\) are the same.
- Slope(S): SnuRng -> RngIntElt#
- Slope(S): SpRng -> RngIntElt#
- Slope(S): SuRng -> RngIntElt#
The slope of the \(S^\nu\) ring.
Element Operations#
The full range of addition, subtraction, multiplication, division (where applicable) and powering are available, similarly with equality.
- Parent(f): SnuElement -> SnuRng#
- Parent(f): SpElement -> SpRng#
- Parent(f): SuElement -> SuRng#
Return the \(S^\nu\) ring to which the element belongs.
- IsWeaklyZero(f): SnuElement -> BoolElt#
- IsWeaklyZero(f): SpElement -> BoolElt#
- IsWeaklyZero(f): SuElement -> BoolElt#
This is the proper way to test equality with elements of \(S^\nu\). It checks whether every (known) coefficient is zero to within the \(p\)-adic precision.
Valuation and Degree#
- GaussValuation(f): SnuElement -> FldRatElt#
- GaussValuation(f): SpElement -> FldRatElt#
- GaussValuation(f): SuElement -> FldRatElt#
- WeierstrassDegree(f): SnuElement -> FldRatElt#
- WeierstrassDegree(f): SpElement -> FldRatElt#
- WeierstrassDegree(f): SuElement -> FldRatElt#
The Gauss valuation and Weierstrass degree respectively return these values.
- IsDistinguished(f): SnuElement -> BoolElt#
The
IsDistinguishedintrinsic returns whether the Gauss valuation is zero (this intrinsic is only for \(S^\nu\) elements).
- LeadingTerm(f): SnuElement -> RngSerPowElt#
- LeadingTerm(f): SpElement -> RngSerPowElt#
- LeadingTerm(f): SuElement -> RngSerLaurElt#
Gives the first non(weakly)zero term in the \(S^\nu_p\)-element, as a power series (or Laurent series). Useful in particular when examining vectors or matrices of such.
- WeierstrassTerm(f): SnuElement -> RngSerPowElt#
- WeierstrassTerm(f): SpElement -> RngSerPowElt#
- WeierstrassTerm(f): SuElement -> RngSerLaurElt#
Gives the term corresponding to the Weierstrass degree of the \(S^\nu_p\)-element, as a power series (or Laurent series). Useful in particular when examining vectors or matrices of such.
- O(x): SnuElement -> SnuElement#
- O(x): SpElement -> SpElement#
- O(x): SuElement -> SuElement#
Gives the big-Oh value of the argument.
- Example: Basic Snu Ring (ex-c0e1cb)#
Here are some basic operations with a ring of slope 1.
> S<u> := SnuRing (pAdicField (5, 15), 1); // slope 1 over 5-adics > assert Slope(S) eq 1; > f := 5*u + u^2 + 2*u^3 + u^5 + O(u^10); > g := u^4/25 + u^6 + u^8 + O(u^10); > GaussValuation (f); // both have Gauss valuation 2 2 > GaussValuation (g); // both have Gauss valuation 2 2 > q := g/f; q; // g has degree 4, so this division works (5^-3 + O(5^12))*u^3 + (-5^-4 + O(5^11))*u^4 + (616*5^-5 + O(5^10))*u^5 + (-606*5^-6 + O(5^9))*u^6 + (9946*5^-7 + O(5^8))*u^7 + (-3761*5^-8 + O(5^7))*u^8 + O(u^9) > LeadingTerm (q); // returned as a power series ring element (5^-3 + O(5^12))*$.1^3
All the same functionality copies over to the \(S^\nu_p\) rings, the main difference is that one can invert \(p\) directly there. There is automatic coercion from \(S^\nu\) to \(S^\nu_p\) rings in some cases, even when the slopes are not equal. The criterion is whether the result in the \(S^\nu_p\) ring is valid.
> Sp<uu> := SpRing (pAdicField (5, 15), 1/2); // slope 1/2 over 5-adics > assert Slope(Sp) eq 1/2; > ff := 1/5 + uu + 5*uu^2 + O(uu^10); > GaussValuation (ff); -1 > gg := uu + 5^2*uu^2 + uu^3 - uu^6 + uu^9 + O(uu^10); > h := S ! (ff * S!gg); // coerced back to the Snu-ring > assert IsDistinguished (h); > LeadingTerm (ff) * LeadingTerm (gg) eq LeadingTerm (h); true
Similarly with \(S^\nu_u\) rings, where Laurent series are now also allowed.
> Su<z> := SuRing (pAdicField (7, 25), 2/3); // slope 2/3 over 7-adics > F := 7/z + 3*7 + z^2/7 + 7^2*z^3 + O(z^10); > GaussValuation (F); 1/3 > WeierstrassTerm (F); (7 + O(7^26))*$.1^-1 > SR<t> := SnuRing (Su); > t*z/7; // automatic coercion into Su (7^-1 + O(7^24))*z^2 + O(z^20)
Euclidean Algorithm#
Given \(A,B\in S^\nu\) with \(v_\nu(A)\ge v_\nu(B)\) (so in particular \(B\) is nonzero) the quotient-remainder algorithm returns \(Q,R\) such that \(A=BQ+R\) with \(R\) a polynomial of degree less that \(d_\nu(B)\). In general the precision loss in this operation becomes more acute with larger \(\nu\). This precision loss percolates throughout all computations. Note that the result in general depends on \(\nu\).
The Weierstrass preparation theorem takes a distinguished element \(f\in S^\nu\) and writes \(f=UP\) where \(U\) is invertible in \(S^\nu(R)\) and \(P\) is a polynomial of degree \(d_\nu(f)\). The units of \(S^\nu\) are precisely those elements with Gauss valuation and Weierstrass degree both 0.
The ring \(S^\nu\) is not itself Euclidean, as we can only properly quotient elements as \(A/B\) when \(v_\nu(B)\ge v_\nu(A)\), and this property need not be preserved in the Euclidean steps. For instance with \(\nu=1\), starting with \(A=pu^2+p^4\) and \(B=p^2u\) we get \(Q=u/p\) and \(R=p^4\), but then \(v_\nu(R)=4>3=v_\nu(B)\), so that we cannot divide \(B\) by \(R\).
However, the ability to scale by arbitrary powers of the uniformiser implies that the ring \(S_p^\nu\) is Euclidean with respect to the Weierstrass degree, and similarly the ring \(S_u^\nu\) is a discrete valuation ring (hence Euclidean) for the valuation \(v_\nu\).
The extended gcd in \(S^\nu\) or \(S^\nu_p\) takes \(A,B\) with \(v(A)\ge v(B)\) and returns \((G,H,w,x,y,z)\) has \(Aw+Bx=G\) where \(v(B)=v(G)\) and \(Ay+Bz=H\) with \(v(H)>v(A)\) with \(wz-xy=1\) (consecutive Euclidean steps). The gcd is \(G\) in the case where \(H\) is the zero polynomial (this will always be true over \(S^\nu_p\)).
Since \(S^\nu_u\) is a discrete valuation ring, the quotient-remainder \(A=qB+r\) always has \(r=0\) when \(v(B)<v(A)\), and else \(q=0\). The canonical element of valuation \(v\) in \(S^\nu_u\) is \(u^y p^z\) where \(0\le y<{\rm denom}(\nu)\) is as small as possible and \(y\nu+z=v\). The gcd of two elements \(A\) and \(B\) can always be taken to be a canonical element of valuation equal to the smaller of the valuations of \(A\) and \(B\).
Intrinsics#
- WeierstrassPreparation(f): SnuElement -> SnuElement, SnuElement#
Given a distinguished element \(f\) of \(S^\nu\) (one of Gauss valuation 0), write \(f=UP\) where \(U\) is invertible in \(S^\nu\) and \(P\) is a polynomial (whose degree equals the Weierstrass degree of \(f\)).
- Quotrem(A, B): SnuElement, SnuElement -> SnuElement, SnuElement#
Given \(S^\nu\) elements \(A\) and \(B\) with \(v(A)\ge v(B)\), determine \(Q,R\) with \(A=BQ+R\) where \(B\) is a polynomial whose degree is less than the Weierstrass degree of \(B\).
- Quotrem(A, B): SpElement, SpElement -> SpElement, SpElement#
Given \(A\) and (nonzero) \(B\) which are \(S_p^\nu\) elements, determine \(Q,R\) with \(A=BQ+R\) where \(B\) is a polynomial whose degree is less than the Weierstrass degree of \(B\).
- Quotrem(A, B): SuElement, SuElement -> SuElement, SuElement#
Given \(A\) and (nonzero) \(B\) which are \(S_u^\nu\) elements, determine \(Q,R\) with \(A=BQ+R\). Here when \(v(A)\ge v(B)\) we have \(Q=A/B\) and \(R=0\), and when \(v(A)<v(B)\) we have \(Q=0\) and \(R=A\).
- ExtendedGcd(A, B): SnuElement, SnuElement -> SnuElement, SnuElement, SnuElement, SnuElement, SnuElement, SnuElement#
Given \(S^\nu\) elements \(A\) and \(B\) with \(v(A)\ge v(B)\), try to compute the gcd. This returns a 6-tuple \((G,H,w,x,y,z)\) with \(Aw+Bx=G\), \(Cw+Dy=H\), and \(wz-xy=1\). When \(H=0\) then \(G\) is the gcd. Alternatively, \(v(H)\) will be some element with \(v(H)>v(A)\), which precludes the Euclidean algorithm from progressing.
- ExtendedGcd(A, B): SpElement, SpElement -> SpElement, SpElement, SpElement, SpElement, SpElement, SpElement#
Given \(S_p^\nu\) elements \(A\) and \(B\) compute the extended gcd. This returns a 6-tuple \((G,H,w,x,y,z)\) with \(Aw+Bx=G\), \(Cw+Dy=H=0\), and \(wz-xy=1\), where \(G\) is the gcd.
- ExtendedGcd(A, B): SuElement, SuElement -> SuElement, SuElement, SuElement, SuElement, SuElement, SuElement#
Given \(S_u^\nu\) elements \(A\) and \(B\) compute the extended gcd. Since \(S_u^\nu\) is a DVR, the gcd can be taken to be the
CanonicalElementof the smaller valuation of \(A\) and \(B\).
- CanonicalElement(S, v): SuRng, FldRatElt -> SuElement#
The canonical element of valuation \(v\) in \(S^\nu_u\) is \(u^y p^z\) where \(0\le y<{\rm denom}(\nu)\) is as small as possible and \(y\nu+z=v\).
- Example: Euclidean Basics (ex-db44fa)#
Here are some basic examples of Euclidean operations.
> S<u> := SnuRing (pAdicField (5, 15), 1); // slope 1 over 5-adics > f := 5*u + u^2 + 2*u^3 + u^5 + O(u^10); > g := u^4/25 + u^6 + u^8 + O(u^10); > q := g/f; > assert IsDistinguished (q); > U, P := WeierstrassPreparation (q); // loses a lot of precision > U; 1 + O(5^15) + (-5^-1 + O(5^14))*u + (616*5^-2 + O(5^13))*u^2 + (-606*5^-3 + O(5^12))*u^3 + (9946*5^-4 + O(5^11))*u^4 + (-3761*5^-5 + O(5^10))*u^5 + O(u^6) > P; (5^-3 + O(5^12))*u^3 + O(u^6) > q, r := Quotrem (g, f); assert r eq 0; assert q eq g/f; > q; // same as above, though is O(u^10) not O(u^9) (5^-3 + O(5^12))*u^3 + (-5^-4 + O(5^11))*u^4 + (616*5^-5 + O(5^10))*u^5 + (-606*5^-6 + O(5^9))*u^6 + (9946*5^-7 + O(5^8))*u^7 + (-3761*5^-8 + O(5^7))*u^8 + (-172699*5^-9 + O(5^6))*u^9 + O(u^10) > q, r := Quotrem (f, g); // this is valid, as the valuations are equal > q, r; assert f eq g*q + r; (5^2 + O(5^17))*u + (-5^4 + O(5^17))*u^3 + (24*5^4 + O(5^17))*u^5 + (-23*5^6 + O(5^17))*u^7 + (551*5^6 + O(5^17))*u^9 + O(u^10) (5 + O(5^16))*u + (1 + O(5^15))*u^2 + (2 + O(5^15))*u^3 + O(u^10) > G, H, A, B := ExtendedGcd (f, g); assert H eq 0; > G; (-5 + O(5^16))*u + (-1 + O(5^15))*u^2 + (-2 + O(5^15))*u^3 + O(u^10) > assert A*f + B*g eq G;
> f1 := 5*u^2 + 5^4; // example from the text > g1 := 5^2*u; // where ExtendedGcd fails > G, H := ExtendedGcd (f1, g1); assert H ne 0; > H; -5^4 + O(5^24) + O(u^20) > GaussValuation (H); GaussValuation (g1); 4 3
The above will also work in \(S^\nu_p\). As noted above, the corresponding commands for \(S^\nu_u\) rings are particularly simplified.
> Su<z> := SuRing (S); > F := Su!f; assert GaussValuation(F) eq 2; > G := Su!g; assert GaussValuation(G) eq 2; > Q, R := Quotrem (F, G); assert R eq 0; > g, _, A, B, C, D := ExtendedGcd (F, G); > g; assert g eq CanonicalElement (Su, 2); 5^2 + O(5^17) + O(z^20) > assert A*F + B*G eq g; > assert C*F + D*G eq 0; > assert A*D - B*C eq 1;