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

void padic_poly_init(padic_poly_t poly)

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.

void padic_poly_fit_length(padic_poly_t poly, slong len)

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.

void _padic_poly_set_length(padic_poly_t poly, slong len)

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.

void padic_poly_clear(padic_poly_t poly)

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

void _padic_poly_normalise(padic_poly_t poly)

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)

void padic_poly_canonicalise(padic_poly_t poly, const fmpz_t p)

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

void padic_poly_reduce(padic_poly_t poly, const padic_ctx_t ctx)

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

slong padic_poly_degree(const padic_poly_t poly)

Returns the degree of the polynomial poly.

slong padic_poly_length(const padic_poly_t poly)

Returns the length of the polynomial poly.

slong padic_poly_val(const padic_poly_t 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.

slong padic_poly_prec(padic_poly_t poly)

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

void padic_poly_set_padic(padic_poly_t poly, const padic_t x, const padic_ctx_t ctx)

Sets the polynomial poly to the \(p\)-adic number \(x\), reduced to the precision of the polynomial.

void padic_poly_set(padic_poly_t poly1, const padic_poly_t poly2, const padic_ctx_t ctx)

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

void padic_poly_set_si(padic_poly_t poly, slong x, const padic_ctx_t ctx)

Sets the polynomial poly to the signed slong integer \(x\) reduced to the precision of the polynomial.

void padic_poly_set_ui(padic_poly_t poly, ulong x, const padic_ctx_t ctx)

Sets the polynomial poly to the unsigned slong integer \(x\) reduced to the precision of the polynomial.

void padic_poly_set_fmpz(padic_poly_t poly, const fmpz_t x, const padic_ctx_t ctx)

Sets the polynomial poly to the integer \(x\) reduced to the precision of the polynomial.

void padic_poly_set_fmpq(padic_poly_t poly, const fmpq_t x, const padic_ctx_t ctx)

Sets the polynomial poly to the value of the rational \(x\), reduced to the precision of the polynomial.

void padic_poly_set_fmpz_poly(padic_poly_t rop, const fmpz_poly_t op, const padic_ctx_t ctx)

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

void padic_poly_set_fmpq_poly(padic_poly_t rop, const fmpq_poly_t op, const padic_ctx_t ctx)

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

int padic_poly_get_fmpz_poly(fmpz_poly_t rop, const padic_poly_t op, const padic_ctx_t ctx)

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

void padic_poly_get_fmpq_poly(fmpq_poly_t rop, const padic_poly_t op, const padic_ctx_t ctx)

Sets rop to the rational polynomial corresponding to the \(p\)-adic polynomial op.

void padic_poly_zero(padic_poly_t poly)

Sets poly to the zero polynomial.

void padic_poly_one(padic_poly_t poly)

Sets poly to the constant polynomial \(1\), reduced to the precision of the polynomial.

void padic_poly_swap(padic_poly_t poly1, padic_poly_t poly2)

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

This is done efficiently by swapping pointers.

Getting and setting coefficients

void padic_poly_get_coeff_padic(padic_t c, const padic_poly_t poly, slong n, const padic_ctx_t ctx)

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

void padic_poly_set_coeff_padic(padic_poly_t f, slong n, const padic_t c, const padic_ctx_t ctx)

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

int padic_poly_equal(const padic_poly_t poly1, const padic_poly_t poly2)

Returns whether the two polynomials poly1 and poly2 are equal.

int padic_poly_is_zero(const padic_poly_t poly)

Returns whether the polynomial poly is the zero polynomial.

int padic_poly_is_one(const padic_poly_t poly)

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.

void padic_poly_add(padic_poly_t f, const padic_poly_t g, const padic_poly_t h, const padic_ctx_t ctx)

Sets \(f\) to the sum \(g + h\).

void _padic_poly_sub(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 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.

void padic_poly_sub(padic_poly_t f, const padic_poly_t g, const padic_poly_t h, const padic_ctx_t ctx)

Sets \(f\) to the difference \(g - h\).

void padic_poly_neg(padic_poly_t f, const padic_poly_t g, const padic_ctx_t ctx)

Sets \(f\) to \(-g\).

Scalar multiplication

void _padic_poly_scalar_mul_padic(fmpz *rop, slong *rval, slong N, 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.

void padic_poly_scalar_mul_padic(padic_poly_t rop, const padic_poly_t op, const padic_t c, const padic_ctx_t ctx)

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.

void padic_poly_mul(padic_poly_t res, const padic_poly_t poly1, const padic_poly_t poly2, const padic_ctx_t ctx)

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.

void padic_poly_pow(padic_poly_t rop, const padic_poly_t op, ulong e, const padic_ctx_t ctx)

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

void padic_poly_inv_series(padic_poly_t g, const padic_poly_t f, slong n, const padic_ctx_t ctx)

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.

void padic_poly_derivative(padic_poly_t rop, const padic_poly_t op, const padic_ctx_t ctx)

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

Shifting

void padic_poly_shift_left(padic_poly_t rop, const padic_poly_t op, slong n, const padic_ctx_t ctx)

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

void padic_poly_shift_right(padic_poly_t rop, const padic_poly_t op, slong n, const padic_ctx_t ctx)

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)

void padic_poly_evaluate_padic(padic_t y, const padic_poly_t poly, const padic_t a, 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.

void padic_poly_compose(padic_poly_t rop, const padic_poly_t op1, const padic_poly_t op2, const padic_ctx_t ctx)

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.

void padic_poly_compose_pow(padic_poly_t rop, const padic_poly_t op, slong k, const padic_ctx_t ctx)

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

int padic_poly_debug(const padic_poly_t poly)

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)

int padic_poly_fprint(FILE *file, const padic_poly_t poly, 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)

int padic_poly_print(const padic_poly_t poly, 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(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)

int padic_poly_is_canonical(const padic_poly_t op, const padic_ctx_t ctx)

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

int padic_poly_is_reduced(const padic_poly_t op, const padic_ctx_t ctx)