\chapter{Functions and Operations available in PARI and GP} The functions and operators available in PARI and in the GP/PARI calculator are numerous and everexpanding. Here is a description of the ones available in version \vers. It should be noted that many of these functions accept quite different types as arguments, but others are more restricted. The list of acceptable types will be given for each function or class of functions. Except when stated otherwise, it is understood that a function or operation which should make natural sense is legal. In this chapter, we will describe the functions according to a rough classification. For the functions in alphabetical order, see the general index. \section{Standard monadic or dyadic operators.} \subsec{$\pm$} $+x$ and $-x$ refer to monadic operators ($+x$ does nothing and $-x$ negates $x$). The library syntax is $\teb{gneg}(x)$ for $-x$. \subsec{$+$, $-$} $x+y$ and $x-y$ are the \ref{sum} and \ref{difference} of $x$ and $y$. Among the prominent impossibilities are addition/subtraction between a scalar type and a vector or a matrix, between vector/matrices of incompatible sizes and between an integermod and a real number. The library syntax is $\teb{gadd}(x,y)$ for $x+y$, $\teb{gsub}(x,y)$ for $x-y$. \subsec{$*$} $x*y$ is the \ref{product} of $x$ and $y$. Among the prominent impossibilities are multiplication between vector/matrices of incompatible sizes, between an integermod and a real number. Note that because of vector and matrix operations, $*$ is not necessarily commutative. Note also that since multiplication between two column or two row vectors is not allowed, to obtain the \ref{scalar product} of two vectors of the same length, you must multiply a line vector by a column vector, if necessary by transposing one of the vectors (using {\tt \~{}} or {\tt trans$(\,)$}, see section 8). The library syntax is $\teb{gmul}(x,y)$ for $x*y$. \subsec{$/$} $x/y$ is the \ref{quotient} of $x$ and $y$. In addition to the impossibilities for multiplication, note that if the divisor is a matrix, it must be an invertible square matrix, and in that case the result is $x*y^{-1}$. Furthermore note that the result is as exact as possible: in particular, division of two integers always gives a rational number (which may be an integer if the quotient is exact) and {\sl not\/} the Euclidean quotient (see $x\backslash y$ for that), and similarly the quotient of two polynomials is a rational function in general. To obtain the approximate real value of the quotient of two integers, add $0.$ to the result; to obtain the approximate $p$-adic value of the quotient of two integers, add $O(p^k)$ to the result; finally, to obtain the \ref{taylor series} expansion of the quotient of two polynomials, add $O(X\hat{\ }k)$ to the result or use the {\tt taylor} function (see section 7). The library syntax is $\teb{gdiv}(x,y)$ for $x/y$. \subsec{$\backslash$} $x\backslash y$ is the \ref{euclidean quotient} of $x$ and $y$. The types must be either both integer or both polynomials. The result is the Euclidean quotient. In the case of integer division, the quotient is such that the corresponding remainder is nonnegative. The library syntax is $\teb{gdivent}(x,y)$ for $x\backslash y$. \subsec{$\%$} $x\%y$ is the \ref{euclidean remainder} of $x$ and $y$. The modulus $y$ must be of type integer or polynomial. The result is the remainder, always nonnegative in the case of integers. Allowed dividend types are scalar exact types when the modulus is an integer, and polynomials, polymods and rational functions when the modulus is a polynomial. The library syntax is $\teb{gmod}(x,y)$ for $x\%y$. \subsec{\ref{divres}}$(x,y)$ creates a vector with two components, the first being the Euclidean quotient, the second the Euclidean remainder, of the division of $x$ by $y$. This avoids the need to do two divisions if one needs both the quotient and the remainder. The arguments must be both integers or both polynomials, and in the case of integers the remainder is of the sign of the dividend. The library syntax is $\teb{gdiventres}(x,y)$. \subsec{$\hat{}$} $x\hat{\ }y$ is \ref{powering}. If the exponent is an integer, then exact operations are performed using binary powering techniques. In particular, in this case the first argument cannot be a vector or matrix unless it is a square matrix (and moreover invertible if the exponent is negative). If the exponent is not of type integer, this is treated as a transcendental function (see section 3), and in particular has the effect of componentwise powering on vector or matrices. The library syntax is $\teb{gpui}(x,y,prec)$ for $x\hat{\ }y$ where the precision parameter prec must be given only if $y$ is not integral but $x$ is an exact (real or complex) type. In addition, there are two shift functions (i.e. multiplication and division by powers of 2) which are faster than the general multiplication or division routines: \subsecref{shift}$(x,n)$: shift $x$ componentwise left by n bits if $n\ge0$ and right by $-n$ bits if $n<0$. A left shift by $n$ corresponds to multiplication by $2^n$, and a right shift by $-n$ corresponds to Euclidean division of $x$ by $2^{-n}$. The library syntax is $\teb{gshift}(x,n)$ where $n$ is a C-integer. \subsecref{shiftmul}$(x,n)$: multiply $x$ by $2^n$. The difference with {\tt shift} is that when $n<0$, the ordinary division takes place, hence for example if $x$ is an integer the result may be a fraction, while for {\tt shift} Euclidean division takes place when $n<0$ hence if $x$ is an integer the result is still an integer. The library syntax is $\teb{gmul2n}(x,n)$ where $n$ is a C-integer. \subsec{comparison and \ref{boolean operators}}. The six standard \ref{comparison operators} $<=$, $<$, $>=$, $>$, $==$, $!=$ are available in GP, and in library mode under the names {\bf \ref{gle}, \ref{glt}, \ref{gge}, \ref{ggt}, \ref{geq}, \ref{gne}} respectively. The library syntax is ${\bf co}(x,y)$, where co is the comparison operator. The result is 1 if the comparison is true, 0 if it is false. The standard boolean functions $|\,|$ (\ref{inclusive or}) and $\&\&$ (\ref{and}) \sref{or}are also available, and the library syntax is $\teb{gor}(x,y)$ and $\teb{gand}(x,y)$ respectively. Note that to avoid confusion with the factorial function, there is no $!$ (\ref{not}) operator, but this can easily be circumvented. In library mode, it is in fact usually preferable to use the two basic functions which are $\teb{gcmp}(x,y)$ which gives the sign (1, 0, or -1) of $x-y$, where $x$ and $y$ must be in $\Bbb R$, and $\teb{gegal}(x,y)$ which can be applied to any two PARI objects $x$ and $y$ and gives 1 (i.e. true) if they are equal (but not necessarily identical), 0 (i.e. false) otherwise. Particular cases of gegal which should be used are $\teb{gcmp0}(x)$ ($x=0$ ?), $\teb{gcmp1}(x)$ ($x=1$ ?), and \sref{gcmp\string\_1} {\bf gcmp\_1} $(x)$ ($x=-1$ ?). Note that $\teb{gcmp0}(x)$ tests whether $x$ is equal to zero, even if $x$ is not an exact object. To test whether $x$ is an exact object which is equal to zero, one must use $\teb{isexactzero}$. \smallskip GP accepts the following synonyms for some of the above functions: since there is no bitwise {\tt and} or bitwise {\tt or}, $|$ and $\&$ are accepted as\sref{bitwise and} \sref{bitwise or} synonyms of $|\,|$ and $\&\&$ respectively. Also, $<>$ is accepted as a synonym for $!=$. On the other hand, $=$ is definitely {\sl not} a synonym for $==$ since it is the assignment statement. \subsec{lex}$(x,y)$: gives the result of a lexicographic comparison between $x$ and $y$. This is to be interpreted in quite a wide sense. For example, the vector $[1,3]$ will be considered smaller than the longer vector $[1,3,-1]$ (but of course larger than $[1,2,5]$), i.e. {\tt lex([1,3],[1,3,5])} will give -1 as a result. The library syntax is $\teb{lexcmp}(x,y)$. \subsec{sign}$(x)$: \ref{sign} of $x$, which must be of type integer, real or fraction. The result (0, 1 or -1) is a C-integer. The library syntax is $\teb{gsigne}(x)$. \subsec{\ref{max}}$(x,y)$ and {\bf \ref{min}}$(x,y)$ create the maximum and minimum of $x$ and $y$ when they can be compared. The library syntax is $\teb{gmax}(x,y)$ and $\teb{gmin}(x,y)$. \subsectitle{Important remark.} In all the above library syntaxes, we have given only the basic names of the functions. For example ${\tt gadd}(x,y )$ assumes that $x$ and $y$ are PARI objects (the GEN type) and {\sl creates} the result $x+y$ on the PARI stack. From most of these basic names, the names and effects of other functions can be obtained in the following way. We give the example for gadd, but the same is true for all the other functions above, and a few more that we have not given: $\teb{gaddgs}(x,y)$: here $x$ is a GEN, $y$ is an ordinary 32-bit integer. $\teb{gaddsg}(x,y)$: here $x$ is an ordinary 32-bit integer, $y$ is a GEN. $\teb{gaddz}(x,y,z),\ \teb{gaddgsz}(x,y,z),\ \teb{gaddsgz}(x,y,z)$: here $z$ is a preexisting GEN and the result of the corresponding operation is put in $z$. The size of the PARI stack does not change. As simplification to programming, for many functions beginning with a {\bf g}, such as gadd, one can replace the {\bf g} by an {\bf l} to obtain a {\bf long} result instead of a GEN (i.e. pointer to long) result. For instance $\teb{ladd}(x,y)$ is identical with $({\tt (long)gadd}(x,y))$. These macros are written in the files listed in {\tt \ref{gencom.h}}. \section{Conversions and similar elementary functions or commands} Many of the conversion functions are rounding or truncating operations. In this case, if the argument is a rational function, the result is the Euclidean quotient of the numerator by the denominator, and if the argument is a vector or a matrix, the operation is done componentwise. This will not be restated for every function. \subsecref{allocatemem}$(x)$: this is a very special operation which allows the user to change the stack size {\it after} initalization. $x$ must be a non-negative integer. If $x>2$, a new stack of size $16*\lceil x/16\rceil$ bytes will be allocated, all the Pari data on the old stack will be moved to the new one, and the old stack will be freed and discarded. If $x=0$, $1$ or $2$, the size of the new stack will be double that of the old one. Finally, in case $x=0$, after doubling the stack, a warning message will be printed. Although it is a function, this must be the {\it only} instruction in a GP line. The technical reason is that this program terminates by a longjmp and not by a return. The library syntax is $\teb{allocatemoremem}(x)$, where $x$ is an unsigned long, and the return type is void. GP uses a variant which ends by a longjmp. \subsecref{binary}$(x)$: outputs the vector of the binary digits of $|x|$. Here $x$ can be an integer, a real number (in which case the result has two components, one for the integer part, one for the fractional part) or a vector/matrix. The library syntax is $\teb{binaire}(x)$. \subsecref{bittest}$(x,n)$: outputs the $n^{\text{th}}$ bit of $|x|$ starting from the right (i.e. the coefficient of $2^n$ in the binary expansion of $x$. The result is 0 or 1. The library syntax is $\teb{bittest}(x,n)$ where $n$ as well as the result are C-integers. \subsecref{bytesize}$(x)$: outputs the total number of bytes occupied by the tree representing the Pari object $x$. The library syntax is $\teb{taille2}(x)$ which returns a C {\tt long}. The function {\tt taille} returns the number of {\it words} instead. \subsec{\ref{ceil}}$(x)$: ceiling of $x$. When $x$ is in $\Bbb R$, the result is the smallest integer greater than or equal to $x$. The library syntax is $\teb{gceil}(x)$. \subsecref{centerlift}$(x)$: lifts an element $x=a \bmod n$ of $\Bbb Z/n\Bbb Z$ to $a$ in $\Bbb Z$, and similarly lifts a polymod to a polynomial. This is the same as {\tt lift} except that in the particular case of elements of $\Bbb Z/n\Bbb Z$, the lift $y$ is such that $-n/20$. In any case, it returns the value of the default precision before the change. Apart from the fact that it returns a value, this is identical to the $\backslash$precision=$n$ command, with the difference that it can be used inside any GP expression or program. The library syntax is $\teb{setprecr}(n)$, where $n$ is a C-integer, as is the returned value. \subsecref{setrand}$(n)$: reseeds the random number generator to the value $n$. The initial seed (in Unix systems at least) is $n=1$. The library syntax is $\teb{setrand}(n)$ where $n$ is a C-integer. The value returned is $n$ once again, but as a GEN. \subsecref{setserieslength}$(n)$: sets the current default series length equal to $n$ if $n>0$. In any case, it returns the value of the default length before the change. Apart from the fact that it returns a value, this is identical to the $\backslash$serieslength=$n$ command, with the difference that it can be used inside any GP expression or program. The library syntax is $\teb{setserieslength}(n)$, where $n$ is a C-integer, as is the returned value. \subsecref{settype}$(x,t)$: makes a copy of $x$ and sets its type equal to type number $t$. This function must be used with extreme caution, otherwise disasters may occur, but one instance where it is extremely useful is {\tt settyp(x,14)} when $x$ is a rational function (type 13). In this case, the created object, as well as the objects created from it, will not be reduced automatically, making the operations much faster. In fact this function is the {\it only} way to create reducible rationals (type 5) or rational functions (type 14) in GP. The library syntax is $\teb{gsettype}(x,t)$, where $t$ is a long, but need not be used since the internal function {\tt settyp} is available. Note that {\tt settyp} does {\it not} create a copy of $x$, while {\tt gsettype} does. \subsecref{simplify}$(x)$: this function tries to simplify the object $x$ as much as it can. The simplifications do not concern rational functions (which Pari automatically tries to simplify), but type changes. Specifically, a complex or quadratic number whose imaginary part is exactly equal to 0 (i.e. not a real zero) is converted to its real part, and a polynomial of degree zero is converted to its constant term. For all types, this of course occurs recursively. This function is useful in any case, but in particular before the use of arithmetic functions which expect integer arguments, and not for example a complex number of 0 imaginary part an integer real part (which is however printed as an integer). The library syntax is $\teb{simplify}(x)$. \subsecref{size}$(x)$: gives the maximal number of decimal digits minus one of the components of $x$. The library syntax is $\teb{size}(x)$, and the result is a C-integer. \subsecref{trunc}$(x)$: truncation of $x$. When $x$ is in $\Bbb R$, this means that the part after the decimal point is chopped away. If the result is not significant because the exponent is too large compared to the precision, an error occurs. Use {\tt cvtoi} (see above) to suppress this error handling. Note a very special use of {\tt trunc}: when applied to a power series, it transforms it into a polynomial or a rational function with denominator a power of $X$, by chopping away the $O(X^k)$. Similarly, when applied to a $p$-adic number, it transforms it into an integer or a rational number by chopping away the $O(p^k)$. The library syntax is $\teb{gtrunc}(x)$. \subsecref{type}$(x)$: internal type number (from 1 to 19) of the pari object $x$. This is useful only under GP. See also the function {\tt settype}. The library syntax is $\teb{gtype}(x)$, but need not be used since the internal function {\tt typ} is available. Note that {\tt gtype} gives a GEN while {\tt typ} gives a C-integer. \subsecref{valuation}$(x,p)$: Computes the highest exponent of $p$ dividing $x$. If $p$ is of type integer, $x$ must be an integer, an integermod whose modulus is divisible by $p$, a fraction, a $q$-adic number with $q=p$, or a polynomial or power series in which case the valuation is the minimum of the valuation of the coefficients. If $p$ is of type polynomial, $x$ must be of type polynomial or rational function, and also a power series if $x$ is a monomial. If $x=0$, an error is issued except in case of $p$-adic numbers and power series, in which case the result is the exponent of the zero. Finally, the valuation of a vector, complex or quadratic number is the minimum of the component valuations. Any other type combinations gives an error. The library syntax is $\teb{ggval}(x)$. \subsecref{vec}$(x)$: transform the object $x$ into a vector. The vector will be with one component only, except when $x$ is a vector/matrix or a quadratic form (in which case the resulting vector is simply the initial object considered as a row vector), but more importantly when $x$ is a polynomial or a power series. In the case of a polynomial, the coefficients of the vector starts with the leading coefficient of the polynomial, while for power series only the significant coefficients are taken into account, but this time by increasing order of degree. The library syntax is $\teb{gtovec}(x)$. \subsecref{vecmax}$(x)$: if $x$ is a vector or a matrix, returns the maximum of the elements of $x$, otherwise returns a copy of $x$. Returns zero if $x$ is empty (as it should). The library syntax is $\teb{vecmax}(x)$. \subsecref{vecmin}$(x)$: if $x$ is a vector or a matrix, returns the minimum of the elements of $x$, otherwise returns a copy of $x$. Gives an error if $x$ is empty. The library syntax is $\teb{vecmin}(x)$. \section{Transcendental functions.} As a general rule, which of course in some cases may have exceptions, transcendental functions operate in the following way: \quad If the argument is either an integer, a real, a rational, a complex or a quadratic number, it is, if necessary, first converted to a real (or complex) number using the current \ref{precision} held in the variable {\bf prec}. Under GP this is transparent to the user, but when programming in library mode, care must be taken to supply the parameter {\tt prec} as the last argument of the function if the first argument is an exact object (see 1.2.5.), otherwise disaster will occur. Then, the function is computed. Note that even if the argument is real, the result may be complex (e.g. $\text{acos}(2.0)$ or $\text{acosh}(0.0 )$). Note also that the principal branch is always chosen. \quad If the argument is an integermod or a $p$-adic, at present only a few functions like {\tt sqrt} (square root), {\tt sqr} (square), {\tt log}, {\tt exp}, powering, {\tt teich} (Teichm\"uller character) and {\tt agm} (arithmetic-geometric mean) are implemented. Note that in the case of a $2$-adic number, ${\tt sqr}(x)$ is not identical to $x*x$: for example if $x = 1+O(2^5)$ then $x*x = 1+O(2^5)$ while ${\tt sqr}(x) = 1+O(2^6)$. (Remark: note that if we wanted to be strictly consistent with the PARI philosophy, we should have $x*y= (4 \mod 8)$ when both $x$ and $y$ are congruent to $2$ modulo $4$, or ${\tt sqr}(x)=(4\mod 32)$ when $x$ is congruent to $2$ modulo $4$. However, since an integermod is an exact object, PARI assumes that the modulus must not change, and the result is hence $0 \mod 4$ in both cases. On the other hand, $p$-adics are not exact objects, hence are treated differently.) \quad If the argument is a polynomial, power series or rational function, it is, if necessary, first converted to a power series using the current precision held in the variable {\bf \ref{precdl}}. Under GP this again is transparent to the user. When programming in library mode, however, the global variable {\tt precdl} must be set before calling the function if the argument has an exact type (i.e. not a power series). Here {\tt precdl} is not an argument of the function, but a global variable. Then the Taylor series expansion of the function around $X=0$ (where $X$ is the main variable) is computed to a number of terms depending on the number of terms of the argument and the function being computed. \quad If the argument is a vector or a matrix, the result is componentwise evaluation of the function. In particular, transcendental functions on square matrices, which are not implemented in the present version \vers{} (see Appendix C however), will have a slightly different name if they are implemented some day. \subsec{$\hat{}$} $x\hat{\ }y$: if $y$ is not of type integer, this has the same effect as $\exp(y*\ln(x))$. It can be applied to $p$-adic numbers as well as to the more usual types.\sref{powering} The library syntax is $\teb{gpui}(x,y,prec)$. \subsecref{abs}$(x)$: absolute value of $x$ (modulus if $x$ is complex). Polynomials, power series and rational functions are not allowed. The library syntax is $\teb{gabs}(x,prec)$ where the second argument $prec$ is necessary only in the complex or imaginary quadratic case. \subsecref{acos}$(x)$: principal branch of $\text{cos}^{-1}(x)$, i.e. such that $\text{Re(acos}(x))\in [0,\pi]$. If $x\in \Bbb R$ and $|x|>1$ then $\text{acos}(x)$ is complex. The library syntax is $\teb{gacos}(x,prec)$. \subsecref{acosh}$(x)$: principal branch of $\text{cosh}^{-1}(x)$, i.e. such that $\text{Im(acosh}(x))\in [0,\pi]$. If $x\in \Bbb R$ and $x<1$ then $\text{acosh}(x)$ is complex. The library syntax is $\teb{gach}(x,prec)$. \subsecref{agm}$(x,y)$: arithmetic-geometric mean of $x$ and $y$. In the case of complex or negative numbers, the principal square root is always chosen. $p$-adic or power series arguments are also allowed. Note that a $p$-adic agm exists only if $x/y$ is congruent to 1 modulo $p$ (modulo 16 for $p=2$). $x$ and $y$ cannot both be vectors or matrices. The library syntax is $\teb{agm}(x,y,prec)$. \subsecref{arg}$(x)$: argument of the complex number $x$, such that $-\pi<\text{arg}(x)\le\pi$. The library syntax is $\teb{garg}(x,prec)$. \subsecref{asin}$(x)$: principal branch of $\text{sin}^{-1}(x)$, i.e. such that $\text{Re(asin}(x))\in [-\pi/2,\pi/2]$. If $x\in \Bbb R$ and $|x|>1$ then $\text{asin}(x)$ is complex. The library syntax is $\teb{gasin}(x,prec)$. \subsecref{asinh}$(x)$: principal branch of $\text{sinh}^{-1}(x)$, i.e. such that $\text{Im(asinh)}(x)\in [-\pi/2,\pi/2]$. The library syntax is $\teb{gash}(x,prec)$. \subsecref{atan}$(x)$: principal branch of $\text{tan}^{-1}(x)$, i.e. such that $\text{Re(atan}(x))\in ]-\pi/2,\pi/2[$. The library syntax is $\teb{gatan}(x,prec)$. \subsecref{atanh}$(x)$: principal branch of $\text{tanh}^{-1}(x)$. i.e. such that $\text{Im(atanh}(x))\in ]-\pi/2,\pi/2]$. If $x\in \Bbb R$ and $|x|>1$ then $\text{atanh}(x)$ is complex. The library syntax is $\teb{gath}(x,prec)$. \subsecref{bernreal}$(x)$: Bernoulli number $B_x$, where $B_0=1$, $B_1=-1/2$, $B_2=1/6$,\dots, expressed as a real number with the current precision. The library syntax is $\teb{bernreal}(x,prec)$. \subsecref{bernvec}$(x)$: creates a vector containing, as rational numbers, the Bernoulli numbers $B_0$, $B_2$,\dots, $B_{2x}$. These Bernoulli numbers can then be used as follows. Assume that this vector has been put into a variable, say b. Then we define under GP: {\tt bern(x)=if(x==1,-1/2,if((x<0)||(x\%2),0,b[x/2+1]))} and then {\tt bern(k)} gives the Bernoulli number of index $k$ as a rational number, exactly as {\tt bernreal(k)} gives it as a real number. The library syntax is $\teb{bernvec}(x)$. \subsecref{cos}$(x)$: cosine of $x$. The library syntax is $\teb{gcos}(x,prec)$. \subsecref{cosh}$(x)$: hyperbolic cosine of $x$. The library syntax is $\teb{gch}(x,prec)$. \subsecref{dilog}$(x)$: principal branch of the dilogarithm of $x$, i.e. analytic continuation of the power series $\log_2(x)=\sum_{n\ge1}x^n/n^2$. The library syntax is $\teb{dilog}(x,prec)$. \subsecref{eint1}$(x)$: exponential integral $\int_x^\infty \dfrac{e^{-t}}{t}\,dt$. The library syntax is $\teb{eint1}(x,prec)$. \subsecref{erfc}$(x)$: complementary error function $(2/\sqrt\pi)\int_x^\infty e^{-t^2}\,dt$. The library syntax is $\teb{erfc}(x,prec)$. \subsecref{eta}$(x)$: Dedekind's $\eta$ function, without the $q^{1/24}$. The meaning is this. If $x$ is a complex number with positive imaginary part, the result is $\prod_{n=1}^\infty(1-q^n)$, where $q=e^{2i\pi x}$. If $x$ is a power series (or can be converted to a power series) with positive valuation, the result is $\prod_{n=1}^\infty(1-x^n)$. The library syntax is $\teb{eta}(x,prec)$. \subsecref{euler}: Euler's constant $0.57721\cdots$. Note that {\tt euler} is one of the few special reserved names which cannot be used for variables. The library syntax is $\teb{mpeuler}(prec)$ where $prec$ {\sl must} be given. Note that this creates $\gamma$ on the PARI stack. If one does not want to create it on that stack but be able to use it later under the global name {\bf \ref{geuler}} (with no parentheses) use instead $\teb{consteuler}(prec )$. \subsecref{exp}$(x)$: exponential of $x$. $p$-adic arguments with positive valuation are accepted. The library syntax is $\teb{gexp}(x,prec)$. \subsecref{gamh}$(x)$: gamma function evaluated at the argument $x+1/2$. When $x$ is an integer, this is much faster than using $\text{gamma}(x + 1/2)$. The library syntax is $\teb{ggamd}(x,prec)$. \subsecref{gamma}$(x)$: gamma function of $x$. In the present version \vers{} the $p$-adic gamma function is not yet implemented. The library syntax is $\teb{ggamma}(x,prec)$. \subsecref{hyperu}$(a,b,x)$: U-confluent hypergeometric function with parameters $a$ and $b$. The library syntax is $\teb{hyperu}(a,b,x,prec)$. \subsecref{incgam}$(x,y)$: incomplete gamma function. The arguments $x$ and $y$ must be positive. The result returned is $\int_y^\infty e^{-t}t^{x-1}\,dt$. The library syntax is $\teb{incgam}(x,y,prec)$. Note: in addition, there exist also the functions {\tt \ref{incgam1} and \ref{incgam2}} which are used for internal purposes. \subsecref{incgam3}$(x,y)$: complementary incomplete gamma function. The arguments $x$ and $y$ must be positive. The result returned is $\int_0^y e^{-t}t^{x-1}\,dt$. when $y$ is not too large. The library syntax is $\teb{incgam3}(x,y,prec)$. \subsecref{incgam4}$(x,y,z)$: incomplete gamma function with given gamma value. This function assumes (of course without checking) that $z=\Gamma(x)$. The arguments $x$ and $y$ must be positive. The result returned is $\int_y^\infty e^{-t}t^{x-1}\,dt$, as in the ordinary {\tt incgam} function, but the computation will be much faster when $y$ is small. The library syntax is $\teb{incgam4}(x,y, z,prec)$. \subsecref{jbesselh}$(n,x)$: $J$-Bessel function of half integral index. More precisely, {\tt jbesselh(n,x)} computes $J_{n+1/2}(x)$ where $n$ must be of type integer, and $x$ is any element of $\Bbb C$. In the present version \vers, this function is not very accurate when $x$ is small. The library syntax is $\teb{jbesselh}(n,x,prec)$. \subsecref{jell}$(x)$: elliptic $j$-invariant. $x$ must be a complex number with positive imaginary part, or convertible into a power series or a $p$-adic number with positive valuation. The library syntax is $\teb{jell}(x,prec)$. \subsecref{kbessel}$(nu,x)$: K-Bessel function of index $nu$ (which can be complex) and argument $x$. Only real and positive arguments $x$ are allowed in the present version \vers. The library syntax is $\teb{kbessel}(nu, x,prec)$. Note: in addition, another implementation of this function which is often faster than kbessel is the function {\bf \ref{kbessel2}}. \subsecref{ln}$(x)$ or {\bf log}$(x)$:\sref{log} principal branch of the natural logarithm of $x$, i.e. such that $\text{Im(ln}(x))\in ]-\pi,\pi]$. The result is complex (with imaginary part equal to $\pi$) if $x\in \Bbb R$ and $x<0$. $p$-adic arguments are also accepted for $x$, with the convention that $\ln(p)=0$. Hence in particular $\exp(\ln(x))/x$ will not in general be equal to 1 but to a $p-1$-th root of unity (or $\pm1$ if $p=2$) times a power of $p$. The library syntax is $\teb{glog}(x,prec)$. \subsecref{lngamma}$(x)$: principal branch of the logarithm of the gamma function of $x$. Can have much larger arguments than {\tt gamma} itself. In the present version \vers{} the $p$-adic lngamma function is not yet implemented. The library syntax is $\teb{glngamma}(x,prec)$. \subsecref{logagm}$(x)$: principal branch of the natural logarithm of $x$, computed using an agm formula suggested by Mestre, when $x$ is real, otherwise identical to {\tt log}. The library syntax is $\teb{glogagm}(x,prec)$. \subsecref{pi}: the constant pi ($3.14159\cdots$). The library syntax is $\teb{mppi}(prec)$ where $prec$ {\sl must} be given. Note that this creates $\pi$ on the PARI stack. If one does not want to create it on that stack but be able to use it later under the global name {\bf \ref{gpi}} (with no parentheses) use instead $\teb{constpi}(prec)$. \subsecref{polylog}$(m,x)$: $m^\text{th}$ polylogarithm of $x$, i.e. analytic continuation of the power series $\log_m(x)=\sum_{n\ge1}x^n/n^m$. The program uses the power series when $|x|^2\le1/2$, and the power series expansion in $log(x)$ otherwise. It is valid in a large domain (at least $|x|<230$), but should not be used too far away from the unit circle since it is then better to use the functional equation linking the value at $x$ to the value at $1/x$, which takes a trivial form for the {\tt polylogd} and {\tt polylogp} functions below. Power series, polynomial, rational and vector/matrix arguments are allowed. The library syntax is $\teb{gpolylog}(m,x,prec)$. \subsecref{polylogd}$(m,x)$: modified $m^\text{th}$ polylogarithm of $x$, called $\tilde D_m(x)$ in Zagier, defined for $|x|\le1$ by $$\Re_m\left(\sum_{k=0}^{m-1}\dfrac{(-\log|x|)^k}{k!}\log_{m-k}(x) +\dfrac{(-\log|x|)^{m-1}}{m!}\log|1-x|\right)$$ and such that $D_m(1/x)=(-1)^{m-1}D_m(x)$, where $\Re_m$ denotes $\Re$ or $\Im$ depending whether $m$ is odd or even. The library syntax is $\teb{polylogd}(m,x,prec)$. \subsecref{polylogdold}$(m,x)$: modified $m^\text{th}$ polylogarithm of $x$, called $D_m(x)$ in Zagier, defined for $|x|\le1$ by $$\Re_m\left(\sum_{k=0}^{m-1}\dfrac{(-\log|x|)^k}{k!}\log_{m-k}(x) -\dfrac{1}{2}\dfrac{(-\log|x|)^m}{m!}\right)$$ and such that $D_m(1/x)=(-1)^{m-1}D_m(x)$, where $\Re_m$ denotes $\Re$ or $\Im$ depending whether $m$ is odd or even. The library syntax is $\teb{polylogdold}(m,x,prec)$. \subsecref{polylogp}$(m,x)$: another modified $m^\text{th}$ polylogarithm of $x$, called $P_m(x)$ in Zagier, defined for $|x|\le1$ by $$\Re_m\left(\sum_{k=0}^{m-1}\dfrac{2^kB_k}{k!}(\log|x|)^k\log_{m-k}(x) -\dfrac{2^{m-1}B_m}{m!}(\log|x|)^m\right)$$ and such that $P_m(1/x)=(-1)^{m-1}P_m(x)$, where $\Re_m$ denotes $\Re$ or $\Im$ depending whether $m$ is odd or even. The library syntax is $\teb{polylogp}(m,x,prec)$. \subsecref{psi}$(x)$: the $\psi$-function of $x$, i.e. the logarithmic derivative $\Gamma'(x)/\Gamma(x)$. The library syntax is $\teb{gpsi}(x,prec)$. \subsecref{sin}$(x)$: sine of $x$. The library syntax is $\teb{gsin}(x,prec)$. \subsecref{sinh}$(x)$: hyperbolic sine of $x$. The library syntax is $\teb{gsh}(x,prec)$. \subsecref{sqr}$(x)$: square of $x$. Not identical to $x*x$ in the case of $2$-adics (see above), and acts componentwise on vectors and matrices. In particular, if $x$ is a square matrix, sqr($x$) is not the square of $x$ (use instead $x*x$ or $x\hat{\ }2$). The library syntax is $\teb{gsqr}(x)$. \subsecref{sqrt}$(x)$: principal branch of the square root of $x$, i.e. such that $\text{Arg(sqrt}(x))\in ]-\pi/2,\pi/2]$, or in other words such that $\text{Re(sqrt}(x))>0$ or $\text{Re(sqrt}(x))=0$ and $\text{Im(sqrt}(x))>=0$. Integermod a prime and $p$-adics are allowed as arguments. If $x\in \Bbb R$ and $x<0$ the result is complex with positive imaginary part. The library syntax is $\teb{gsqrt}(x,prec)$. \subsecref{tan}$(x)$: tangent of $x$. The library syntax is $\teb{gtan}(x,prec)$. \subsecref{tanh}$(x)$: hyperbolic tangent of $x$. The library syntax is $\teb{gth}(x,prec)$. \subsecref{teich}$(x)$: Teichmuller character of the $p$-adic number $x$. The library syntax is $\teb{teich}(x)$. \subsecref{wf}$(x)$: Weber's $f$ function, i.e. such that $j=(f^{24}-16)^3/f^{24}$. The library syntax is $\teb{wf}(x,prec)$. \subsecref{wf2}$(x)$: Weber's $f_2$ function, i.e. such that $j=(f_2^{24}+16)^3/f_2^{24}$. The library syntax is $\teb{wf2}(x,prec)$. \subsecref{zeta}$(s)$: Riemann's zeta function $\zeta(s)=\sum_{n\ge1}n^{-s}$, computed using the Euler-Maclaurin summation formula, except when $s$ is of type integer, in which case it is computed using Bernoulli numbers for $s<=0$ or $s>0$ and even, and using modular forms for $s>0$ and odd. The library syntax is $\teb{gzeta}(s,prec)$. \section{Arithmetic functions.} These functions are by definition functions whose natural domain of definition is either $\Bbb Z$ (or $\Bbb N$), or sometimes polynomials over a base ring. Functions which concern polynomials exclusively will be explained in the next section. The way these functions are used is completely different from transcendental functions: in general only the types integer and polynomial are accepted as arguments. In the present version \vers{} a primitive but useful version of the \ref{ECM} method has been implemented. Also, numbers found to be pseudo-primes after 10 successful trials of the \ref{Rabin-Miller} test are declared primes. \subsecref{bestappr}$(x,k)$: if $x\in\Bbb R$, finds the best rational approximation to $x$ with denominator at most equal to $k$ using continued fractions. If $x$ is a generic type, {\tt bestappr} is used on each coefficient independently. The library syntax is $\teb{bestappr}(x,k)$. \subsecref{bezout}$(x,y)$: finds $u$ and $v$ minimal in a natural sense such that $x*u+y*v=\text{gcd}(x,y)$. The arguments must be both integers or both polynomials, and the result is a row vector with three components $u$, $v$, and $\text{gcd}(x,y)$. The library syntax is either $\teb{vecbezout}(x,y)$ to get the vector, or $\teb{gbezout}(x,y, \& u, \& v)$ which gives as result the address of the created gcd, and puts in $u$ and $v$ the addresses of the corresponding created objects. \subsecref{bigomega}$(x)$: number of prime divisors of $x$ counted with multiplicity. $x$ must be an integer, and the result is a 32-bit C-integer. The library syntax is $\teb{bigomega}(x)$. \subsecref{bin}$(x,y)$: \ref{binomial coefficient} $\binom x y$. Here $y$ must be an integer, but $x$ can be any PARI object. The library syntax is $\teb{binome}(x,y)$, where $y$ must be a C-integer. \subsecref{boundcf}$(x,lmax)$: creates the row vector whose components are the partial quotients of the \ref{continued fraction} expansion of $x$, the number of partial quotients being limited to lmax. If $x$ is a real number, the expansion stops at the last significant partial quotient or after lmax terms, whichever is smallest. $x$ can also be a rational function or a power series. The library syntax is $\teb{gboundcf}(x,lmax)$, where $lmax$ is a C integer. \subsecref{boundfact}$(x,p)$: For integer $x$, finds only the prime factors up to $p$ or to the default bound of the prime table created upon initialization of GP, whichever is lowest (except when $p<=1$ where the effect is identical to {\tt smallfact}. The remaining part is hence not necessarily prime. The library syntax is $\teb{boundfact}(x,p)$. \subsecref{buchimag}$(D,c,c2)$: McCurley's sub-exponential algorithm for computing the class group of an imaginary quadratic field of discriminant $D$. Should be used instead of {\tt classno} for $|D|>10^{25}$ or when the {\sl structure} is wanted. The numbers $c$ and $c2$ are positive real numbers which control the execution time and the stack size. To get maximum speed, set $c2=c$. To get a rigorous result (under GRH) you must take $c2=6$. Reasonable values for $c$ are between $0.1$ and $2$. The result of this function is a vector with 4 components. The first is the class number, the second is a vector giving the structure of the class group as a product of cyclic groups, and the third is a vector giving as binary quadratic forms generators of those cyclic groups. The last component is a measure of the correctness of the result. If it is close to 1, the result is correct (under GRH). If it is close to a larger integer, this shows that the class number is off by a factor equal to this integer, and you must start again with a larger value for $c$ or a different random seed. In this case, a warning message is printed. Note: some installations may have this function disabled. The library syntax is $\teb{buchimag}(D,c,c2)$. \subsecref{buchreal}$(D,n,c,c2)$: Buchmann's sub-exponential algorithm for computing the class group and the regulator of a real quadratic field of discriminant $D$. Should be used instead of {\tt classno} and {\tt regula} for $D>10^{10}$ or when the {\sl structure} is wanted. If the integer $n$ is equal to 0 the function computes the ordinary (or wide) class group and regulator, while if $n$ is non-zero it computes the narrow class group and regulator (this case is not yet implemented in version \vers). The numbers $c$ and $c2$ are positive real numbers which control the execution time and the stack size. To get maximum speed, set $c2=c$. To get a rigorous result (under GRH) you must take $c2=6$. Reasonable values for $c$ are between $0.1$ and $2$. The result of this function is a vector with 5 components. The first is the class number, the second is a vector giving the structure of the class group as a product of cyclic groups, and the third is a vector giving as binary quadratic forms generators of those cyclic groups. The fourth component is the regulator, computed to an accuracy which is the maximum of an internal accuracy determined by the program and the current default (note that once the regulator is known to a small accuracy it is trivial to compute it to very high accuracy. I leave this as an exercise to the reader, or see the tutorial). The last component is a measure of the correctness of the result. If it is close to 1, the results are correct (under GRH). If it is close to a larger integer, this shows that the product of the class number by the regulator is off by a factor equal to this integer, and you must start again with a larger value for $c$ or a different random seed. In this case, a warning message is printed. Note: some installations may have this function disabled. The library syntax is $\teb{buchreal}(D,n,c,c2)$. \subsecref{cf}$(x)$: creates the row vector whose components are the partial quotients of the \ref{continued fraction} expansion of $x$. If $x$ is a real number, the expansion stops at the last significant partial quotient. $x$ can also be a rational function. The library syntax is $\teb{gcf}(x)$. \subsecref{cf2}$(b,x)$: creates the row vector whose components are the partial quotients of the continued fraction expansion of $x$, the numerators being equal to the coefficients of the vector $b$. The length of the result is equal to the length of $b$ unless a partial remainder is encountered which is equal to zero, in which case the expansion stops. In the case of real numbers, the stopping criterion in thus different from that of {\tt cf} since if $b$ is too long, some partial quotients may not be significant. $x$ can also be a rational function or a power series. The library syntax is $\teb{gcf2}(b,x)$. \subsecref{chinese}$(x,y)$: $x$ and $y$ being both integermods or polymods, creates (with the same type) a $z$ in the same residue class as $x$ and in the same residue class as $y$, if it is possible. The library syntax is $\teb{chinois}(x,y)$. \subsecref{classno}$(x)$: class number of the quadratic field of discriminant $x$. In the present version \vers, a simple algorithm is used for $x>0$, so $x$ should not be too large (say $x<10^7$) for the time to be reasonable. On the other hand, for $x<0$ one can reasonably compute classno($x$) for $|x|<10^{25}$, since the method used is Shanks' method which is in $O(|x|^{1/4})$. For larger values of $|D|$, see {\tt buchimag} for $D<0$ and {\tt buchreal} for $D>0$. The library syntax is $\teb{classno}(x)$. There also exists the function {\tt \ref{classno2}}, which computes the class number using the functional equation. However, it is in $O(|x|^{1/2})$. Finally, in library mode only there exists the function {\tt \ref{classno3}} which computes the class number of an imaginary quadratic field by counting reduced forms, a $O(|x|)$ algorithm. See also {\tt hclassno} below. \subsecref{compimag}$(x,y)$ composition of the binary quadratic forms $x$ and $y$. This is of course a special case of {\tt gmul(x,y)}. See also {\tt nucomp} and {\tt nudupl}. The library syntax is $\teb{compimag}(x,y)$. \subsecref{comprealraw}$(x,y)$ composition of the binary quadratic forms $x$ and $y$ with positive discriminant, without reduction of the result. This is useful e.g. to compute a generating element of an ideal. The library syntax is $\teb{comprealraw}(x,y)$. \subsecref{content}$(x)$: computes the gcd of all the coefficients of $x$, when this gcd makes sense. If $x$ is a scalar, this simply gives $x$. If $x$ is a polynomial (and by extension a power series), it gives the usual content of $x$. If $x$ is a rational function, it gives the ratio of the contents of the numerator and the denominator. Finally, if $x$ is a vector or a matrix, it gives the gcd of all the entries. The library syntax is $\teb{content}(x)$. \subsecref{divisors}$(x)$: creates a row vector whose components are the positive divisors of the integer $x$ in increasing order. The library syntax is $\teb{divisors}(x)$. \subsecref{fact}$(x)$ or $x!$: factorial of $x$. The expression $x!$ gives a result which is an integer, while $\text{fact}(x)$ gives a real number. The library syntax is $\teb{mpfact}(x)$ for $x!$ and $\teb{mpfactr}(x,prec)$ for $\text{fact}(x)$. $x$ must be a 32-bit C-integer and not a PARI integer. \subsecref{factfq}$(x,p,a)$: factorization in the field $\Bbb F_q$ defined by the irreducible polynomial $a$ over $\Bbb F_p$ of the polynomial $x$. The coefficients of $x$ must be operation-compatible with $\Bbb Z/p\Bbb Z$. The result is a two column matrix, the first column being the irreducible polynomials dividing $x$, and the second the exponents. It is advised to use for the variable of $a$ (which will be used as variable of a polymod), a name distinct from the other variables used, so that a {\tt lift()} of the result will be legible. The library syntax is $\teb{factmod9}(x,p,a)$. \subsecref{factmod}$(x,p)$: factorization mod $p$ of the polynomial $x$. The coefficients of $x$ must be operation-compatible with $\Bbb Z/p\Bbb Z$. The result is a two column matrix, the first column being the irreducible polynomials dividing $x$, and the second the exponents. If you want only the {\sl degrees} of the irreducible polynomials (for example for computing an $L$-function), use the function {\tt simplefactmod}. The library syntax is $\teb{factmod}(x,p)$. \subsecref{factor}$(x)$: general factorization function. If $x$ is of type integer, rational, polynomial or rational function, the result is a two column matrix, the first column being the irreducibles dividing $x$ (prime numbers or polynomials), and the second the exponents. If $x$ is a vector or a matrix, the factoring is done componentwise (hence the result is a vector or matrix of two column matrices). The polynomials or rational functions to be factored must have coefficients either integers or integermods. Note that PARI does {\sl not} yet know how to factor multivariate polynomials. The library syntax is $\teb{factor}(x)$. See also {\tt \ref{factpol}} {\tt \ref{factpol2}} and {\tt \ref{factornf}}. \subsecref{fibo}$(x)$: $x^{\text{th}}$ Fibonacci number. The library syntax is $\teb{fibo}(x)$. $x$ must be a 32-bit C-integer and not a PARI integer. \subsecref{gcd}$(x,y)$: creates the greatest common divisor of $x$ and $y$. $x$ and $y$ can be of quite general types; for instance both rational numbers. Vector/matrix types are also accepted. Note that for these types, {\tt gcd} is not commutative. The library syntax is $\teb{ggcd}(x,y)$. \subsecref{hclassno}$(x)$: \ref{Hurwitz class number} of $x$, where $x$ is nonnegative and congruent to 0 or 3 modulo 4. See also {\tt classno} above. The library syntax is $\teb{hclassno}(x)$. \subsecref{hilb}$(x,y,p)$ or {\bf hilbp}$(x,y)$: \ref{Hilbert symbol} of $x$ and $y$. If $x$ and $y$ are of type integer or fraction, the function {\tt hilb} must be used with an explicit third parameter $p$, $p=0$ meaning the place at infinity. Otherwise, $p$ need not be given, and $x$ and $y$ can be of compatible types integer, fraction, real, integermod or $p$-adic. The library syntax is in both cases $\teb{hil}(x,y,p)$ or $\teb{hil}(x,y)$. \subsecref{isfund}$(x)$: true (1) if $x$ is equal to 1 or to the discriminant of a quadratic field, false (0) otherwise. The library syntax is $\teb{isfundamental}(x)$. \subsecref{isprime}$(x)$: true (1) if $x$ is a strong pseudo-prime for 10 randomly chosen bases, false (0) otherwise. The library syntax is $\teb{isprime}(x)$. \subsecref{ispsp}$(x)$: true (1) if $x$ is a strong pseudo-prime for a randomly chosen base, false (0) otherwise. The library syntax is $\teb{ispsp}(x)$. \subsecref{isqrt}$(x)$: integer square root of $x$, which must be of PARI type integer. A negative $x$ is allowed, and the result in that case is {\tt i*isqrt(-x)}. The library syntax is $\teb{racine}(x)$. \subsecref{issqfree}$(x)$: true (1) if $x$ is squarefree, false if not. Here $x$ can be an integer or a polynomial. The library syntax is $\teb{issquarefree}(x)$. \subsecref{issquare}$(x)$: true (1) if $x$ is square, false if not. $x$ can be of any type (for vector/matrix types the function is applied to the components). The library syntax is $\teb{gcarreparfait}(x)$. \subsecref{kro}$(x,y)$: Kronecker \sref{Legendre symbol} (i.e. generalized Legendre) symbol $\left(\dfrac{x}{y}\right)$. $x$ and $y$ must be of type integer and the result ($0$ or $\pm 1$) is a 32-bit C-integer. The library syntax is $\teb{kronecker}(x,y)$. \subsecref{lcm}$(x,y)$: least common multiple of $x$ and $y$, i.e. such that $\text{lcm}(x,y)*\text{gcd}(x,y)=x*y$. The library syntax is $\teb{glcm}(x,y)$. \subsecref{mu}$(x)$: M\"obius $\mu$-function of $x$. $x$ must be of type integer and the result ($0$ or $\pm 1$) is a 32-bit C-integer. The library syntax is $\teb{mu}(x)$. \subsecref{nextprime}$(x)$: finds the smallest prime greater than or equal to $x$. $x$ must be of type integer. The library syntax is $\teb{bigprem}(x)$. \subsecref{nucomp}$(x,y,l)$ composition of the primitive positive definite binary quadratic forms $x$ and $y$ using the NUCOMP and NUDUPL algorithms of Shanks (a la Atkin). $l$ is any positive constant, but for optimal speed, one should take $l=|D|^{1/4}$ where $D$ is the common discriminant of $x$ and $y$. The library syntax is $\teb{nucomp}(x,y,l)$. The auxiliary function $\teb{nudupl}(x,l)$ also exists when $x=y$. \subsecref{numdiv}$(x)$: number of divisors of $x$. $x$ must be of type integer, and the result is a 32-bit C-integer. The library syntax is $\teb{numbdiv}(x)$. \subsecref{nupow}$(x,n)$: $n$-th power of the primitive positive definite binary quadratic form $x$ using the NUCOMP and NUDUPL algorithms (see {\tt nucomp} above). The library syntax is $\teb{nupow}(x,n)$. \subsecref{omega}$(x)$: number of distinct prime divisors of $x$. $x$ must be of type integer, and the result is a 32-bit C-integer. The library syntax is $\teb{omega}(x)$. \subsecref{order}$(x)$: $x$ must be an integer mod $n$, and the result is the order of $x$ in the multiplicative group $(\Bbb Z/n\Bbb Z)^*$. Error if $x$ is not invertible. The library syntax is $\teb{order}(x)$. \subsecref{pf}$(x,p)$: prime binary quadratic form of discriminant $x$ whose first coefficient is the prime number $p$. Error if $x$ is not a quadratic residue mod $p$. In the case where $x>0$, the ``distance'' component of the form is set equal to zero to the current precision. The library syntax is $\teb{primeform}(x,p,prec)$, where the third variable $prec$ is a C-integer, but is necessary only when $x>0$. \subsecref{phi}$(x)$: Euler's $\phi$-function of $x$. $x$ must be of type integer. The library syntax is $\teb{phi}(x)$. \subsecref{pnqn}$(x)$: When $x$ is a vector or a one row matrix, $x$ is considered as the list of partial quotients $[a_0,a_1,\dots,a_n]$ of a rational number, and the result is the 2 by 2 matrix $[p_n,p_{n-1};q_n,q_{n-1}]$ in the standard notation of continued fractions, so $p_n/q_n=a_0+1/(a_1+\dots+1/a_n)\dots)$. If $x$ is a matrix with two rows $[b_0,b_1,\dots,b_n]$ and $[a_0,a_1,\dots,a_n]$, this is then considered as a generalized continued fraction and we have similarly $p_n/q_n=1/b_0(a_0+b_1/(a_1+\dots+b_n/a_n)\dots)$. Note that in this case one usually has $b_0=1$. The library syntax is $\teb{pnqn}(x)$. \subsecref{powrealraw}$(x,n)$ $n$-th power of the binary quadratic form $x$ of positive discriminant, computed without doing any reduction (i.e. using {\tt comprealraw} above). Here $n$ must be non-negative and $n<2^{31}$. The library syntax is $\teb{powrealraw}(x,n)$ where $n$ must be a C-integer. \subsecref{prime}$(x)$: the $x^{\text{th}}$ prime number. The library syntax is $\teb{prime}(x)$. $x$ must be a 32-bit C-integer. \subsecref{primes}$(x)$: creates a row vector whose components are the first $x$ prime numbers. The library syntax is $\teb{primes}(x)$. $x$ must be a 32-bit C-integer. \subsecref{primroot}$(x)$: returns a primitive root of $x$, where $x$ is a prime power. The library syntax is $\teb{gener}(x)$. \subsecref{qfi}$(a,b,c)$: creates the binary quadratic form $ax^2+bxy+cy^2$ with $b^2-4ac<0$. The library syntax is $\teb{qfi}(a,b,c)$. \sref{Binary quadratic form} \subsecref{qfr}$(a,b,c,d)$: creates the binary quadratic form $ax^2+bxy+cy^2$ with $b^2-4ac>0$ and distance function $d$. The library syntax is $\teb{qfr}(a,b,c,d)$. \subsecref{quaddisc}$(x)$: discriminant of the quadratic field $\Bbb Q(\sqrt(x))$, where $x\in\Bbb Q$. Up to trivial 2-factors, this function can also be used to compute the squarefree part of $x$. The library syntax is $\teb{quaddisc}(x)$. \subsecref{redimag}$(x)$: reduce the binary quadratic form $x$ with negative discriminant. The library syntax is $\teb{redimag}(x)$. \subsecref{redreal}$(x)$: reduce the binary quadratic form $x$ with positive discriminant. The library syntax is $\teb{redreal}(x)$. \subsecref{redrealnod}$(x,sq)$: reduce the binary quadratic form $x$ with positive discriminant $D$ without computing the distance function, where $sq$ is the integer square root of $D$ (no checking is done of this fact). The library syntax is $\teb{redrealnod}(x,sq)$. \subsecref{regula}$(x)$: regulator of the quadratic field of positive discriminant $x$. Error if $x$ is not a discriminant (fundamental or not) or if $x$ is a square. See also {\tt buchreal} if $x$ is large. The library syntax is $\teb{regula}(x,prec)$. \subsecref{rhoreal}$(x)$: perform one reduction step on the binary quadratic form $x$ with positive discriminant. The library syntax is $\teb{rhoreal}(x)$. \subsecref{rhorealnod}$(x,sq)$: perform one reduction step on the binary quadratic form $x$ with positive discriminant $D$ without computing the distance function, where $sq$ is the integer square root of $D$ (no checking is done of this fact). The library syntax is $\teb{rhorealnod}(x,sq)$. \subsecref{sigma}$(x)$: sum of the positive divisors of $x$. $x$ must be of type integer. The library syntax is $\teb{sumdiv}(x)$. \subsecref{sigmak}$(k,x)$: sum of the $k^{\text{th}}$ powers of the positive divisors of $x$. $x$ must be of type integer, but (in library mode) $k$ must be a 32-bit C-integer. The library syntax is $\teb{sumdivk}(k,x)$. \subsecref{simplefactmod}$(x,p)$: factorization mod $p$ of the polynomial $x$. The coefficients of $x$ must be operation-compatible with $\Bbb Z/p\Bbb Z$. The result is a two column matrix, the first column being the degrees of the irreducible polynomials dividing $x$, and the second the exponents. If you want the irreducible polynomials themselves, use the function {\tt factmod}. The library syntax is $\teb{simplefactmod}(x,p)$. \subsecref{smallfact}$(x)$: For integer $x$, finds only the prime factors up to the default table created when GP was started (usually $500000$). The remaining part is hence not necessarily prime. This never takes more than a few seconds, and is particularly advantageous with respect to {\tt factor} when one needs only the small prime divisors and not the complete factorization. The library syntax is $\teb{smallfact}(x)$. \subsecref{unit}$(x)$: \ref{fundamental unit} of the real quadratic field $\Bbb Q(\sqrt x)$ where $x$ is the positive discriminant of the field. If $x$ is not a fundamental discriminant, this probably gives the fundamental unit of the corresponding order. $x$ must be of type integer, and the result is a quadratic number. The library syntax is $\teb{fundunit}(x)$. \section{Functions related to elliptic curves.} We have implemented a number of functions which are useful for number theorists working on elliptic curves. We always use Tate's notations. The functions assume that the curve is given by a general Weierstrass model $$y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6,$$ where a priori the $a_i$ can be of any scalar type. This curve can be considered as a five component vector {\tt e=[a1,a2,a3,a4,a6]}, but for most functions it is useful to have at one's disposal more information. This is given either by the function {\tt initell} (see below), which gives a 19 component vector (which we will call a long vector in this section), or by the faster function {\tt smallinitell} which gives a 13 component vector (which we will call a medium vector), all these vectors starting in the same way. Consequently, in functions which do not use the extra information given by {\tt initell}, the curve can be given either as a five component vector, or by one of the longer vectors computed by {\tt initell} or {\tt smallinitell}. Other functions, in particular those relative to height computations (see {\tt hell} below) require also that the curve be in minimal Weierstrass form. This is achieved by the function {\tt globalred} below. Points on elliptic curves are represented as two component vectors {\tt [x,y]}, except for the point at infinity, i.e. the identity element of the group law, represented by the one-component vector {\tt [0]}. \subsecref{addell}$(e,z1,z2)$: sum of the points $z1$ and $z2$ on the elliptic curve corresponding to the vector $e$. The library syntax is $\teb{addell}(e,z1,z2)$. \subsecref{akell}$(e,n)$: compute the coefficient $a_n$ of the $L$-function of the elliptic curve $e$, i.e. in principle coefficients of a newform of weight 2 assuming Taniyama-Weil. $e$ must be a medium or long vector of the type given by {\tt smallinitell} or {\tt initell}. For this function to work for every $n$ and not just those prime to the conductor, $e$ must be a minimal Weierstrass equation. If this is not the case, use the function {\tt globalred} first before using {\tt akell}. The library syntax is $\teb{akell}(e,n)$. \subsecref{anell}$(e,n)$: compute the vector of the first $n$ $a_k$ corresponding to the elliptic curve $e$, i.e. in principle coefficients of a newform of weight 2 assuming Taniyama-Weil. $e$ must be a medium or long vector of the type given by {\tt smallinitell} or {\tt initell}. For this function to work for every $n$ and not just those prime to the conductor, $e$ must be a minimal Weierstrass equation. If this is not the case, use the function {\tt globalred} first before using {\tt anell}. The library syntax is $\teb{anell}(e,n)$, where $n$ is a C integer. \subsecref{apell}$(e,p)$: compute the $a_p$ corresponding to the elliptic curve $e$ and the prime number $p$, using the baby-step giant-step method and a trick due to Mestre. No checking is done that $p$ is indeed prime. The number of points of $e$ over $\Bbb F_p$ is $p+1-a_p$. $e$ must be a medium or long vector of the type given by {\tt smallinitell} or {\tt initell}. The library syntax is $\teb{apell}(e,p)$. \subsecref{apell2}$(e,p)$: compute the $a_p$ corresponding to the elliptic curve $e$ and the prime number $p$ as a sum of Legendre symbols. This is slower than {\tt apell} as soon as $p$ is greater than 100, say. $e$ must be a medium or long vector of the type given by {\tt smallinitell} or {\tt initell}. The library syntax is $\teb{apell2}(e,p)$. \subsecref{bilhell}$(e,z1,z2)$: If $z1$ and $z2$ are points on the elliptic curve $e$, this function computes the value of the canonical bilinear form on $z1$, $z2$, i.e. {\tt hell(e,z1$+$z2)-hell(e,z1)-hell(e,z2)}, where $+$ denotes of course addition on $e$. In addition, $z1$ or $z2$ (but not both) can be vectors or matrices. The library syntax is $\teb{bilhell}(e,z1,z2,prec)$. \subsecref{chell}$(e,v)$: change the data for the elliptic curve $e$ by changing the coordinates using the vector {\tt v=[u,r,s,t]}, i.e. if $x'$ and $y'$ are the new coordinates, then $x=u^2x'+r$, $y=u^3y'+su^2x'+t$. The vector $e$ must be a medium or long vector of the type given by {\tt smallinitell} or {\tt initell}. The library syntax is $\teb{coordch}(e,v)$. \subsecref{chptell}$(x,v)$: change the coordinates of the point or vector of points $x$ using the vector {\tt v=[u,r,s,t]}, i.e. if $x'$ and $y'$ are the new coordinates, then $x=u^2x'+r$, $y=u^3y'+su^2x'+t$ (see also {\tt chell} above). The library syntax is $\teb{pointch}(x,v)$. \subsecref{globalred}$(e)$: calculate the arithmetic conductor, the global minimal model of $e$ and the global Tamagawa number $c$. Here $e$ is an elliptic curve given by a medium or long vector of the type given by {\tt smallinitell} or {\tt initell}, and is supposed to have all its coefficients $a_i$ in $\Bbb Q$. The result is a 3 component vector $[N,v,c]$. $N$ is the arithmetic conductor of the curve, $v$ is itself a vector $[u,r,s,t]$ with rational components. It gives a coordinate change for $e$ over $\Bbb Q$ such that the resulting model has integral coefficients, is everywhere minimal, $a_1$ is 0 or 1, $a_2$ is 0, 1 or $-1$ and $a_3$ is 0 or 1. Such a model is unique, and the vector $v$ is unique if we specify that $u$ is positive. To get the new model, simply type {\tt chell(e,v)}. Finally $c$ is the product of the local Tamagawa numbers $c_p$, which is a quantity which enters in the Birch and Swinnerton-Dyer conjecture. The library syntax is $\teb{globalreduction}(e)$. \subsecref{hell}$(e,z)$: global \ref{N\'eron-Tate height} of the point $z$ on the elliptic curve $e$. The vector $e$ must be a long vector of the type given by {\tt initell}. This computation is done using sigma and theta-functions and a trick due to J. Silverman. The library syntax is $\teb{ghell}(e,z,prec)$. The archimedean contribution alone is given by the library function $\teb{hell}(e,z,prec)$. \subsecref{hell2}$(e,z)$: same as {\tt hell}, except that the algorithm used is Tate's $4^n$ algorithm, and is much slower. The library syntax is $\teb{ghell2}(e,z,prec)$. \subsecref{initell}$(e)$: compute some fixed data concerning the elliptic curve given by the five component vector $e$, which will be essential for most further computations on the curve. The result is a 19-component vector E (called a long vector in this section), containing the following information: The first 13 components contain $$a_1,a_2,a_3,a_4,a_6,b_2,b_4,b_6,b_8,c_4,c_6,\Delta,j.$$ In particular, the discriminant is $E[12]$, and the $j$-invariant is $E[13]$. For the other six components, their content depends on whether the curve is defined over $\Bbb R$ or not. \smallskip When $e$ is defined over $\Bbb R$, $E[14]$ is a vector with three components containing the roots of the associated Weierstrass equation. If the roots are all real, then they are ordered by decreasing value. If only one is real, it is the first component of $E[14]$. $E[15]$ is the real period of $E$ (integral of $dx/(2y+a_1x+a_3)$ over the connected component of the identity element of the real points of the curve), and $E[16]$ is a complex period. In other words, $\omega_1=E[15]$ and $\omega_2=E[16]$ form a basis of the complex lattice defining $e$, with $\tau=\dfrac{\omega_2}{\omega_1}$ having positive imaginary part. $E[17]$ and $E[18]$ are the corresponding values $\eta_1$ and $\eta_2$ such that $\eta_1\omega_2-\eta_2\omega_1=i\pi$. Finally, $E[19]$ is the volume of the complex lattice defining $e$. \smallskip When $e$ is defined over $\Bbb Q_p$, the $p$-adic valuation of $j$ must be negative. Then $E[14]$ is the vector with a single component equal to the $p$-adic root of the associated Weierstrass equation corresponding to $-1$ under the Tate parametrization. $E[15]$ is equal to the square of the $u$-value, in the notation of Tate. $E[16]$ is the $u$-value itself, if it belongs to $\Bbb Q_p$, otherwise zero. $E[17]$ is the value of Tate's $q$ for the curve $e$. $E[18]$ is the value of Mestre's $w$ (this is technical), and $E[19]$ is arbitrarily set equal to zero. \smallskip For all other base fields or rings, the last six components are arbitrarily set equal to zero. Note: temporarily, an older version of {\tt initell} called {\tt initell2} is installed, but will disappear in the near future. The library syntax is $\teb{initell}(e,prec)$. \subsecref{isoncurve}$(e,z)$: gives 1 (i.e. true) if the point $z$ is on the elliptic curve $e$, 0 otherwise. Here $e$ can be a five-component vector or a long vector. The library syntax is $\teb{oncurve}(e,z)$, and the result is a C-integer. \subsecref{localred}$(e,p)$: calculate the Kodaira type of the local fiber of the elliptic curve $e$ at the prime $p$. $e$ must be given by a medium or long vector of the type given by {\tt smallinitell} or {\tt initell}, and is assumed to have all its coefficients $a_i$ in $\Bbb Z$. The result is a 4 component vector $[f,kod,v,c]$. Here $f$ is the exponent of $p$ in the arithmetic conductor of $e$, $kod$ is the Kodaira type which is coded as follows: 1 means good reduction (type I$_0$), 2, 3 and 4 mean types II, III and IV respectively, $4+\nu$ with $\nu>0$ means type I$_\nu$; finally the opposite values -1, -2, etc. refer to the starred types I$_0^*$, II$^*$, etc. The third component $v$ is itself a vector $[u,r,s,t]$ giving the coordinate changes done during the local reduction. Normally, this has no use if u is 1, that is, if the given equation was already minimal. Finally, the last component $c$ is the local Tamagawa number $c_p$. The library syntax is $\teb{localreduction}(e,p)$. \subsecref{lseriesell}$(e,s,N,A)$: $e$ being a medium or long vector given by {\tt smallinitell} or {\tt initell}, this computes the value of the L-series of $e$ at $s$. It is assumed that $e$ is a minimal model over $\Bbb Z$, $N$ is equal to plus or minus the conductor depending on the sign of the functional equation, that the curve is a Weil curve, and $A$ is a cutoff point for the integral, which must be chosen close to 1 for best speed. The result being independent of $A$, this function can be used to compute the sign of the functional equation, and even $N$ if one wants, although it is always much faster to apply the function {\tt globalred}. Note that in the present version \vers, this function is accessible externally in GP, but in future versions it may only be accessible in library mode since it will be superseded. Note also that if the conductor of the curve is large, say greater than $10^{12}$, this function will take an unreasonable amount of time since it uses a $O(N^{1/2})$ algoorithm. The library syntax is $\teb{lseriesell}(e,s,N,A,prec)$ where $prec$ is a C-integer. \subsecref{mathell}$(e,x)$: $x$ being a vector of points, this function outputs the Gram matrix of $x$ with respect to the N\'eron-Tate height, in other words, the {\tt (i,j)} component of the matrix is equal to {\tt hell(e,x[i]+x[j])-hell(e,x[i])-hell(e,x[j])}, where {\tt x[i]+x[j]} denotes of course the sum of the points on the curve $e$. The rank of this matrix, at least in some approximate sense, gives the rank of the set of points, and if $x$ is a basis of the Mordell-Weil group of $e$, its determinant is equal to the regulator of $e$. The library syntax is $\teb{mathell}(e,x,prec)$. \subsecref{ordell}$(e,x)$: gives a 0, 1 or 2-component vector containing the $y$-coordinates of the points of the curve $e$ having $x$ as $x$-coordinate. The library syntax is $\teb{ordell}(e,x)$. \subsecref{orderell}$(e,z)$: gives the order of the point $z$ on the elliptic curve $e$ if it is a torsion point, zero otherwise. In the present version \vers{}, this is implemented only for elliptic curves defined over $\Bbb Q$. The library syntax is $\teb{orderell}(e,z)$, and the result is a GEN. \subsecref{pointell}$(e,z)$: $e$ being a long vector, computes the coordinates $[x,y]$ on the curve $e$ corresponding to the complex number $z$. Hence this is the inverse function of {\tt zell}. In other words, if the curve is put in Weierstra\ss\ form, $[x,y]$ represent the Weierstra\ss\ $\wp$-function and its derivative. If $z$ is in the lattice defining $e$ over $\Bbb C$, the result is the point at infinity $[0]$. The library syntax is $\teb{pointell}(e,z,prec)$. \subsecref{powell}$(e,n,z)$: computes $n$ times the point $z$ for the group law on the elliptic curve $e$. Here $n$ is in $\Bbb Z$. The library syntax is $\teb{powell}(e,n,z)$. \subsecref{smallinitell}$(e)$: compute some fixed data concerning the elliptic curve given by the five component vector $e$, which may be useful for further computations on the curve. The result is a 13-component vector E (called a medium vector in this section), containing the first 13 components of the vector given by {\tt initell}, in other words the vector $$[a_1,a_2,a_3,a_4,a_6,b_2,b_4,b_6,b_8,c_4,c_6,\Delta,j].$$ In particular, the discriminant is $E[12]$, and the $j$-invariant is $E[13]$. The library syntax is $\teb{smallinitell}(e)$. \subsecref{subell}$(e,z1,z2)$: difference of the points $z1$ and $z2$ on the elliptic curve corresponding to the vector $e$. The library syntax is $\teb{subell}(e,z1,z2)$. \subsecref{taniyama}$(e)$: computes the modular parametrization of the elliptic curve $e$ (where $e$ is given in the format output by {\tt initell} or {\tt smallinitell}), in the form of a two component vector $[u,v]$ of power series, given to the current default series precision. This vector is characterized by the following two properties. First the point $(x,y)=(u,v)$ satisfies the equation of the elliptic curve. Second, the differential $du/(2v+a_1u+a_3)$ is equal to $f(z)dz$, a differential form on $H/\Gamma_0(N)$ where $N$ is the conductor of the curve. The variable used in the power series for $u$ and $v$ is $x$, which is implicitly understood to be equal to $\exp(2*i*\pi*z)$. The equation of the curve $e$ must be minimal (use {\tt globalred} to get a minimal equation). The library syntax is $\teb{taniyama}(e)$, and the precision of the result is determined by the global variable {\tt precdl}. \subsecref{torsell}$(e)$: If $e$ is an elliptic curve defined over $\Bbb Q$, this outputs the torsion subgroup of $e$ as a 3 component vector {\tt [t,v1,v2]} with the following meaning. {\tt t} is the order of the torsion group. {\tt v1} is a 0, 1 or 2-component vector giving the structure of the torsion group as a product of cyclic groups, with {\tt v1[2]=2} if it exists. Finally {\tt v2}, which is a vector of the same length as {\tt v1}, gives generators for these cyclic groups. $e$ must be a vector as output by {\tt initell} or {\tt smallinitell}. The library syntax is $\teb{torsell}(e)$. \subsecref{zell}$(e,z)$: If $e$ is an elliptic curve with coefficients in $\Bbb R$, this computes a complex number $t$ (modulo the lattice defining $e$) corresponding to the point $z$, i.e. such that, in the standard Weierstrass model, $\wp(t)=z[1],\wp'(t)=z[2]$. In other words, this is the inverse function of {\tt pointell}. If $e$ has coefficients in $\Bbb Q_p$, then either Tate's $u$ is in $\Bbb Q_p$, in which case the output is a $p$-adic number $t$ corresponding to the point $z$ under the Tate parametrization, or only its square is, in which case the output is $t+1/t$. $e$ must be a long vector of the type given by {\tt initell}. The library syntax is $\teb{zell}(e,z,prec)$. \section{Functions related to general number fields.} In this section can be found functions which are used almost exclusively for working in general number fields. Other less specific functions can be found in the next section on polynomials. Functions related to quadratic number fields can be found in section 4 above. Unless otherwise noted, $nf$ will denote a number field, i.e. a 9-component vector in the format output by {\tt initalg} or {\tt initalg0}. An {\it ideal} (usually $x$ or $y$) will mean the following: $x$ can be a $\Z$-basis, in HNF or not. In this case $x$ is a square matrix. $x$ can be an {\it idele}, i.e. a 2-component vector, the first being an ideal given as a $\Z$-basis, the second being a $r_1+r_2$-row vector giving the complex logarithmic archimedean information. $x$ can be a $\Z_K$-generating system for an ideal. $x$ can be a prime ideal, i.e. a 5-component vector in the format output by {\tt primedec}. $x$ can be a polymod, i.e. an algebraic integer, in which case $x$ is treated as being the principal idele generated by $x$. Finally, $x$ can be an integer or a rational number, also treated as a principal idele. \subsecref{base}$(x)$: \ref{integral basis} of the number field defined by the monic irreducible polynomial $x$, using the round 4 algorithm. For small degrees and coefficient size, {\tt base2} is a little faster. For larger degrees, {\tt base} is much faster. This program is the translation in C by D. Letard of a program written by David Ford in Maple. If only a local integral basis is desired, use {\tt factoredbase}. The library syntax is $\teb{base}(x,\&d)$, where $d$ will receive the discriminant of the number field ({\sl not} of the polynomial $x$). \subsecref{base2}$(x)$: integral basis of the number field defined by the monic irreducible polynomial $x$, using the round 2 algorithm. This program is the translation by in C of a program written by David Ford in Algeb. The library syntax is $\teb{base2}(x,\&d)$, where $d$ will receive the discriminant of the number field ({\sl not} of the polynomial $x$). \subsecref{buchgen}$(P,c,c2)$: identical to {\tt buchgenfu} (see below) except that the fundamental units and roots of unity are not computed. Hence the result has only 7 components. The library syntax is $\teb{buchgen}(P,c,c2,prec)$. \subsecref{buchgenfu}$(P,c,c2)$: Buchmann's sub-exponential algorithm for computing the class group, the regulator and a system of fundamental units of the general algebraic number field $K$ defined by the irreducible monic polynomial $P$ with integer coefficients. {\bf Note that this is a completely experimental program which is constantly being improved}. The numbers $c$ and $c2$ are positive real numbers which control the execution time and the stack size. To get maximum speed, set $c2=c$. To get a rigorous result (under GRH and more) you must take $c2=12$ (or $c2=6$ in the quadratic case, but then you should use the much faster functions {\tt buchimag} and {\tt buchreal} below). Reasonable values for $c$ are between $0.1$ and $2$. The result of this function is a vector $v$ with 10 components, which for ease of presentation is in fact output as a one column matrix. $v[1]$ is equal to the polynomial $P$. Note that for optimum performance, $P$ should have gone through {\tt polred} or {\tt initalg}. $v[2]$ is the 2-component vector $[r1,r2]$ (where $r1$ and $r2$ are as usual the number of real and half the number of complex embeddings of the number field $K$). $v[3]$ is the 2-component vector containing the field discriminant and the index, $v[4]$ is an integral basis in Hermite normal form. $v[5]$ is a 3-component vector containing the class number, the structure of the class group as a product of cyclic groups of order $n_i$, and the corresponding generators of the class group of respective orders $n_i$. $v[6]$ is the regulator computed to an accuracy which is the maximum of an internally determined accuracy and of the default. $v[7]$ is a measure of the correctness of the result. If it is close to 1, the results are correct (under GRH and a few more reasonable assumptions). If it is close to a larger integer, this shows that the product of the class number by the regulator is off by a factor equal to this integer, and you must start again with a larger value for $c$ or a different random seed. (Since the computation involves a random process, starting again with exactly the same parameters may give the correct result.) In this case a warning message is printed. $v[8]$ a vector with 2 components, the first being the number $w$ of roots of unity in $K$ and the second a primitive $w$-th root of unity expressed as a polynomial. $v[9]$ is a system of fundamental units also expressed as polynomials. Finally, $v[10]$ gives a measure of the correctness of the computations of the fundamental units (not of the regulator), expressed as a number of bits. If this number is greater than $20$, say, everything is OK. If $v[10]\le0$, then we have lost all accuracy in computing the units (usually an error message will be printed and the units not given). In the intermediate cases, one must proceed with caution (for example by increasing the current precision). Note: some installations may have this function disabled. The library syntax is $\teb{buchgenfu}(P,c,c2,prec)$. \subsecref{buchinit}$(P,c,c2)$: essentially identical to {\tt buchgen} except that the output is much longer, and should not be printed out explicitly in general. The result of buchinit is used in programs such as {\tt isprincipal} and {\tt isunit}. The result is an 8-component vector $v$, whose first 6 components are technical and in principle are not used by the casual user. However, for the sake of completeness, their description is as follows. We use the notations explained in the book by H. Cohen, {\it A Course in Computational Algebraic Number Theory\/}, Graduate Texts in Maths {\bf 138}, Springer-Verlag, 1993, Section 6.5, and pages 354 and 355 in particular. $v[1]$ contains the matrix $W$ ({\tt mit} in the source code), i.e. the matrix in Hermite Normal Form giving on prime ideal generators $(\bf p_i)_{1\le i\le r}$ relations for the class group. $v[2]$ contains the matrix $B$ ({\tt matalpha}), i.e. the matrix containing the expressions of the prime ideal factorbase in terms of the $\bf p_i$. It is an $r\times c$ matrix. $v[3]$ contains the complex logarithmic embeddings of the system of fundamental units which has been found (although not computed in the case of {\tt buchinit}). It is an $(r_1+r_2)\times(r_1+r_2-1)$ matrix. $v[4]$ contains the matrix $M''_C$ of Archimedean components of the relations of the matrix $M$, except that the first $r_1+r_2-1$ columns are suppressed since they are already in $v[3]$. $v[5]$ contains the prime factor base, i.e. the list of $k$ prime ideals used in finding the relations. Finally, $v[6]$ contains the permutation of the prime factor base which was necessary to reduce the relation matrix to the form explained on page 354 (i.e. with a big $c\times c$ identity matrix on the lower right). Note that in the above mentioned book, the need to permute the rows of the relation matrices which occur was not stressed. The less technical components are as follows. $v[7]$ is equal to the number field data $nf$ given by {\tt initalg0}, and $v[8]$ is a 4-component vector containing the 5-th, 6-th, 7-th and 8-th components of the result of {\tt buchgenfu[,1]}, i.e. the class group, the regulator, the ``check'' number which should be close to 1 and the number of roots of unity and a generator. The library syntax is $\teb{buchinit}(P,c,c2,t,prec)$. \subsecref{buchinitfu}$(P,c,c2)$: same as {\tt buchinit} except that the 8-th component contains the last 6 components of {\tt buchgenfu[,1]}, i.e. also the fundamental units and the check on their computation. The library syntax is $\teb{buchinitfu}(P,c,c2,prec)$. \subsecref{discf}$(x)$: \ref{field discriminant} of the number field defined by the monic irreducible polynomial $x$. The library syntax is $\teb{discf}(x)$. See also {\tt base} above. \subsecref{factoredbase}$(x,f)$: \ref{integral basis} of the number field defined by the monic irreducible polynomial $x$, using the round 2 algorithm, where $f$ is the two column matrix of the factorization of the discriminant of the polynomial $x$. Note that $f$ does {\it not} need to be a complete factorization of the discriminant. This is especially useful if only a local integral basis at a prime or primes is desired: only factors with exponents greater or equal to 2 will be considered. The library syntax is $\teb{factoredbase}(x,p,\&d)$, where $d$ will receive the discriminant of the number field. \subsecref{factoreddiscf}$(x,p)$: \ref{field discriminant} of the number field defined by the monic irreducible polynomial $x$, using the round 2 algorithm, where $p$ is the two column matrix of the factorization of the discriminant of the polynomial $x$. The library syntax is $\teb{factoreddiscf}(x,p)$. \subsecref{factoredpolred}$(x,p)$: same as {\tt polred} (see below) except that $p$ is the two column matrix of the factorization of the discriminant of the polynomial $x$. The library syntax is $\teb{factoredpolred}(x,p,prec)$. \subsecref{factoredpolred2}$(x,p)$: same as {\tt polred2} (see below) except that $p$ is the two column matrix of the factorization of the discriminant of the polynomial $x$. The library syntax is $\teb{factoredpolred2}(x,p,prec)$. \subsecref{factornf}$(x,t)$: factorization of the univariate polynomial $x$ over the number field defined by the (univariate) polynomial $t$. $x$ may have coefficients in $\Bbb Q$ or in the number field. The main variable of $t$ must be of lower priority than that of $x$ (in other words the variable number of $t$ must be greater than that of $x$). However if the coefficients of the number field occur explicitly (as polymods) as coefficients of $x$, the variable of these polymods {\it must} be the same as the main variable of $t$. For example {\tt factornf(x\^{}2+mod(y,y\^{}2+1),y\^{}2+1)} and {\tt factornf(x\^{}2+1,y\^{}2+1)} are legal but {\tt factornf(x\^{}2+mod(z,z\^{}2+1),y\^{}2+1)} is not. The library syntax is $\teb{polfnf}(x,t)$. \subsecref{galois}$(x)$: Galois group of the nonconstant polynomial $x\in\Bbb Q[X]$. In the present version \vers, $x$ must be irreducible and the degree of $x$ must be less than or equal to 7 (for degrees 8,9,10, and 11 we have specific Pari programs available upon request). The output is a 3-component vector $[n,s,k]$ with the following meaning: $n$ is the cardinality of the group, $s$ is its signature ($s=1$ if the group is a subgroup of the alternating group $A_n$, $s=-1$ otherwise), and $k$ is the number of the group corresponding to a given pair $(n,s)$ ($k=1$ except in 2 cases). Specifically, the groups are coded as follows, using standard notations: \smallskip In degree 1: $S_1=[1,-1,1]$. \smallskip In degree 2: $S_2=[2,-1,1]$. \smallskip In degree 3: $A_3=C_3=[3,1,1]$, $S_3=[6,-1,1]$. \smallskip In degree 4: $C_4=[4,-1,1]$, $V_4=[4,1,1]$, $D_4=[8,-1,1]$, $A_4=[12,1,1]$, $S_4=[24,-1,1]$. \smallskip In degree 5: $C_5=[5,1,1]$, $D_5=[10,1,1]$, $M_{20}=[20,-1,1]$, $A_5=[60,1,1]$, $S_5=[120,-1,1]$. \smallskip In degree 6: $C_6=[6,-1,1]$, $S_3=[6,-1,2]$, $D_6=[12,-1,1]$, $A_4=[12,1,1]$, $G_{18}=[18,-1,1]$, $S_4^-=[24,-1,1]$, $A_4\times C_2=[24,-1,2]$, $S_4^+=[24,1,1]$, $G_{36}^-=[36,-1,1]$, $G_{36}^+=[36,1,1]$, $S_4\times C_2=[48,-1,1]$, $A_5=PSL_2(5)=[60,1,1]$, $G_{72}=[72,-1,1]$, $S_5=PGL_2(5)=[120,-1,1]$, $A_6=[360,1,1]$, $S_6=[720,-1,1]$. \smallskip In degree 7: $C_7=[7,1,1]$, $D_7=[14,-1,1]$, $M_{21}=[21,1,1]$, $M_{42}=[42,-1,1]$, $PSL_2(7)=PSL_3(2)=[168,1,1]$, $A_7=[2520,1,1]$, $S_7=[5040,-1,1]$. \smallskip The method used is that of resolvent polynomials. Beware that in the case of degree 7 one has to factor polynomials of degree 35 over $\Bbb Z$, and this can take a long time. Furthermore there is a risk that the pari stack overflows, so it is prudent in this case to start with a large stack. The library syntax is $\teb{galois}(x,prec)$. \subsecref{galoisconj}$(x)$: conjugates of a root $r$ of the nonconstant polynomial $x$ expressed as polynomials in $r$. This can be used even if the corresponding number field is not Galois since some conjugates may lie in the field. The library syntax is $\teb{galoisconj}(x,prec)$. A slower version but which has a better chance of finding the conjugates when the index is large is $\teb{galoisconj2}(x,prec)$ (not accessible from GP). \subsecref{idealadd}$(nf,x,y)$: sum of the two ideals $x$ and $y$ in the number field $nf$. When $x$ and $y$ are given by $\Z$-bases, this does not depend on $nf$ and can be used to compute the sum of any two $\Z$-modules. The result is given in HNF. The library syntax is $\teb{idealadd}(nf,x,y)$. \subsecref{idealdiv}$(nf,x,y)$: quotient $x\cdot y^{-1}$ of the two ideals $x$ and $y$ in the number field $nf$, where $nf$ is a 9-component vector given by {\tt initalg} or {\tt initalg0}. The result is given in HNF. The library syntax is $\teb{idealdiv}(nf,x,y)$. \subsecref{idealfactor}$(nf,x)$: factors into prime ideal powers the ideal $x$ in the number field $nf$, where $nf$ is a 9-component vector given by {\tt initalg} or {\tt initalg0}. The output format is similar to the {\tt factor} function, and the prime ideals are represented in the form output by the {\tt primedec} function, i.e. as 5-element vectors. The library syntax is $\teb{idealfactor}(nf,x)$. \subsecref{idealintersect}$(nf,x,y)$: sum of the two ideals $x$ and $y$ in the number field $nf$. When $x$ and $y$ are given by $\Z$-bases, this does not depend on $nf$ and can be used to compute the intersection of any two $\Z$-modules. The result is given in HNF. The library syntax is $\teb{idealintersect}(nf,x,y)$. \subsecref{idealinv}$(nf,x)$: inverse of the ideal $x$ in the number field $nf$. $nf$ must be a 9-component vector as given by {\tt initalg}, The result is the Hermite normal form of the inverse of the ideal, together with the opposite of the Archimedean information if it is given. The library syntax is $\teb{idealinv}(nf,x)$. \subsecref{ideallllred}$(nf,x,vdir)$: LLL reduction of the ideal $x$ in the number field $nf$, along the direction $vdir$. Here $vdir$ must be either an $r1+r2$-component vector ($r1$ and $r2$ number of real and complex places of $nf$ as usual), or the Pari zero, in which case $vdir$ is assumed to be equal to the vector having only components equal to 1. The notion of reduction along a direction is technical and cannot be explained here. Note that this is {\it not\/} the same as the LLL reduction of the lattice $x$ since ideal operations are involved. The result is the Hermite normal form of the LLL-reduced ideal, which is usually, but not always, a reduced ideal. $x$ may also be a 2-component vector, the first being as above, and the second containing a matrix of Archimedean information. In that case, this matrix is suitably updated. The library syntax is $\teb{ideallllred}(nf,x,vdir,prec)$. \subsecref{idealmul}$(nf,x,y)$: ideal multiplication of the ideals $x$ and $y$ in the number field $nf$. $nf$ must be a 9-component vector as given by {\tt initalg} or {\tt initalg0}. The result is a generating set for the ideal product with at most $n$ elements, and is in Hermite normal form if $x$ and $y$ are, and this is given together with the sum of the Archimedean information in $x$ and $y$ if both are given. The library syntax is $\teb{idealmul}(nf,x,y)$. \subsecref{idealmulred}$(nf,x,y)$: same as {\tt idealmul}, except that the result is reduced using {\tt ideallllred}. The library syntax is $\teb{idealmulred}(nf,x,y,prec)$, where $prec$ is a C-integer representing the precision. \subsecref{idealpow}$(nf,x,k)$: computes the $k$-th power of the ideal $x$ in the number field $nf$ as given by {\tt initalg} or {\tt initalg0}. $k$ can be positive negative or zero. The result is NOT reduced, it is really the $k$-th ideal power, and is given in HNF. Use {\tt idealpowred} if you want a reduced result. The library syntax is $\teb{idealpow}(nf,x,k)$. \subsecref{idealpowred}$(nf,x,k)$: computes a reduced $k$-th power of the ideal $x$ in the number field $nf$ as given by {\tt initalg} or {\tt initalg0}. To get a non-reduced result, use {\tt idealpow}. Note however that {\tt idealpowred} is NOT the same as as {\tt idealpow} followed by reduction (i.e. {\tt ideallllred}), since the reduction is performed throughout the powering process. The library syntax is $\teb{idealpowred}(nf,vp,k,prec)$, where $prec$ is a C-integer. \subsecref{idealval}$(nf,x,vp)$: gives the valuation of the ideal $x$ at the prime ideal $vp$ in the number field $nf$. $nf$ must be a 9-component vector as given by {\tt initalg} or {\tt initalg0}, and $vp$ must be a 6-component vector as given by {\tt primedec}. The library syntax is $\teb{idealval}(nf,x,vp)$ and the result is a C-integer. \subsecref{initalg}$(x)$: $x$ being a nonconstant irreducible polynomial in $\Bbb Q[X]$, computes a 9-component vector $v$ useful in working in the number field $K$ defined by $x$. $v[1]$ contains a polynomial defining $K$ which is as simple as can easily be found using the {\tt polred} algorithm. $v[2]$ contains $[r1,r2]$, the number of real and complex places of $K$. $v[3]$ contains the discriminant of the number field $K$. $v[4]$ contains the index of $v[1]$, i.e. $[\Bbb Z_K:\Bbb Z[\theta]]$, where $\theta$ is any root of $v[1]$. $v[5]$ is a vector containing 5 matrices $M$, $MC$, $T2$, $T$ and $MD$ useful for certain computations in the number field $K$. The matrix $M$ is the $(r1+r2)\times n$ matrix whose columns represent the numerical values of the conjugates of the elements of the integral basis. The matrix $MC$ is essentially the conjugate of the transpose of $M$, except that the last $r2$ columns are also multiplied by 2. The matrix $T2$ is an $n\times n$ matrix equal to the product $MC\cdot M$, the so-called T2-matrix. The matrix $T$ is the $n\times n$ matrix whose coefficients are $\text{Tr}(\omega_i\omega_j)$ where the $\omega_i$ are the elements of the integral basis. Note that $T=\overline{MC}\cdot M$ and in particular that $T=T_2$ if the field is totally real (in practice $T_2$ will have real approximate entries and $T$ will have integer entries). Note also that $\det(T)$ is equal to the discriminant of the field $K$. Finally, the columns of $MD$ express a $\Bbb Z$-basis of the different of $K$ on the integral basis $v[7]$. $v[6]$ is the vector containing the $r1+r2$ roots of $v[1]$ corresponding to the $r1+r2$ embeddings of the number field into $\Bbb C$ (the first $r1$ components are real, the next $r2$ have positive imaginary part). $v[7]$ is an integral basis in Hermite normal form for $\Bbb Z_K$ expressed on the powers of $\theta$. $v[8]$ is the $n\times n$ integral matrix expressing the power basis in terms of the integral basis, and finally $v[9]$ is the $n\times n^2$ matrix giving the multiplication table of the integral basis. The library syntax is $\teb{initalg}(x,prec)$. \subsecref{initalg0}$(x)$: same as {\tt initalg} except that the polynomial is not changed. This is useful in conjunction with functions expecting a number field {\tt nf} but where one wants to keep the initial polynomial. The library syntax is $\teb{initalg0}(x,prec)$. \subsecref{initalg2}$(P)$: this is a complement to {\tt initalg}. With the same conditions, it produces a polymod $mod(a,pol)$ equal to $mod(x,P)$ where $pol$ is the polynomial output by {\tt initalg}. The library syntax is $\teb{initalg2}(x,prec)$. \subsecref{isincl}$(x,y)$: tests whether the number field $K$ defined by the polynomial $x$ is conjugate to a subfield of the field $L$ defined by $y$ (where $x$ and $y$ must be in $\Bbb Q[X]$). If they are not, the output is the number 0. If they are, the output is a vector of polynomials, each polynomial $a$ representing an isomorphism of $K$ into $L$, i.e. being such that $y=x\circ a$. The library syntax is $\teb{nfincl}(x,y)$. \subsecref{isisom}$(x,y)$: tests whether the two number fields defined by the polynomials $x$ and $y$ (which must be in $\Bbb Q[X]$) are isomorphic. If they are not, the output is the number 0. If they are, the output is a vector of polynomials, each polynomial $a$ representing an isomorphism, i.e. being such that $y=x\circ a$. The library syntax is $\teb{nfiso}(x,y)$. \subsecref{isprincipal}$(bnf,x)$: $bnf$ being the number field data output by {\tt buchinit}, and $x$ being either a $\Z$-basis of an ideal in the number field (not necessarily in HNF) or a prime ideal in the format output by the function {\tt primedec}, this function tests whether the ideal is principal or not. The result is much more complete than a simple true/false answer: it is given as a 3 component vector $[v_1,v_2,e]$ with the following meaning. $v_1$ is the vector of components $c_i$ of the class of the ideal $x$ in the class group, expressed on the generators $g_i$ given by {\tt buchinit} (specifically {\tt buchinit[8][1][3]}). The $c_i$ are chosen so that $0\le c_i0$, search only for irreducible factors of degree less than or equal to $l$. The result is a two column matrix, the first one containing the irreducible factors, the second one the exponents. The library syntax is $\teb{factpol}(x,l)$. The algorithm used is the standard Hensel lifting of a mod $p$ factorization. Another implementation using instead root finding over $\Bbb C$ (instead of implicitly using $\Bbb Q_p$) is $\teb{factpol2}(x,l)$. \subsecref{integ}$(x,y)$: \ref{formal integration} of $x$ with respect to the simple variable $y$. No logarithmic terms must occur in the result. $x$ can be of any type, but the case where $x$ is a rational function is not implemented in the present version \vers. The library syntax is $\teb{integ}(x)$. \subsecref{laplace}$(x)$: $x$ must be a power series with only nonnegative exponents. If $x=\sum (a_k/k!)*X^k$ then the result is $\sum a_k*X^k$. The library syntax is $\teb{laplace}(x)$. \subsecref{legendre}$(x)$: creates the $x^{\text{th}}$ \ref{Legendre polynomial}. The library syntax is $\teb{legendre}(x)$, where $x$ is a 32-bit C-integer. \subsecref{polint}$(xa,ya,x)$: 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 \ref{interpolating polynomial} passing through these points and evaluates it at the value $x$. The library syntax is $\teb{polint}(xa,ya,x,\&er)$, where $er$ will contain an error estimate on the returned value. \subsecref{polsym}$(x,n)$: creates the vector of the \ref{symmetric powers} of the roots of the polynomial $x$ up to power $n$. The library syntax is $\teb{polsym}(x)$. \subsecref{recip}$(x)$: reciprocal polynomial of $x$, i.e. the coefficients are in reverse order. $x$ must be a polynomial. The library syntax is $\teb{polrecip}(x)$. \subsecref{resultant}$(x,y)$: resultant of the two polynomials $x$ and $y$ with exact entries. The algorithm used is the subresultant algorithm. The library syntax is $\teb{subres}(x,y)$. \subsecref{resultant2}$(x,y)$: resultant of the two polynomials $x$ and $y$. The algorithm used is the determinant of Sylvester's matrix. The library syntax is $\teb{resultant2}(x,y)$. \subsecref{reverse}$(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 $\teb{recip}(x)$. \subsecref{rootmod}$(x,p)$: roots modulo $p$ of the polynomial $x$. Slightly slower than {\tt rootmod2} below for $p<100$, but much faster for larger values. The particular nonprime value $p=4$ is accepted, mainly for $2$-adic computations. Multiple roots are {\sl not} repeated. The library syntax is $\teb{rootmod}(x,p)$. \subsecref{rootmod2}$(x,p)$: roots modulo $p$ of the polynomial $x$. To be used only when $p$ is small. Multiple roots are repeated with their order of multiplicity. The library syntax is $\teb{rootmod2}(x,p)$. \subsecref{rootpadic}$(x,p,r)$: vector of $p$-adic roots of the polynomial $x$ with $p$-adic precision equal to $r$. Multiple roots are {\sl not} repeated. The library syntax is $\teb{rootpadic}(x,p,r)$, where $r$ is a C-integer. \subsecref{roots}$(x)$: complex roots of the polynomial $x$, given as a column vector where each root is repeated according to its multiplicity. The precision is given as for transcendental functions: under GP it is kept in the variable {\tt prec} and is transparent to the user, but it must be explicitly given as a second argument in library mode. The algorithm used is a variant of the Newton-Raphson method and 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'', try modifying your polynomial to get the roots, or try to use the slower function {\tt rootslong}. The library syntax is $\teb{roots}(x,prec)$. \subsecref{rootslong}$(x)$: same as {\tt roots} except that the program is a little more robust and slower. The library syntax is $\teb{rootslong}(x,prec)$. \subsecref{sturm}$(x)$: number of real roots of the real polynomial $x$, using Sturm's algorithm. The library syntax is $\teb{sturm}(x)$. The result is a 32-bit C-integer. \subsecref{sturmpart}$(x,a,b)$: number of real roots of the real polynomial $x$ in the interval $(a,b]$, using Sturm's algorithm. The library syntax is $\teb{sturmpart}(x)$. The result is a 32-bit C-integer. \subsecref{subst}$(x,y,z)$: replace the simple variable $y$ by the argument $z$ in expression $x$. Every non-scalar type is allowed for $x$. If $x$ is a power series, $z$ must be either a polynomial, a power series, or a rational function. $y$ must be a simple variable name. The library syntax is $\teb{gsubst}(x, v,z)$, where $v$ is the number of the variable $y$. \subsecref{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 under GP, but must be given as a second argument in library mode. The library syntax is $\teb{tayl}(x,y,n)$, where the 32-bit C-integer $n$ is the desired number of terms in the expansion. \subsecref{tchebi}$(x)$: creates the $x^{\text{th}}$ Tchebicheff polynomial. The library syntax is $\teb{tchebi}(x)$, where $x$ is a 32-bit C-integer. \section{Vectors, matrices and linear algebra.} \subsecref{adj}$(x)$: \ref{adjoint matrix} of $x$, i.e. the matrix $y$ of cofactors of $x$ such that $x*y=\text{det}(x)*\text{Id}$. $x$ must be a (non necessarily invertible) square matrix. The library syntax is $\teb{adj}(x)$. \subsecref{algdep}$(x, k)$: \sref{algebraic dependence} $x$ being real or complex, finds a polynomial of degree at most $k$ having $x$ as approximate root. The algorithm used is a variant of the LLL algorithm due to Hastad, Lagarias and Schnorr (STACS 1986). Note that the polynomial which is obtained is not necessarily the ``correct'' one. One can check the closeness either by a polynomial evaluation or substitution, or by finding the roots of the polynomial given by algdep. The library syntax is $\teb{algdep}(x,k,prec)$, where $k$ is a 32-bit C-integer. \subsecref{algdep2}$(x, k, dec)$: \sref{algebraic dependence} $x$ being real or complex, finds a polynomial of degree at most $k$ having $x$ as approximate root. $dec$ is a number which should be between half the number of decimal digits of precision and that number. The algorithm used is the LLL algorithm. Note that the polynomial which is obtained is not necessarily the ``correct'' one. One can check the closeness either by a polynomial evaluation or substitution, or by finding the roots of the polynomial given by algdep2. The library syntax is $\teb{algdep2}(x,k,dec,prec)$, where $k$ and $dec$ are 32-bit C-integers. \subsecref{char}$(x,y)$: \ref{characteristic polynomial} of $x$ with respect to the variable $y$, i.e. determinant of $y*I-x$ if $x$ is a square matrix, determinant of the map multiplication by $x$ if $x$ is a polymod, error if $x$ is of any other type. For matrices, the method used is essentially the same as for computing the adjoint matrix, i.e. computing the traces of the powers of $x$. The library syntax is $\teb{caradj0}(x, v)$, where $v$ is the variable number, or even $\teb{caradj}(x,v,0)$. Note that the function {\tt caradj(x,v,pty)} returns the characteristic polynomial of $x$ in the variable $v$, and if {\tt pty} is not equal to 0, puts in {\tt pty} the address of the adjoint matrix of $x$, so both can be obtained at once. \subsecref{char1}$(x,y)$: \ref{characteristic polynomial} of $x$ with respect to the variable $y$, i.e. determinant of $y*I-x$ if $x$ is a square matrix, determinant of the map multiplication by $x$ if $x$ is a polymod, error if $x$ is of any other type. For matrices, the method used is that of Lagrange interpolation and is almost always slower than {\tt char}. Identical to {\tt char} for polymods. The library syntax is $\teb{caract}(x, v)$, where $v$ is the variable number. \subsecref{char2}$(x,y)$: characteristic polynomial of the square matrix $x$ with respect to the variable $y$ using the Hessenberg form. This is faster than {\tt char} when the coefficients are integermod a prime or real numbers, but is usually slower in other base rings. The library syntax is $\teb{carhess}(x,v)$, where $v$ is the variable number. \subsecref{concat}$(x,y)$: concatenation of $x$ and $y$. If $x$ or $y$ is not a vector or matrix, it is considered as a one dimensional vector. All types are allowed for $x$ and $y$, but the sizes must be compatible. Note that matrices are concatenated horizontally, i.e. the number of rows stays the same. Using transpositions, it is easy to concatenate them vertically. To concatenate vectors sideways (i.e. to obtain a 2-row or two column matrix), first transform the vector into a 1-row or 1-column matrix using the function {\tt mat} below. The library syntax is $\teb{concat}(x,y)$. \subsecref{det}$(x)$: determinant of $x$. $x$ must be a square matrix. Another program called {\bf \ref{det2}}$(x)$ is better when the entries of the matrix are reals or integers for example, but can be much worse for more complicated entries like multivariate polynomials. The library syntax is $\teb{det}(x)$ and $\teb{det2}(x)$. \subsecref{detint}$(x)$: $x$ being an $m\times n$ matrix with integer coefficients, this function computes a multiple of the determinant of the lattice generated by the columns of $x$ if it is of rank $m$, and returns zero otherwise. This function can be useful in conjunction with the function {\tt hermitemod} which needs to know such a multiple. Other ways to obtain this determinant (assuming the rank is maximal) is {\tt det(lllkerim(x)[2]$*$x)} or simply {\tt det(hermite(x))}. Try to see which is faster in your case. The library syntax is $\teb{detint}(x)$. \subsecref{eigen}$(x)$: gives the eigenvectors of $x$ as columns of a matrix. The library syntax is $\teb{eigen}(x)$. \subsecref{extract}$(x,y)$: extraction of components of the vector or matrix $x$ according to $y$. $x$ must be a vector or a matrix. In the case of a matrix, the components are as usual the {\sl columns} of $x$. $y$ must be either a number of PARI type integer, in which case it is considered as a mask: The binary bits of $y$ are read from right to left, but correspond to taking the components from left to right. For example, if $y=13=(1101)_2$ then the components 1,3 and 4 are extracted. Or $y$ can be a vector, with integer entries, in which case these entries correspond to the component number to be extracted, in the order specified. In the case of a matrix, the difference between extract and matextract is that only columns are extracted. The library syntax is $\teb{extract}(x,y)$. \subsecref{gauss}$(x,y)$: $x$ being a square matrix and $y$ a column vector, finds the solution $u$ of $x*u=y$, using Gaussian elimination. This has the same effect, but is much faster, than $x^{-1}*y$. The library syntax is $\teb{gauss}(x,y)$. \subsecref{hermite}$(x)$: if $x$ is a (not necessarily square) matrix of maximal rank, finds the {\sl upper triangular} Hermite Normal Form of $x$ If the rank of $x$ is equal to its number of rows, the result is a square matrix. In general, the columns of the result form a basis of the lattice spanned by the columns of $x$. The library syntax is $\teb{hnf}(x)$. \subsecref{hermitemod}$(x,d)$: if $x$ is a (not necessarily square) matrix of maximal rank, and $d$ is the (non-zero) determinant of the lattice spanned by the columns of $x$, finds the {\sl upper triangular} Hermite Normal Form of $x$ If the rank of $x$ is equal to its number of rows, the result is a square matrix. In general, the columns of the result form a basis of the lattice spanned by the columns of $x$. This is much faster than {\tt hermite} when $d$ is known. The library syntax is $\teb{hnfmod}(x,d)$. \subsecref{hess}$(x)$: Hessenberg form of the square matrix $x$. The library syntax is $\teb{hess}(x)$. \subsec{hilbert}$(x)$: $x$ being a 32-bit C-integer, creates the \ref{Hilbert matrix} of order $x$, i.e. the matrix whose coefficient ($i$,$j$) is $1\over {i+j-1}$. The library syntax is $\teb{hilbert}(x)$. \subsecref{idmat}$(n)$: creates the $n\times n$ identity matrix. The library syntax is $\teb{idmat}(n)$ where $n$ is a C-integer. Related functions are $\teb{gscalmat}(x,n)$ which creates $x$ times the identity matrix ($x$ being a GEN and $n$ a C-integer) and $\teb{gscalsmat}(x,n)$ which is the same when $x$ is a C-integer. \subsecref{image}$(x)$: gives a basis for the image of the matrix $x$ as columns of a matrix. A priori the matrix can have entries of any type. The library syntax is $\teb{image}(x)$. \subsecref{imagecompl}$(x)$: gives the vector of the column indices which are not extracted by the function {\tt image}. Hence the number of components of {\tt imagecompl(x)} plus the number of columns of {\tt image(x)} is equal to the number of columns of the matrix $x$. The library syntax is $\teb{imagecompl}(x)$. \subsecref{imager}$(x)$: gives a basis for the image of the matrix $x$ as columns of a matrix, where $x$ has elements which can be nonexact real or complex numbers. In that case, the precision of the matrix entries determines what is meant by an element of the image. In particular, if the matrix is ill conditioned, the results may not be what you expect. The library syntax is $\teb{imagereel}(x)$. \subsecref{indexrank}$(x)$: $x$ being a matrix of rank $r$, gives two vectors of length $r$ giving a list of rows and columns respectively (starting from 1) such that the extracted matrix obtained from these 2 vectors using {\tt matextract} is invertible. The library syntax is $\teb{indexrank}(x)$. \subsecref{indsort}$(x)$: indirect sorting of the vector $x$, i.e. if $x$ is an $n$-dimensional vector, creates the permutation of $[1,2,\dots,n]$ which applied to the components of $x$ sorts $x$ in increasing order. The library syntax is $\teb{indexsort}(x)$. \subsecref{intersect}$(x,y)$: $x$ and $y$ being two matrices with the same number of rows whose columns are independent, finds a basis of the $\Bbb Q$-vector space equal to the intersection of the spaces spanned by the columns of $x$ and $y$ respectively. The library syntax is $\teb{intersect}(x,y)$. \subsecref{inverseimage}$(x,y)$: gives one column vector belonging to the inverse image of the column vector $y$ by the matrix $x$ if one exists, the empty vector otherwise. To get the complete inverse image, it suffices to add to the result any element of the kernel of $x$ obtained for example by {\tt ker}. The library syntax is $\teb{inverseimage}(x,y)$. \subsecref{jacobi}$(x)$: $x$ being a real symmetric matrix, this gives a vector having two components: the first one is the vector of eigenvalues of $x$, the second is the corresponding orthogonal matrix of eigenvectors of $x$. The method used is Jacobi's method for symmetric matrices. The library syntax is $\teb{jacobi}(x)$. \subsecref{ker}$(x)$: gives a basis for the kernel of the matrix $x$ as columns of a matrix. A priori the matrix can have entries of any type. See also {\tt keri} and {\tt kerr}. The library syntax is $\teb{ker}(x)$. \subsecref{keri}$(x)$: same as {\tt ker}, except that it assumes that the matrix has entries of type integer. In that case it is much faster. The library syntax is $\teb{keri}(x)$. \subsecref{kerint}$(x)$: gives an LLL-reduced $\Bbb Z$-basis for the lattice equal to the kernel of the matrix $x$ as columns of the matrix $x$ with integer entries (rational entries are not permitted) using a modified integer LLL algorithm. The library syntax is $\teb{kerint}(x)$. \subsecref{kerint1}$(x)$: like {\tt kerint}, but using {\tt matrixqz3}, gives an LLL-reduced $\Bbb Z$-basis for the lattice equal to the kernel of the matrix $x$ as columns of the matrix $x$ with integer or rational entries. If LLL reduction of the final result is not desired, use {\tt matrixqz3(ker(x))} instead. The library syntax is $\teb{kerint1}(x)$. \subsecref{kerint2}$(x)$: like {\tt kerint}, but using another modified LLL algorithm, gives an LLL-reduced $\Bbb Z$-basis for the lattice equal to the kernel of the matrix $x$ as columns of the matrix $x$ with integer entries (rational entries are not permitted). In the present version \vers, only independent rows are allowed. The library syntax is $\teb{kerint2}(x)$. \subsecref{kerr}$(x)$: gives a basis for the kernel of the matrix $x$ as columns of a matrix, where $x$ has elements which can be nonexact real or complex numbers. In that case, the precision of the matrix entries determines what is meant by an element of the kernel. In particular, if the matrix is ill conditioned, the results may not be what you expect. The library syntax is $\teb{kerreel}(x)$. \subsecref{lexsort}$(x)$ sort the elements of the vector $x$ by ascending lexicographic order (see {\tt lex} above). The library syntax is $\teb{lexsort}(x)$. \subsecref{lindep}$(x)$: \sref{linear dependence}$x$ being a vector with real or complex coefficients, finds a small integral linear combination among these coefficients using a variant of the LLL algorithm due to Hastad, Lagarias and Schnorr (STACS 1986). The library syntax is $\teb{lindep}(x,prec)$. \subsecref{lindep2}$(x,dec)$: \sref{linear dependence}$x$ being a vector with real or complex coefficients, finds a small integral linear combination among these coefficients using the LLL algorithm. $dec$ is a parameter which should be between one half the number of decimal digits of precision and that number. The library syntax is $\teb{lindep2}(x,dec,prec)$ where $dec$ is a C-integer. \subsecref{lll}$(x)$: LLL algorithm applied to the {\bf columns} of the (non necessarily square) matrix $x$. The columns of $x$ must however be of maximal rank (otherwise if $x$ has integral coefficients use {\tt lllint}. The result is a square transformation matrix $T$ such that $x\cdot T$ is an LLL-reduced basis of the lattice generated by the column vectors of $x$. The computations are done with real numbers (i.e. not with rational numbers) hence are fast but as presently programmed (version \vers) are numerically unstable. An older version of this program is {\tt lll1}. The library syntax is $\teb{lll}(x,prec)$. \subsecref{lllgram}$(x)$: same as LLL except that the matrix $x$ which is now square is the gram matrix of the lattice vectors, and not the coordinates of the vectors themselves. The result is again the transformation matrix $T$ which gives (as columns) the coefficients with respect to the initial basis vectors. Same remarks as for LLL about numerical instability in the present version \vers. An older version of this program is {\tt lllgram1}. The library syntax is $\teb{lllgram}(x,prec)$. \subsecref{lllgramint}$(x)$: The matrix $x$ being the gram matrix of a basis of some lattice, is assumed to have integral entries. The result is the unimodular transformation matrix $T$ which gives (as columns) the coefficients with respect to the initial basis vectors. The computations are done entirely with integers and is both accurate and quite fast. The library syntax is $\teb{lllgramint}(x)$. \subsecref{lllgramkerim}$(x)$: LLL algorithm applied to the gram matrix of some lattice, which is assumed to have integral entries. Here the columns can be linearly dependent. The result is a two component vector of matrices whose concatenation form a unimodular transformation matrix $T$ which gives as columns the coefficients with respect to the initial basis vectors. The first matrix will give the kernel, the second will give an LLL-reduced basis of the image. The library syntax is $\teb{lllgramkerim}(x)$. \subsecref{lllint}$(x)$: LLL algorithm applied to the {\bf columns} of the (non necessarily square) matrix $x$. It is assumed that the corresponding gram matrix is integral. The result is a square transformation matrix $T$ such that $x\cdot T$ is an LLL-reduced basis of the lattice generated by the column vectors of $x$. The computations are done entirely with integers and is both accurate and quite fast. The library syntax is $\teb{lllint}(x)$. \subsecref{lllkerim}$(x)$: LLL algorithm applied to the columns of the (non necessarily square) matrix $x$ which is assumed to have integral entries. Here the columns can be linearly dependent. The result is a two component vector of matrices, the columns of the first matrix representing a basis of the integer kernel of $x$ (not necessarily LLL-reduced) and the columns of the second matrix being an LLL-reduced $\Bbb Z$-basis of the image of the matrix $x$. The library syntax is $\teb{lllkerim}(x)$. \subsecref{lllrat}$(x)$: same as LLL except that the computations are all done in rational numbers. Hence no risk of numerical instability, but extremely slow. This function is essentially superseded by {\tt lllint} so will soon disappear. The library syntax is $\teb{lllrat}(x)$. \subsecref{mat}$(x)$: transform the object $x$ into a matrix. If $x$ is not a vector or a matrix, this creates a $1\times 1$ matrix. If $x$ is a row (resp. column) vector, this creates a 1-row (resp. 1-column) matrix. If $x$ is already a matrix, a copy of $x$ is created. This function can be useful in connection with the function {\tt concat} (see above). The library syntax is $\teb{gtomat}(x)$. \subsecref{matextract}$(x,y,z)$: extraction of a matrix from the matrix $x$, the line mask or vector $y$ and the column mask or vector $z$. $x$ must be a matrix, and $y$ and $z$ either numbers of PARI type integer or vectors. The extraction is done using the same rules as for {\tt extract} (see above). The difference with {\tt extract} is that both lines and columns are extracted. The library syntax is $\teb{matextract}(x,y,z)$. \subsecref{matinvr}$(x)$: computes the inverse matrix of $x$ assumed to have real entries. This may be more efficient than using {\tt ginv} (or $x^{-1}$ under GP). The library syntax is $\teb{invmatreel}(x)$. A related function is $\teb{invmulmatreel}(x,y)$ which directly computes $x^{-1}*y$ for matrices $x$ and $y$. \subsecref{matsize}$(x)$: $x$ being a vector or matrix, returns a row vector with two components, the first being the number of rows (1 for a row vector), the second the number of columns (1 for a column vector). The library syntax is $\teb{matsize}(x)$. \subsecref{matrixqz}$(x,p)$: $x$ being an $m\times n$ matrix with $m\ge n$ with rational or integer entries and of maximal rank, this function returns a matrix having only integral entries, having the same image as $x$ (so is which is obtained from $x$ by right multiplication with an $n\times n$ invertible matrix) and such that the GCD of all its $n\times n$ subdeterminants is equal to 1 when $p$ is equal to 0, or non divisible by $p$ otherwise. Here $p$ must be a prime number (when it is nonzero). However, if the function is used when $p$ has no small prime factors, it will either work or give the message ``impossible inverse modulo'' and a nontrivial divisor of $p$. The library syntax is $\teb{matrixqz}(x,p)$. \subsecref{matrixqz2}$(x)$: $x$ being an $m\times n$ matrix with rational or integer entries, this function returns a matrix whose columns form a basis of the lattice equal to $\Bbb Z^n$ intersected with the lattice generated by the columns of $x$. The library syntax is $\teb{matrixqz2}(x)$. \subsecref{matrixqz3}$(x)$: $x$ being an $m\times n$ matrix with rational or integer entries, this function returns a matrix whose columns form a basis of the lattice equal to $\Bbb Z^n$ intersected with the $\Bbb Q$-vector space generated by the columns of $x$. The library syntax is $\teb{matrixqz3}(x)$. \subsecref{minim}$(x,b,m)$: $x$ being a square and symmetric matrix with integer entries representing a positive definite quadratic form, gives the number of vectors of square norm less than or equal to $b$ (for the norm defined by $x$), and at most $m$ of these vectors. The result is a three component vector, the first component being the number of vectors, the second being the maximum norm found, and the last vector is a matrix whose columns are the vectors found (at most $m$). In the special case where $b=0$, the function searches for the minimal non-zero vectors. The library syntax is $\teb{minim}(x,b,m)$ \subsecref{perf}$(x)$: $x$ being a square and symmetric matrix with integer entries representing a positive definite quadratic form, looks for the perfection of the form: gives the rank of the family of the s symetric matices $v_iv_i^t$, the $v_i$ ($1\le i\le s$) beeing the minimal vectors. The library syntax is $\teb{perf}(x)$ \subsec{pascal}$(x)$: creates as a matrix the lower triangular \ref{pascal triangle} of order $x+1$ (i.e. with binomial coefficients up to $x$). The library syntax is $\teb{pascal}(x)$, where $x$ is a 32-bit C-integer. \subsecref{rank}$(x)$: rank of the matrix $x$. The library syntax is $\teb{rank}(x)$, and the result is a 32-bit C-integer. \subsecref{signat}$(x)$: signature of the quadratic form represented by the symmetric matrix $x$. The result is a two-component vector. The library syntax is $\teb{signat}(x)$ \subsecref{smith}$(x)$: if $x$ is a (singular or non-singular) square matrix, outputs the vector of elementary divisors of $x$ (i.e. the diagonal of the Smith normal form of $x$) The library syntax is $\teb{smith}(x)$. \subsecref{smith2}$(x)$: if $x$ is a (singular or non-singular) square matrix, outputs a 2-component vector $[u,v]$ where $u$ and $v$ are two unimodular matrices such that $uxv$ is the diagonal mattrix whose diagonal is {\tt smith(x)}. The library syntax is $\teb{smith2}(x)$. \subsecref{sort}$(x)$: sort the vector $x$ in ascending order, using the heapsort method. $x$ must be a vector, and its components integers, reals, or fractions. A related function is {\tt indsort} (see above) which gives the indexes of the sorted vector in terms of the initial one. For example, {\tt extract(x,indsort(x))} is equivalent to {\tt sort(x)}. The library syntax is $\teb{sort}(x)$. \subsecref{sqred}$(x)$: \ref{decomposition into squares} of the quadratic form represented by the symmetric matrix $x$. The result is a matrix whose diagonal entries are the coefficients of the squares, and the non diagonal entries represent the bilinear forms. The library syntax is $\teb{sqred}(x)$. \subsecref{supplement}$(x)$: assuming that the columns of the matrix $x$ are linearly independent (if they are not, an error message is issued), find a square invertible matrix whose first columns are the columns of $x$, i.e. supplement the columns of $x$ to a basis of the whole space. The library syntax is $\teb{suppl}(x)$. \subsecref{trace}$(x)$: This applies to quite general $x$. If $x$ is not a matrix, it is equal to the sum of $x$ and its conjugate, except for polymods where it is the trace as an algebraic number. For $x$ a square matrix, it is the ordinary trace. If $x$ is a non square matrix (but not a vector), an error occurs. The library syntax is $\teb{trace}(x)$. \subsecref{trans}$(x)$ or $x\tilde{\ }$: transpose of $x$. This has an effect only on vectors and matrices. The library syntax is $\teb{gtrans}(x)$. \subsecref{vecsort}$(x,k)$: sort the vector of vectors or matrix $x$ in ascending order of the $k$-th component, using the heapsort method. The components being compared must be of type integer, real or fraction. $k$ can also be a vector, in which case the sorting is done lexicographically according to the components listed in the vector $k$. For example, if $k=[2,1,3]$, sorting will be done with respect to the 2nd-component, and when these are equal with respect to the 1st, and when these are equal with respect to the 3rd. The library syntax is $\teb{vecsort}(x,k)$. \section{Sums, products, integrals and similar functions.} Although the GP calculator is programmable, it is useful to have preprogrammed a number of loops, including sums, products, and a certain number of recursions. Also, a number of functions from numerical analysis like numerical integration and summation of series will be described here. One of the parameters in these loops must be the control variable, hence a simple variable name. The last parameter must be any legal PARI expression, including of course expressions using loops. Since it is much easier to program directly the loops in library mode, these functions are mainly useful for GP programming. The use of these functions in library mode is a little tricky and its explanation will be omitted, although the reader can try and figure it out by himself by reading the source code. A brief explanatory sketch is given in section 11. Hence in this section we only give the library syntax, with no semantic explanation. The letter $X$ will always denote any simple variable name, and represents the formal parameter used in the function. \subsecref{divsum}$(n,X,expr)$: sum of expression $expr$ over the positive divisors of $n$. In the present version \vers, $n$ is restricted to being less than $2^{31}$. The library syntax is \tec{divsomme}{(entree *ep, GEN num, char *ch)}. \subsecref{hvector}$(n,X,expr)$: creates a row vector with $n$ components whose components are the expression $expr$ evaluated at the integral points between 1 and $n$. The library syntax is \tec{vecteur}{(entree *ep, GEN nmax, char *ch)}. \subsec{(numerical) integration}:\sref{numerical integration} A number of Romberg-like integration methods are implemented. The user should not require too much accuracy: 18 or 28 decimal digits is OK, but not much more. In addition, analytical cleanup of the integral must have been done: there must be no singularities in the interval or at the boundaries. In practice this can be accomplished with a simple change of variable. Furthermore, for improper integrals, where one or both of the limits of integration are plus or minus infinity, the function must decrease sufficiently rapidly at infinity. This can often be accomplished through integration by parts. Note that \ref{infinity} can be represented with essentially no loss of accuracy by 1e4000. However beware of real underflow when dealing with rapidly decreasing functions. For example, if one wants to compute the $\int_0^\infty e^{-x^2}\,dx$ to 28 decimal digits, one should set infinity equal to 10 for example, and certainly not to 1e4000. The integrand may have values belonging to a vector space over the real numbers; in particular, it can be complex-valued or vector-valued. \subsecref{intgen}$(X=a, b, expr)$: general driver routine for doing numerical integration from $a$ to $b$ of the expression $expr$, with respect to the formal variable $X$. The library syntax is \tec{rombint}{(entree *ep, GEN a, GEN b, char *ch, long int prec)}. \subsecref{intinf}$(X=a, b, expr)$: numerical integration from $a$ to $b$, tailored for being used when $a$ or $b$ are infinite. One {\sl must} have $ab>0$, and in fact if for example $b=\infty$, then it is preferable to have $a$ as large as possible, at least $a\ge1$. The library syntax is \tec{qromi}{(entree *ep, GEN a, GEN b, char *ch, long int prec)}. \subsecref{intnum}$(X=a,b,expr)$: simple numerical integration from $a$ to $b$. This is the fastest method, and should be used when $a$ and $b$ are not too large, the function is smooth, and can be evaluated exactly everywhere on the interval $[a,b]$. The library syntax is \tec{qromb}{(entree *ep, GEN a, GEN b, char *ch, long int prec)}. \subsecref{intopen}$(X=a,b,expr)$: numerical integration from $a$ to $b$. This method should be used, again when $a$ and $b$ are not too large, but when the function is now allowed to be undefined (but continuous) at $a$ or $b$, for example the function $\sin(x)/x$ at $x=0$. The library syntax is \tec{qromo}{(entree *ep, GEN a, GEN b, char *ch, long int prec)}. Two summation methods are also implemented, for alternating series, and for series with terms of the same sign (see {\tt sumalt} and {\tt sumpos} below). \subsecref{matrix}$(m,n,X,Y,expr)$: creation of the $m\times n$ matrix whose coefficients are given by the expression $expr$. There are two formal parameters in $expr$, the first one ($X$) corresponding to the rows, the second ($Y$) to the columns, and $X$ goes from 1 to $m$, $Y$ goes from 1 to $n$. The library syntax is \tec{matrice}{(entree *ep1, entree *ep2, GEN nlig, GEN ncol, char *ch)}. \subsecref{prod}$(x,X=a,b,expr)$: product of expression $expr$, initialized at $x$, the formal parameter $X$ going from $a$ to $b$. As for {\tt sum}, the initialization parameter $x$ must be given: its main purpose is to force the type of the operations being performed. For example if it is put equal to the integer 1, operations will start being done exactly. If it is put equal to the real $1.$, they will be done using real numbers having the default precision. If it is put equal to the power series $1+O(X^k)$ for a certain $k$, they will be done using power series of precision at most $k$. These are the three most common initializations. As an extreme example, compare $$\text{prod}(1,j=1,100,(1-X\hat{\ }j))$$ with $$\text{prod}(1+O(X\hat{\ }101),j=1, 100, (1-X\hat{\ }j) ).$$ The library syntax is \tec{produit}{(entree *ep, GEN x, GEN a, GEN b, char *ch)}. \subsecref{prodeuler}$(X=a,b,expr)$: product of expression $expr$, initialized at 1., the formal parameter $X$ ranging over the prime numbers between $a$ and $b$.\sref{Euler product} The library syntax is \tec{prodeuler}{(entree *ep, GEN a, GEN b, char *ch, long int prec)}. \subsecref{prodinf}$(X=a,expr)$: \ref{infinite product} of expression $expr$, the formal parameter $X$ starting at $a$. The evaluation stops when the relative error of the expression minus 1 is less than the default precision. The expressions must always evaluate to an element of $\Bbb C$. The library syntax is \tec{prodinf}{(entree *ep, GEN a, char *ch, long int prec)}. \subsecref{prodinf1}$(X=a,expr)$: infinite product of expression $1+expr$, the formal parameter $X$ starting at $a$. The evaluation stops when the relative error of the expression is less than the default precision. The expressions must always evaluate to an element of $\Bbb C$. The library syntax is \tec{prodinf1}{(entree *ep, GEN a, char *ch, long int prec)}. \subsecref{solve}$(X=a,b,expr)$: real root of expression $expr$ between $a$ and $b$, under the condition $expr(X=a)*expr(X=b)\le0$. The method used is Brent's method. The library syntax is \tec{zbrent}{(entree *ep, GEN a, GEN b, char *ch, long int prec)}. \subsecref{sum}$(x,X=a,b,expr)$: sum of expression $expr$, initialized at $x$, the formal parameter going from $a$ to $b$. As for {\tt prod}, the initialization parameter $x$ must be given: its main purpose is to force the type of the operations being performed. For example if it is put equal to the integer 0, operations will start being done exactly. If it is put equal to the real $0.$, they will be done using real numbers having the default precision. If it is put equal to the power series $O(X^k)$ for a certain $k$, they will be done using power series of precision at most $k$. These are the three most common initializations. As an extreme example, compare $$\text{sum}(0,j=1, 1000, 1/j)$$ with $$\text{sum}(0.,j=1, 1000, 1/j ).$$ The library syntax is \tec{somme}{(entree *ep, GEN x, GEN a, GEN b, char *ch)}. \subsecref{sumalt}$(X=a, expr)$: numerical summation of the series $expr$, which should be an \ref{alternating series}, the formal variable $X$ starting at $a$. The algorithm used is Euler's method of finite differences combined with a trick due to van Wijngaarden. Beware that the stopping criterion is that the term gets small enough, hence terms which are equal to 0 will create problems and should be removed. Divergent alternating series can sometimes be summed by this method, as well as series which are not exactly alternating (see for example section 11). The library syntax is \tec{sumalt}{(entree *ep, GEN a, char *ch, long int prec)}. \subsecref{suminf}$(X=a,expr)$: \ref{infinite sum} of expression $expr$, the formal parameter $X$ starting at $a$. The evaluation stops when the relative error of the expression is less than the default precision. The expressions must always evaluate to an element of $\Bbb C$. The library syntax is \tec{suminf}{(entree *ep, GEN a, char *ch, long int prec)}. \subsecref{sumpos}$(X=a,expr)$: numerical summation of the series $expr$, which must be a series of terms having the same sign, the formal variable $X$ starting at $a$. The algorithm used is van Wijngaarden's trick for converting such a series into an alternating one, and is quite slow. Beware that the stopping criterion is that the term gets small enough, hence terms which are equal to 0 will create problems and should be removed. The library syntax is \tec{sumpos}{(entree *ep, GEN a, char *ch, long int prec)}. \subsecref{vector}$(n,X,expr)$: creates a row vector with $n$ components whose components are the expression $expr$ evaluated at the integral points between 1 and $n$ (identical with {\tt hvector}). The library syntax is \tec{vecteur}{(entree *ep, GEN nmax, char *ch)}. \subsecref{vvector}$(n,X,expr)$: creates a column vector with $n$ components whose components are the expression $expr$ evaluated at the integral points between 1 and $n$. The library syntax is \tec{vvecteur}{(entree *ep, GEN nmax, char *ch)}. \section{Plotting functions.} Although plotting is not the main purpose of Pari, a number of plotting functions are provided. These functions are either high-level plotting functions (all the functions starting with {\tt plot}) in which the user has little to do but explain what type of plot he wants, and whose syntax is similar to the one used in the preceding section. Or they can be low-level plotting functions, where every drawing primitive (point, line, box, etc...) must be specified by the user. These low-level functions (called rectplot functions) work as follows. You have at your disposal 16 virtual windows which are filled independently, and can then be physically ORed on a single window at user-defined positions. These rectwindows are numbered from 0 to 15, and must be initialized before being used by the function {\tt initrect}, which specifies the height and width of the virtual window. At all times, a virtual cursor (initialized at $[0,0]$) is associated to the window, and its current value can be obtained using the function {\tt cursor}. A number of primitive graphic objects can then be drawn in these windows, and only the part of the object which is inside the window will be drawn, with the exception of polygons and strings which are drawn entirely (but the virtual cursor can move outside of the window). Finally, the actual physical drawing is done using the function {\tt draw}. Note that the windows are preserved so that further drawings using the same windows at different positions or different windows can be done without extra work. If you want to erase a window (and free the corresponding memory), use the function {\tt killrect}. It is not possible to partially erase a window. Erase it completely, initialize it again and then fill it with the graphic objects that you want to keep. In addition to initializing the window, you may want to have a scaled window to avoid unnecessary conversions. For this, use the function {\tt scale} below. As long as this function is not called, the scaling is simply the number of pixels, the origin being at the upper left and the $y$-coordinates going downwards. Finally, note that in the same way that {\tt texprint} allows you to have a \TeX{} output corresponding to printed results, the functions starting with {\tt post} allow you to have {\tt postscript} output of the plots. This will not be absolutely identical with the screen output, but will be sufficiently close. Note that you can use postscript output even if you do not have the plotting routines enabled. The postscript output is written in a file called {\tt pari.ps}. Each time a new postscript output is asked for the postscript output is appended to that file. Hence the user must remove this file first if he does not want unnecessary drawings from preceding sessions to appear. On the other hand, in this manner as many plots as desired can be kept in a single file. \smallskip \subsecref{box}$(w,x2,y2)$: let $(x1,y1)$ be the current position of the virtual cursor. Draw in the rectwindow $w$ the outline of the rectangle which is such that the points $(x1,y1)$ and $(x2,y2)$ are opposite corners. Only the part of the rectangle which is in $w$ is drawn. The virtual cursor does {\it not} move. The library syntax is $\teb{rectbox}(w,x2,y2)$ where $w$ is a C-integer. \subsecref{cursor}$(w)$: give as a 2-component vector the current (scaled) position of the virtual cursor corresponding to the rectwindow $w$. The library syntax is $\teb{rectcursor}(w)$ where $w$ is a C-integer. \subsecref{draw}$(list)$: physically draw the rectwindows given in $list$ which must be a vector whose number of components is divisible by 3. If $list=[w1,x1,y1,w2,x2,y2,\dots]$, the windows $w1$, $w2$, etc... are physically placed with their upper left corner at physical position $(x1,y1)$, $(x2,y2)$, \dots respectively, and are then drawn together. Overlapping regions will thus be drawn twice, and the windows are considered transparent. The library syntax is $\teb{rectdraw}(list)$. Note that in the present version \vers{} this function has been written for the X11-window system (hence also for GUI's based on X11 such as Openwindows and Motif), and for Sunview/Suntools. \subsecref{initrect}$(w,x,y)$: initialize the rectwindow $w$ to width $x$ and height $y$, and position the virtual cursor at $(0,0)$. The library syntax is $\teb{initrect}(w,x,y)$ where all 3 arguments are C-integers. \subsecref{killrect}$(w)$: erase rectwindow $w$ and free the corresponding memory. Note that if you want to use the rectwindow $w$ again, you must use {\tt initrect} first to specify the new size. The library syntax is $\teb{killrect}(w)$ where $w$ is a C-integer. \subsecref{line}$(w,x2,y2)$: let $(x1,y1)$ be the position of the virtual cursor. Draw in the rectwindow $w$ the part of the segment $(x1,y1)-(x2,y2)$ which is inside $w$, and move the virtual cursor to $(x2,y2)$ (even if it is outside the window). If you want to draw a line from $(x1,y1)$ to $(x2,y2)$ where $(x1,y1)$ is not necessarily the position of the virtual cursor, use {\tt move(w,x1,y1)} before using the {\tt line} function. The library syntax is $\teb{rectline}(w,x2,y2)$ where $w$ is a C-integer. \subsecref{lines}$(w,listx,listy)$: draw on the rectwindow $w$ the polygon such that the (x,y)-coordinates of the vertices are in the vectors of equal length $listx$ and $listy$. The virtual cursor does not move. This is basically the same function as the function {\tt ploth2}, but with no scaling factors. Note that to obtain a closed polygon, the first and last point must be the same. Finally, for simplicity, the whole polygon is drawn, not only the part of the polygon which is inside the rectwindow. The library syntax is $\teb{rectlines}(w,listx,listy)$ where $w$ is a C-integer. \subsecref{move}$(w,x,y)$: move the virtual cursor of the rectwindow $w$ to position $(x,y)$. The library syntax is $\teb{rectmove}(w,x,y)$ where $w$ is a C-integer. \subsecref{plot}$(X=a, b, expr)$: crude plot of the function represented by expression $expr$ from $a$ to $b$. The library syntax is \tec{plot}{(entree *ep, GEN a, GEN b, char *ch)}. \subsecref{ploth}$(X=a,b,expr)$: high precision plot of the function $y=f(x)$ represented by the expression $expr$, $x$ going from $a$ to $b$. Since this involves around 1000 function calls, it is advised to keep the current precision to a minimum (i.e. 9) before calling {\tt ploth}. Note that in the present version \vers{} this function has been written for the Macintosh, the X11-window system (hence also for GUI's based on X11 such as Openwindows and Motif), and for Sunview/Suntools. An Atari/gem version is also available upon request. The library syntax is \tec{ploth}{(entree *ep, GEN a, GEN b, char *ch, long int prec)}. \subsecref{ploth2}$(T=a,b,expr)$: high precision plot of the curve represented in parametric form by $x=f(t),y=g(t)$, represented by the expression $expr$, $t$ going from $a$ to $b$. The expression must be a two component vector. Since this involves around 2000 function calls, it is advised to keep the current precision to a minimum (i.e. 9) before calling {\tt ploth2}. Note that in the present version \vers{} this function has been written for the Macintosh, the X11-window system (hence also for GUI's based on X11 such as Openwindows and Motif), and for Sunview/Suntools. An Atari/gem version is also available upon request. The library syntax is \tec{ploth2}{(entree *ep, GEN a, GEN b, char *ch, long int prec)}. \subsecref{plothraw}$(listx,listy)$: high precision plot of the points whose (x,y)-coordinates are in the vectors of equal length listx and listy. Automatic positioning and scaling is done, but with the same scaling factor on $x$ and $y$. The library syntax is $\teb{plothraw}(listx,listy)$. Note that in the present version \vers{} this function has been written for the X11-window system (hence also for GUI's based on X11 such as Openwindows and Motif), and for Sunview/Suntools. \subsecref{point}$(w,x,y)$: draw the point $(x,y)$ on the rectwindow $w$ (if it is inside $w$), and in any case move the virtual cursor to position $(x,y)$. The library syntax is $\teb{rectpoint}(w,x,y)$ where $w$ is a C-integer. \subsecref{points}$(w,listx,listy)$: draw on the rectwindow $w$ the points whose (x,y)-coordinates are in the vectors of equal length $listx$ and $listy$ and which are inside $w$. The virtual cursor does not move. This is basically the same function as the function {\tt plothraw}, but either with no scaling factor or with a scale chosen using the function {\tt scale}. The library syntax is $\teb{rectpoints}(w,listx,listy)$ where $w$ is a C-integer. \subsecref{postdraw}$(list)$: same as {\tt draw}, except that the output is a postscript program appended to the file {\tt pari.ps}. The library syntax is $\teb{postdraw}(list)$. \subsecref{postploth}$(X=a,b,expr)$: same as {\tt ploth}, except that the output is a postscript program appended to the file {\tt pari.ps}. The library syntax is \tec{postploth}{(entree *ep, GEN a, GEN b, char *ch)}. \subsecref{postploth2}$(T=a,b,expr)$: same as {\tt ploth2}, except that the output is a postscript program appended to the file {\tt pari.ps}. The library syntax is \tec{postploth2}{(entree *ep, GEN a, GEN b, char *ch)}. \subsecref{postplothraw}$(listx,listy)$: same as {\tt plothraw}, except that the output is a postscript program appended to the file {\tt pari.ps}. The library syntax is $\teb{postplothraw}(listx,listy)$. \subsecref{rbox}$(w,dx,dy)$: draw in the rectwindow $w$ the outline of the rectangle which is such that the points $(x1,y1)$ and $(x1+dx,y1+dy)$ are opposite corners, where $(x1,y1)$ is the current position of the cursor. Only the part of the rectangle which is in $w$ is drawn. The virtual cursor does {\it not} move. The library syntax is $\teb{rectrbox}(w,dx,dy)$ where $w$ is a C-integer. \subsecref{rline}$(w,dx,dy)$: draw in the rectwindow $w$ the part of the segment $(x1,y1)-(x1+dx,y1+dy)$ which is inside $w$, where $(x1,y1)$ is the current position of the virtual cursor, and move the virtual cursor to $(x1+dx,y1+dy)$ (even if it is outside the window). The library syntax is $\teb{rectrline}(w,dx,dy)$ where $w$ is a C-integer. \subsecref{rmove}$(w,dx,dy)$: move the virtual cursor of the rectwindow $w$ to position $(x1+dx,y1+dy)$, where $(x1,y1)$ is the initial position of the cursor (i.e. to position $(dx,dy)$ relative to the initial cursor). The library syntax is $\teb{rectrmove}(w,dx,dy)$ where $w$ is a C-integer. \subsecref{rpoint}$(w,dx,dy)$: draw the point $(x1+dx,y1+dy)$ on the rectwindow $w$ (if it is inside $w$), where $(x1,y1)$ is the current position of the cursor, and in any case move the virtual cursor to position $(x1+dx,y1+dy)$. The library syntax is $\teb{rectrpoint}(w,dx,dy)$ where $w$ is a C-integer. \subsecref{scale}$(w,x1,x2,y1,y2)$: scale the local coordinates of the rectwindow $w$ so that $x$ goes from $x1$ to $x2$ and $y$ goes from $y1$ to $y2$ ($x2b$. $a$ and $b$ must be in $\Bbb R$. \subsubsecref{fordiv}$(n,X,seq)$: the formal variable $X$ ranging through the positive divisors of $n$, the sequence $seq$ is evaluated. $n$ must be of type integer. \subsubsecref{forprime}$(X=a,b,seq)$: the formal variable $X$ ranging over the prime numbers between $a$ to $b$ (including $a$ and $b$ if they are prime), the $seq$ is evaluated. Nothing is done if $a>b$. Note that $a$ and $b$ must be in $\Bbb R$. \subsubsecref{forstep}$(X=a,b,s,seq)$: the formal variable $X$ going from $a$ to $b$, in increments of $s$, the $seq$ is evaluated. Nothing is done if $s>0$ and $a>b$ or if $s<0$ and $a$. This tells GP that what you will write on the next line is the physical continuation of what you have just written. In other words, it makes GP forget your newline character. For example if you use this while defining a function, and if you ask for the definition of the function using {\tt ?name}, you will see that your backslash has disappeared and that everything is on the same line. You can type a $\backslash$ anywhere. It will be interpreted as above only if it is immediately followed by a newline. For example, you can type {\tt 3+$\backslash$} {\tt 4} instead of typing {\tt 3+4}. The second one cannot be used everywhere, but is in general more useful. It is the use \sref{brace characters} of braces '$\{$' and '$\}$'. When GP sees an opening brace ('$\{$`) at the beginning of a line, it understands that you are writing a program, and newlines will be ignored (but registered, contrary to when you use a backslash) until you type a closing brace '$\}$'. However, there is an important (but easily obeyed) restriction: inside an open brace-close brace pair, all newlines must occur after a semicolon (';'), i.e. between two expressions forming a $seq$. Of course you can combine the use of backslash and braces. \subsec{The GP/PARI \ref{programming} language}. As we have seen, the GP calculator uses a primitive purely interpreted language. The structure of this language is in fact more reminiscent of LISP with a functional notation, {\tt f(x,y)} rather than {\tt (f x y)}: all programming constructs, such as {\tt if, while,} etc... are functions, and the main loop does not really execute, but rather evaluates (sequences of) expressions. Of course, it is by no means a true LISP. Function names are distinct from variable names: once a name has been used as a variable name, this cannot be changed in the same session. Predefined function names cannot be used for anything else, and the number of actual parameters must match the declaration given in the online help. Identifiers that are used for user-defined functions can be freely redefined for other functions, or totally forgotten (using {\tt kill}) and later reused for a variable, for example. Each variable has a stack of values, implemented as a linked list. When a new scope is entered, during a function call, the value of the actual parameter is pushed on the stack. If the parameter is not supplied, a special $0$ value called {\bf \ref{gnil}} is pushed on the stack (this value is not printed if it is returned as the result of a GP expression sequence). Upon exit, the stack decreases. You can {\tt kill} a variable, decreasing the stack yourself. This should be used only at the top level of GP, to undo the effect of an assignment, not from a function. However, the stack has a bottom: the value of a variable is the monomial of degree 1 in this variable, as is natural for a mathematician. Note that the iterative constructs which use a variable name ({\tt for, fordiv, forprime, prod, sum, vector, matrix, plot,} etc.) also consider the given variable to be local to the construct. A value is pushed on entry and pulled on exit. So, it is not necessary for a function using such a construct to declare the variable as a dummy formal parameter. In particular, in our {\tt zet} example above, the variable {\tt j} need not be declared. Otherwise, it is strongly recommended to declare in this way all other variables that are used inside a function: If a function accesses a variable which is not one of its formal parameters, the value used will be the one which happens to be on top of the stack at the time of the call. This could be a ``global'' value, or a local value belonging to any function higher in the call chain. So, be warned. {\bf Implementation note.} For the curious reader, here is how these stacks are handled: a \ref{hashing function} is computed from the identifier, and used as an index in {\tt \ref{hashtable}}, a table of pointers. Each of these pointers begins a linked list of structures (type {\tt \ref{entree}}). The linked list is searched linearly for the identifier (each list will have less than 7 components or so). When the correct {\tt entree} is found, it points to the top of the stack of values for that identifier if it is a variable, to the function itself if it is a predefined function, and to a copy of the text of the function if it is a user-defined function. When an error occurs, all of this maze (rather a tree, in fact) is searched and (hopefully) replaced in the situation preceding the last call of the main evaluator. \section{Using GP under \ref{gnuemacs}.} Thanks to the help of Annette Hoffman from the university of Saarbr\"ucken, and since version 1.34.05 from David Carlisle from the university of Manchester, it is possible and in fact desirable to use GP as a subprocess of gnuemacs. This is of course possible only if gnuemacs has been installed on your machine. To use this, you must include in your {\tt .emacs} file the following line: {\tt (load "\ref{pari}" nil t)} where {\tt pari.el} is the name of the file that will have to be loaded by gnuemacs (if you have changed the name, or if you have the file in a different directory, you must of course supply the correct name). This file is included in the PARI distribution. Once this is done, under gnuemacs if you type {\tt M-x gp} (where as usual M is the Meta key, i.e. Escape, or on SUN keyboards, the Left key), a special shell will be started, which in particular launches GP with the default stack size, prime limit and input buffer size. If you type instead {\tt C-u M-x gp}, you will be asked for the name of the GP executable, the stack size, the prime limit and the input buffer size before the execution of GP begins. If for any of these you simply type return, the default value will be used (on Unix machines it will be {\tt /usr/local/bin/gp} for the executable, 4000000 for the stack, 500000 for the prime limit and 30000 for the buffer size). \smallskip You can then work as usual under GP, but with two notable advantages. First and foremost, you have at your disposal all the facilities of a text editor like emacs, in particular for correcting or copying blocks. Second, you can have an on-line help which is much more complete than what you obtain by typing {\tt ?name}. This is done by typing M-? (where M is the Meta key). In the minibuffer, emacs asks what function you want to describe, and after your reply you obtain the description which is in the users manual, including the description of functions (such as $\backslash$, $\%$) which use special symbols. This help system can also be menu-driven, by using the command {\tt M-\char`\\ c} which opens a help menu window which enables you to choose the category of commands for which you want an explanation. Finally you can use command completion in the following way. After the prompt, type the first few letters of the command, then M-TAB where TAB is the TAB key (of course not the letters T,A,B). If there exists a unique command starting with the letters you have typed, the command name will be completed. If not, either the list of commands starting with the letters you typed will be displayed in a separate window (which you can then kill by typing as usual C-x 1 or by typing in more letters), or ``no match found'' will be displayed in the Emacs command line. \smallskip You also have at your disposal a few other commands. Read the file pari.txt for details. Note that if for some reason the session crashes (due to a bug in your program or in the PARI system), you will usually stay under emacs, but the GP buffer will be killed. To recover it, simply type again M-x gp (or C-u M-x gp), and a new session of GP will be started after the old one, so you can recover what you have typed. Note that this will of course {\sl not} work if for some reason you exited emacs before coming back (except for the C-z temporary stopping command). \vfill\eject