# TriangularSetCategory(R, E, V, P)ΒΆ

- R: IntegralDomain
- E: OrderedAbelianMonoidSup
- V: OrderedSet
- P: RecursivePolynomialCategory(R, E, V)

The category of triangular sets of multivariate polynomials with coefficients in an integral domain. Let `R`

be an integral domain and `V`

a finite ordered set of variables, say `X1 < X2 < ... < Xn`

. A set `S`

of polynomials in `R[X1, X2, ..., Xn]`

is triangular if no elements of `S`

lies in `R`

, and if two distinct elements of `S`

have distinct main variables. Note that the empty set is a triangular set. A triangular set is not necessarily a (lexicographical) Groebner basis and the notion of reduction related to triangular sets is based on the recursive view of polynomials. We recall this notion here and refer to [1] for more details. A polynomial `P`

is reduced `w`

.`r`

.`t`

a non-constant polynomial `Q`

if the degree of `P`

in the main variable of `Q`

is less than the main degree of `Q`

. A polynomial `P`

is reduced `w`

.`r`

.`t`

a triangular set `T`

if it is reduced `w`

.`r`

.`t`

. every polynomial of `T`

.

- #: % -> NonNegativeInteger
- from Aggregate
- =: (%, %) -> Boolean
- from BasicType
- ~=: (%, %) -> Boolean
- from BasicType

- algebraic?: (V, %) -> Boolean
`algebraic?(v, ts)`

returns`true`

iff`v`

is the main variable of some polynomial in`ts`

.

- algebraicVariables: % -> List V
`algebraicVariables(ts)`

returns the decreasingly sorted list of the main variables of the polynomials of`ts`

.- any?: (P -> Boolean, %) -> Boolean
- from HomogeneousAggregate P

- autoReduced?: (%, (P, List P) -> Boolean) -> Boolean
`autoReduced?(ts, redOp?)`

returns`true`

iff every element of`ts`

is reduced`w`

.`r`

.`t`

to every other in the sense of`redOp?`

- basicSet: (List P, (P, P) -> Boolean) -> Union(Record(bas: %, top: List P), failed)
`basicSet(ps, redOp?)`

returns`[bs, ts]`

where`concat(bs, ts)`

is`ps`

and`bs`

is a basic set in Wu Wen Tsun sense of`ps`

`w`

.`r`

.`t`

the reduction-test`redOp?`

, if no non-zero constant polynomial lie in`ps`

, otherwise`"failed"`

is returned.

- basicSet: (List P, P -> Boolean, (P, P) -> Boolean) -> Union(Record(bas: %, top: List P), failed)
`basicSet(ps, pred?, redOp?)`

returns the same as`basicSet(qs, redOp?)`

where`qs`

consists of the polynomials of`ps`

satisfying property`pred?`

.- coerce: % -> List P
- from CoercibleTo List P
- coerce: % -> OutputForm
- from CoercibleTo OutputForm

- coHeight: % -> NonNegativeInteger if V has Finite
`coHeight(ts)`

returns`size()\$V`

minus`\#ts`

.- collect: (%, V) -> %
- from PolynomialSetCategory(R, E, V, P)

- collectQuasiMonic: % -> %
`collectQuasiMonic(ts)`

returns the subset of`ts`

consisting of the polynomials with initial in`R`

.- collectUnder: (%, V) -> %
- from PolynomialSetCategory(R, E, V, P)
- collectUpper: (%, V) -> %
- from PolynomialSetCategory(R, E, V, P)
- construct: List P -> %
- from Collection P
- convert: % -> InputForm
- from ConvertibleTo InputForm
- copy: % -> %
- from Aggregate
- count: (P -> Boolean, %) -> NonNegativeInteger
- from HomogeneousAggregate P
- count: (P, %) -> NonNegativeInteger
- from HomogeneousAggregate P

- degree: % -> NonNegativeInteger
`degree(ts)`

returns the product of main degrees of the members of`ts`

.- empty: () -> %
- from Aggregate
- empty?: % -> Boolean
- from Aggregate
- eq?: (%, %) -> Boolean
- from Aggregate
- eval: (%, Equation P) -> % if P has Evalable P
- from Evalable P
- eval: (%, List Equation P) -> % if P has Evalable P
- from Evalable P
- eval: (%, List P, List P) -> % if P has Evalable P
- from InnerEvalable(P, P)
- eval: (%, P, P) -> % if P has Evalable P
- from InnerEvalable(P, P)
- every?: (P -> Boolean, %) -> Boolean
- from HomogeneousAggregate P

- extend: (%, P) -> %
`extend(ts, p)`

returns a triangular set which encodes the simple extension by`p`

of the extension of the base field defined by`ts`

, according to the properties of triangular sets of the current category If the required properties do not hold an error is returned.

- extendIfCan: (%, P) -> Union(%, failed)
`extendIfCan(ts, p)`

returns a triangular set which encodes the simple extension by`p`

of the extension of the base field defined by`ts`

, according to the properties of triangular sets of the current domain. If the required properties do not hold then “failed” is returned. This operation encodes in some sense the properties of the triangular sets of the current category. Is is used to implement the`construct`

