Introduction¶

The padic_t data type represents elements of $$\mathbf{Q}_p$$ to precision $$N$$, stored in the form $$x = p^v u$$ with $$u, v \in \mathbf{Z}$$. Arithmetic operations can be carried out with respect to a context containing the prime number $$p$$ and various pieces of pre-computed data.

Independent of the context, we consider a $$p$$-adic number $$x = u p^v$$ to be in canonical form whenever either $$p \nmid u$$ or $$u = v = 0$$, and we say it is reduced if, in addition, for non-zero $$u$$, $$u \in (0, p^{N-v})$$.

We briefly describe the interface:

The functions in this module expect arguments of type padic_t, and each variable carries its own precision. The functions have an interface that is similar to the MPFR functions. In particular, they have the same semantics, specified as follows: Compute the requested operation exactly and then reduce the result to the precision of the output variable.

Data structures¶

A $$p$$-adic number of type padic_t comprises a unit $$u$$, a valuation $$v$$, and a precision $$N$$. We provide the following macros to access these fields, so that code can be developed somewhat independently from the underlying data layout.

Returns the unit part of the $$p$$-adic number as a FLINT integer, which can be used as an operand for the fmpz functions.

Returns the valuation part of the $$p$$-adic number.

Note that this function is implemented as a macro and that the expression padic_val(op) can be used as both an lvalue and an rvalue.

Returns the valuation part of the $$p$$-adic number.

Returns the precision of the $$p$$-adic number.

Note that this function is implemented as a macro and that the expression padic_prec(op) can be used as both an lvalue and an rvalue.

Returns the precision of the $$p$$-adic number.

Context¶

A context object for $$p$$-adic arithmetic contains data pertinent to $$p$$-adic computations, but which we choose not to store with each element individually. Currently, this includes the prime number $$p$$, its double inverse in case of word-sized primes, precomputed powers of $$p$$ in the range given by min and max, and the printing mode.

Initialises the context ctx with the given data.

Assumes that $$p$$ is a prime. This is not verified but the subsequent behaviour is undefined if $$p$$ is a composite number.

Assumes that min and max are non-negative and that min is at most max, raising an abort signal otherwise.

Assumes that the printing mode is one of PADIC_TERSE, PADIC_SERIES, or PADIC_VAL_UNIT. Using the example $$x = 7^{-1} 12$$ in $$\mathbf{Q}_7$$, these behave as follows:

In PADIC_TERSE mode, a $$p$$-adic number is printed in the same way as a rational number, e.g. 12/7.

In PADIC_SERIES mode, a $$p$$-adic number is printed digit by digit, e.g. 5*7^-1 + 1.

In PADIC_VAL_UNIT mode, a $$p$$-adic number is printed showing the valuation and unit parts separately, e.g. 12*7^-1.

Clears all memory that has been allocated as part of the context.

Sets rop to $$p^e$$ as efficiently as possible, where rop is expected to be an uninitialised fmpz_t.

If the return value is non-zero, it is the responsibility of the caller to clear the returned integer.

Memory management¶

Initialises the $$p$$-adic number with the precision set to PADIC_DEFAULT_PREC, which is defined as $$20$$.

Initialises the $$p$$-adic number rop with precision $$N$$.

Clears all memory used by the $$p$$-adic number rop.

Brings the $$p$$-adic number rop into canonical form.

That is to say, ensures that either $$u = v = 0$$ or $$p \nmid u$$. There is no reduction modulo a power of $$p$$.

Given a $$p$$-adic number rop in canonical form, reduces it modulo $$p^N$$.

Ensures that the $$p$$-adic number rop is reduced.

Randomisation¶

Sets rop to a random $$p$$-adic number modulo $$p^N$$ with valuation in the range $$[- \lceil N/10\rceil, N)$$, $$[N - \lceil -N/10\rceil, N)$$, or $$[-10, 0)$$ as $$N$$ is positive, negative or zero, whenever rop is non-zero.

Sets rop to a random non-zero $$p$$-adic number modulo $$p^N$$, where the range of the valuation is as for the function padic_randtest().

