# padic_poly.h – polynomials over p-adic numbers¶

## Module documentation¶

We represent a polynomial in $$\mathbf{Q}_p[x]$$ as a product $$p^v f(x)$$, where $$p$$ is a prime number, $$v \in \mathbf{Z}$$ and $$f(x) \in \mathbf{Z}[x]$$. As a data structure, we call this polynomial normalised if the polynomial $$f(x)$$ is normalised, that is, if the top coefficient is non-zero. We say this polynomial is in canonical form if one of the coefficients of $$f(x)$$ is a $$p$$-adic unit. If $$f(x)$$ is the zero polynomial, we require that $$v = 0$$. We say this polynomial is reduced modulo $$p^N$$ if it is canonical form and if all coefficients lie in the range $$[0, p^N)$$.

## Memory management¶

Initialises poly for use, setting its length to zero. The precision of the polynomial is set to PADIC_DEFAULT_PREC. A corresponding call to padic_poly_clear() must be made after finishing with the padic_poly_t to free the memory used by the polynomial.

void padic_poly_init2(padic_poly_t poly, slong alloc, slong prec)

Initialises poly with space for at least alloc coefficients and sets the length to zero. The allocated coefficients are all set to zero. The precision is set to prec.

void padic_poly_realloc(padic_poly_t poly, slong alloc, const fmpz_t p)

Reallocates the given polynomial to have space for alloc coefficients. If alloc is zero the polynomial is cleared and then reinitialised. If the current length is greater than alloc the polynomial is first truncated to length alloc.

If len is greater than the number of coefficients currently allocated, then the polynomial is reallocated to have space for at least len coefficients. No data is lost when calling this function.

The function efficiently deals with the case where fit_length is called many times in small increments by at least doubling the number of allocated coefficients when length is larger than the number of coefficients currently allocated.

Demotes the coefficients of poly beyond len and sets the length of poly to len.

Note that if the current length is greater than len the polynomial may no slonger be in canonical form.

Clears the given polynomial, releasing any memory used. It must be reinitialised in order to be used again.

Sets the length of poly so that the top coefficient is non-zero. If all coefficients are zero, the length is set to zero. This function is mainly used internally, as all functions guarantee normalisation.

void _padic_poly_canonicalise(fmpz *poly, slong *v, slong len, const fmpz_t p)

Brings the polynomial poly into canonical form, assuming that it is normalised already. Does not carry out any reduction.

Reduces the polynomial poly modulo $$p^N$$, assuming that it is in canonical form already.

void padic_poly_truncate(padic_poly_t poly, slong n, const fmpz_t p)

Truncates the polynomial to length at most~n.

## Polynomial parameters¶

Returns the degree of the polynomial poly.

Returns the length of the polynomial poly.

Returns the valuation of the polynomial poly, which is defined to be the minimum valuation of all its coefficients.

The valuation of the zero polynomial is~0.

Note that this is implemented as a macro and can be used as either a lvalue or a rvalue.

Returns the precision of the polynomial poly.

Note that this is implemented as a macro and can be used as either a lvalue or a rvalue.

Note that increasing the precision might require a call to padic_poly_reduce().

## Randomisation¶

void padic_poly_randtest(padic_poly_t f, flint_rand_t state, slong len, const padic_ctx_t ctx)

Sets $$f$$ to a random polynomial of length at most len with entries reduced modulo $$p^N$$.

void padic_poly_randtest_not_zero(padic_poly_t f, flint_rand_t state, slong len, const padic_ctx_t ctx)

Sets $$f$$ to a non-zero random polynomial of length at most len with entries reduced modulo $$p^N$$.

void padic_poly_randtest_val(padic_poly_t f, flint_rand_t state, slong val, slong len, const padic_ctx_t ctx)

Sets $$f$$ to a random polynomial of length at most len with at most the prescribed valuation val and entries reduced modulo $$p^N$$.

Specifically, we aim to set the valuation to be exactly equal to val, but do not check for additional cancellation when creating the coefficients.

## Assignment and basic manipulation¶

Sets the polynomial poly to the $$p$$-adic number $$x$$, reduced to the precision of the polynomial.

Sets the polynomial poly1 to the polynomial poly2, reduced to the precision of poly1.

Sets the polynomial poly to the signed slong integer $$x$$ reduced to the precision of the polynomial.

Sets the polynomial poly to the unsigned slong integer $$x$$ reduced to the precision of the polynomial.

Sets the polynomial poly to the integer $$x$$ reduced to the precision of the polynomial.

Sets the polynomial poly to the value of the rational $$x$$, reduced to the precision of the polynomial.

Sets the polynomial rop to the integer polynomial op reduced to the precision of the polynomial.

Sets the polynomial rop to the value of the rational polynomial op, reduced to the precision of the polynomial.