operation to guarantee that every triangular set build from a list of polynomials has the required properties.- find: (P -> Boolean, %) -> Union(P, failed)
- from Collection P

- first: % -> Union(P, failed)
`first(ts)`

returns the polynomial of`ts`

with greatest main variable if`ts`

is not empty, otherwise returns`"failed"`

.- hash: % -> SingleInteger
- from SetCategory
- hashUpdate!: (HashState, %) -> HashState
- from SetCategory

- headReduce: (P, %) -> P
`headReduce(p, ts)`

returns a polynomial`r`

such that`headReduce?(r, ts)`

holds and there exists some product`h`

of`initials(ts)`

such that`h*p - r`

lies in the ideal generated by`ts`

.

- headReduced?: % -> Boolean
`headReduced?(ts)`

returns`true`

iff the head of every element of`ts`

is reduced`w`

.`r`

.`t`

to any other element of`ts`

.

- headReduced?: (P, %) -> Boolean
`headReduced?(p, ts)`

returns`true`

iff the head of`p`

is reduced`w`

.`r`

.`t`

.`ts`

.- headRemainder: (P, %) -> Record(num: P, den: R)
- from PolynomialSetCategory(R, E, V, P)
- iexactQuo: (R, R) -> R
- from PolynomialSetCategory(R, E, V, P)

- infRittWu?: (%, %) -> Boolean
`infRittWu?(ts1, ts2)`

returns`true`

iff`ts2`

has higher rank than`ts1`

in Wu Wen Tsun sense.

- initiallyReduce: (P, %) -> P
`initiallyReduce(p, ts)`

returns a polynomial`r`

such that`initiallyReduced?(r, ts)`

holds and there exists some product`h`

of`initials(ts)`

such that`h*p - r`

lies in the ideal generated by`ts`

.

- initiallyReduced?: % -> Boolean
`initiallyReduced?(ts)`

returns`true`

iff for every element`p`

of`ts`

`p`

and all its iterated initials are reduced`w`

.`r`

.`t`

. to the other elements of`ts`

with the same main variable.

- initiallyReduced?: (P, %) -> Boolean
`initiallyReduced?(p, ts)`

returns`true`

iff`p`

and all its iterated initials are reduced`w`

.`r`

.`t`

. to the elements of`ts`

with the same main variable.

- initials: % -> List P
`initials(ts)`

returns the list of the non-constant initials of the members of`ts`

.

- last: % -> Union(P, failed)
`last(ts)`

returns the polynomial of`ts`

with smallest main variable if`ts`

is not empty, otherwise returns`"failed"`

.- latex: % -> String
- from SetCategory
- less?: (%, NonNegativeInteger) -> Boolean
- from Aggregate
- mainVariable?: (V, %) -> Boolean
- from PolynomialSetCategory(R, E, V, P)
- mainVariables: % -> List V
- from PolynomialSetCategory(R, E, V, P)
- map!: (P -> P, %) -> %
- from HomogeneousAggregate P
- map: (P -> P, %) -> %
- from HomogeneousAggregate P
- member?: (P, %) -> Boolean
- from HomogeneousAggregate P
- members: % -> List P
- from HomogeneousAggregate P
- more?: (%, NonNegativeInteger) -> Boolean
- from Aggregate
- mvar: % -> V
- from PolynomialSetCategory(R, E, V, P)

- normalized?: % -> Boolean
`normalized?(ts)`

returns`true`

iff for every`p`

in`ts`

we have`normalized?(p, us)`

where`us`

is`collectUnder(ts, mvar(p))`

.

- normalized?: (P, %) -> Boolean
`normalized?(p, ts)`

returns`true`

iff`p`

and all its iterated initials have degree zero`w`

.`r`

.`t`

. the main variables of the polynomials of`ts`

- parts: % -> List P
- from HomogeneousAggregate P

- quasiComponent: % -> Record(close: List P, open: List P)
`quasiComponent(ts)`

returns`[lp, lq]`

where`lp`

is the list of the members of`ts`

and`lq`

is`initials(ts)`

.- reduce: ((P, P) -> P, %) -> P
- from Collection P
- reduce: ((P, P) -> P, %, P) -> P
- from Collection P
- reduce: ((P, P) -> P, %, P, P) -> P
- from Collection P

- reduce: (P, %, (P, P) -> P, (P, P) -> Boolean) -> P
`reduce(p, ts, redOp, redOp?)`

returns a polynomial`r`

such that`redOp?(r, p)`

holds for every`p`

of`ts`

and there exists some product`h`

of the initials of the members of`ts`

such that`h*p - r`

lies in the ideal generated by`ts`

. The operation`redOp`

must satisfy the following conditions. For every`p`

and`q`

we have`redOp?(redOp(p, q), q)`

and there exists an integer`e`

and a polynomial`f`

such that`init(q)^e*p = f*q + redOp(p, q)`

.

- reduceByQuasiMonic: (P, %) -> P
`reduceByQuasiMonic(p, ts)`