Sets rop to a random $$p$$-adic integer modulo $$p^N$$.

Note that whenever $$N \leq 0$$, rop is set to zero.

Assignments and conversions¶

All assignment functions set the value of rop from op, reduced to the precision of rop.

Sets rop to the $$p$$-adic number op.

Sets the $$p$$-adic number rop to the slong integer op.

Sets the $$p$$-adic number rop to the ulong integer op.

Sets the $$p$$-adic number rop to the integer op.

Sets rop to the rational op.

Sets the $$p$$-adic number rop to the MPIR integer op.

Sets rop to the MPIR rational op.

Sets the integer rop to the exact $$p$$-adic integer op.

If op is not a $$p$$-adic integer, raises an abort signal.

Sets the rational rop to the $$p$$-adic number op.

Sets the MPIR integer rop to the $$p$$-adic integer op.

If op is not a $$p$$-adic integer, raises an abort signal.

Sets the MPIR rational rop to the value of op.

Swaps the two $$p$$-adic numbers op1 and op2.

Note that this includes swapping the precisions. In particular, this operation is not equivalent to swapping op1 and op2 using padic_set() and an auxiliary variable whenever the precisions of the two elements are different.

Sets the $$p$$-adic number rop to zero.

Sets the $$p$$-adic number rop to one, reduced modulo the precision of rop.

Comparison¶

Returns whether op is equal to zero.

Returns whether op is equal to one, that is, whether $$u = 1$$ and $$v = 0$$.

Returns whether op1 and op2 are equal, that is, whether $$u_1 = u_2$$ and $$v_1 = v_2$$.

Arithmetic operations¶

slong * _padic_lifts_exps(slong *n, slong N)

Given a positive integer $$N$$ define the sequence $$a_0 = N, a_1 = \lceil a_0/2\rceil, \dotsc, a_{n-1} = \lceil a_{n-2}/2\rceil = 1$$. Then $$n = \lceil\log_2 N\rceil + 1$$.

This function sets $$n$$ and allocates and returns the array $$a$$.

void _padic_lifts_pows(fmpz *pow, const slong *a, slong n, const fmpz_t p)

Given an array $$a$$ as computed above, this function computes the corresponding powers of $$p$$, that is, pow[i] is equal to $$p^{a_i}$$.

Sets rop to the sum of op1 and op2.

Sets rop to the difference of op1 and op2.

Sets rop to the additive inverse of op.

Sets rop to the product of op1 and op2.

Sets rop to the product of op and $$p^v$$.

Sets rop to the quotient of op1 and op2.

Pre-computes some data and allocates temporary space for $$p$$-adic inversion using Hensel lifting.

Frees the memory used by $$S$$.

Sets rop to the inverse of op modulo $$p^N$$, assuming that op is a unit and $$N \geq 1$$.

In the current implementation, allows aliasing, but this might change in future versions.

Uses some data $$S$$ precomputed by calling the function _padic_inv_precompute(). Note that this object is not declared const and in fact it carries a field providing temporary work space. This allows repeated calls of this function to avoid repeated memory allocations, as used e.g. by the function padic_log().

void _padic_inv(fmpz_t rop, const fmpz_t op, const fmpz_t p, slong N)

Sets rop to the inverse of op modulo $$p^N$$, assuming that op is a unit and $$N \geq 1$$.

In the current implementation, allows aliasing, but this might change in future versions.

Computes the inverse of op modulo $$p^N$$.

Suppose that op is given as $$x = u p^v$$. Raises an abort signal if $$v < -N$$. Otherwise, computes the inverse of $$u$$ modulo $$p^{N+v}$$.

This function employs Hensel lifting of an inverse modulo $$p$$.

Returns whether op is a $$p$$-adic square. If this is the case, sets rop to one of the square roots; otherwise, the value of rop is undefined.

We have the following theorem:

Let $$u \in \mathbf{Z}^{\times}$$. Then $$u$$ is a square if and only if $$u \bmod p$$ is a square in $$\mathbf{Z} / p \mathbf{Z}$$, for $$p > 2$$, or if $$u \bmod 8$$ is a square in $$\mathbf{Z} / 8 \mathbf{Z}$$, for $$p = 2$$.

