### Polynomials and power series

#### O(p{`^`}e)

if p is an integer greater than 2, returns a p-adic 0 of precision e. In all other cases, returns a power series zero with precision given by e v, where v is the X-adic valuation of p with respect to its main variable.

The library syntax is zeropadic(p,e) for a p-adic and `zeroser(v,e)` for a power series zero in variable v, which is a `long`. The precision e is a `long`.

#### deriv(x,{v})

derivative of x with respect to the main variable if v is omitted, and with respect to v otherwise. The derivative of a scalar type is zero, and the derivative of a vector or matrix is done componentwise. One can use x' as a shortcut if the derivative is with respect to the main variable of x.

By definition, the main variable of a `t_POLMOD` is the main variable among the coefficients from its two polynomial components (representative and modulus); in other words, assuming a polmod represents an element of R[X]/(T(X)), the variable X is a mute variable and the derivative is taken with respect to the main variable used in the base ring R.

The library syntax is deriv(x,v), where v is a `long`, and an omitted v is coded as -1. When x is a `t_POL`, `derivpol`(x) is a shortcut for `deriv`(x, -1).

#### eval(x)

replaces in x the formal variables by the values that have been assigned to them after the creation of x. This is mainly useful in GP, and not in library mode. Do not confuse this with substitution (see `subst`).

If x is a character string, `eval(x)` executes x as a GP command, as if directly input from the keyboard, and returns its output. For convenience, x is evaluated as if `strictmatch` was off. In particular, unused characters at the end of x do not prevent its evaluation:

        ? eval("1a")
         % 1 = 1

The library syntax is geval(x). The more basic functions `poleval(q,x)`, `qfeval(q,x)`, and `hqfeval(q,x)` evaluate q at x, where q is respectively assumed to be a polynomial, a quadratic form (a symmetric matrix), or an Hermitian form (an Hermitian complex matrix).

#### factorpadic(pol,p,r,{flag = 0})

p-adic factorization of the polynomial pol to precision r, the result being a two-column matrix as in `factor`. The factors are normalized so that their leading coefficient is a power of p. r must be strictly larger than the p-adic valuation of the discriminant of pol for the result to make any sense. The method used is a modified version of the round 4 algorithm of Zassenhaus.

If flag = 1, use an algorithm due to Buchmann and Lenstra, which is usually less efficient.

The library syntax is factorpadic4(pol,p,r), where r is a `long` integer.

#### intformal(x,{v})

formal integration of x with respect to the main variable if v is omitted, with respect to the variable v otherwise. Since PARI does not know about "abstract" logarithms (they are immediately evaluated, if only to a power series), logarithmic terms in the result will yield an error. x can be of any type. When x is a rational function, it is assumed that the base ring is an integral domain of characteristic zero.

The library syntax is integ(x,v), where v is a `long` and an omitted v is coded as -1.

#### padicappr(pol,a)

vector of p-adic roots of the polynomial pol congruent to the p-adic number a modulo p, and with the same p-adic precision as a. The number a can be an ordinary p-adic number (type `t_PADIC`, i.e.an element of Z_p) or can be an integral element of a finite extension of Q_p, given as a `t_POLMOD` at least one of whose coefficients is a `t_PADIC`. In this case, the result is the vector of roots belonging to the same extension of Q_p as a.

The library syntax is padicappr(pol,a).

#### polcoeff(x,s,{v})

coefficient of degree s of the polynomial x, with respect to the main variable if v is omitted, with respect to v otherwise. Also applies to power series, scalars (polynomial of degree 0), and to rational functions provided the denominator is a monomial.

The library syntax is polcoeff0(x,s,v), where v is a `long` and an omitted v is coded as -1. Also available is `truecoeff(x,v)`.

#### poldegree(x,{v})

degree of the polynomial x in the main variable if v is omitted, in the variable v otherwise.

The degree of 0 is a fixed negative number, whose exact value should not be used. The degree of a non-zero scalar is 0. Finally, when x is a non-zero polynomial or rational function, returns the ordinary degree of x. Raise an error otherwise.