returns the same as`remainder(p, collectQuasiMonic(ts)).polnum`

.

- reduced?: (P, %, (P, P) -> Boolean) -> Boolean
`reduced?(p, ts, redOp?)`

returns`true`

iff`p`

is reduced`w`

.`r`

.`t`

. in the sense of the operation`redOp?`

, that is if for every`t`

in`ts`

`redOp?(p, t)`

holds.- remainder: (P, %) -> Record(rnum: R, polnum: P, den: R)
- from PolynomialSetCategory(R, E, V, P)
- remove: (P -> Boolean, %) -> %
- from Collection P
- remove: (P, %) -> %
- from Collection P
- removeDuplicates: % -> %
- from Collection P

- removeZero: (P, %) -> P
`removeZero(p, ts)`

returns`0`

if`p`

reduces to`0`

by pseudo-division`w`

.`r`

.`t`

`ts`

otherwise returns a polynomial`q`

computed from`p`

by removing any coefficient in`p`

reducing to`0`

.

- rest: % -> Union(%, failed)
`rest(ts)`

returns the polynomials of`ts`

with smaller main variable than`mvar(ts)`

if`ts`

is not empty, otherwise returns “failed”- retract: List P -> %
- from RetractableFrom List P
- retractIfCan: List P -> Union(%, failed)
- from RetractableFrom List P
- rewriteIdealWithHeadRemainder: (List P, %) -> List P
- from PolynomialSetCategory(R, E, V, P)
- rewriteIdealWithRemainder: (List P, %) -> List P
- from PolynomialSetCategory(R, E, V, P)

- rewriteSetWithReduction: (List P, %, (P, P) -> P, (P, P) -> Boolean) -> List P
`rewriteSetWithReduction(lp, ts, redOp, redOp?)`

returns a list`lq`

of polynomials such that`[reduce(p, ts, redOp, redOp?) for p in lp]`

and`lp`

have the same zeros inside the regular zero set of`ts`

. Moreover, for every polynomial`q`

in`lq`

and every polynomial`t`

in`ts`

`redOp?(q, t)`

holds and there exists a polynomial`p`

in the ideal generated by`lp`

and a product`h`

of`initials(ts)`

such that`h*p - r`

lies in the ideal generated by`ts`

. The operation`redOp`

must satisfy the following conditions. For every`p`

and`q`

we have`redOp?(redOp(p, q), q)`

and there exists an integer`e`

and a polynomial`f`

such that`init(q)^e*p = f*q + redOp(p, q)`

.- roughBase?: % -> Boolean
- from PolynomialSetCategory(R, E, V, P)
- roughEqualIdeals?: (%, %) -> Boolean
- from PolynomialSetCategory(R, E, V, P)
- roughSubIdeal?: (%, %) -> Boolean
- from PolynomialSetCategory(R, E, V, P)
- roughUnitIdeal?: % -> Boolean
- from PolynomialSetCategory(R, E, V, P)
- sample: %
- from Aggregate

- select: (%, V) -> Union(P, failed)
`select(ts, v)`

returns the polynomial of`ts`

with`v`

as main variable, if any.- select: (P -> Boolean, %) -> %
- from Collection P
- size?: (%, NonNegativeInteger) -> Boolean
- from Aggregate
- sort: (%, V) -> Record(under: %, floor: %, upper: %)
- from PolynomialSetCategory(R, E, V, P)

- stronglyReduce: (P, %) -> P
`stronglyReduce(p, ts)`

returns a polynomial`r`

such that`stronglyReduced?(r, ts)`

holds and there exists some product`h`

of`initials(ts)`

such that`h*p - r`

lies in the ideal generated by`ts`

.

- stronglyReduced?: % -> Boolean
`stronglyReduced?(ts)`

returns`true`

iff every element of`ts`

is reduced`w`

.`r`

.`t`

to any other element of`ts`

.

- stronglyReduced?: (P, %) -> Boolean
`stronglyReduced?(p, ts)`

returns`true`

iff`p`

is reduced`w`

.`r`

.`t`

.`ts`

.- triangular?: % -> Boolean
- from PolynomialSetCategory(R, E, V, P)
- trivialIdeal?: % -> Boolean
- from PolynomialSetCategory(R, E, V, P)
- variables: % -> List V
- from PolynomialSetCategory(R, E, V, P)

- zeroSetSplit: List P -> List %
`zeroSetSplit(lp)`

returns a list`lts`

of triangular sets such that the zero set of`lp`

is the union of the closures of the regular zero sets of the members of`lts`

.

- zeroSetSplitIntoTriangularSystems: List P -> List Record(close: %, open: List P)
`zeroSetSplitIntoTriangularSystems(lp)`

returns a list of triangular systems`[[ts1, qs1], ..., [tsn, qsn]]`

such that the zero set of`lp`

is the union of the closures of the`W_i`

where`W_i`

consists of the zeros of`ts`

which do not cancel any polynomial in`qsi`

.

Evalable P if P has Evalable P

InnerEvalable(P, P) if P has Evalable P

PolynomialSetCategory(R, E, V, P)