Sets rop to op raised to the power $$e$$, which is defined as one whenever $$e = 0$$.

Assumes that some computations involving $$e$$ and the valuation of op do not overflow in the slong range.

Note that if the input $$x = p^v u$$ is defined modulo $$p^N$$ then $$x^e = p^{ev} u^e$$ is defined modulo $$p^{N + (e - 1) v}$$, which is a precision loss in case $$v < 0$$.

Exponential¶

slong _padic_exp_bound(slong v, slong N, const fmpz_t p)

Returns an integer $$i$$ such that for all $$j \geq i$$ we have $$\operatorname{ord}_p(x^j / j!) \geq N$$, where $$\operatorname{ord}_p(x) = v$$.

When $$p$$ is a word-sized prime, returns $$\left\lceil \frac{(p-1)N - 1}{(p-1)v - 1}\right\rceil$$. Otherwise, returns $$\lceil N/v\rceil$$.

Assumes that $$v < N$$. Moreover, $$v$$ has to be at least $$2$$ or $$1$$, depending on whether $$p$$ is $$2$$ or odd.

void _padic_exp_rectangular(fmpz_t rop, const fmpz_t u, slong v, const fmpz_t p, slong N)
void _padic_exp_balanced(fmpz_t rop, const fmpz_t u, slong v, const fmpz_t p, slong N)
void _padic_exp(fmpz_t rop, const fmpz_t u, slong v, const fmpz_t p, slong N)

Sets rop to the $$p$$-exponential function evaluated at $$x = p^v u$$, reduced modulo $$p^N$$.

Assumes that $$x \neq 0$$, that $$\operatorname{ord}_p(x) < N$$ and that $$\exp(x)$$ converges, that is, that $$\operatorname{ord}_p(x)$$ is at least $$2$$ or $$1$$ depending on whether the prime $$p$$ is $$2$$ or odd.

Supports aliasing between rop and $$u$$.

Returns whether the $$p$$-adic exponential function converges at the $$p$$-adic number $$x$$, and if so sets $$y$$ to its value.

The $$p$$-adic exponential function is defined by the usual series

$\exp_p(x) = \sum_{i = 0}^{\infty} \frac{x^i}{i!}$

but this only converges only when $$\operatorname{ord}_p(x) > 1 / (p - 1)$$. For elements $$x \in \mathbf{Q}_p$$, this means that $$\operatorname{ord}_p(x) \geq 1$$ when $$p \geq 3$$ and $$\operatorname{ord}_2(x) \geq 2$$ when $$p = 2$$.

Returns whether the $$p$$-adic exponential function converges at the $$p$$-adic number $$x$$, and if so sets $$y$$ to its value.

Uses a rectangular splitting algorithm to evaluate the series expression of $$\exp(x) \bmod{p^N}$$.

Returns whether the $$p$$-adic exponential function converges at the $$p$$-adic number $$x$$, and if so sets $$y$$ to its value.

Uses a balanced approach, balancing the size of chunks of $$x$$ with the valuation and hence the rate of convergence, which results in a quasi-linear algorithm in $$N$$, for fixed $$p$$.

Logarithm¶

slong _padic_log_bound(slong v, slong N, const fmpz_t p)

Returns $$b$$ such that for all $$i \geq b$$ we have

$i v - \operatorname{ord}_p(i) \geq N$

where $$v \geq 1$$.

Assumes that $$1 \leq v < N$$ or $$2 \leq v < N$$ when $$p$$ is odd or $$p = 2$$, respectively, and also that $$N < 2^{f-2}$$ where $$f$$ is FLINT_BITS.

void _padic_log(fmpz_t z, const fmpz_t y, slong v, const fmpz_t p, slong N)
void _padic_log_rectangular(fmpz_t z, const fmpz_t y, slong v, const fmpz_t p, slong N)
void _padic_log_satoh(fmpz_t z, const fmpz_t y, slong v, const fmpz_t p, slong N)
void _padic_log_balanced(fmpz_t z, const fmpz_t y, slong v, const fmpz_t p, slong N)