The library syntax is poldegree(x,v), where v and the result are `long`s (and an omitted v is coded as -1). Also available is `degree(x)`, which is equivalent to `poldegree(x,-1)`.

#### polcyclo(n,{v = x})

n-th cyclotomic polynomial, in variable v (x by default). The integer n must be positive.

The library syntax is cyclo(n,v), where n and v are `long` integers (v is a variable number, usually obtained through `varn`).

#### poldisc(pol,{v})

discriminant of the polynomial pol in the main variable is v is omitted, in v otherwise. The algorithm used is the subresultant algorithm.

The library syntax is poldisc0(x,v). Also available is `discsr(x)`, equivalent to `poldisc0(x,-1)`.

#### poldiscreduced(f)

reduced discriminant vector of the (integral, monic) polynomial f. This is the vector of elementary divisors of Z[alpha]/f'(alpha)Z[alpha], where alpha is a root of the polynomial f. The components of the result are all positive, and their product is equal to the absolute value of the discriminant off.

The library syntax is reduceddiscsmith(x).

#### polhensellift(x, y, p, e)

given a prime p, an integral polynomial x whose leading coefficient is a p-unit, a vector y of integral polynomials that are pairwise relatively prime modulo p, and whose product is congruent to x modulo p, lift the elements of y to polynomials whose product is congruent to x modulo p^e.

The library syntax is polhensellift(x,y,p,e) where e must be a `long`.

#### polinterpolate(xa,{ya},{v = x},{&e})

given the data vectors xa and ya of the same length n (xa containing the x-coordinates, and ya the corresponding y-coordinates), this function finds the interpolating polynomial passing through these points and evaluates it atv. If ya is omitted, return the polynomial interpolating the (i,xa[i]). If present, e will contain an error estimate on the returned value.

The library syntax is polint(xa,ya,v,&e), where e will contain an error estimate on the returned value.

#### polisirreducible(pol)

pol being a polynomial (univariate in the present version 2.2.13), returns 1 if pol is non-constant and irreducible, 0 otherwise. Irreducibility is checked over the smallest base field over which pol seems to be defined.

The library syntax is gisirreducible(pol).

#### pollead(x,{v})

leading coefficient of the polynomial or power series x. This is computed with respect to the main variable of x if v is omitted, with respect to the variable v otherwise.

The library syntax is pollead(x,v), where v is a `long` and an omitted v is coded as -1. Also available is `leading_term(x)`.

#### pollegendre(n,{v = x})

creates the n^{{th}} Legendre polynomial, in variable v.

The library syntax is legendre(n), where x is a `long`.

#### polrecip(pol)

reciprocal polynomial of pol, i.e.the coefficients are in reverse order. pol must be a polynomial.

The library syntax is polrecip(x).

#### polresultant(x,y,{v},{flag = 0})

resultant of the two polynomials x and y with exact entries, with respect to the main variables of x and y if v is omitted, with respect to the variable v otherwise. The algorithm assumes the base ring is a domain.

If flag = 0, uses the subresultant algorithm.

If flag = 1, uses the determinant of Sylvester's matrix instead (here x and y may have non-exact coefficients).

If flag = 2, uses Ducos's modified subresultant algorithm. It should be much faster than the default if the coefficient ring is complicated (e.g multivariate polynomials or huge coefficients), and slightly slower otherwise.

The library syntax is polresultant0(x,y,v,flag), where v is a `long` and an omitted v is coded as -1. Also available are `subres(x,y)` (flag = 0) and `resultant2(x,y)` (flag = 1).

#### polroots(pol,{flag = 0})

complex roots of the polynomial pol, given as a column vector where each root is repeated according to its multiplicity. The precision is given as for transcendental functions: in GP it is kept in the variable `realprecision` and is transparent to the user, but it must be explicitly given as a second argument in library mode.

The algorithm used is a modification of A.Sch¨nhage's root-finding algorithm, due to and implemented by X.Gourdon. Barring bugs, it is guaranteed to converge and to give the roots to the required accuracy.

