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.

fmpz * padic_unit(const padic_t op)

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

slong padic_val(const padic_t op)

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.

slong padic_get_val(const padic_t op)

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

slong padic_prec(const padic_t op)

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.

slong padic_get_prec(const padic_t op)

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.

void padic_ctx_init(padic_ctx_t ctx, const fmpz_t p, slong min, slong max, enum padic_print_mode 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.

void padic_ctx_clear(padic_ctx_t ctx)

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

int _padic_ctx_pow_ui(fmpz_t rop, ulong e, const padic_ctx_t ctx)

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¶

void padic_init(padic_t rop)

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

void padic_init2(padic_t rop, slong N)

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

void padic_clear(padic_t rop)

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

void _padic_canonicalise(padic_t rop, const padic_ctx_t ctx)

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$$.

void _padic_reduce(padic_t rop, const padic_ctx_t ctx)

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

void padic_reduce(padic_t rop, const padic_ctx_t ctx)

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

Randomisation¶

void padic_randtest(padic_t rop, flint_rand_t state, const padic_ctx_t ctx)

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.

void padic_randtest_not_zero(padic_t rop, flint_rand_t state, const padic_ctx_t ctx)

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().

void padic_randtest_int(padic_t rop, flint_rand_t state, const padic_ctx_t ctx)

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.

void padic_set(padic_t rop, const padic_t op, const padic_ctx_t ctx)

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

void padic_set_si(padic_t rop, slong op, const padic_ctx_t ctx)

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

void padic_set_ui(padic_t rop, ulong op, const padic_ctx_t ctx)

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

void padic_set_fmpz(padic_t rop, const fmpz_t op, const padic_ctx_t ctx)

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

void padic_set_fmpq(padic_t rop, const fmpq_t op, const padic_ctx_t ctx)

Sets rop to the rational op.

void padic_set_mpz(padic_t rop, const mpz_t op, const padic_ctx_t ctx)

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

void padic_set_mpq(padic_t rop, const mpq_t op, const padic_ctx_t ctx)

Sets rop to the MPIR rational op.

void padic_get_fmpz(fmpz_t rop, const padic_t op, const padic_ctx_t ctx)

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

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

void padic_get_fmpq(fmpq_t rop, const padic_t op, const padic_ctx_t ctx)

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

void padic_get_mpz(mpz_t rop, const padic_t op, const padic_ctx_t ctx)

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

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

void padic_get_mpq(mpq_t rop, const padic_t op, const padic_ctx_t ctx)

Sets the MPIR rational rop to the value of op.

void padic_swap(padic_t op1, padic_t op2)

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.

void padic_zero(padic_t rop)

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

void padic_one(padic_t rop)

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

Comparison¶

int padic_is_zero(const padic_t op)

Returns whether op is equal to zero.

int padic_is_one(const padic_t op)

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

int padic_equal(const padic_t op1, const padic_t op2)

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}$$.

void padic_add(padic_t rop, const padic_t op1, const padic_t op2, const padic_ctx_t ctx)

Sets rop to the sum of op1 and op2.

void padic_sub(padic_t rop, const padic_t op1, const padic_t op2, const padic_ctx_t ctx)

Sets rop to the difference of op1 and op2.

void padic_neg(padic_t rop, const padic_t op, const padic_ctx_t ctx)

Sets rop to the additive inverse of op.

void padic_mul(padic_t rop, const padic_t op1, const padic_t op2, const padic_ctx_t ctx)

Sets rop to the product of op1 and op2.

void padic_shift(padic_t rop, const padic_t op, slong v, const padic_ctx_t ctx)

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

void padic_div(padic_t rop, const padic_t op1, const padic_t op2, const padic_ctx_t ctx)

Sets rop to the quotient of op1 and op2.

void _padic_inv_precompute(padic_inv_t S, const fmpz_t p, slong N)

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

void _padic_inv_clear(padic_inv_t S)

Frees the memory used by $$S$$.

void _padic_inv_precomp(fmpz_t rop, const fmpz_t op, const padic_inv_t 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.

void padic_inv(padic_t rop, const padic_t op, const padic_ctx_t ctx)

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$$.

int padic_sqrt(padic_rop, const padic_t op, const padic_ctx_t ctx)

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$$.

void padic_pow_si(padic_t rop, const padic_t op, slong e, const padic_ctx_t ctx)

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$$.

int padic_exp(padic_t y, const padic_t x, const padic_ctx_t ctx)

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$$.

int padic_exp_rectangular(padic_t y, const padic_t x, const padic_ctx_t ctx)

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}$$.

int padic_exp_balanced(padic_t y, const padic_t x, const padic_ctx_t ctx)

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$$.

int padic_log(padic_t rop, const padic_t op, const padic_ctx_t ctx)

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.

int padic_log_rectangular(padic_t rop, const padic_t op, const padic_ctx_t ctx)

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}$$.

int padic_log_satoh(padic_t rop, const padic_t op, const padic_ctx_t ctx)

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}.$
int padic_log_balanced(padic_t rop, const padic_t op, const padic_ctx_t ctx)

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.

void padic_teichmuller(padic_t rop, const padic_t op, const padic_ctx_t ctx)

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.

ulong padic_val_fac_ui_2(ulong n)

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¶

char * padic_get_str(char * str, const padic_t op, const padic_ctx_t ctx)

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)
int padic_fprint(FILE * file, const padic_t op, 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$$.

int _padic_print(const fmpz_t u, slong v, const padic_ctx_t ctx)
int padic_print(const padic_t op, const padic_ctx_t ctx)

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

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

void padic_debug(const padic_t op)

Prints debug information about op to the stream stdout, in the format "(u v N)".