Introduction

Thanks to Xavier Caruso and David Lubicz, Magma now contains an implementation of linear algebra over \({\bf Z}_p[[u]]\) and related rings [CL12]. 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

\[S^\nu(R)=\biggl\{\sum_{i=0}^\infty a_i u^i| v_R(a_i)+i\cdot\nu\ge 0,a_i\in{\rm Frac}(R)\biggr\}.\]

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.

SnuRing(S): SpRng -> SnuRng
SpRing(S): SnuRng -> SpRng
SnuRing(S): SuRng -> SnuRng
SuRing(S): SnuRng -> SuRng: Given an \(S^\nu_p\)-ring, create the associated \(S^\nu\)-ring, and vice-versa. Similarly with an \(S^\nu_u\)-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.

Precision(S): SnuRng -> RngIntElt
Precision(S): SpRng -> RngIntElt
Precision(S): SuRng -> RngIntElt: The precision of the underlying power-series ring.

CoefficientRing(S): SnuRng -> RngIntElt
CoefficientRing(S): SpRng -> RngIntElt
CoefficientRing(S): SuRng -> RngIntElt: The underlying \(p\)-adic ring 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 IsDistinguished intrinsic 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 Operations in a Slope Ring (ex-c0e1cb)

Run in calculator (opens in a new tab)

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)

Run in calculator (opens in a new tab)

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 CanonicalElement of 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 Operations on Series (ex-db44fa)

Run in calculator (opens in a new tab)

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;

Run in calculator (opens in a new tab)

Introduction#

Background#

Basic Operations#

Creation Intrinsics#

Access Functions#

Element Operations#

Valuation and Degree#

Euclidean Algorithm#

Intrinsics#

Introduction

Background

Basic Operations

Creation Intrinsics

Access Functions

Element Operations

Valuation and Degree

Euclidean Algorithm

Intrinsics