Elements of $$p$$-Adic Rings and Fields

AUTHORS:

• David Roe
• Genya Zaytman: documentation
• David Harvey: doctests
• Julian Rueth: fixes for exp() and log(), implemented gcd, xgcd
class sage.rings.padics.padic_generic_element.pAdicGenericElement
abs(prec=None)

Return the $$p$$-adic absolute value of self.

This is normalized so that the absolute value of $$p$$ is $$1/p$$.

INPUT:

• prec – Integer. The precision of the real field in which the answer is returned. If None, returns a rational for absolutely unramified fields, or a real with 53 bits of precision for ramified fields.

EXAMPLES:

sage: a = Qp(5)(15); a.abs()
1/5
sage: a.abs(53)
0.200000000000000
sage: Qp(7)(0).abs()
0
sage: Qp(7)(0).abs(prec=20)
0.00000


An unramified extension:

sage: R = Zp(5,5)
sage: P.<x> = PolynomialRing(R)
sage: Z25.<u> = R.ext(x^2 - 3)
sage: u.abs()
1
sage: (u^24-1).abs()
1/5


A ramified extension:

sage: W.<w> = R.ext(x^5 + 75*x^3 - 15*x^2 + 125*x - 5)
sage: w.abs()
0.724779663677696
sage: W(0).abs()
0.000000000000000

additive_order(prec=None)

Returns the additive order of this element truncated at precision prec

INPUT:

• prec – an integer or None (default: None)

OUTPUT:

The additive order of this element

EXAMPLES:

sage: R = Zp(7, 4, 'capped-rel', 'series'); a = R(7^3); a.additive_order(3)
1
+Infinity
sage: R = Zp(7, 4, 'fixed-mod', 'series'); a = R(7^5); a.additive_order(6)
1

algdep(n)

Returns a polynomial of degree at most $$n$$ which is approximately satisfied by this number. Note that the returned polynomial need not be irreducible, and indeed usually won’t be if this number is a good approximation to an algebraic number of degree less than $$n$$.

ALGORITHM: Uses the PARI C-library algdep command.

INPUT:

• self – a p-adic element
• n – an integer

OUTPUT:

polynomial – degree n polynomial approximately satisfied by self

EXAMPLES:

sage: K = Qp(3,20,'capped-rel','series'); R = Zp(3,20,'capped-rel','series')
sage: a = K(7/19); a
1 + 2*3 + 3^2 + 3^3 + 2*3^4 + 2*3^5 + 3^8 + 2*3^9 + 3^11 + 3^12 + 2*3^15 + 2*3^16 + 3^17 + 2*3^19 + O(3^20)
sage: a.algdep(1)
19*x - 7
sage: K2 = Qp(7,20,'capped-rel')
sage: b = K2.zeta(); b.algdep(2)
x^2 - x + 1
sage: K2 = Qp(11,20,'capped-rel')
sage: b = K2.zeta(); b.algdep(4)
x^4 - x^3 + x^2 - x + 1
sage: a = R(7/19); a
1 + 2*3 + 3^2 + 3^3 + 2*3^4 + 2*3^5 + 3^8 + 2*3^9 + 3^11 + 3^12 + 2*3^15 + 2*3^16 + 3^17 + 2*3^19 + O(3^20)
sage: a.algdep(1)
19*x - 7
sage: R2 = Zp(7,20,'capped-rel')
sage: b = R2.zeta(); b.algdep(2)
x^2 - x + 1
sage: R2 = Zp(11,20,'capped-rel')
sage: b = R2.zeta(); b.algdep(4)
x^4 - x^3 + x^2 - x + 1

algebraic_dependency(n)

Returns a polynomial of degree at most $$n$$ which is approximately satisfied by this number. Note that the returned polynomial need not be irreducible, and indeed usually won’t be if this number is a good approximation to an algebraic number of degree less than $$n$$.

ALGORITHM: Uses the PARI C-library algdep command.

INPUT:

• self – a p-adic element
• n – an integer

OUTPUT:

polynomial – degree n polynomial approximately satisfied by self

EXAMPLES:

sage: K = Qp(3,20,'capped-rel','series'); R = Zp(3,20,'capped-rel','series')
sage: a = K(7/19); a
1 + 2*3 + 3^2 + 3^3 + 2*3^4 + 2*3^5 + 3^8 + 2*3^9 + 3^11 + 3^12 + 2*3^15 + 2*3^16 + 3^17 + 2*3^19 + O(3^20)
sage: a.algebraic_dependency(1)
19*x - 7
sage: K2 = Qp(7,20,'capped-rel')
sage: b = K2.zeta(); b.algebraic_dependency(2)
x^2 - x + 1
sage: K2 = Qp(11,20,'capped-rel')
sage: b = K2.zeta(); b.algebraic_dependency(4)
x^4 - x^3 + x^2 - x + 1
sage: a = R(7/19); a
1 + 2*3 + 3^2 + 3^3 + 2*3^4 + 2*3^5 + 3^8 + 2*3^9 + 3^11 + 3^12 + 2*3^15 + 2*3^16 + 3^17 + 2*3^19 + O(3^20)
sage: a.algebraic_dependency(1)
19*x - 7
sage: R2 = Zp(7,20,'capped-rel')
sage: b = R2.zeta(); b.algebraic_dependency(2)
x^2 - x + 1
sage: R2 = Zp(11,20,'capped-rel')
sage: b = R2.zeta(); b.algebraic_dependency(4)
x^4 - x^3 + x^2 - x + 1

artin_hasse_exp(prec=None, algorithm=None)

Return the Artin-Hasse exponential of this element.

INPUT:

• prec – an integer or None (default: None) the desired precision on the result; if None, the precision is derived from the precision on the input

• algorithmdirect, series, newton or None (default)

The direct algorithm computes the Artin-Hasse exponential of x, namely AH(x) as