Computes

$z = - \sum_{i = 1}^{\infty} \frac{y^i}{i} \pmod{p^N},$

reduced modulo $$p^N$$.

Note that this can be used to compute the $$p$$-adic logarithm via the equation

$\begin{split}\log(x) & = \sum_{i=1}^{\infty} (-1)^{i-1} \frac{(x-1)^i}{i} \\ & = - \sum_{i=1}^{\infty} \frac{(1-x)^i}{i}.\end{split}$

Assumes that $$y = 1 - x$$ is non-zero and that $$v = \operatorname{ord}_p(y)$$ is at least $$1$$ when $$p$$ is odd and at least $$2$$ when $$p = 2$$ so that the series converges.

Assumes that $$v < N$$, and hence in particular $$N \geq 2$$.

Does not support aliasing between $$y$$ and $$z$$.

Returns whether the $$p$$-adic logarithm function converges at the $$p$$-adic number op, and if so sets rop to its value.

The $$p$$-adic logarithm function is defined by the usual series

$\log_p(x) = \sum_{i=1}^{\infty} (-1)^{i-1} \frac{(x-1)^i}{i}$

but this only converges when $$\operatorname{ord}_p(x - 1)$$ is at least $$2$$ or $$1$$ when $$p = 2$$ or $$p > 2$$, respectively.

Returns whether the $$p$$-adic logarithm function converges at the $$p$$-adic number op, and if so sets rop to its value.

Uses a rectangular splitting algorithm to evaluate the series expression of $$\log(x) \bmod{p^N}$$.

Returns whether the $$p$$-adic logarithm function converges at the $$p$$-adic number op, and if so sets rop to its value.

Uses an algorithm based on a result of Satoh, Skjernaa and Taguchi that $$\operatorname{ord}_p\bigl(a^{p^k} - 1\bigr) > k$$, which implies that

$\log(a) \equiv p^{-k} \Bigl( \log\bigl(a^{p^k}\bigr) \pmod{p^{N+k}} \Bigr) \pmod{p^N}.$

Returns whether the $$p$$-adic logarithm function converges at the $$p$$-adic number op, and if so sets rop to its value.

Special functions¶

void _padic_teichmuller(fmpz_t rop, const fmpz_t op, const fmpz_t p, slong N)

Computes the Teichm”uller lift of the $$p$$-adic unit op, assuming that $$N \geq 1$$.

Supports aliasing between rop and op.

Computes the Teichm”uller lift of the $$p$$-adic unit op.

If op is a $$p$$-adic integer divisible by $$p$$, sets rop to zero, which satisfies $$t^p - t = 0$$, although it is clearly not a $$(p-1)$$-st root of unity.

If op has negative valuation, raises an abort signal.

Computes the $$2$$-adic valuation of $$n!$$.

Note that since $$n$$ fits into an ulong, so does $$\operatorname{ord}_2(n!)$$ since $$\operatorname{ord}_2(n!) \leq (n - 1) / (p - 1) = n - 1$$.

ulong padic_val_fac_ui(ulong n, const fmpz_t p)

Computes the $$p$$-adic valuation of $$n!$$.

Note that since $$n$$ fits into an ulong, so does $$\operatorname{ord}_p(n!)$$ since $$\operatorname{ord}_p(n!) \leq (n - 1) / (p - 1)$$.

void padic_val_fac(fmpz_t rop, const fmpz_t op, const fmpz_t p)

Sets rop to the $$p$$-adic valuation of the factorial of op, assuming that op is non-negative.

Input and output¶

Returns the string representation of the $$p$$-adic number op according to the printing mode set in the context.

If str is NULL then a new block of memory is allocated and a pointer to this is returned. Otherwise, it is assumed that the string str is large enough to hold the representation and it is also the return value.

int _padic_fprint(FILE * file, const fmpz_t u, slong v, const padic_ctx_t ctx)

Prints the string representation of the $$p$$-adic number op to the stream file.

In the current implementation, always returns $$1$$.

Prints the string representation of the $$p$$-adic number op to the stream stdout.
In the current implementation, always returns $$1$$.