Sets the integer polynomial rop to the value of the $$p$$-adic polynomial op and returns $$1$$ if the polynomial is $$p$$-adically integral. Otherwise, returns $$0$$.

Sets rop to the rational polynomial corresponding to the $$p$$-adic polynomial op.

Sets poly to the zero polynomial.

Sets poly to the constant polynomial $$1$$, reduced to the precision of the polynomial.

Swaps the two polynomials poly1 and poly2, including their precisions.

This is done efficiently by swapping pointers.

## Getting and setting coefficients¶

Sets $$c$$ to the coefficient of $$x^n$$ in the polynomial, reduced modulo the precision of $$c$$.

Sets the coefficient of $$x^n$$ in the polynomial $$f$$ to $$c$$, reduced to the precision of the polynomial $$f$$.

Note that this operation can take linear time in the length of the polynomial.

## Comparison¶

Returns whether the two polynomials poly1 and poly2 are equal.

Returns whether the polynomial poly is the zero polynomial.

Returns whether the polynomial poly is equal to the constant polynomial~1, taking the precision of the polynomial into account.

## Addition and subtraction¶

void _padic_poly_add(fmpz *rop, slong *rval, slong N, const fmpz *op1, slong val1, slong len1, slong N1, const fmpz *op2, slong val2, slong len2, slong N2, const padic_ctx_t ctx)

