# Monomial Orders

In this section we describe each of the **module monomial orders** available in Magma. If the user wishes to work with reduced modules only (particularly for homology computations), then the underlying monomial orders and Gröbner bases will probably be rarely of interest to the user, so this section may be skipped. The monomial orders are mostly of interest if one wishes to work with embedded modules with special orders so that the relevant Gröbner bases have special properties. In either case, elements of the module are represented by vectors in an ambient and we refer to the vector component positions as *columns* in analogy to matrix terminology: a presentational module is often just defined by a matrix of relations, the rows giving vectors generating the relation module and the column numbering labelling the components of the vectors. For our modules there can be a non-trivial column weighting, which we think of as applying a shift to the degree of a homogeneous polynomial that occurs as the corresponding vector component of the module element. This is used to define homogeneity and degree of the overall vector. Given an $R$-module $M$, suppose that the underlying monomial order of $R$ is $<_R$. A **module monomial** of $M$ is a monomial-column pair consisting of a monomial $s$ of $R$ and a column number $c$ (with $c \geq 1$), written as $s[c]$ in the following. Monomial-column pairs give an (infinite) basis for the elements in a free module $R^k$ and a vector representing an element of $M$ can be decomposed into a sum of scalar multiples of monomial-column pairs just as elements of the polynomial ring $R$ can be written as a sum of scalar multiples of plain monomials. Now suppose that $s_1[c_1]$ and $s_2[c_2]$ are module monomials from $M$. Any order on the pairs is then fully defined by just specifying exactly when $s_1[c_1] < s_2[c_2]$ with respect to that order. As for multivariate polynomial rings, in the following the argument(s) are described for an order as a list of expressions; that means that the expressions (without the parentheses) should be appended to any base arguments when any particular intrinsic function is called which expects a module monomial order. See [[Adams and Loustaunau, 1994](../../references.md#cite-adamsloustaunau), Sec. 3.5] and [[Cox *et al.*, 1998](../../references.md#cite-uag-clo), Def. 2.4] for motivation and further discussion.

## Term Over Position: TOP

Definition: $s_1[c_1] < s_2[c_2]$ iff $s_1 <_R s_2$ or $s_1 = s_2$ and $c_2 > c_1$. The order is specified by the argument (`"top"`). This order is called “TOP” (term over position) since it first compares the underlying monomials (terms with the coefficients ignored (Some authors apply the terms ‘monomial’ and ‘term’ in opposite senses to how we do here, so that is why there are the established names ‘TOP’ and ‘POT’; we follow this instead of using ‘MOP’ and ‘POM’!)) and then compares the columns (the positions). The column comparison is ordered so that the first column is the greatest. A Gröbner basis of a module with respect to the `TOP` order is usually the easiest to compute, and corresponds to the `grevlex` order for polynomial rings in a certain way (i.e., the order favours the ‘size’ of monomials and only gives priority to the columns in a secondary way).

## Term Over Position (Weighted): TOPW

Definition (given a sequence $W$ of $k$ integer weights, where $k$ is the degree of the ambient module): write $d_i =$ Degree$_W(s_i[c_i])=$ Degree$(s_i)+W[c_i]$; then $s_1[c_1] < s_2[c_2]$ iff $d_1<d_2$ or $d_1=d_2$ and $s_1 <_R s_2$ or $d_1=d_2$, $s_1 = s_2$ and $c_2 > c_1$. The order is specified by the arguments (`"topw", W`). The weights need not be positive (but must be small integers). This order first compares the degrees of the monomial-coefficient pairs using both the weights of the underlying ring $R$ and the weights on the columns given by $W$ and then proceeds as for the `TOP` order. If there is a natural grading $W$ on the columns of the module, then it is preferable to use this order with $W$, particularly if submodules of interest are homogeneous or graded w.r.t. $W$, since then the GB w.r.t. this order will tend to be smaller and easier to compute. Normally one would also make the base order $<_R$ to be one of the `grevlex` or `grevlexw` degree orders (see Subsections [Graded Reverse Lexicographical: grevlex](../GrobnerBases/order.md#grevlex-order), [Graded Reverse Lexicographical: grevlex](../GrobnerBases/order.md#grevlex-order)), so that the order $<$ extends the degree order $<_R$ to a degree order on the module.

## Position Over Term: POT

Definition: $s_1[c_1] < s_2[c_2]$ iff $c_2 > c_1$ or $c_1 = c_2$ and $s_1 <_R s_2$. The order is specified by the argument (`"pot"`). This order is called “POT” (position over term) since it first compares the columns and then compares the underlying monomials. The column comparison is ordered so that the first column is the greatest. A Gröbner basis of a module with respect to the `POT` order is like an echelon form of a matrix, since the order gives priority to the columns but this is in general rather harder to compute than the GB w.r.t. the `TOP` order.

## Position Over Term (Permutation): POTPERM

Definition (given a sequence $P$ of $k$ integers describing a permutation of $[1..k]$, where $k$ is the degree of the ambient module): $s_1[c_1] < s_2[c_2]$ iff $P[c_2] > P[c_1]$ or $c_1 = c_2$ and $s_1 <_R s_2$. The order is specified by the arguments (`"potperm", P`). This order first compares the columns using the given permutation, and then compares the underlying monomials.

## Block TOP-TOP: TOPTOP

Definition (given a integer $k$): say that a column $c$ is in the 1st block if $c \leq k$ and in the 2nd block if $c > k$; then $s_1[c_1] < s_2[c_2]$ iff $c_2$ is in the 1st block and $c_1$ is in the 2nd block, or if the columns are in the same block and $s_1[c_1] < s_2[c_2]$ w.r.t. the `TOP` order. This order is a block order, like an elimination order for polynomial rings: comparison is first made on the blocks in which the columns lie, and then the `TOP` order is applied within each block. A GB w.r.t. this order is easier in general to compute than the `POT` order and so is useful when one wishes to ‘eliminate’ the first $k$ columns only in a GB.

## Block TOP-POT: TOPPOT

Definition (given a integer $k$): say that a column $c$ is in the 1st block if $c \leq k$ and in the 2nd block if $c > k$; then $s_1[c_1] < s_2[c_2]$ iff $c_2$ is in the 1st block and $c_1$ is in the 2nd block, or if the columns are in the same block and $s_1[c_1] < s_2[c_2]$ w.r.t. the `TOP`/`POT` order (respective to the 1st/2nd blocks). This order is a block order, like an elimination order for polynomial rings: comparison is first made on the blocks in which the columns lie, and then the `TOP` order is applied within the 1st block and the `POT` order is applied within the 2nd block. This is similar to the `TOPTOP` order, but it may be preferable to order the 2nd block w.r.t. the `POT` order. Note: `POTPOT` would equal to `POT`, and `POTTOP` does not seem to be useful.