If flag = 1, use a variant of the Newton-Raphson method, which is not guaranteed to converge, but is rather fast. If you get the messages "too many iterations in roots" or "INTERNAL ERROR: incorrect result in roots", use the default algorithm. This used to be the default root-finding function in PARI until version 1.39.06.

The library syntax is roots(pol,prec) or `rootsold(pol,prec)`.

#### polrootsmod(pol,p,{flag = 0})

row vector of roots modulo p of the polynomial pol. The particular non-prime value p = 4 is accepted, mainly for 2-adic computations. Multiple roots are not repeated.

If p is very small, you may try setting flag = 1, which uses a naive search.

The library syntax is rootmod(pol,p) (flag = 0) or `rootmod2(pol,p)` (flag = 1).

#### polrootspadic(pol,p,r)

row vector of p-adic roots of the polynomial pol, given to p-adic precision r. Multiple roots are not repeated. p is assumed to be a prime, and pol to be non-zero modulo p. Note that this is not the same as the roots in Z/p^rZ, rather it gives approximations in Z/p^rZ of the true roots living in Q_p.

If pol has inexact `t_PADIC` coefficients, this is not always well-defined; in this case, the equation is first made integral, then lifted to Z. Hence the roots given are approximations of the roots of a polynomial which is p-adically close to the input.

The library syntax is rootpadic(pol,p,r), where r is a `long`.

#### polsturm(pol,{a},{b})

number of real roots of the real polynomial pol in the interval ]a,b], using Sturm's algorithm. a (resp.b) is taken to be - oo (resp.+ oo ) if omitted.

The library syntax is sturmpart(pol,a,b). Use `NULL` to omit an argument. `sturm(pol)` is equivalent to `sturmpart(pol,`NULL`,`NULL`)`. The result is a `long`.

#### polsubcyclo(n,d,{v = x})

gives polynomials (in variable v) defining the sub-Abelian extensions of degree d of the cyclotomic field Q(zeta_n), where d | phi(n).

If there is exactly one such extension the output is a polynomial, else it is a vector of polynomials, eventually empty.

To be sure to get a vector, you can use `concat([],polsubcyclo(n,d))`

The function `galoissubcyclo` allows to specify more closely which sub-Abelian extension should be computed.

The library syntax is polsubcyclo(n,d,v), where n, d and v are `long` and v is a variable number. When (Z/nZ)^* is cyclic, you can use `subcyclo(n,d,v)`, where n, d and v are `long` and v is a variable number.

#### polsylvestermatrix(x,y)

forms the Sylvester matrix corresponding to the two polynomials x and y, where the coefficients of the polynomials are put in the columns of the matrix (which is the natural direction for solving equations afterwards). The use of this matrix can be essential when dealing with polynomials with inexact entries, since polynomial Euclidean division doesn't make much sense in this case.

The library syntax is sylvestermatrix(x,y).

#### polsym(x,n)

creates the vector of the symmetric powers of the roots of the polynomial x up to power n, using Newton's formula.

The library syntax is polsym(x).

#### poltchebi(n,{v = x})

creates the n^{{th}} Chebyshev polynomialT_n of the first kind in variable v.

The library syntax is tchebi(n,v), where n and v are `long` integers (v is a variable number).

#### polzagier(n,m)

creates Zagier's polynomial P_n^{(m)} used in the functions `sumalt` and `sumpos` (with flag = 1). One must have m\le n. The exact definition can be found in "Convergence acceleration of alternating series", Cohen et al., Experiment.Math., vol.9, 2000, pp.3--12.

The library syntax is polzagreel(n,m,prec) if the result is only wanted as a polynomial with real coefficients to the precision prec, or `polzag(n,m)` if the result is wanted exactly, where n and m are `long`s.

#### serconvol(x,y)

convolution (or Hadamard product) of the two power series x and y; in other words if x = sum a_k*X^k and y = sum b_k*X^k then `serconvol`(x,y) = sum a_k*b_k*X^k.

The library syntax is convol(x,y).

#### serlaplace(x)

x must be a power series with non-negative exponents. If x = sum (a_k/k!)*X^k then the result is sum a_k*X^k.

The library syntax is laplace(x).

#### serreverse(x)