Sets (rop, *val, FLINT_MAX(len1, len2) to the sum of (op1, val1, len1) and (op2, val2, len2).

Assumes that the input is reduced and guarantees that this is also the case for the output.

Assumes that $$\min\{v_1, v_2\} < N$$.

Supports aliasing between the output and input arguments.

Sets $$f$$ to the sum $$g + h$$.

void _padic_poly_sub(fmpz *rop, slong *rval, const fmpz *op1, slong val1, slong len1, const fmpz *op2, slong val2, slong len2, const padic_ctx_t ctx)

Sets (rop, *val, FLINT_MAX(len1, len2) to the difference of (op1, val1, len1) and (op2, val2, len2).

Assumes that the input is reduced and guarantees that this is also the case for the output.

Assumes that $$\min\{v_1, v_2\} < N$$.

Support aliasing between the output and input arguments.

Sets $$f$$ to the difference $$g - h$$.

Sets $$f$$ to $$-g$$.

## Scalar multiplication¶

void _padic_poly_scalar_mul_padic(fmpz *rop, slong *rval, const fmpz *op, slong val, slong len, const padic_t c, const padic_ctx_t ctx)

Sets (rop, *rval, len) to (op, val, len) multiplied by the scalar $$c$$.

The result will only be correctly reduced if the polynomial is non-zero. Otherwise, the array (rop, len) will be set to zero but the valuation *rval might be wrong.

Sets the polynomial rop to the product of the polynomial op and the $$p$$-adic number $$c$$, reducing the result modulo $$p^N$$.

## Multiplication¶

void _padic_poly_mul(fmpz *rop, slong *rval, slong N, const fmpz *op1, slong val1, slong len1, const fmpz *op2, slong val2, slong len2, const padic_ctx_t ctx)

Sets (rop, *rval, len1 + len2 - 1) to the product of (op1, val1, len1) and (op2, val2, len2).

Assumes that the resulting valuation *rval, which is the sum of the valuations val1 and val2, is less than the precision~N of the context.

Assumes that len1 >= len2 > 0.

Sets the polynomial res to the product of the two polynomials poly1 and poly2, reduced modulo $$p^N$$.

## Powering¶

void _padic_poly_pow(fmpz *rop, slong *rval, slong N, const fmpz *op, slong val, slong len, ulong e, const padic_ctx_t ctx)

Sets the polynomial (rop, *rval, e (len - 1) + 1) to the polynomial (op, val, len) raised to the power~e.

Assumes that $$e > 1$$ and len > 0.

Does not support aliasing between the input and output arguments.

Sets the polynomial rop to the polynomial op raised to the power~e, reduced to the precision in rop.

In the special case $$e = 0$$, sets rop to the constant polynomial one reduced to the precision of rop. Also note that when $$e = 1$$, this operation sets rop to op and then reduces rop.

When the valuation of the input polynomial is negative, this results in a loss of $$p$$-adic precision. Suppose that the input polynomial is given to precision~N and has valuation~v < 0. The result then has valuation $$e v < 0$$ but is only correct to precision $$N + (e - 1) v$$.

## Series inversion¶

Computes the power series inverse $$g$$ of $$f$$ modulo $$X^n$$, where $$n \geq 1$$.

Given the polynomial $$f \in \mathbf{Q}[X] \subset \mathbf{Q}_p[X]$$, there exists a unique polynomial $$f^{-1} \in \mathbf{Q}[X]$$ such that $$f f^{-1} = 1$$ modulo $$X^n$$. This function sets $$g$$ to $$f^{-1}$$ reduced modulo $$p^N$$.

Assumes that the constant coefficient of $$f$$ is non-zero.

Moreover, assumes that the valuation of the constant coefficient of $$f$$ is minimal among the coefficients of $$f$$.

Note that the result $$g$$ is zero if and only if $$- \operatorname{ord}_p(f) \geq N$$.

## Derivative¶

void _padic_poly_derivative(fmpz *rop, slong *rval, slong N, const fmpz *op, slong val, slong len, const padic_ctx_t ctx)

Sets (rop, rval) to the derivative of (op, val) reduced modulo $$p^N$$.

Supports aliasing of the input and the output parameters.

Sets rop to the derivative of op, reducing the result modulo the precision of rop.

## Shifting¶

Notationally, sets the polynomial rop to the polynomial op multiplied by $$x^n$$, where $$n \geq 0$$, and reduces the result.

Notationally, sets the polynomial rop to the polynomial op after floor division by $$x^n$$, where $$n \geq 0$$, ensuring the result is reduced.

## Evaluation¶

void _padic_poly_evaluate_padic(fmpz_t u, slong *v, slong N, const fmpz *poly, slong val, slong len, const fmpz_t a, slong b, const padic_ctx_t ctx)

Sets the $$p$$-adic number y to poly evaluated at $$a$$, reduced in the given context.

Suppose that the polynomial can be written as $$F(X) = p^w f(X)$$ with $$\operatorname{ord}_p(f) = 1$$, that $$\operatorname{ord}_p(a) = b$$ and that both are defined to precision~N. Then $$f$$ is defined to precision $$N-w$$ and so $$f(a)$$ is defined to precision $$N-w$$ when $$a$$ is integral and $$N-w+(n-1)b$$ when $$b < 0$$, where $$n = \deg(f)$$. Thus, $$y = F(a)$$ is defined to precision $$N$$ when $$a$$ is integral and $$N+(n-1)b$$ when $$b < 0$$.

## Composition¶

void _padic_poly_compose(fmpz *rop, slong *rval, slong N, const fmpz *op1, slong val1, slong len1, const fmpz *op2, slong val2, slong len2, const padic_ctx_t ctx)

Sets (rop, *rval, (len1-1)*(len2-1)+1) to the composition of the two input polynomials, reducing the result modulo $$p^N$$.

Assumes that len1 is non-zero.

Does not support aliasing.

Sets rop to the composition of op1 and op2, reducing the result in the given context.

To be clear about the order of composition, let $$f(X)$$ and $$g(X)$$ denote the polynomials op1 and op2, respectively. Then rop is set to $$f(g(X))$$.

void _padic_poly_compose_pow(fmpz *rop, slong *rval, slong N, const fmpz *op, slong val, slong len, slong k, const padic_ctx_t ctx)

Sets (rop, *rval, (len - 1)*k + 1) to the composition of (op, val, len) and the monomial $$x^k$$, where $$k \geq 1$$.

Assumes that len is positive.

Supports aliasing between the input and output polynomials.

Sets rop to the composition of op and the monomial $$x^k$$, where $$k \geq 1$$.

Note that no reduction takes place.

## Input and output¶

Prints the data defining the $$p$$-adic polynomial poly in a simple format useful for debugging purposes.

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

int _padic_poly_fprint(FILE *file, const fmpz *poly, slong val, slong len, const padic_ctx_t ctx)

Prints a simple representation of the polynomial poly to the stream file.

A non-zero polynomial is represented by the number of coefficients, two spaces, followed by a list of the coefficients, which are printed in a way depending on the print mode,

In the PADIC_TERSE mode, the coefficients are printed as rational numbers.

The PADIC_SERIES mode is currently not supported and will raise an abort signal.

In the PADIC_VAL_UNIT mode, the coefficients are printed in the form $$p^v u$$.

The zero polynomial is represented by "0".

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

int _padic_poly_print(const fmpz *poly, slong val, slong len, const padic_ctx_t ctx)

Prints a simple representation of the polynomial poly to stdout.

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

int _padic_poly_fprint_pretty(FILE *file, const fmpz *poly, slong val, slong len, const char *var, const padic_ctx_t ctx)
int padic_poly_fprint_pretty(FILE *file, const padic_poly_t poly, const char *var, const padic_ctx_t ctx)
int _padic_poly_print_pretty(FILE *file, const fmpz *poly, slong val, slong len, const char *var, const padic_ctx_t ctx)
int padic_poly_print_pretty(const padic_poly_t poly, const char *var, const padic_ctx_t ctx)

## Testing¶

int _padic_poly_is_canonical(const fmpz *op, slong val, slong len, const padic_ctx_t ctx)