# padic.h – p-adic numbers

## 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 GMP integer `op`.

  Note: Requires that `gmp.h` has been included before any FLINT header is included.

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

  Sets `rop` to the GMP rational `op`.

  Note: Requires that `gmp.h` has been included before any FLINT header is included.

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 GMP integer `rop` to the \(p\)-adic integer `op`.

  If `op` is not a \(p\)-adic integer, raises an `abort` signal.

  Note: Requires that `gmp.h` has been included before any FLINT header is included.

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

  Sets the GMP rational `rop` to the value of `op`.

  Note: Requires that `gmp.h` has been included before any FLINT header is included.

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_t 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)"`.