reverse power series (i.e.x^{-1}, not 1/x) of x. x must be a power series whose valuation is exactly equal to one.

The library syntax is recip(x).

#### subst(x,y,z)

replace the simple variable y by the argument z in the "polynomial" expression x. Every type is allowed for x, but if it is not a genuine polynomial (or power series, or rational function), the substitution will be done as if the scalar components were polynomials of degree zero. In particular, beware that:

    ? subst(1, x, [1,2; 3,4])
     %1 =
     [1 0]

     [0 1]

     ? subst(1, x, Mat([0,1]))
       ***   forbidden substitution by a non square matrix

If x is a power series, z must be either a polynomial, a power series, or a rational function.

The library syntax is gsubst(x,y,z), where y is the variable number.

#### substpol(x,y,z)

replace the "variable" y by the argument z in the "polynomial" expression x. Every type is allowed for x, but the same behaviour as `subst` above apply.

The difference with `subst` is that y is allowed to be any polynomial here. The substitution is done as per the following script:

       subst_poly(pol, from, to) =
        { local(t = 'subst_poly_t, M = from - t);

          subst(lift(Mod(pol,M), variable(M)), t, to)
        }

For instance

    ? substpol(x^4 + x^2 + 1, x^2, y)
     %1 = y^2 + y + 1
     ? substpol(x^4 + x^2 + 1, x^3, y)
     %2 = x^2 + y*x + 1
     ? substpol(x^4 + x^2 + 1, (x+1)^2, y)
     %3 = (-4*y - 6)*x + (y^2 + 3*y - 3)

The library syntax is gsubstpol(x,y,z).

#### substvec(x,v,w)

v being a vector of monomials (variables), w a vector of expressions of the same length, replace in the expression x all occurences of v_i by w_i. The substitutions are done simultaneously; more precisely, the v_i are first replaced by new variables in x, then these are replaced by the w_i:

    ? substvec([x,y], [x,y], [y,x])
     %1 = [y, x]
     ? substvec([x,y], [x,y], [y,x+y])
     %2 = [y, x + y]     \\ not [y, 2*y]

The library syntax is gsubstvec(x,v,w).

#### taylor(x,y)

Taylor expansion around 0 of x with respect to the simple variable y. x can be of any reasonable type, for example a rational function. The number of terms of the expansion is transparent to the user in GP, but must be given as a second argument in library mode.

The library syntax is tayl(x,y,n), where the `long` integer n is the desired number of terms in the expansion.

#### thue(tnf,a,{sol})

solves the equation P(x,y) = a in integers x and y, where tnf was created with `thueinit`(P). sol, if present, contains the solutions of \Norm(x) = a modulo units of positive norm in the number field defined by P (as computed by `bnfisintnorm`). If the result is conditional (on the GRH or some heuristic strenghtening), a Warning is printed. Otherwise, the result is unconditional, barring bugs. For instance, here's how to solve the Thue equation x^{13} - 5y^{13} = - 4:

    ? tnf = thueinit(x^13 - 5);
     ? thue(tnf, -4)
     %1 = [[1, 1]]

Hence, the only solution is x = 1, y = 1 and the result is unconditional. On the other hand:

    ? tnf = thueinit(x^3-2*x^2+3*x-17);
     ? thue(tnf, -15)
       *** thue: Warning: Non trivial conditional class group.
       *** May miss solutions of the norm equation.
     %2 = [[1, 1]]

This time the result is conditional. All results computed using this tnf are likewise conditional, except for a right-hand side of ± 1.

The library syntax is thue(tnf,a,sol), where an omitted sol is coded as `NULL`.

#### thueinit(P,{flag = 0})

initializes the tnf corresponding to P. It is meant to be used in conjunction with `thue` to solve Thue equations P(x,y) = a, where a is an integer. If flag is non-zero, certify the result unconditionnally. Otherwise, assume GRH, this being much faster of course.

If the conditional computed class group is trivial or you are only interested in the case a = ±1, then results are unconditional anyway. So one should only use the flag is `thue` prints a Warning (see the example there).

The library syntax is thueinit(P,flag,prec).