\documentclass{article}

\usepackage{openmathcd}

\errorcontextlines=999

\DeclareTextSymbolDefault{\textquotedbl}{T1}
\DeclareHarmlessAccent{\"}{0308}

\begin{document}

\begin{OpenMathCD}{polyd-not}

  \StandardOMLicence
% <CDBase>http://www.openmath.org/cd</CDBase> 
%    <CDURL> http://www.openmath.org/cd/polyd.ocd </CDURL>
%    <CDReviewDate>2006-03-30</CDReviewDate> 
  \CDDate{2004-03-30}
  \CDStatus{experimental}
  \CDVersion{4}{1}
  
%    <Description>
%      This CD contains operators to deal with polynomials and more precisely 
%      Distributed Multivariate Polynomials.
%    </Description>

% <CDComment>
Original OpenMath v1.1 Poly 1997\par
Update to Current Format 1999-07-07 DPC\par
Move the names of rings to setname.ocd 1999-11-09 JHD\par
Delete those items moved to the new poly.ocd 1999-11-14 JHD\par
Update following Abbott/Davenport/Strotmann at Dagstuhl 2001-10-12 
JHD\par
Added example to weighted\_degree 2002-09-17 JHD\par
Experimental conversion to literate form begun 2014-03-01 LH
% </CDComment>

% <CDComment>

 \subsection{Abstract}

 This is our attempt at defining a first Content Dictionary to deal with
 polynomials. There are many possible choices for a polynomial CD, and
 several questions to answer. 

 The reader may feel that this content dictionary is quite different in
 spirit from the ``Basic'' one. Although it basically defines a set of concepts
 related to polynomials (such as degree, factorization, resultant\dots), there
 are two new points here:
 \begin{itemize}
 \item
   a certain emphasis on representation issues (including structural
   constraints on some OM objects),
 \item
   an attempt to specify some ``computational behaviour'' of an OM application
   that handles (part of) this CD.
 \end{itemize}
 
 As some people may disagree with some of our choices, we will try to justify
 them in this rather long foreword. 
 
 \subsection{Representation issues}

 One of the interest of OM is certainly to enable the use of specialized
 servers. It is important to promote the writing of OM-compliant servers by
 placing as few constraints as possible on the programmers of these
 packages. This CD has been designed with the idea that it could be simple to
 use for a server dealing only with polynomial computations. Hence we have
 used a particular representation for polynomials (distributed with dense
 monomials). This representation is rather abstract in the sense that it does
 not introduce names for variables. It explicitly contains the polynomial
 ring a polynomial belongs to as the set of the coefficients and the number
 of variables. It seems (from our experience) that this information is
 necessary for most specialized servers. 

 Expressing constraints on the structure of OM objects made from the symbols
 in this CD is not always easy. One of the main reason is that a symbol such
 as \texttt{gcd} is meant to denote the GCD of a set of polynomials, no matter how
 the polynomials are represented. Such a function should thus accept both
 ``symbolic'' arguments (a list of symbolic object meant to be polynomials) and
 the polynomials in the specific representation defined in this CD. Of
 course, another solution will be to have one \texttt{gcd} for one (or several)
 particular representation and another \texttt{gcd} to express the general notion
 of polynomial GCD. We though that the solution we chose was more in the
 spirit of ``Basic'' and the discussions of the last OpenMath meeting.

 A question which is not entirely answered is whether or not it is
 interesting to have ``symbolic'' objects inside some constructors (such as a
 power which is not an OM integer in \texttt{Monom} or a symbolic \texttt{PolyRingD} 
 (a variable) as an argument of \texttt{DMP}). We explicitly forbid that in the first
 version of this CD.

 Note that we did not try to express the constraints with signatures in this
 version because we did not find a really satisfactory solution.
 
 
 \subsection{Specifying some ``computational behaviour''}

 Of course it would be of no use to exactly specify the behaviour of any OM
 application that receives an OM object. There are (at least) two reasons for
 that:
 \begin{itemize}
 \item
   an OM object is intended to represent a mathematical object and thus the
   same OM object could be sent to a typesetter as well as to a symbolic
   computation system,
 \item
   even when dealing with programs that compute, exact specifications could be
   impossible or too much constraining for a given system.
 \end{itemize}
 
 On the other hand, we believe that one of the goal of OM is certainly that a
 program needing to factorize an integer could transparently use Maple, Axiom
 or Pari to do the job. This is of course possible only if all severs that
 ``implement'' (in the sense of really performing) the mathematical notion of
 integer factorization answer in a similar way. In other words, we should not
 hesitate to specify what a particulary useful class of OM applications (the
 ``computing'' ones) should return (the form of the result) everytime
 compliance to this specification is simple enough because it is obviously
 very useful. We have tried to express this idea in this CD through some
 comments and the use of symbols such as \texttt{factored} or 
 \texttt{groebnered} that describe the required results of some functions. 
 
 The general ``compliance'' rule can be stated as:
 \begin{quote}
   an OM application that understands this CD and implements some of the 
   polynomials operation described is required to implement them using the
   constructors defined in this CD, as indicated in the comments associated
   with the operations.
 \end{quote}

 This means that if the OM version of a computer algebra system claims to
 implement polynomial factorization, another application can send him an
 OM object as described in the \texttt{factor} comment (the symbol 
 \texttt{factor} applied to one argument, a DMP) and the result will be 
 return as defined : a \texttt{factored} symbol whose arguments are 
 described in the corresponding entry of the poly CD.
% </CDComment>


% <CDComment>
\subsection{Definition of data-structure constructors}
% </CDComment>

% <CDComment>
%      The polynomial x^2*y^6 + 3*y^5 can be encoded as
%      DMP(poly_ring_d(Z, 2), SDMP(term(1, 2, 6), term(3, 0, 5)))
%      if the variables are anonymous, or if they are named, as
%      DMP(poly_ring_d_named(Z, x,y), SDMP(term(1, 2, 6), term(3, 0, 5)))
% 
%      The polynomial 2*y^3*z^5 + x + 1 can be
%      DMP(poly_ring_d(Q, 3), 
%          SDMP(term(2, 0, 3, 5), term(1, 1, 0, 0), term(1, 0, 0, 0)))
% 
%      Note that these are not real encodings but a "term-like" encoding (whose
%      understanding should be trivial) meant for the human readers of this
%      dictionary. Of course, actual encodings can be more compact...
% </CDComment>

\begin{CDDefinition}[application]{DMP}{
  The constructor of DMPs. The first argument is the polynomial
  ring containing the polynomial and the second is a "SDMP". 
  Should be of the form DMP(PolyRingD(...), SDMP(...))
}
\end{CDDefinition}

\begin{CDDefinition}[application]{DMPL}{
  The constructor for lists of multivariate polynomial members of the 
  same polynomial ring. The first argument is a polynomial ring
  and the rest are "SDMP"s. DMPL can be attributed with the "ordering" 
  symbol to indicate a particular ordering for monomials of all its
  polynomials. 
  Should be of the form DMPL(PolyRingD(...), SDMP(...)+)
}
\end{CDDefinition}


\begin{CDDefinition}[application]{SDMP}{
  The constructor for multivariate polynomials without
  any indication of variables or domain for the coefficients.
  Its arguments are just "term"s. No terms should differ only by
  the coefficient (i.e it is not permitted to have both "2*x*y" and
  "x*y" as terms in a SDMP). SDMP can be attributed with 
  the "ordering" symbol to indicate a particular ordering of its
  terms. This attribute shall not be set if the SDMP is part of 
  DMPL that has this attribute set. If the SDMP is ordered, explicitly
  or implicitly via an outer ordering, the terms must be in decreasing
  order with respect to this order. The zero polynomial is represented
  by an SDMP with no terms.
}
\end{CDDefinition}


\begin{CDDefinition}[application]{term}{
  The constructor of terms. Valid applications are of the form
  Term(coeff, exp1, exp2, ... expn)
  which represents the term 
  coeff * var1^exp1*...varn^expn
  where n is the number of variables, expi are non-negative integers.
  coeff should be non-zero.
}
\end{CDDefinition}

% <CDComment>
\subsection{Polynomial ring constructors}
% </CDComment>


\begin{CDDefinition}[application]{poly_ring_d}{
  The constructor of polynomial ring. The first argument is a ring
  (the ring of the coefficients), the second is the number 
  of variables as an integer.
}
\end{CDDefinition}

\begin{CDDefinition}[application]{poly_ring_d_named}{
  The constructor of polynomial ring. The first argument is a ring
  (the ring of the coefficients), the remaining arguments are the 
  names of the variables. The first variable given is the most
  important from the point of view of lexicographic ordering, then
  the second, and so on.
}
\end{CDDefinition}

\begin{CDDefinition}[constant]{anonymous}{
  Indicates a variable that we do not want to name
}
\end{CDDefinition}


% <CDComment>
\subsection{Definitions related to orderings}
% </CDComment>


\begin{CDDefinition}[semantic-attribution]{ordering}{
  Used as an attribute to indicate an ordering of the terms in a
  polynomial or list of polynomials. The value of this attribute
  should be one of the constructors specifying ordering. 
}
\end{CDDefinition}

% <CDComment>
      The following orders on terms have their standards definitions, 
     see, for example, ``Ideals, Varieties and Algorithms'', D. Cox, 
     J.B. Little and D. O'Shea, Springer Verlag.
% </CDComment>

\begin{CDDefinition}[constant]{lexicographic}{
  The lexicographic ordering of terms.
  Note that, if a poly_ring_d_named is used, lexigographic refers
  to the order of the variables in the poly_ring_d_named, not to 
  their order as strings.
}
\end{CDDefinition}


\begin{CDDefinition}[constant]{reverse_lexicographic}{
  The reverse lexicographic ordering of terms.
  Note that, if a poly_ring_d_named is used, lexigographic refers
  to the order of the variables in the poly_ring_d_named, not to 
  their order as strings.
}
\end{CDDefinition}


\begin{CDDefinition}[constant]{graded_lexicographic}{
  Total degree order, graded with the lexicographic ordering.
  Note that, if a poly_ring_d_named is used, lexigographic refers
  to the order of the variables in the poly_ring_d_named, not to 
  their order as strings.
}
\end{CDDefinition}


\begin{CDDefinition}[constant]{graded_reverse_lexicographic}{
  Total degree order, graded with the reverse lexicographic ordering.
  Note that, if a poly_ring_d_named is used, lexigographic refers
  to the order of the variables in the poly_ring_d_named, not to 
  their order as strings.
}
\end{CDDefinition}


\begin{CDDefinition}[constant]{elimination}{
  This is an ordering, which is partially in terms of one
  ordering, and partially in terms of another.
  First argument is a number of variables.
  Second is ordering to apply on the first so many variables.
  Third is an ordering on the rest, to be used to break ties.
}
  \begin{Example}
    \begin{OMOBJ} % xmlns="http://www.openmath.org/OpenMath" version="2.0" cdbase="http://www.openmath.org/cd">
      \begin{OMA}
        \OMS{}{elimination}
        \OMI{1}
        \OMS{}{lexicographic}
        \OMS{}{graded_reverse_lexicographic}
      \end{OMA}
    \end{OMOBJ}
  \end{Example}
\end{CDDefinition}


\begin{CDDefinition}[application]{matrix_ordering}{
  The argument is a matrix with as many columns as indeterminates
  (= rank). Each row in turm is multiplied by the column vector of
  exponents to produce a weighting for comparison purposes.
}
\end{CDDefinition}


\begin{CDDefinition}[application]{weighted}{
  The first argument is a list of integers to act as variable weights,
  and the second is an ordering. The result is an ordering.
}
\end{CDDefinition}


% <CDComment>
  We need a few more orderings\dots
% </CDComment>

% <CDComment>
\subsection{Definition of some other constructors}
% </CDComment>

\begin{CDDefinition}[application]{weighted_degree}{
  The total degree of its argument, taking into account any weights 
  declared. The value returned is an integer: non-negative if the 
  weights are. We note that the degree of 0 is undefined.
}
  \begin{Example}
    The following formula states essentially that if x, y, and z are 
    variables with weighted degrees 1, 2, and 3 respectively, then 
    the weighted degree of the polynomial 1z + 2x^2 + 3y + 4x is 3.
    
    \begin{OMOBJ} % xmlns="http://www.openmath.org/OpenMath" version="2.0" cdbase="http://www.openmath.org/cd">
      \begin{OMA}
        \OMS{relation1}{eq}
        \begin{OMA}
          \OMS{}{weighted_degree}
          \begin{OMA}
            \OMS{}{DMP}
            \begin{OMA}
              \OMS{}{poly_ring_d}
              \OMS{setname1}{Q}
              \OMI{3}
            \end{OMA}
            \begin{OMATTR}
              \begin{OMATP}
                \OMS{}{ordering}
                \begin{OMA}
                  \OMS{}{weighted}
                  \begin{OMA}
                    \OMS{list1}{list}
                    \OMI{1}\OMI{2}\OMI{3}
                  \end{OMA}
                  \OMS{}{graded_lexicographic}
                \end{OMA}
              \end{OMATP}
              \begin{OMA}
                \OMS{}{SDMP}
                \begin{OMA}
                  \OMS{}{term}
                  \OMI{1}
                  \OMI{0}\OMI{0}\OMI{1}
                \end{OMA}
                \begin{OMA}
                  \OMS{}{term}
                  \OMI{2}
                  \OMI{2}\OMI{0}\OMI{0}
                \end{OMA}
                \begin{OMA}
                  \OMS{}{term}
                  \OMI{3}
                  \OMI{0}\OMI{1}\OMI{0}
                \end{OMA}
                \begin{OMA}
                  \OMS{}{term}
                  \OMI{4}
                  \OMI{1}\OMI{0}\OMI{0}
                \end{OMA}
              \end{OMA}
            \end{OMATTR}
          \end{OMA}
        \end{OMA}
        \OMI{3}
      \end{OMA}
    \end{OMOBJ}
  \end{Example}
\end{CDDefinition}

\begin{CDDefinition}[application]{groebnered}{
  The constructor for a Gr\"obner basis (reduced, minimal). The first
  argument is an ordering, the second is the Gr\"obner Basis itself
  (with respect to the ordering) that should be represented as a DMPL.
}
\end{CDDefinition}

\begin{CDDefinition}[semantic-attribution]{completely_reduced}{
  This attribute, attached to a groebnered object, says 'true' if
  the base is fully reduced, i.e. no monomial is divisible by the
  leading monomial of any other polynomial.
}
\end{CDDefinition}


% <CDComment>
\subsection{Definition of operations}
% </CDComment>


\begin{CDDefinition}[application]{plus}{
  The sum. The argument is a DMPL. The sum lies within the same
  "PolyRingD" i.e. a program implementing this operation
  should return a DMP with the same "poly_ring_d" 
  (or "poly_ring_d_named").
}
\end{CDDefinition}

\begin{CDDefinition}[application]{times}{
  The product. The argument is a DMPL. The product lies within the same
  "PolyRingD" i.e. a program implementing this operation
  should return a DMP with the same "poly_ring_d"
  (or "poly_ring_d_named").
}
\end{CDDefinition}

\begin{CDDefinition}[application]{power}{
  The power. First argument is a DMP, second
  argument is the integer power. The power lies within the same
  "PolyRingD"  i.e. a program implementing this operation 
  should return a DMP with the same "poly_ring_d"
  (or "poly_ring_d_named").
}
\end{CDDefinition}

\begin{CDDefinition}[application]{groebner}{
  The Gr\"obner basis (lt-reduced, minimal) of a set of polynomials, 
  with respect to a given ordering. First argument is an ordering, the
  second is a list of polynomials. A program that can compute
  the basis is required to return a "groebnered" object.
}
\end{CDDefinition}

\begin{CDDefinition}[application]{reduce}{
  The reduction of a polynomial with respect to a Gr\"obner basis. 
  First argument is a DMP, the second argument is a "groebnered" 
  object.
  i.e. a program implementing this operation should return a DMP which
  represents the polynomial reduced with respect to the Gr\"obner basis.
}
\end{CDDefinition}

\end{OpenMathCD}


\end{document}