1. INTPS - a collection of polynomial systems

As a first application we tried to specify a framework to unify the different benchmark collections of systems of polynomials as, e.g., [1,2,4,8,11,12]. Each such system of polynomials is defined through a finite basis in a certain polynomial ring $R[{\bf x}]$ in a list of variables ${\bf x}$ over a base domain $R$. It occurs that most examples may be reduced to systems of polynomial with integer coefficients or with coefficients in $R={\bf Z}[{\bf p}]$ where ${\bf p}$ is a list of parameters. We decided to focus on such systems and to define the corresponding table INTPS accordingly.

A system of polynomials in INTPS is defined through its basis, list of variables, and list of parameters. The tags basis, vars, and parameters correspond to these entries. They are the most important tags: basis and vars of level==1, hence, mandatory; parameters of level==2 since for $R={\bf Z}$ there are no parameters.

For uniformity reasons and to ease comparison, we require of a ``valid'' INTPS record, that its basis polynomials are stored in expanded form using the +, *, and ^ operators, and that the monomials of a polynomial and the polynomials of the basis are ordered w.r.t. the degree reverse lexicographical ordering. Based on SINGULAR, the (Perl) INTPS::validate routine defined in the INTPS table module validates, and, if requested, necessary, and possible, ``fixes'' these properties of an INTPS record.

Further tags are defined to collect background information about the different polynomial systems. Background information may be of structural or relational type. Structural information about a polynomial system concerns invariant properties of the basis and the ideal generated by it, e.g., lists of the lengths and degrees of the basis polynomials, the dimension or degree of the ideal, a prime or primary decomposition of the ideal, or certain parameters of such a description. Several optional tags, like llist, dlist, dim, degree, isoPrimes, isoPrimeDims, etc., and Perl routines are defined to collect or even generate such information.

Relational information relates the polynomial systems to other tables. This might be a bibliography reference of the origin of the example, bibliography references of papers that considered the example, a problem description of where the example came from or how it was generated from certain parameters, etc. Since relational information relates two tables we have to declare one of them as foreign and to attach the information to the other table. For INTPS, we define optional tags BIB containing a reference to the original bibliography source described in the BIB table and PROBLEMS containing a reference to a problem description in the PROBLEMS table. For the bibliography references to papers that consider the given example we declare the INTPS table as foreign, i.e., we define a corresponding INTPS tag in the BIB table. The main reason for this decision is persistence in the sense that we do not need to change an INTPS record each time a new publication refers to it. For similar reasons, the bibliography reference of the origin is attached to the INTPS table, not to BIB. Note that it is not always as easy as here to make such a judicious decision.

For integrity reasons, we furthermore need to assure that there are no ``equal'' records in our collection of INTPS records. The first problem we face here, is to decide what we actually mean by ``equality'' of INTPS records. Possible definitions range from equality of the ideals generated by the basis polynomials up to string equality of the basis tag values. With benchmark computations in mind, we decided on the following definition: Let $F=(f_1,\ldots, f_n) \in R[x_1,\ldots,x_m]^n$, $G=(g_1,\ldots,g_n) \in R[y_1, \ldots, y_m]^n$ be $n$-tuples of polynomials. Then we define $F$ to be equal to $G$ iff there exist permutations $\pi \in S_m, \sigma \in S_n$ such that

$$f_i(y_{\pi(1)},\ldots,y_{\pi(m)}) = g_{\sigma(i)}$$

for all $1 \le i \le n$.

Having this definition at hand, we still need effective methods to actually determine the equality of two INTPS records: a brute-force, trial-and-error method is certainly computationally infeasible, since already by now we have INTPS records with polynomials in more than 40 variables. For this purpose, the first author has developed and implemented within SINGULAR an algorithm which uses structural information of the polynomials to significantly cut-down the number of possible permutations. Tested with random permutations on about 500 examples from our collection, the implementation needs at most a minute or so to recover the input permutations and hence, to decide the equality of INTPS records in the above sense. Details of the algorithm and its implementation will be given in a forthcoming publication.