%% for a long time these were red and blue by default, %% now black, but keep variables to overwrite \definecolor{FuncColor}{rgb}{0.0,0.0,0.0} %% strange name because of pdflatex bug: \definecolor{Chapter }{rgb}{0.0,0.0,0.0} \definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064}
% write page numbers to a .pnr log file for online help \newwrite\pagenrlog \immediate\openout\pagenrlog =\jobname.pnr \immediate\write\pagenrlog{PAGENRS := [} \newcommand{\logpage}[1]{\protect\write\pagenrlog{#1, \thepage,}} %% were never documented, give conflicts with some additional packages
\newcommand{\GAP}{\textsf{GAP}}
%% nicer description environments, allows long labels \usepackage{enumitem} \setdescription{style=nextline}
{\Huge 0.17 \mbox{}}\\[1cm]
{ 11 September 2025 \mbox{}}\\[1cm] \mbox{}\\[2cm]
{\Large\textbf{ Gareth A. Evans\\ \mbox{}}}\\
{\Large\textbf{ Christopher D. Wensley\\ \mbox{}}}\\ \hypersetup{pdfauthor= Gareth A. Evans\\
; Christopher D. Wensley\\
} \end{center}\vfill
\mbox{}\\
{\mbox{}\\ \small\noindent\textbf{ Gareth A. Evans\\
} Email: \href{mailto://gareth@mathemateg.com} {\texttt{gareth@mathemateg.com}}\\ Address: \begin{minipage}[t]{8cm}\noindent
Ysgol y Creuddyn \\
Ffordd Derwen, Bae Penrhyn \\
Llandudno, LL30 3LB \\
U.K.\\ \end{minipage}
}\\
{\mbox{}\\ \small\noindent\textbf{ Christopher D. Wensley\\
} Email: \href{mailto://cdwensley.maths@btinternet.com} {\texttt{cdwensley.maths@btinternet.com}}\\
Homepage: \href{https://github.com/cdwensley} {\texttt{https://github.com/cdwensley}}}\\ \end{titlepage}
\newpage\setcounter{page}{2}
{\small \section*{Abstract} \logpage{[ 0, 0, 1 ]}
The \textsf{IBNP} package provides methods for computing an involutive (Gr{\"o}bner) basis $B$ for an ideal $J$ over a polynomial ring $R$ in both the commutative and noncommutative cases.
Secondly, methods are provided to involutively reduce a given polynomial to
its normal form in $R/J$.
Bug reports, comments, suggestions for additional features, and offers to
implement some of these, will all be very welcome.
Please submit any issues at \href{https://github.com/gap-packages/ibnp/issues/} {\texttt{https://github.com/gap\texttt{\symbol{45}}packages/ibnp/issues/}} or send an email to the second author at \href{mailto://cdwensley.maths@btinternet.com} {\texttt{cdwensley.maths@btinternet.com}}.
\mbox{}}\\[1cm]
{\small \section*{Copyright} \logpage{[ 0, 0, 2 ]}
{\copyright} 2024\texttt{\symbol{45}}2025, Gareth Evans and Chris Wensley.
The \textsf{IBNP} package is free software; you can redistribute it and/or modify it under the
terms of the GNU General Public License as published by the Free Software
Foundation; either version 2 of the License, or (at your option) any later
version. \mbox{}}\\[1cm]
{\small \section*{Acknowledgements} \logpage{[ 0, 0, 3 ]}
This documentation was prepared with the \textsf{GAPDoc} \cite{GAPDoc} and \textsf{AutoDoc} \cite{AutoDoc} packages.
The procedure used to produce new releases uses the package \textsf{GitHubPagesForGAP} \cite{GitHubPagesForGAP} and the package \textsf{ReleaseTools}.
\mbox{}}\\[1cm] \newpage
\def\contentsname{Contents\logpage{[ 0, 0, 4 ]}}
\tableofcontents \newpage
\chapter{\textcolor{Chapter }{Introduction}}\label{chap-intro} \logpage{[ 1, 0, 0 ]} \hyperdef{L}{X7DFB63A97E67C0A1}{}
{
The \textsf{IBNP} package provides methods for computing an involutive (Gr{\"o}bner) basis $B$ for an ideal $J$ over a polynomial ring $\mathbb{R}$ in both the commutative and noncommutative cases. Secondly, methods are
provided to involutively reduce a given polynomial to its normal form in $\mathbb{R}/J$.
This package was started using \textsf{GAP} 4.13.1 and first released with \textsf{GAP} 4.15.0.
The package is loaded with the command \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
The package may be obtained as a compressed \texttt{.tar} file \texttt{IBNP\texttt{\symbol{45}}0.16.tar.gz} from the GitHub release site: \href{https://github.com/gap-packages/ibnp/releases/tag/v0.16} {\texttt{https://github.com/gap\texttt{\symbol{45}}packages/ibnp/releases/tag/v0.16}}. \index{GitHub repository} The package also has a GitHub repository at: \href{https://github.com/gap-packages/ibnp} {\texttt{https://github.com/gap\texttt{\symbol{45}}packages/ibnp}}.
Once the package is loaded, the manual \texttt{doc/manual.pdf} can be found in the documentation folder. The \texttt{html} versions, with or without MathJax, may be rebuilt as follows:
\section{\textcolor{Chapter }{History}}\label{sec-history} \logpage{[ 1, 1, 0 ]} \hyperdef{L}{X811375BC7CA25F51}{}
{
The theoretical basis behind this package is the Ph.D. thesis "Noncommutative
Involutive Bases" of Gareth Evans in 2005 \cite{gareth-thesis}. (The main concepts and results may also be found in the papers \cite{Beaumont} and \cite{EW-JSC}.) We quote here the summary from that thesis.
\emph{The theory of Gr{\"o}bner Bases originated in the work of Buchberger \cite{buchberger} and is now considered to be one of the most important and useful areas of
symbolic computation. A great deal of effort has been put into improving
Buchberger's algorithm for computing a Gr{\"o}bner Basis, and indeed in
finding alternative methods of computing Gr{\"o}bner Bases. Two of these
methods include the Gr{\"o}bner Walk method \cite{onthewalk} and the computation of Involutive Bases \cite{yuyu}.}
\emph{By the mid 1980's, Buchberger's work had been generalised for noncommutative
polynomial rings by Bergman \cite{bergman} and Mora \cite{mora}. This thesis provides the corresponding generalisation for Involutive Bases
and (to a lesser extent) the Gr{\"o}bner Walk, with the main results being as
follows. } \begin{itemize} \item\emph{Algorithms for several new noncommutative involutive divisions are given,
including strong; weak; global and local divisions.} \item\emph{An algorithm for computing a noncommutative Involutive Basis is given. When
used with one of the aforementioned involutive divisions, it is shown that
this algorithm returns a noncommutative Gr{\"o}bner Basis on termination.} \item\emph{An algorithm for a noncommutative Gr{\"o}bner Walk is given, in the case of
conversion between two harmonious monomial orderings. It is shown that this
algorithm generalises to give an algorithm for performing a noncommutative
Involutive Walk, again in the case of conversion between two harmonious
monomial orderings.} \item\emph{Two new properties of commutative involutive divisions are introduced
(stability and extendibility), respectively ensuring the termination of the
Involutive Basis algorithm and the applicability (under certain conditions) of
homogeneous methods of computing Involutive Bases.} \end{itemize}
\emph{Source code for an initial implementation of an algorithm to compute
noncommutative Involutive Bases is provided in Appendix B. This source code,
written using ANSI C and a series of libraries (AlgLib) provided by MSSRC
forms part of a larger collection of programs providing examples for this
thesis, including implementations of the commutative and noncommutative
Gr{\"o}bner Basis algorithms \cite{buchberger}, \cite{mora}; the commutative Involutive Basis algorithm for the Pommaret and Janet
involutive divisions \cite{yuyu}; and the Knuth\texttt{\symbol{45}}Bendix critical pairs completion algorithm
for monoid rewrite systems \cite{knuth-bendix}.}
The implementations described in the last paragraph formed a package \emph{Involutive} in 2005. This was based on libraries developed by the \emph{Multidisciplinary Software Systems Research Corporation} (MSSRC) which apparently no longer exists. This software was provided for the
research by Larry Lambe who was an Honorary Professor in the Mathematics
Department at Bangor at that time. (For an example of his work, see \cite{lambe-radford}.)
It has long been our intention to make these algorithms available to the wider
symbolic computation community, and this \textsf{GAP} package is the result. Involutive Bases are constructed, but Gr{\"o}bner Walks
will have to wait until a later version. In place of the AlgLib library
functions we use the noncommutative polynomial operations provided by the \textsf{GBNP} \cite{GBNP} package. }
}
\chapter{\textcolor{Chapter }{Using the packages \textsf{GBNP} and \textsf{NMO}}}\label{chap-desc} \logpage{[ 2, 0, 0 ]} \hyperdef{L}{X86057870803DCA93}{}
{
This package deals with polynomials in noncommutative algebras and to do so
makes use of the noncommutative polynomial operations provided by the \textsf{GBNP} \cite{GBNP} package, and orderings provided by the \textsf{NMO} package, which is now included within \textsf{GBNP}. In this chapter we remind users how to call some of these operations. \section{\textcolor{Chapter }{Noncommutative polynomials (NPs)}}\label{sec-nps} \logpage{[ 2, 1, 0 ]} \hyperdef{L}{X783C6EC87988B533}{}
{
Recall that the main datatype used by the \textsf{GBNP} package is a list of noncommutative polynomials (NPs). The data type for a
noncommutative polynomial (its NP format) is a list of two lists: \begin{itemize} \item The first is a list $m$ of monomials. \item The second is a list $c$ of coefficients of these monomials. \end{itemize}
The two lists have the same length. The polynomial represented by the ordered
pair $[m,c]$ is $\sum_i c_i m_i$. A monomial is a list of positive integers. They are interpreted as the
indices of the variables. So, if $k = [1,3,2,2,1]$ and the variables are $x,y,z$ (in this order), then $k$ represents the monomial $xzy^2x$. There are various ways to print these, but the default uses variables $a,b,c,\ldots$. The zero polynomial is represented by \texttt{[[],[]]} and the polynomial $1$ is represented by \texttt{[[[]],[1]]}. The algorithms are applicable for the algebra $\mathbb{F}[x_1,x_2,\ldots,x_t]$ of noncommutative polynomials in \mbox{\texttt{\mdseries\slshape t}} variables over the field $\mathbb{F}$. Accordingly, the list $c$ should contain elements of $\mathbb F$.
\index{NP2GP} \index{GP2NP} The \textsf{GBNP} functions \texttt{GP2NP} and \texttt{NP2GP} convert a polynomial to NP format and back again. Polynomials returned by \texttt{NP2GP} print with their coefficients enclosed in brackets. Polynomials may also be
printed using the function \texttt{PrintNP}. The function PrintNPList is used to print a list of NPs, with one polynomial
per line. The function \texttt{CleanNP} is used to collect terms and reorder them. The default ordering is first by
degree and then lexicographically \texttt{\symbol{45}} \texttt{MonomialGrlexOrdering}. Alternative orderings are available \texttt{\symbol{45}} see section \ref{sec-orderings}.
\section{\textcolor{Chapter }{Gr{\"o}bner Bases}}\label{sec-grob} \logpage{[ 2, 2, 0 ]} \hyperdef{L}{X7E4277497D877661}{}
{
The \textsf{GBNP} package computes Gr{\"o}bner bases using the function \texttt{SGrobner}. In the example below the polynomials $\{p,q\}$ define an ideal in $\mathbb{Z}[a,b]$ which has a three element Gr{\"o}bner basis. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
\section{\textcolor{Chapter }{Orderings for monomials}}\label{sec-orderings} \logpage{[ 2, 3, 0 ]} \hyperdef{L}{X7F82A3608248CD31}{}
{
The three monomial orderings provided by the main \textsf{GAP} library are \texttt{MonomialLexOrdering}, \texttt{MonomialGrlexOrdering} and \texttt{MonomialGrevlexOrdering}. The first of these is the default used by \textsf{GBNP}.
The \textsf{NMO} package is now part of the package \textsf{GBNP}. It provides a choice of orderings on monomials, including lexicographic and
length\texttt{\symbol{45}}lexicographic ones.
\chapter{\textcolor{Chapter }{Commutative Involutive Bases}}\label{chap-ibases-cp} \logpage{[ 3, 0, 0 ]} \hyperdef{L}{X780AAD6F8095AE49}{}
{
Given a Gr{\"o}bner Basis $G$ for an ideal $J$ over a polynomial ring $\mathbb{R}$, the remainder of any polynomial $p \in\mathbb{R}$ with respect to $G$ is unique. Although this remainder is unique, there may be many ways of
finding it, as it is possible that several polynomials in $G$ divide $p$, each giving a \emph{reduction path} for $p$. \section{\textcolor{Chapter }{Reduction Paths}}\label{sec-cib} \logpage{[ 3, 1, 0 ]} \hyperdef{L}{X7BBDABD3799443BB}{}
{
\subsection{\textcolor{Chapter }{An Example}}\label{subs-ch4ex402} \logpage{[ 3, 1, 1 ]} \hyperdef{L}{X7B5623E3821CC0D0}{}
{
Consider the DegLex Gr{\"o}bner basis $G := \{g_1, g_2, g_3\} = \{a^2-2ab+3, \: 2ab+b^2+5, \: \frac{5}{4}b^3-\frac{5}{2}a+\frac{37}{4}b\}$ over the polynomial ring $\mathbb{Q}[a,b]$, and consider the polynomial $p := a^2b+b^3+8b$. The remainder of $p$ with respect to $G$ is $0$ (so that $p$ is a member of the ideal $J$ generated by $G$), but there are two ways of obtaining this remainder, as shown in the
following diagram. \[\vcenter{\xymatrix{ & a^2b+b^3+8b \ar[dl]_{g_1} \ar[dr]^{g_2} \\ 2ab^2+b^3+5b \ar[d]_{g_2} && -\frac{1}{2}ab^2 + b^3 - \frac{5}{2}a+8b \ar[d]^{g_2} \\ 0 && \frac{5}{4}b^3-\frac{5}{2}a+\frac{37}{4}b \ar[d]^{g_3} \\ && 0 }} \]
}
An \emph{Involutive Basis} for $J$ is a Gr{\"o}bner Basis $G$ such that there is only \emph{one} possible reduction path for any polynomial $p \in\mathbb{R}$. In order to find such a basis, we restrict which reductions or divisions may
take place by requiring, for each potential reduction of a polynomial $p$ by a polynomial $g_i \in G$ (so that $LM(p) = LM(g_i)\times u$ for some monomial $u$), some extra conditions on the variables in $u$ to be satisfied, namely that all variables in $u$ have to be in a set of \emph{multiplicative variables} for $g_i$, a set that is determined by a particular choice of an \emph{involutive division}. }
\section{\textcolor{Chapter }{Commutative Involutive Divisions}}\label{sec-invdivc} \logpage{[ 3, 2, 0 ]} \hyperdef{L}{X7E43F2087BC8B4F9}{}
{
Recall that a commutative monomial $u$ is divisible by another monomial $w$ if there exists a third monomial $u'$ such that $u = wu'$. We use the notation $w \mid u$ and refer to $w$ as a \emph{conventional} \index{conventional divisor} divisor of $u$. An involutive division $I$ partitions the variables in the polynomial ring into sets of \emph{multiplicative} and \emph{nonmultiplicative} variables for each polynomial. The set of multiplicative variables for $w$ is denoted by $M_I(w)$. Then $w$ is an \emph{involutive divisor} of $u$, \index{involutive divisor} written $w \mid_I u$, if all variables in $u'$ are in $M_I(w)$. \subsection{\textcolor{Chapter }{Example}}\label{subs-ch4ex411} \logpage{[ 3, 2, 1 ]} \hyperdef{L}{X85861B017AEEC50B}{}
{
Let $u := ab^3c$, $v := abc^3$ and $w := bc$ be three monomials over the polynomial ring $\mathbb{R} := \mathbb{Q}[a,b,c]$. Let an involutive division $I$ partition the variables in $\mathbb{R}$ into the following two sets of variables for the monomial $w$: multiplicative = $\{a,b\}$; nonmultiplicative = $\{c\}$. It is true that $w$ conventionally divides both monomials $u$ and $v$, but $w$ only involutively divides monomial $u$ as, defining $u' := ab^2$ and $v' := ac^2$ (so that $u = wu'$ and $v = wv'$), we observe that all variables in $u'$ are in $M_I(w)$, but the variables in $v'$ (in particular the variable $c$) are not all in $M_I(w)$. So $w \mid_Iu$ and $w \nmid_I v$. }
\subsection{\textcolor{Chapter }{Selecting a Division}}\label{subs-select-divcp} \logpage{[ 3, 2, 2 ]} \hyperdef{L}{X83A3B3F77C712DA1}{}
{ \index{CommutativeDivision} The global variable \texttt{CommutativeDivision} is a string which can take values "Pommaret", "Thomas" or "Janet". The default
is "Pommaret". The example shows how to select the Pommaret division. }
\subsection{\textcolor{Chapter }{Selecting an Ordering}}\label{subs-select-ordcp} \logpage{[ 3, 2, 3 ]} \hyperdef{L}{X785D706A86DD7343}{}
{ \index{orderings} These three divisions are defined for a set of monomials, but we shall define
a \texttt{DivisionRecord} below for a set of polynomials. The first step is therefore to select the
leading monomials from this set, and that will bepend of the \emph{ordering} chosen. We shall be using the orderings provided by the main \textsf{GAP} library as described in \ref{sec-orderings}.
When calling \texttt{MonomialLexOrdering}, \texttt{MonomialGrlexOrdering} etc., it is essential to provide a list of indeterminates, as shown in the
example. Otherwise some of the functions in this package will throw an error. }
Let $\mathbb{R} = \mathbb{F}[a_1,\ldots,a_n]$ with $a_1 > a_2 > \ldots > a_n$, and let $w$ be a polynomial in $\mathbb{R}$ with leading monomoial $a_1^{e_1}a_2^{e_2} \ldots a_n^{e_n}$ where $e_i$ is the \emph{first} non\texttt{\symbol{45}}zero exponent. The Pommaret involutive division $\mathbb{P}$ sets $M_{\mathbb{P}}(w) = \{a_1, a_2, \ldots, a_i\}$.
Because $M_{\mathbb{P}}(w)$ does not depend in any way on the other leading monomials in \emph{polys}, this is a \emph{global} division.
In the example the first five monomials $u_i$ in $U$ contain a power of $x$, so $M_{\mathbb{P}}(u_i) = \{x\}$. Then $u_6$ involves $y$ and $z$, so $M_{\mathbb{P}}(u_6) = \{x,y\}$, and similarly $M_{\mathbb{P}}(u_7) = \{x,y,z\}$.
Let $\mathbb{R} = \mathbb{F}[a_1,\ldots,a_n]$ with $a_1 > a_2 > \ldots > a_n$, and let $P$ be a set of polynomials $P = \{p_1,\ldots,p_m\}$ in $\mathbb{R}$ with leading monomials $U = \{u_1,\ldots,u_m\}$ where $u_i = a_1^{e^1_i}a_2^{e^2_i} \ldots a_n^{e^n_i}$. The Thomas involutive division $\mathbb{T}$ sets $a_i$ to be multiplicative for $p_j$ and $u_j$ if $e^i_j = \max_k e^i_k$ for all $1 \leqslant k \leqslant m$.
In the example, using the same seven monomials, the highest powers of $[x,y,z]$ are $[5,2,3]$ respectively. So $x$ is multiplicative only for $u_1$, $y$ is multiplicative for $\{u_1,u_3,u_6\}$, and $z$ is multiplicative only for $u_4$ and $u_5$. Note that two of the monomials have no multiplicative variable.
Let $\mathbb{R} = \mathbb{F}[a_1,\ldots,a_n]$ with $a_1 > a_2 > \ldots > a_n$, and let $P$ be a set of polynomials $P = \{p_1,\ldots,p_m\}$ in $\mathbb{R}$ with leading monomials $U = \{u_1,\ldots,u_m\}$ where $u_i = a_1^{e^1_i}a_2^{e^2_i} \ldots a_n^{e^n_i}$. The Janet involutive division $\mathbb{J}$ sets $a_n$ to be multiplicative for $u_j$ provided $e^n_j = \max_k e^n_k$ for all $1 \leqslant k \leqslant m$. To determine whether $a_i$ is multiplicative for $u_j$, let $L = [e^{i+1}_j,e^{i+2}_j,\ldots,e^n_j]$. Let $S$ be the subset of $\{1,\ldots,m\}$ containing those $k$ such that $[e^{i+1}_k,e^{i+2}_k,\ldots,e^n_k] = L$. Then $a_i$ is multiplicative for $u_j$ provided $e^i_j = \max_{k \in S}e^i_k$.
In the example, recall that the exponent lists for the seven monomials are \[ [5,2,1],~~~ [4,1,2],~~~ [2,2,1],~~~ [1,1,3],~~~ [1,0,3],~~~ [0,2,1],~~~
[0,0,1]. \]
As with the Thomas division, $\max_k e^3_k = 3$ and $z$ is multiplicative only for $u_4$ and $u_5$.
For $y$, $L = [1]$ when $k \in\{1,3,6,7\}$ and $\max_{\{1,3,6,7\}} e^2_k = 2$, so $y$ is multiplicative for $u_1, u_3$ and $u_6$, but not for $u_7$. $L = [2]$ only for $u_2$, so $y$ is multiplicative for $u_2$. $L = [3]$ for $u_4$ and $u_5$, and $e^2_4 > e^2_5$, so $y$ is multiplicative for $u_4$ but not $u_5$.
For $x$, $L = [2,1]$ for $k \in\{1,3,6\}$ and $e^1_1 = 5$ is greater than $e^1_3$ and $e^1_6$, so $x$ is multiplicative for $u_1$. The other values for $L$, namely $[1,2], [1,3], [0,3]$ and $[0,1]$, occur just once each, so $x$ is multiplicative for $u_2, u_4, u_5$ and $u_7$.
The global function \texttt{DivisionRecord} calls one of the operations \texttt{DivisionRecordCP} and \texttt{DivisionRecordNP}, depending on whether the algebra is commutative or not. In the commutative
case, this function finds the sets of multiplicative variables for a set of
polynomials using one of the involutive divisions listed above. The record
constructed has three fields: the chosen division; a list of lists of
positions of the multiplicative variables; and the set of polynomials.
In the following example, polynomials $\{u = b^3-3a, v=a^3-3b\}$ define an ideal and form a Gr{\"o}bner basis for that ideal. Using the
Pommaret division, $M_{\mathbb{P}}(u) = \{a,b\}$ and $M_{\mathbb{P}}(v) = \{a\}$. The variable \texttt{drec2.mvars} in the listing below contains the \emph{positions} of these variables in the generating set $\{a,b\}$. }
\end{Verbatim}
In the \emph{reduction diagrams} below the nodes $(j,k)$ represent the monomials $a^jb^k$. The lead monomials of $u$ and $v$ are marked by these two names. In the left hand diagram the two shaded areas
indicate those monomials which are conventionally reducible by $u$ and by $v$, so that the doubly shaded area contains those monomials which are
conventionally reducible by both. For an involutive division, this must be
avoided.
In the right\texttt{\symbol{45}}hand diagram we see that $u$ involutively divides the same set of monomials in the main shaded area. On the
other hand $v$ just involutively divides monomials $\{a^j \mid j \ge 3\}$. So none of the monomials $\{a^jb, a^jb^2 \mid j \ge 3\}$ reduce by $v$ involutively. The operation \texttt{InvolutiveBasis}, to be described below, produces two further polynomials, $w = vb = a^3b-3b^2$ and $vb^2$ which reduces by $u$ to $x = a^3b^2 - 9a$. Both $w$ and $x$ have multiplicative variables $\{a\}$ and the monomials which they can reduce lie on the two horizantal line
segments in the right\texttt{\symbol{45}}hand diagram. In this way, all the
conventionally reducible monomials are involutively reducible by just one of $\{u,v,w,x\}$.
The global function \texttt{IPolyReduce} calls one of the operations \texttt{IPolyReduceCP} and \texttt{IPolyReduceNP} depending on whether the algebra is commutative or not. This function reduces
a polynomial $p$ using the current overlap record for a basis, and an ordering.
In the example, using \texttt{drec2}, the polynomial $p$ reduces only to $2a^3b+9a^2+9ab$ \[ p \stackrel{u}{\longrightarrow} 3a^4 + 2a^3b + 3ab^3 \stackrel{v}{\longrightarrow} 2a^3b + 3ab^3 + 9ab \stackrel{u}{\longrightarrow} 2a^3b + 9a^2 + 9ab \]
because the polynomial $x$ is not available to reduce $2a^3b$ to $6b^2$. }
The global function \texttt{LoggedIPolyReduce} calls one of the operations \texttt{LoggedIPolyReduceCP} and \texttt{LoggedIPolyReduceNP} depending on whether the algebra is commutative or not. This function is
similar to \texttt{IPolyReduce}, reducing a polynomial $p$ using the current overlap record for a basis, and an ordering. It's output,
however, is a record containing, as well as the reduced polynomial $r$, logging information which shows how the reduction has been obtained: \[ p ~=~ r + \sum_i logs[i] * polys[i]. \]
In the example \texttt{r.result} is equal to the previous result $q$, and the equation above is verified: \[ a^3b^3 + 2a^3b + 3ab^3 ~=~ (2a^3b+9a^2+9ab) + (a^3+3a)(b^3-3a) + 3a(a^3-3b). \]
}
The global function \texttt{IAutoreduce} calls one of the operations \texttt{IAutoreduceCP} and \texttt{IAutoreduceNP} depending on whether the algebra is commutative or not. This function applies \texttt{IPolyReduce} to a list of polynomials recursively until no more reductions are possible.
More specifically, this function involutively reduces each member of a list of
polynomials with respect to all the other members of the list, removing the
polynomial from the list if it reduces involutively to $0$. This process is iterated until no more reductions are possible.
If no reduction takes place, so that the result is equal to the initial list
of polynomials, then \texttt{true} is returned.
In the example we form \texttt{L3} by adding $p$ to \texttt{L2}. On applying \texttt{IAutoreduceCP}, only $p$ reduces, and the concatenation of \texttt{L2} with $q$ is returned. Starting with \texttt{L4 = [u,v,w,x]}, there are no reductions, and \texttt{true} is returned.
\section{\textcolor{Chapter }{Computing a Commutative Involutive Basis}}\label{sec-compibc} \logpage{[ 3, 3, 0 ]} \hyperdef{L}{X864907F987701716}{}
{
The involutive algorithm for constructing an involutive basis uses \emph{prolongations} and \emph{autoreduction}. \subsection{\textcolor{Chapter }{Prolongations and Autoreduction}}\label{subs-prolong} \logpage{[ 3, 3, 1 ]} \hyperdef{L}{X7ACAA0847CC0DBCC}{}
{
Given a set of polynomials $P$, a \emph{prolongation} of $ p \in P$ is a product $pa_i$ where the generator $a_i$ is \emph{not} multiplicative with respect to the current involutive division.
A set of polynomials $P$ is said to be \emph{autoreduced} if no polynomial $p \in P$ contains a term which is involutively divisible by some polynomial $p' \in P \setminus \{p\}$.
We denote by $rem_I(p,Q)$ the involutive remainder of polynomial $p$ with respect to a set of polynomials $Q$. Here is the \emph{Commutative Autoreduction Algorithm}: \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=] Input: a set of polynomials P = {p_1,p_2,...,p_n} and an involutive division I
while there exists p_i in P such that rem_I(p_i, P\{p_i}) <> p_i do
q := Rem_I(p_i, P\{p_i});
P := P\{p_i};
if (q<>0) then
P := P union {q};
fi;
od;
return P; \end{Verbatim}
It can be shown that if $P$ is a set of polynomials over a polynomial ring $\mathbb{R} = \mathbb{F}[a_1,\ldots,a_n]$, such that $P$ is autoreduced with respect to an involutive division $I$, and if $p,q$ are two polynomials in $\mathbb{R}$, then $rem_I(p,P) + rem_I(q,P) = rem_I(p+q,P)$.
Given an involutive division $I$ and an admissible monomial ordering $O$, an autoreduced set of polynomials $P$ is a \emph{locally involutive basis} with respect to $I$ and $O$ if any prolongation of any $p_i \in P$ involutively reduces to zero using $P$. Further, $P$ is an \emph{involutive basis} with respect to $I$ and $O$ if any multiple $p_it$ of any $p_i \in P$ by any term $t$ involutively reduces to zero using $P$.
The \emph{Commutative Involutive Basis Algorithm}: \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=] Input: a basis F = {f_1,f_2,...,f_m} for an ideal J
over a commutative polynomial ring R[a_1,...,a_n];
an admissible monomial ordering O;
a continuous and constructive involutive division I
Output: an involutive basis G = {g_1,g_2,...,g_k} for J (if it terminates)
G := { };
F := autoreduction of F with respect to O and I;
while G = { } do
P := set of all prolongations f_i*a_j, 1<=i<=m, 1<=j<=n;
q := 0;
while (P <> { }) and (q=0) do
p := a polynomial in P with minimal lead monomial w.r.t. O;
P := P \ {p};
q := rem_I(p,F);
od;
if (q <> 0) then ## new basis element found
F := autoreduction of (F union {q})
else ## all the prolongations have reduced to zero
G := F;
fi;
od;
return G; \end{Verbatim}
The global function \texttt{InvolutiveBasis} calls one of the operations \texttt{InvolutiveBasisCP} and \texttt{InvolutiveBasisNP} depending on whether the algebra is commutative or not. This function finds an
involutive basis for the ideal generated by a set of polynomials, using a
chosen ordering, and returns a division record.
Any involutive basis returned by this algorithm is a Gr{\"o}bner basis, and
remainders are involutively unique with respect to this basis.
\end{Verbatim}
Here we have returned to the example in section \ref{DivisionRecord}. Starting with $F=\{u,v\}$, there is only one prolongation, $P=\{w=vb\}$, and $F$ becomes $\{u,v,w\}$. At the second iteration, $P=\{vb,wb\}$; $vb$ reduces to zero; $wb$ reduces to $x=a^3b^2-9a$; and $F$ becomes $\{u,v,w,x\}$. At the third iteration $P=\{vb,wb,xb\}$ and all three of these reduce to zero, so $G = F$ is returned.
It is then shown that the multiplicative variables for $\{u,v,w,x\}$ are $\{\{a,b\},\{a\},\{a\},\{a\}\}$.
Finally, the full reduction $r$ of $p$ is computed.
If, instead of the Pommaret division, we use Janet or Thomas we obtain:
\end{Verbatim}
The Janet division gives the same involutive basis as Pommaret, but the Thomas
Division produces $7$, rather than $4$ polynomials: \[ [u,v,y,w,z,x,t] ~=~ [~ b^3-3a,\ a^3-3b,\ ab^3-3a^2,\ a^3b-3b^2,\ a^2b^3-9b,java.lang.NullPointerException
a^3b^2-9a,\ a^3b^3-9ab ~]. \]
The multiplicative variables for these polynomials are $[ \{b\}, \{a\}, \{b\}, \{a\}, \{b\}, \{a\}, \{a,b\} ]$, so the reduction diagram for the Thomas basis is: \[\vcenter{\xymatrix@=1em{ b & & & & & & & & \\ : \ar[u] & ;\cdot & \cdot & \cdot \ar@{-}[ur] & \cdot & \cdot & \cdot & & \\ 5 \ar@{-}[u] & \cdot & \cdot & \cdot\ar@{-}[uurr] & \cdot & \cdot & \cdot & & \\ 4 \ar@{-}[u] & \cdot & \cdot & \cdot\ar@{-}[uuurrr] & \cdot & \cdot & \cdot & & \\ u \ar@{-}[u] & y \ar@{-}[uuuu] & z \ar@{-}[uuuu] & t \ar@{-}[uuuurrrr] \ar@{-}[uuuu] \ar@{-}[rrrr] & \cdot\ar@{-}[uuurrr] & \cdot\ar@{-}[uurr] & \cdot \ar@{-}[ur] & & \\ 2 \ar@{-}[u] & \cdot & \cdot & x \ar@{-}[rrrr] & \cdot & \cdot & \cdot & & \\ 1 \ar@{-}[u] & \cdot & \cdot & w \ar@{-}[rrrr] & \cdot & \cdot & \cdot & & \\ 0 \ar@{-}[r]\ar@{-}[u] & 1 \ar@{-}[r] & 2 \ar@{-}[r] & v \ar@{-}[r] & 4 \ar@{-}[r] & 5 \ar@{-}[r] & \cdots\ar[r] & a & }} \]
The reduction of $p$ with this basis is: \[ p = a^3b^3 + 2a^3b + 3ab^3 \stackrel{t}{\longrightarrow} 2a^3b + 3ab^3 + 9ab \stackrel{w}{\longrightarrow} 3ab^3 + 9ab + 6b^2 \stackrel{y}{\longrightarrow}
9a^2 + 9ab + 6b^2. \]
\subsection{\textcolor{Chapter }{A more detailed example}}\label{subs-ex452} \logpage{[ 3, 3, 3 ]} \hyperdef{L}{X831D45437DE37177}{}
{
Here we consider Example 4.5.2 in the thesis \cite{gareth-thesis}. On setting \texttt{InfoLevel(InfoIBNP)} to \texttt{1} some of the intermediate calculations are displayed. The setting of the
problem is a rational polynomial ring in three variables with the lex ordering $[x,y,z]$, using the Janet involutive division. \begin{itemize} \item the initial basis contains two polynomials $\{a=x^2+y^3,~b=x+z^3\}$ \item the reduced Gr{\"o}bner basis is $\{c=y^3+z^6,~b=x+z^3\}$, and the irreducible monomials are $\{z^k,~yz^k,~y^2z^k~|~ k \geqslant 0\}$ \item when starting to calculate an involutive basis, the autoreduction does nothing
because $x$ is not multiplicative for $b$ \item the only prolongation is $bx = x^2+xz^3$ which reduces, on subtracting $a+bz^3$ and changing the sign, to $c=y^3+z^6$ \item on restarting with basis $[c,b,a]$, autoreduction replaces $a$ with $a-c = d = x^2-z^6$ \item there are then $3$ prolongations $[by,bx,dy]$ and $bx$ now reduces to zero \item $by = e = xy+yz^3$ is then added to the basis: $[c,b,e,d]$ \item $dy = x^2y-yz^6$ reduces to zero on adding $e(-x+z^3)$ \item on restarting with basis $[c,b,e,d]$ there are $4$ prolongations $[by,ey,bx,dy]$ and of these only $f = ey = xy^2+y^2z^3$ does not reduce to zero \item restarting with basis $[c,b,e,f,d]$, the $5$ prolongations $[by,ey,fy,bx,dy]$ all reduce to zero. \item now see what happens when reducing $p = x^7+y^7+z^7$ using the basis $[c,b,e,f,d]$ \item $x^7-dx^5 = x^5z^6$ and $x^5z^6 - dx^3z^6 = x^3z^{12}$ and $x^3z^{12}-dxz^{12} = xz^{18}$ and $xz^{18}-bz^{18}=-z^{21}$ \item $y^7 - cy^4 = -y^4z^6$ and $-y^4z^6 + cyz^6 = yz^{12}$, so $p$ reduces to $-z^{21} + yz^{12} + z^7$. \end{itemize}
\subsection{\textcolor{Chapter }{Using homogeneous polynomials}}\label{subs-hompolys} \logpage{[ 3, 3, 4 ]} \hyperdef{L}{X791740DF84B742A2}{}
{
If the polynomials in an initial basis are not homogeneous \index{homogeneous polynomials} then they may be made homogeneous by introducing an additional variable. The
resulting involutive basis will contain only homogeneous polynomials. However,
if these are de\texttt{\symbol{45}}homogenised by setting the additional
variable equal to $1$, the resulting basis may not be involutive.
Applying this to the previous example, the resulting basis contains $10$ polynomials which include homogenised versions of $[c,b,e,f]$, but not $d$. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
\chapter{\textcolor{Chapter }{Functions for Noncommutative Monomials}}\label{chap-monom} \logpage{[ 4, 0, 0 ]} \hyperdef{L}{X872783907DFA29B7}{}
{
A monomial, such as $ab^2a$ is represented in \textsf{GBNP} as the list $[1,2,2,1]$. Polynomials have a more complicated structure, for example $6ab^2a - 7ab + 8ba$ is represented in \textsf{GBNP} by $[ [ [1,2,2,1], [1,2], [2,1] ], [6,-7,8] ]$, which is a list of monomials followed by the corresponding list of
coefficients. Polynomials are dealt with in the following chapter.
As shown in Section \ref{sec-nps}, \textsf{GBNP} has functions \texttt{PrintNP} and \texttt{PrintNPList} to print a polynomial and a list of polynomials. Here we provide equivalent
functions for monomials. \section{\textcolor{Chapter }{Basic functions for monomials}}\label{sec-basic} \logpage{[ 4, 1, 0 ]} \hyperdef{L}{X846C3B0F79265278}{}
{
\subsection{\textcolor{Chapter }{Predefined algebras}}\label{sub-inbuilt-alg} \logpage{[ 4, 1, 1 ]} \hyperdef{L}{X84F106BB8093FCAE}{}
{
For convenience of use in examples, three algebras over the rationals, \texttt{AlbebraIBNP} and \texttt{AlgebrakIBNP} with $k \in [2,3,4]$, are predefined in this package. \index{AlgebraIBNP} \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
Recall, from \textsf{GBNP}, that the functions \texttt{NP2GP} and \texttt{NP2GPList} convert a polynomial (or list of polynomials) in NP\texttt{\symbol{45}}format
to an element of the algebra. This package provides additional functions \texttt{NM2GM} and \texttt{NM2GMList} which do the equivalent conversion for monomials. }
Recall, from \textsf{GBNP}, that the functions \texttt{GP2NP} and \texttt{GP2NPList} convert a polynomial (or list of polynomials) to the equivalent
NP\texttt{\symbol{45}}format. This package provides additional functions \texttt{GM2NM} and \texttt{GM2NMList} which do the equivalent conversion for monomials. }
The operation \texttt{SuffixPrefixPosNM( left, right, start, limit)} looks for overlaps of type \emph{suffix of left = prefix of right}. The size of the smallest such overlap is returned. The overlaps which are
considered are controlled by the third and fourth arguments. We commence by
looking at the overlap of size \emph{start} and go no further than the overlap of size \emph{limit}. When no overlap exists, $0$ is returned. To test all possibilities, \emph{start} should be $1$ and \emph{limit} should be $min(|left|,|right|)-1$. It is the user's responsibility to make sure that these bounds are correct \texttt{\symbol{45}} no checks are made.
The operation \texttt{SubwordPosNM( small, large, start );} answers the question for monomials \emph{Is small a subword of large?}. The value returned is the start position in \emph{large} of the first subword found. When no subword is found, $0$ is returned. The search commences at position \emph{start} in \emph{large} so, to test all possibilities, the third argument should be $1$.
To just ask whether or not \emph{small} is a subword of \emph{large}, use \texttt{IsSubwordNM( small, large);}. }
Given the word $w = b^4a^3c^2$, represented by $[2,2,2,2,1,1,1,3,3]$, the \emph{lead variable} is $b$ or $2$, and the \emph{lead exponent} is $4$. Removing $b^4$ from $w$ leaves the \emph{tail} $a^3c^2$. }
The operation \texttt{DivNM(large, small);} for two monomials returns all the ways that \emph{small} divides \emph{large} in the form of a list of pairs of monomials \emph{[left,right]} so that \emph{large = left*small*right}. In the example we search for subwords $ab$ of $m = abcababc$, returning $[ [abcab,c], [abc,abc], [1,cababc] ]$. }
Given an \texttt{FAlgList}, this function calculates the degree of the lead term for each element of the
list and returns the largest value found. In the example this is $v$ with degree $4$ }
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