$AH(x) = \exp(x + \frac{x^p}{p} + \frac{x^{p^2}}{p^2} + \dots$

It runs roughly as fast as the computation of the exponential (since the computation of the argument is not that costly).

The series algorithm computes the series defining the Artin-Hasse exponential and evaluates it.

The Newton algorithm solves the equation

$\log(AH(x)) = x + \frac{x^p}{p} + \frac{x^{p^2}}{p^2} + \dots$

using a Newton scheme. It runs roughly as fast as the computation of the logarithm.

By default, we use the direct algorithm if a fast algorithm for computing the exponential is available. If not, we use the Newton algorithm if a fast algorithm for computing the logarithm is available. Otherwise we switch to the series algorithm.

OUTPUT:

The Artin-Hasse exponential of this element.

EXAMPLES:

sage: x = Zp(5)(45/7)
sage: y = x.artin_hasse_exp(); y
1 + 2*5 + 4*5^2 + 3*5^3 + 5^7 + 2*5^8 + 3*5^10 + 2*5^11 + 2*5^12 +
2*5^13 + 5^14 + 3*5^17 + 2*5^18 + 2*5^19 + O(5^20)

sage: y * (-x).artin_hasse_exp()
1 + O(5^20)


sage: x = Zp(3,30)(45/7)
sage: x.artin_hasse_exp()
1 + 2*3^2 + 3^4 + 2*3^5 + 3^6 + 2*3^7 + 2*3^8 + 3^9 + 2*3^10 + 3^11 +
3^13 + 2*3^15 + 2*3^16 + 2*3^17 + 3^19 + 3^20 + 2*3^21 + 3^23 + 3^24 +
3^26 + 3^27 + 2*3^28 + O(3^30)


Unless you tell it not to:

sage: x = Zp(3,30)(45/7)
sage: x.artin_hasse_exp()
1 + 2*3^2 + 3^4 + 2*3^5 + 3^6 + 2*3^7 + 2*3^8 + 3^9 + 2*3^10 + 3^11 +
3^13 + 2*3^15 + 2*3^16 + 2*3^17 + 3^19 + 3^20 + 2*3^21 + 3^23 + 3^24 +
3^26 + 3^27 + 2*3^28 + O(3^30)
sage: x.artin_hasse_exp(10)
1 + 2*3^2 + 3^4 + 2*3^5 + 3^6 + 2*3^7 + 2*3^8 + 3^9 + O(3^10)


For precision 1 the function just returns 1 since the exponential is always a 1-unit:

sage: x = Zp(3).random_element()
sage: x.artin_hasse_exp(1)
1 + O(3)


AUTHORS:

• Mitchell Owen, Sebastian Pancrantz (2012-02): initial version.
• Xavier Caruso (2018-08): extend to any p-adic rings and fields and implement several algorithms.
dwork_expansion(bd=20, a=0)

Return the value of a function defined by Dwork.

Used to compute the $$p$$-adic Gamma function, see gamma().

INPUT:

• bd – integer. Is a bound for precision, defaults to 20
• a – integer. Offset parameter, defaults to 0

OUTPUT:

A p– adic integer.

Note

This is based on GP code written by Fernando Rodriguez Villegas (http://www.ma.utexas.edu/cnt/cnt-frames.html). William Stein sped it up for GP (http://sage.math.washington.edu/home/wstein/www/home/wbhart/pari-2.4.2.alpha/src/basemath/trans2.c). The output is a $$p$$-adic integer from Dwork’s expansion, used to compute the $$p$$-adic gamma function as in [RV2007] section 6.2. The coefficients of the expansion are now cached to speed up multiple evaluation, as in the trace formula for hypergeometric motives.

EXAMPLES:

sage: R = Zp(17)
sage: x = R(5+3*17+13*17^2+6*17^3+12*17^5+10*17^(14)+5*17^(17)+O(17^(19)))
sage: x.dwork_expansion(18)
16 + 7*17 + 11*17^2 + 4*17^3 + 8*17^4 + 10*17^5 + 11*17^6 + 6*17^7
+ 17^8 + 8*17^10 + 13*17^11 + 9*17^12 + 15*17^13  + 2*17^14 + 6*17^15
+ 7*17^16 + 6*17^17 + O(17^18)

sage: R = Zp(5)
sage: x = R(3*5^2+4*5^3+1*5^4+2*5^5+1*5^(10)+O(5^(20)))
sage: x.dwork_expansion()
4 + 4*5 + 4*5^2 + 4*5^3 + 2*5^4 + 4*5^5 + 5^7 + 3*5^9 + 4*5^10 + 3*5^11
+ 5^13 + 4*5^14 + 2*5^15 + 2*5^16 + 2*5^17 + 3*5^18 + O(5^20)


This test was added in trac ticket #24433:

sage: F = Qp(7)
sage: F(4).gamma()
6 + O(7^20)
sage: -F(1).dwork_expansion(a=3)
6 + 4*7^19 + O(7^20)

exp(aprec=None, algorithm=None)

Compute the $$p$$-adic exponential of this element if the exponential series converges.

INPUT:

• aprec – an integer or None (default: None); if specified, computes only up to the indicated precision.

• algorithmgeneric, binary_splitting, newton or None (default) The generic algorithm evaluates naively the series defining the exponential, namely

$\exp(x) = 1 + x + x^2/2 + x^3/6 + x^4/24 + \cdots$

Its binary complexity is quadratic with respect to the precision.

The binary splitting algorithm is faster, it has a quasi-linear complexity.

The Newton algorithms solve the equation $$\log(x) = self$$ using a Newton scheme. It runs roughly as fast as the computation of the logarithm.

By default, we use the binary splitting if it is available. If it is not, we use the Newton algorithm if a fast algorithm for computing the logarithm is available. Otherwise we switch to the generic algorithm.

EXAMPLES:

log() and exp() are inverse to each other:

sage: Z13 = Zp(13, 10)
sage: a = Z13(14); a
1 + 13 + O(13^10)
sage: a.log().exp()
1 + 13 + O(13^10)


An error occurs if this is called with an element for which the exponential series does not converge:

sage: Z13.one().exp()
Traceback (most recent call last):
...
ValueError: Exponential does not converge for that input.


The next few examples illustrate precision when computing $$p$$-adic exponentials:

sage: R = Zp(5,10)
sage: e = R(2*5 + 2*5**2 + 4*5**3 + 3*5**4 + 5**5 + 3*5**7 + 2*5**8 + 4*5**9).add_bigoh(10); e
2*5 + 2*5^2 + 4*5^3 + 3*5^4 + 5^5 + 3*5^7 + 2*5^8 + 4*5^9 + O(5^10)
sage: e.exp()*R.teichmuller(4)
4 + 2*5 + 3*5^3 + O(5^10)

sage: K = Qp(5,10)
sage: e = K(2*5 + 2*5**2 + 4*5**3 + 3*5**4 + 5**5 + 3*5**7 + 2*5**8 + 4*5**9).add_bigoh(10); e
2*5 + 2*5^2 + 4*5^3 + 3*5^4 + 5^5 + 3*5^7 + 2*5^8 + 4*5^9 + O(5^10)
sage: e.exp()*K.teichmuller(4)
4 + 2*5 + 3*5^3 + O(5^10)


Logarithms and exponentials in extension fields. First, in an Eisenstein extension:

sage: R = Zp(5,5)
sage: S.<x> = R[]
sage: f = x^4 + 15*x^2 + 625*x - 5
sage: W.<w> = R.ext(f)
sage: z = 1 + w^2 + 4*w^7; z
1 + w^2 + 4*w^7 + O(w^20)
sage: z.log().exp()
1 + w^2 + 4*w^7 + O(w^20)


Now an unramified example:

sage: R = Zp(5,5)
sage: S.<x> = R[]
sage: g = x^3 + 3*x + 3
sage: A.<a> = R.ext(g)
sage: b = 1 + 5*(1 + a^2) + 5^3*(3 + 2*a); b
1 + (a^2 + 1)*5 + (2*a + 3)*5^3 + O(5^5)
sage: b.log().exp()
1 + (a^2 + 1)*5 + (2*a + 3)*5^3 + O(5^5)


AUTHORS:

• Genya Zaytman (2007-02-15)
• Amnon Besser, Marc Masdeu (2012-02-23): Complete rewrite
• Julian Rueth (2013-02-14): Added doctests, fixed some corner cases
• Xavier Caruso (2017-06): Added binary splitting and Newton algorithms
gamma(algorithm='pari')

Return the value of the $$p$$-adic Gamma function.

INPUT:

• algorithm – string. Can be set to 'pari' to call the pari function, or 'sage' to call the function implemented in sage. The default is 'pari' since pari is about 10 times faster than sage.

OUTPUT:

• a $$p$$-adic integer

Note

This is based on GP code written by Fernando Rodriguez Villegas (http://www.ma.utexas.edu/cnt/cnt-frames.html). William Stein sped it up for GP (http://sage.math.washington.edu/home/wstein/www/home/wbhart/pari-2.4.2.alpha/src/basemath/trans2.c). The ‘sage’ version uses dwork_expansion() to compute the $$p$$-adic gamma function of self as in [RV2007] section 6.2.

EXAMPLES:

This example illustrates x.gamma() for $$x$$ a $$p$$-adic unit:

sage: R = Zp(7)
sage: x = R(2+3*7^2+4*7^3+O(7^20))
sage: x.gamma('pari')
1 + 2*7^2 + 4*7^3 + 5*7^4 + 3*7^5 + 7^8 + 7^9 + 4*7^10 + 3*7^12
+ 7^13 + 5*7^14 + 3*7^15 + 2*7^16 + 2*7^17 + 5*7^18 + 4*7^19 + O(7^20)
sage: x.gamma('sage')
1 + 2*7^2 + 4*7^3 + 5*7^4 + 3*7^5 + 7^8 + 7^9 + 4*7^10 + 3*7^12
+ 7^13 + 5*7^14 + 3*7^15 + 2*7^16 + 2*7^17 + 5*7^18 + 4*7^19 + O(7^20)
sage: x.gamma('pari') == x.gamma('sage')
True


Now x.gamma() for $$x$$ a $$p$$-adic integer but not a unit:

sage: R = Zp(17)
sage: x = R(17+17^2+3*17^3+12*17^8+O(17^13))
sage: x.gamma('pari')
1 + 12*17 + 13*17^2 + 13*17^3 + 10*17^4 + 7*17^5 + 16*17^7
+ 13*17^9 + 4*17^10 + 9*17^11 + 17^12 + O(17^13)
sage: x.gamma('sage')
1 + 12*17 + 13*17^2 + 13*17^3 + 10*17^4 + 7*17^5 + 16*17^7
+ 13*17^9 + 4*17^10 + 9*17^11 + 17^12 + O(17^13)
sage: x.gamma('pari') == x.gamma('sage')
True


Finally, this function is not defined if $$x$$ is not a $$p$$-adic integer:

sage: K = Qp(7)
sage: x = K(7^-5 + 2*7^-4 + 5*7^-3 + 2*7^-2 + 3*7^-1 + 3 + 3*7
....:       + 7^3 + 4*7^4 + 5*7^5 + 6*7^8 + 3*7^9 + 6*7^10 + 5*7^11 + 6*7^12
....:       + 3*7^13 + 5*7^14 + O(7^15))
sage: x.gamma()
Traceback (most recent call last):
...
ValueError: The p-adic gamma function only works on elements of Zp

gcd(other)

Return a greatest common divisor of self and other.

INPUT:

• other – an element in the same ring as self

AUTHORS:

• Julian Rueth (2012-10-19): initial version

Note

Since the elements are only given with finite precision, their greatest common divisor is in general not unique (not even up to units). For example $$O(3)$$ is a representative for the elements 0 and 3 in the 3-adic ring $$\ZZ_3$$. The greatest common divisor of $$O(3)$$ and $$O(3)$$ could be (among others) 3 or 0 which have different valuation. The algorithm implemented here, will return an element of minimal valuation among the possible greatest common divisors.

EXAMPLES:

The greatest common divisor is either zero or a power of the uniformizing parameter:

sage: R = Zp(3)
sage: R.zero().gcd(R.zero())
0
sage: R(3).gcd(9)
3 + O(3^21)


A non-zero result is always lifted to the maximal precision possible in the ring:

sage: a = R(3,2); a
3 + O(3^2)
sage: b = R(9,3); b
3^2 + O(3^3)
sage: a.gcd(b)
3 + O(3^21)
sage: a.gcd(0)
3 + O(3^21)


If both elements are zero, then the result is zero with the precision set to the smallest of their precisions:

sage: a = R.zero(); a
0
sage: b = R(0,2); b
O(3^2)
sage: a.gcd(b)
O(3^2)


One could argue that it is mathematically correct to return $$9 + O(3^{22})$$ instead. However, this would lead to some confusing behaviour:

sage: alternative_gcd = R(9,22); alternative_gcd
3^2 + O(3^22)
sage: a.is_zero()
True
sage: b.is_zero()
True
sage: alternative_gcd.is_zero()
False


If exactly one element is zero, then the result depends on the valuation of the other element:

sage: R(0,3).gcd(3^4)
O(3^3)
sage: R(0,4).gcd(3^4)
O(3^4)
sage: R(0,5).gcd(3^4)
3^4 + O(3^24)


Over a field, the greatest common divisor is either zero (possibly with finite precision) or one:

sage: K = Qp(3)
sage: K(3).gcd(0)
1 + O(3^20)
sage: K.zero().gcd(0)
0
sage: K.zero().gcd(K(0,2))
O(3^2)
sage: K(3).gcd(4)
1 + O(3^20)

is_prime()

Return whether this element is prime in its parent

EXAMPLES:

sage: A = Zp(2)
sage: A(1).is_prime()
False
sage: A(2).is_prime()
True

sage: K = A.fraction_field()
sage: K(2).is_prime()
False

sage: B.<pi> = A.extension(x^5 - 2)
sage: pi.is_prime()
True
sage: B(2).is_prime()
False

is_square()

Returns whether this element is a square

INPUT:

• self – a p-adic element

EXAMPLES:

sage: R = Zp(3,20,'capped-rel')
sage: R(0).is_square()
True
sage: R(1).is_square()
True
sage: R(2).is_square()
False

is_squarefree()

Return whether this element is squarefree, i.e., whether there exists no non-unit $$g$$ such that $$g^2$$ divides this element.

EXAMPLES:

The zero element is never squarefree:

sage: K = Qp(2)
sage: K.zero().is_squarefree()
False


In $$p$$-adic rings, only elements of valuation at most 1 are squarefree:

sage: R = Zp(2)
sage: R(1).is_squarefree()
True
sage: R(2).is_squarefree()
True
sage: R(4).is_squarefree()
False


This works only if the precision is known sufficiently well:

sage: R(0,1).is_squarefree()
Traceback (most recent call last):
...
PrecisionError: element not known to sufficient precision to decide squarefreeness
sage: R(0,2).is_squarefree()
False
sage: R(1,1).is_squarefree()
True


For fields we are not so strict about the precision and treat inexact zeros as the zero element:

K(0,0).is_squarefree()
False

log(p_branch=None, pi_branch=None, aprec=None, change_frac=False, algorithm=None)

Compute the $$p$$-adic logarithm of this element.

The usual power series for the logarithm with values in the additive group of a $$p$$-adic ring only converges for 1-units (units congruent to 1 modulo $$p$$). However, there is a unique extension of the logarithm to a homomorphism defined on all the units: If $$u = a \cdot v$$ is a unit with $$v \equiv 1 \pmod{p}$$ and $$a$$ a Teichmuller representative, then we define $$log(u) = log(v)$$. This is the correct extension because the units $$U$$ split as a product $$U = V \times \langle w \rangle$$, where $$V$$ is the subgroup of 1-units and $$w$$ is a fundamental root of unity. The $$\langle w \rangle$$ factor is torsion, so must go to 0 under any homomorphism to the fraction field, which is a torsion free group.

INPUT:

• p_branch – an element in the base ring or its fraction field; the implementation will choose the branch of the logarithm which sends $$p$$ to branch.

• pi_branch – an element in the base ring or its fraction field; the implementation will choose the branch of the logarithm which sends the uniformizer to branch. You may specify at most one of p_branch and pi_branch, and must specify one of them if this element is not a unit.

• aprec – an integer or None (default: None) if not None, then the result will only be correct to precision aprec.

• change_frac – In general the codomain of the logarithm should be in the $$p$$-adic field, however, for most neighborhoods of 1, it lies in the ring of integers. This flag decides if the codomain should be the same as the input (default) or if it should change to the fraction field of the input.

• algorithmgeneric, binary_splitting or None (default) The generic algorithm evaluates naively the series defining the log, namely

$\log(1-x) = -x - 1/2 x^2 - 1/3 x^3 - 1/4 x^4 - 1/5 x^5 - \cdots$

Its binary complexity is quadratic with respect to the precision.

The binary splitting algorithm is faster, it has a quasi-linear complexity. By default, we use the binary splitting if it is available. Otherwise we switch to the generic algorithm.

NOTES:

What some other systems do:

• PARI: Seems to define the logarithm for units not congruent to 1 as we do.
• MAGMA: Only implements logarithm for 1-units (as of version 2.19-2)

Todo

There is a soft-linear time algorithm for logarithm described by Dan Berstein at http://cr.yp.to/lineartime/multapps-20041007.pdf

EXAMPLES:

sage: Z13 = Zp(13, 10)
sage: a = Z13(14); a
1 + 13 + O(13^10)
sage: a.log()
13 + 6*13^2 + 2*13^3 + 5*13^4 + 10*13^6 + 13^7 + 11*13^8 + 8*13^9 + O(13^10)

sage: Q13 = Qp(13, 10)
sage: a = Q13(14); a
1 + 13 + O(13^10)
sage: a.log()
13 + 6*13^2 + 2*13^3 + 5*13^4 + 10*13^6 + 13^7 + 11*13^8 + 8*13^9 + O(13^10)


Note that the relative precision decreases when we take log. Precisely the absolute precision on \log(a) agrees with the relative precision on a thanks to the relation d\log(a) = da/a.

The call $$log(a)$$ works as well:

sage: log(a)
13 + 6*13^2 + 2*13^3 + 5*13^4 + 10*13^6 + 13^7 + 11*13^8 + 8*13^9 + O(13^10)
sage: log(a) == a.log()
True


The logarithm is not only defined for 1-units:

sage: R = Zp(5,10)
sage: a = R(2)
sage: a.log()
2*5 + 3*5^2 + 2*5^3 + 4*5^4 + 2*5^6 + 2*5^7 + 4*5^8 + 2*5^9 + O(5^10)


If you want to take the logarithm of a non-unit you must specify either p_branch or pi_branch:

sage: b = R(5)
sage: b.log()
Traceback (most recent call last):
...
ValueError: You must specify a branch of the logarithm for non-units
sage: b.log(p_branch=4)
4 + O(5^10)
sage: c = R(10)
sage: c.log(p_branch=4)
4 + 2*5 + 3*5^2 + 2*5^3 + 4*5^4 + 2*5^6 + 2*5^7 + 4*5^8 + 2*5^9 + O(5^10)


The branch parameters are only relevant for elements of non-zero valuation:

sage: a.log(p_branch=0)
2*5 + 3*5^2 + 2*5^3 + 4*5^4 + 2*5^6 + 2*5^7 + 4*5^8 + 2*5^9 + O(5^10)
sage: a.log(p_branch=1)
2*5 + 3*5^2 + 2*5^3 + 4*5^4 + 2*5^6 + 2*5^7 + 4*5^8 + 2*5^9 + O(5^10)


Logarithms can also be computed in extension fields. First, in an Eisenstein extension:

sage: R = Zp(5,5)
sage: S.<x> = ZZ[]
sage: f = x^4 + 15*x^2 + 625*x - 5
sage: W.<w> = R.ext(f)
sage: z = 1 + w^2 + 4*w^7; z
1 + w^2 + 4*w^7 + O(w^20)
sage: z.log()
w^2 + 2*w^4 + 3*w^6 + 4*w^7 + w^9 + 4*w^10 + 4*w^11 + 4*w^12 + 3*w^14 + w^15 + w^17 + 3*w^18 + 3*w^19 + O(w^20)


In an extension, there will usually be a difference between specifying p_branch and pi_branch:

sage: b = W(5)
sage: b.log()
Traceback (most recent call last):
...
ValueError: You must specify a branch of the logarithm for non-units
sage: b.log(p_branch=0)
O(w^20)
sage: b.log(p_branch=w)
w + O(w^20)
sage: b.log(pi_branch=0)
3*w^2 + 2*w^4 + 2*w^6 + 3*w^8 + 4*w^10 + w^13 + w^14 + 2*w^15 + 2*w^16 + w^18 + 4*w^19 + O(w^20)
sage: b.unit_part().log()
3*w^2 + 2*w^4 + 2*w^6 + 3*w^8 + 4*w^10 + w^13 + w^14 + 2*w^15 + 2*w^16 + w^18 + 4*w^19 + O(w^20)
sage: y = w^2 * 4*w^7; y
4*w^9 + O(w^29)
sage: y.log(p_branch=0)
2*w^2 + 2*w^4 + 2*w^6 + 2*w^8 + w^10 + w^12 + 4*w^13 + 4*w^14 + 3*w^15 + 4*w^16 + 4*w^17 + w^18 + 4*w^19 + O(w^20)
sage: y.log(p_branch=w)
w + 2*w^2 + 2*w^4 + 4*w^5 + 2*w^6 + 2*w^7 + 2*w^8 + 4*w^9 + w^10 + 3*w^11 + w^12 + 4*w^14 + 4*w^16 + 2*w^17 + w^19 + O(w^20)


Check that log is multiplicative:

sage: y.log(p_branch=0) + z.log() - (y*z).log(p_branch=0)
O(w^20)


Now an unramified example:

sage: g = x^3 + 3*x + 3
sage: A.<a> = R.ext(g)
sage: b = 1 + 5*(1 + a^2) + 5^3*(3 + 2*a)
sage: b.log()
(a^2 + 1)*5 + (3*a^2 + 4*a + 2)*5^2 + (3*a^2 + 2*a)*5^3 + (3*a^2 + 2*a + 2)*5^4 + O(5^5)


Check that log is multiplicative:

sage: c = 3 + 5^2*(2 + 4*a)
sage: b.log() + c.log() - (b*c).log()
O(5^5)


We illustrate the effect of the precision argument:

sage: R = ZpCA(7,10)
sage: x = R(41152263); x
5 + 3*7^2 + 4*7^3 + 3*7^4 + 5*7^5 + 6*7^6 + 7^9 + O(7^10)
sage: x.log(aprec = 5)
7 + 3*7^2 + 4*7^3 + 3*7^4 + O(7^5)
sage: x.log(aprec = 7)
7 + 3*7^2 + 4*7^3 + 3*7^4 + 7^5 + 3*7^6 + O(7^7)
sage: x.log()
7 + 3*7^2 + 4*7^3 + 3*7^4 + 7^5 + 3*7^6 + 7^7 + 3*7^8 + 4*7^9 + O(7^10)


The logarithm is not defined for zero:

sage: R.zero().log()
Traceback (most recent call last):
...
ValueError: logarithm is not defined at zero


For elements in a $$p$$-adic ring, the logarithm will be returned in the same ring:

sage: x = R(2)
sage: x.log().parent()
7-adic Ring with capped absolute precision 10
sage: x = R(14)
sage: x.log(p_branch=0).parent()
7-adic Ring with capped absolute precision 10


This is not possible if the logarithm has negative valuation:

sage: R = ZpCA(3,10)
sage: S.<x> = R[]
sage: f = x^3 - 3
sage: W.<w> = R.ext(f)
sage: w.log(p_branch=2)
Traceback (most recent call last):
...
ValueError: logarithm is not integral, use change_frac=True to obtain a result in the fraction field
sage: w.log(p_branch=2, change_frac=True)
2*w^-3 + O(w^24)


AUTHORS:

• William Stein: initial version
• David Harvey (2006-09-13): corrected subtle precision bug (need to take denominators into account! – see trac ticket #53)
• Genya Zaytman (2007-02-14): adapted to new $$p$$-adic class
• Amnon Besser, Marc Masdeu (2012-02-21): complete rewrite, valid for generic $$p$$-adic rings.
• Soroosh Yazdani (2013-02-1): Fixed a precision issue in _log_generic(). This should really fix the issue with divisions.
• Julian Rueth (2013-02-14): Added doctests, some changes for capped-absolute implementations.
• Xavier Caruso (2017-06): Added binary splitting type algorithms over Qp
minimal_polynomial(name='x', base=None)

Returns the minimal polynomial of this element over base

INPUT:

• name – string (default: x): the name of the variable
• base – a ring (default: the base ring of the parent): the base ring over which the minimal polynomial is computed

EXAMPLES:

sage: Zp(5,5)(1/3).minimal_polynomial('x')
(1 + O(5^5))*x + 3 + 5 + 3*5^2 + 5^3 + 3*5^4 + O(5^5)

sage: Zp(5,5)(1/3).minimal_polynomial('foo')
(1 + O(5^5))*foo + 3 + 5 + 3*5^2 + 5^3 + 3*5^4 + O(5^5)

sage: K.<a> = QqCR(2^3,5)
sage: S.<x> = K[]
sage: L.<pi> = K.extension(x^4 - 2*a)

sage: pi.minimal_polynomial()
(1 + O(2^5))*x^4 + a*2 + a*2^2 + a*2^3 + a*2^4 + a*2^5 + O(2^6)
sage: (pi^2).minimal_polynomial()
(1 + O(2^5))*x^2 + a*2 + a*2^2 + a*2^3 + a*2^4 + a*2^5 + O(2^6)
sage: (1/pi).minimal_polynomial()
(1 + O(2^5))*x^4 + (a^2 + 1)*2^-1 + O(2^4)

sage: elt = L.random_element()
sage: P = elt.minimal_polynomial()
sage: P(elt) == 0
True

multiplicative_order(prec=None)

Returns the multiplicative order of self, where self is considered to be one if it is one modulo $$p^{\mbox{prec}}$$.

INPUT:

• self – a p-adic element
• prec – an integer

OUTPUT:

• integer – the multiplicative order of self

EXAMPLES:

sage: K = Qp(5,20,'capped-rel')
sage: K(-1).multiplicative_order(20)
2
sage: K(1).multiplicative_order(20)
1
sage: K(2).multiplicative_order(20)
+Infinity
sage: K(5).multiplicative_order(20)
+Infinity
sage: K(1/5).multiplicative_order(20)
+Infinity
sage: K.zeta().multiplicative_order(20)
4


Over unramified extensions:

sage: L1.<a> = Qq(5^3)
sage: c = L1.teichmuller(a)
sage: c.multiplicative_order()
124
sage: c^124
1 + O(5^20)


Over totally ramified extensions:

sage: L2.<pi> = Qp(5).extension(x^4 + 5*x^3 + 10*x^2 + 10*x + 5)
sage: u = 1 + pi
sage: u.multiplicative_order()
5
sage: v = L2.teichmuller(2)
sage: v.multiplicative_order()
4
sage: (u*v).multiplicative_order()
20

norm(base=None)

Returns the norm of this $$p$$-adic element over base.

Warning

This is not the $$p$$-adic absolute value. This is a field theoretic norm down to a base ring. If you want the $$p$$-adic absolute value, use the abs() function instead.

INPUT:

• base – a subring of the parent (default: base ring)

OUTPUT:

The norm of this $$p$$-adic element over the given base.

EXAMPLES:

sage: Zp(5)(5).norm()
5 + O(5^21)

sage: K.<a> = QqCR(2^3,5)
sage: S.<x> = K[]
sage: L.<pi> = K.extension(x^4 - 2*a)

sage: pi.norm()  # norm over K
a*2 + a*2^2 + a*2^3 + a*2^4 + a*2^5 + O(2^6)
sage: (pi^2).norm()
a^2*2^2 + O(2^7)
sage: pi.norm()^2
a^2*2^2 + O(2^7)

nth_root(n, all=False)

Return the nth root of this element.

INPUT:

• n – an integer
• all – a boolean (default: False): if True, return all ntn roots of this element, instead of just one.

EXAMPLES:

sage: A = Zp(5,10)
sage: x = A(61376); x
1 + 5^3 + 3*5^4 + 4*5^5 + 3*5^6 + O(5^10)
sage: y = x.nth_root(4); y
2 + 5 + 2*5^2 + 4*5^3 + 3*5^4 + 5^6 + O(5^10)
sage: y^4 == x
True

sage: x.nth_root(4, all=True)
[2 + 5 + 2*5^2 + 4*5^3 + 3*5^4 + 5^6 + O(5^10),
4 + 4*5 + 4*5^2 + 4*5^4 + 3*5^5 + 5^6 + 3*5^7 + 5^8 + 5^9 + O(5^10),
3 + 3*5 + 2*5^2 + 5^4 + 4*5^5 + 3*5^6 + 4*5^7 + 4*5^8 + 4*5^9 + O(5^10),
1 + 4*5^3 + 5^5 + 3*5^6 + 5^7 + 3*5^8 + 3*5^9 + O(5^10)]


When $$n$$ is divisible by the underlying prime $$p$$, we are losing precision (which is consistant with the fact that raising to the pth power increases precision):

sage: z = x.nth_root(5); z
1 + 5^2 + 3*5^3 + 2*5^4 + 5^5 + 3*5^7 + 2*5^8 + O(5^9)
sage: z^5
1 + 5^3 + 3*5^4 + 4*5^5 + 3*5^6 + O(5^10)


Everything works over extensions as well:

sage: W.<a> = Zq(5^3)
sage: S.<x> = W[]
sage: R.<pi> = W.extension(x^7 - 5)
sage: R(5).nth_root(7)
pi + O(pi^141)
sage: R(5).nth_root(7, all=True)
[pi + O(pi^141)]


An error is raised if the given element is not a nth power in the ring:

sage: R(5).nth_root(11)
Traceback (most recent call last):
...
ValueError: This element is not a nth power


Similarly, when precision on the input is too small, an error is raised:

sage: x = R(1,6); x 1 + O(pi^6) sage: x.nth_root(5) Traceback (most recent call last): … PrecisionError: Not enough precision to be sure that this element is a nth power
ordp(p=None)

Returns the valuation of self, normalized so that the valuation of $$p$$ is 1

INPUT:

• self – a p-adic element
• p – a prime (default: None). If specified, will make sure that p == self.parent().prime()

NOTE: The optional argument p is used for consistency with the valuation methods on integer and rational.

OUTPUT:

integer – the valuation of self, normalized so that the valuation of $$p$$ is 1

EXAMPLES:

sage: R = Zp(5,20,'capped-rel')
sage: R(0).ordp()
+Infinity
sage: R(1).ordp()
0
sage: R(2).ordp()
0
sage: R(5).ordp()
1
sage: R(10).ordp()
1
sage: R(25).ordp()
2
sage: R(50).ordp()
2
sage: R(1/2).ordp()
0

polylog(n)

Return $$Li_n(self)$$ , the $$n$$-adic polylogarithm of this element.

INPUT:

• n – a non-negative integer

OUTPUT:

• $$Li_n(self)$$

EXAMPLES:

The $$n$$-th polylogarithm of $$-1$$ is $$0$$ for even $$n$$

sage: Qp(13)(-1).polylog(6) == 0
True


We can check some identities, for example those mentioned in [DCW2016]

sage: x = Qp(7, prec=30)(1/3)
sage: (x^2).polylog(4) - 8*x.polylog(4) - 8*(-x).polylog(4) == 0
True

sage: x = Qp(5, prec=30)(4)
sage: x.polylog(2) + (1/x).polylog(2) + x.log(0)**2/2 == 0
True

sage: x = Qp(11, prec=30)(2)
sage: x.polylog(2) + (1-x).polylog(2) + x.log(0)**2*(1-x).log(0) == 0
True


$$Li_1(z) = -\log(1-z)$$ for $$|z| < 1$$

sage: Qp(5)(10).polylog(1) == -Qp(5)(1-10).log(0)
True


The polylogarithm of 1 is not defined

sage: Qp(5)(1).polylog(1)
Traceback (most recent call last):
...
ValueError: Polylogarithm is not defined for 1.


The polylogarithm of 0 is 0

sage: Qp(11)(0).polylog(7)
0


ALGORITHM:

The algorithm of Besser-de Jeu, as described in [BdJ2008] is used.

AUTHORS:

• Jennifer Balakrishnan - Initial implementation
• Alex J. Best (2017-07-21) - Extended to other residue disks

Todo

• Implement for extensions
• Use the change method to create K from self.parent()
rational_reconstruction()

Returns a rational approximation to this $$p$$-adic number

This will raise an ArithmeticError if there are no valid approximations to the unit part with numerator and denominator bounded by sqrt(p^absprec / 2).

_rational_()

OUTPUT:

rational – an approximation to self

EXAMPLES:

sage: R = Zp(5,20,'capped-rel')
sage: for i in range(11):
....:     for j in range(1,10):
....:         if j == 5:
....:             continue
....:         assert i/j == R(i/j).rational_reconstruction()

square_root(extend=True, all=False, algorithm=None)

Return the square root of this $$p$$-adic number.

INPUT:

• self – a $$p$$-adic element.
• extend – a boolean (default: True); if True, return a square root in an extension if necessary; if False and no root exists in the given ring or field, raise a ValueError.
• all – a boolean (default: False); if True, return a list of all square roots.
• algorithm"pari", "sage" or None (default: None); Sage provides an implementation for any extension of $$Q_p$$ whereas only square roots over $$Q_p$$ is implemented in Pari; the default is "pari" if the ground field is $$Q_p$$, "sage" otherwise.

OUTPUT:

The square root or the list of all square roots of this $$p$$-adic number.

NOTE:

The square root is chosen (resp. the square roots are ordered) in a deterministic way.

EXAMPLES:

sage: R = Zp(3, 20)
sage: R(0).square_root()
0

sage: R(1).square_root()
1 + O(3^20)

sage: R(2).square_root(extend=False)
Traceback (most recent call last):
...
ValueError: element is not a square

sage: -R(4).square_root()
2 + O(3^20)

sage: R(9).square_root()
3 + O(3^21)


When $$p = 2$$, the precision of the square root is less than the input:

sage: R2 = Zp(2, 20)
sage: R2(1).square_root()
1 + O(2^19)
sage: R2(4).square_root()
2 + O(2^20)

sage: R.<t> = Zq(2^10, 10)
sage: u = 1 + 8*t
sage: u.square_root()
1 + t*2^2 + t^2*2^3 + t^2*2^4 + (t^4 + t^3 + t^2)*2^5 + (t^4 + t^2)*2^6 + (t^5 + t^2)*2^7 + (t^6 + t^5 + t^4 + t^2)*2^8 + O(2^9)

sage: R.<a> = Zp(2).extension(x^3 - 2)
sage: u = R(1 + a^4 + a^5 + a^7 + a^8, 10); u
1 + a^4 + a^5 + a^7 + a^8 + O(a^10)
sage: v = u.square_root(); v
1 + a^2 + a^4 + a^6 + O(a^7)


However, observe that the precision increases to its original value when we recompute the square of the square root:

sage: v^2
1 + a^4 + a^5 + a^7 + a^8 + O(a^10)


If the input does not have enough precision in order to determine if the given element has a square root in the ground field, an error is raised:

sage: R(1, 6).square_root()
Traceback (most recent call last):
...
PrecisionError: not enough precision to be sure that this element has a square root

sage: R(1, 7).square_root()
1 + O(a^4)

sage: R(1+a^6, 7).square_root(extend=False)
Traceback (most recent call last):
...
ValueError: element is not a square


In particular, an error is raised when we try to compute the square root of an inexact zero.

str(mode=None)

Returns a string representation of self.

EXAMPLES:

sage: Zp(5,5,print_mode='bars')(1/3).str()[3:]
'1|3|1|3|2'

trace(base=None)

Returns the trace of this $$p$$-adic element over the base ring

INPUT:

• base – a subring of the parent (default: base ring)

OUTPUT:

The trace of this $$p$$-adic element over the given base.

EXAMPLES:

sage: Zp(5,5)(5).trace()
5 + O(5^6)

sage: K.<a> = QqCR(2^3,7)
sage: S.<x> = K[]
sage: L.<pi> = K.extension(x^4 - 4*a*x^3 + 2*a)

sage: pi.trace()  # trace over K
a*2^2 + O(2^8)
sage: (pi+1).trace()
(a + 1)*2^2 + O(2^7)

val_unit()

Return (self.valuation(), self.unit_part()). To be overridden in derived classes.

EXAMPLES:

sage: Zp(5,5)(5).val_unit()
(1, 1 + O(5^5))

valuation(p=None)

Returns the valuation of this element.

INPUT:

• self – a p-adic element
• p – a prime (default: None). If specified, will make sure that p==self.parent().prime()

NOTE: The optional argument p is used for consistency with the valuation methods on integer and rational.

OUTPUT:

integer – the valuation of self

EXAMPLES:

sage: R = Zp(17, 4,'capped-rel')
sage: a = R(2*17^2)
sage: a.valuation()
2
sage: R = Zp(5, 4,'capped-rel')
sage: R(0).valuation()
+Infinity

xgcd(other)

Compute the extended gcd of this element and other.

INPUT:

• other – an element in the same ring

OUTPUT:

A tuple r, s, t such that r is a greatest common divisor of this element and other and r = s*self + t*other.

AUTHORS:

• Julian Rueth (2012-10-19): initial version

Note

Since the elements are only given with finite precision, their greatest common divisor is in general not unique (not even up to units). For example $$O(3)$$ is a representative for the elements 0 and 3 in the 3-adic ring $$\ZZ_3$$. The greatest common divisor of $$O(3)$$ and $$O(3)$$ could be (among others) 3 or 0 which have different valuation. The algorithm implemented here, will return an element of minimal valuation among the possible greatest common divisors.

EXAMPLES:

The greatest common divisor is either zero or a power of the uniformizing parameter:

sage: R = Zp(3)
sage: R.zero().xgcd(R.zero())
(0, 1 + O(3^20), 0)
sage: R(3).xgcd(9)
(3 + O(3^21), 1 + O(3^20), 0)


Unlike for gcd(), the result is not lifted to the maximal precision possible in the ring; it is such that r = s*self + t*other holds true:

sage: a = R(3,2); a
3 + O(3^2)
sage: b = R(9,3); b
3^2 + O(3^3)
sage: a.xgcd(b)
(3 + O(3^2), 1 + O(3), 0)
sage: a.xgcd(0)
(3 + O(3^2), 1 + O(3), 0)


If both elements are zero, then the result is zero with the precision set to the smallest of their precisions:

sage: a = R.zero(); a
0
sage: b = R(0,2); b
O(3^2)
sage: a.xgcd(b)
(O(3^2), 0, 1 + O(3^20))


If only one element is zero, then the result depends on its precision:

sage: R(9).xgcd(R(0,1))
(O(3), 0, 1 + O(3^20))
sage: R(9).xgcd(R(0,2))
(O(3^2), 0, 1 + O(3^20))
sage: R(9).xgcd(R(0,3))
(3^2 + O(3^22), 1 + O(3^20), 0)
sage: R(9).xgcd(R(0,4))
(3^2 + O(3^22), 1 + O(3^20), 0)


Over a field, the greatest common divisor is either zero (possibly with finite precision) or one:

sage: K = Qp(3)
sage: K(3).xgcd(0)
(1 + O(3^20), 3^-1 + O(3^19), 0)
sage: K.zero().xgcd(0)
(0, 1 + O(3^20), 0)
sage: K.zero().xgcd(K(0,2))
(O(3^2), 0, 1 + O(3^20))
sage: K(3).xgcd(4)
(1 + O(3^20), 3^-1 + O(3^19), 0)