Defining a polynomial quotient algebra over prime field

[Sid Andal]

I'd like to define F13[x,y,z]/(p,q,r) with

p = x^3 - y - 1

q = y^4 - z - 2

r = z^5 - x - 3

and be able to reduce a plynomial, say

f = x^5y^7 + y^4z^7.

Thanks,

Sid

[Ralf Hemmecke]

F := PrimeField 13
P := HDMP([x,y,z], F)
p:P := x^3 - y - 1
q:P := y^4 - z - 2
r:P := z^5 - x - 3
gb := groebner([p,q,r])

f:P := x^5 * y^7 + y^4 * z^7

normalForm(f, gb)

=====================================
Actually, instead of HDMP you can also use other constructors
like DMP, but then the term order will be lexicographic and you will get
a different result.

Ralf

[Sid Andal]

Is it possible to define an infix binary operation, say # or some other suitable symbole

such that f#g, for polynomials f and g, it returns normalForm(f*g, gb)?

[Ralf Hemmecke]

On 4/19/26 17:24, Sid Andal wrote:
> Is it possible to define an infix binary operation, say # or some other
> suitable symbole
> such that f#g, for polynomials f and g, it returns normalForm(f*g, gb)?

Yes it is.

What about trying to implement such a simple domain yourself?
You might learn something, if you try.

Ralf

=====================================

%%% (1) -> )compile polquo.spad
Compiling FriCAS source code from file
/home/hemmecke/scratch/zzz/polquo.spad using system compiler.
POLQUO abbreviates domain PolynomialQuotientAlgebra
------------------------------------------------------------------------
initializing NRLIB POLQUO for PolynomialQuotientAlgebra
compiling into NRLIB POLQUO
processing macro definition Rep ==>
HomogeneousDistributedMultivariatePolynomial(vl,R)
processing macro definition rep x ==>
pretend(@(x,%),HomogeneousDistributedMultivariatePolynomial(vl,R))
processing macro definition per x ==>
pretend(@(x,HomogeneousDistributedMultivariatePolynomial(vl,R)),%)
compiling exported coerce :
HomogeneousDistributedMultivariatePolynomial(vl,R) -> %

;;; *** |POLQUO;coerce;Hdmp%;1| REDEFINED
Time: 0.04 SEC.

compiling exported coerce : % ->
HomogeneousDistributedMultivariatePolynomial(vl,R)
POLQUO;coerce;%Hdmp;2 is replaced by x

;;; *** |POLQUO;coerce;%Hdmp;2| REDEFINED
Time: 0 SEC.

compiling exported * : (%,%) -> %

;;; *** |POLQUO;*;3%;3| REDEFINED
Time: 0 SEC.

compiling exported ^ : (%,PositiveInteger) -> %

;;; *** |POLQUO;^;%Pi%;4| REDEFINED
Time: 0 SEC.

compiling exported ^ : (%,NonNegativeInteger) -> %

;;; *** |POLQUO;^;%Nni%;5| REDEFINED
Time: 0.01 SEC.

****** Domain: % already in scope
augmenting %: (CharacteristicNonZero)
****** Domain: R already in scope
augmenting R: (PolynomialFactorizationExplicit)
****** Domain: R already in scope
augmenting R: (ConvertibleTo (InputForm))
****** Domain: R already in scope
augmenting R: (ConvertibleTo (Pattern (Float)))
****** Domain: R already in scope
augmenting R: (ConvertibleTo (Pattern (Integer)))
****** Domain: R already in scope
augmenting R: (Hashable)
****** Domain: R already in scope
augmenting R: (LinearlyExplicitOver (Integer))
****** Domain: R already in scope
augmenting R: (PatternMatchable (Float))
****** Domain: (OrderedVariableList vl) already in scope
augmenting (OrderedVariableList vl): (PatternMatchable (Float))
****** Domain: R already in scope
augmenting R: (PatternMatchable (Integer))
****** Domain: (OrderedVariableList vl) already in scope
augmenting (OrderedVariableList vl): (PatternMatchable (Integer))
****** Domain: R already in scope
augmenting R: (Comparable)
****** Domain: R already in scope
augmenting R: (PolynomialFactorizationExplicit)
****** Domain: R already in scope
augmenting R: (RetractableTo (Fraction (Integer)))
****** Domain: R already in scope
augmenting R: (RetractableTo (Integer))
(time taken in buildFunctor: 73170)

;;; *** |PolynomialQuotientAlgebra| REDEFINED

;;; *** |PolynomialQuotientAlgebra| REDEFINED
Time: 0.09 SEC.


Cumulative Statistics for Constructor PolynomialQuotientAlgebra
Time: 0.15 seconds

--------------non extending category----------------------
.. PolynomialQuotientAlgebra(#1,#2,#3) of cat
(|Join|
(|PolynomialCategory| |#1|
(|HomogeneousDirectProduct| (|#| |#2|)
(|NonNegativeInteger|))
(|OrderedVariableList| |#2|))
(CATEGORY |domain|
(SIGNATURE |coerce|
((|HomogeneousDistributedMultivariatePolynomial| |#2| |#1|) %))
(SIGNATURE |coerce|
(% (|HomogeneousDistributedMultivariatePolynomial| |#2| |#1|)))))
has no reorder : (%, List(Integer)) -> %
finalizing NRLIB POLQUO
Processing PolynomialQuotientAlgebra for Browser database:
--->/home/hemmecke/scratch/zzz/polquo.spad-->PolynomialQuotientAlgebra(constructor):
Not documented!!!!
--->/home/hemmecke/scratch/zzz/polquo.spad-->PolynomialQuotientAlgebra((coerce
((HomogeneousDistributedMultivariatePolynomial vl R) %))): Not
documented!!!!
--->/home/hemmecke/scratch/zzz/polquo.spad-->PolynomialQuotientAlgebra((coerce
(% (HomogeneousDistributedMultivariatePolynomial vl R)))): Not
documented!!!!
--->/home/hemmecke/scratch/zzz/polquo.spad-->PolynomialQuotientAlgebra():
Missing Description
; compiling file "/home/hemmecke/scratch/zzz/POLQUO.NRLIB/POLQUO.lsp"
(written 19 APR 2026 09:47:27 PM):

; file: /home/hemmecke/scratch/zzz/POLQUO.NRLIB/POLQUO.lsp
; in: SDEFUN |POLQUO;coerce;%Hdmp;2|
; (BOOT::SDEFUN BOOT::|POLQUO;coerce;%Hdmp;2|
; ((BOOT::|x| (BOOT::%))
; (BOOT::%
; (BOOT::|HomogeneousDistributedMultivariatePolynomial|
; BOOT::|vl| BOOT::R)))
; BOOT::|x|)
; --> PROGN SB-IMPL::%DEFUN SB-IMPL::%DEFUN SB-INT:NAMED-LAMBDA
; ==>
; #'(SB-INT:NAMED-LAMBDA BOOT::|POLQUO;coerce;%Hdmp;2|
; (BOOT::|x| BOOT::%)
; (BLOCK BOOT::|POLQUO;coerce;%Hdmp;2| BOOT::|x|))
;
; caught STYLE-WARNING:
; The variable % is defined but never used.
;
; compilation unit finished
; caught 1 STYLE-WARNING condition


; wrote /home/hemmecke/scratch/zzz/POLQUO.NRLIB/POLQUO.fasl
; compilation finished in 0:00:00.021
------------------------------------------------------------------------
PolynomialQuotientAlgebra is now explicitly exposed in frame initial

PolynomialQuotientAlgebra will be automatically loaded when needed
from /home/hemmecke/scratch/zzz/POLQUO.NRLIB/POLQUO

%%% (1) -> F := PrimeField 13

(1) PrimeField(13)

Type: Type
%%% (2) -> vl := [x,y,z]

(2) [x, y, z]
Type:
List(OrderedVariableList([x,y,z]))
%%% (3) -> P := HDMP(vl, F)

(3) HomogeneousDistributedMultivariatePolynomial([x, y,
z],PrimeField(13))

Type: Type
%%% (4) -> p:P := x^3 - y - 1

3
(4) x + 12 y + 12
Type:
HomogeneousDistributedMultivariatePolynomial([x,y,z],PrimeField(13))
%%% (5) -> q:P := y^4 - z - 2

4
(5) y + 12 z + 11
Type:
HomogeneousDistributedMultivariatePolynomial([x,y,z],PrimeField(13))
%%% (6) -> r:P := z^5 - x - 3

5
(6) z + 12 x + 10
Type:
HomogeneousDistributedMultivariatePolynomial([x,y,z],PrimeField(13))
%%% (7) -> gb := groebner([p,q,r])

5 4 3
(7) [z + 12 x + 10, y + 12 z + 11, x + 12 y + 12]
Type:
List(HomogeneousDistributedMultivariatePolynomial([x,y,z],PrimeField(13)))
%%% (8) -> PQA := PolynomialQuotientAlgebra(F, vl, gb)

(8)
PolynomialQuotientAlgebra
PrimeField(13)
,
[x, y, z]
,
5 4 3
[z + 12 x + 10, y + 12 z + 11, x + 12 y + 12]

Type: Type
%%% (9) -> xx := x::P::PQA

(9) x
Type:
PolynomialQuotientAlgebra(PrimeField(13),[x,y,z],[z^5+12*x+10,y^4+12*z+11,x^3+12*y+12])
%%% (10) -> yy := y::P::PQA

(10) y
Type:
PolynomialQuotientAlgebra(PrimeField(13),[x,y,z],[z^5+12*x+10,y^4+12*z+11,x^3+12*y+12])
%%% (11) -> zz := y::P::PQA

(11) y
Type:
PolynomialQuotientAlgebra(PrimeField(13),[x,y,z],[z^5+12*x+10,y^4+12*z+11,x^3+12*y+12])
%%% (12) -> xx^5 * yy^7 + yy^4 * zz^7

2 3 2 3 3 2 3 2 2 3 2 2
(12) x y z + 2 x y + y z + 4 y z + x z + 4 y + 4 x z + 4 x
Type:
PolynomialQuotientAlgebra(PrimeField(13),[x,y,z],[z^5+12*x+10,y^4+12*z+11,x^3+12*y+12])

[Waldek Hebisch]

On Sun, Apr 19, 2026 at 09:58:44PM +0200, 'Ralf Hemmecke' via FriCAS - computer algebra system wrote:
> On 4/19/26 17:24, Sid Andal wrote:
> > Is it possible to define an infix binary operation, say # or some other
> > suitable symbole
> > such that f#g, for polynomials f and g, it returns normalForm(f*g, gb)?
>
> Yes it is.
>
> What about trying to implement such a simple domain yourself?
> You might learn something, if you try.

Expanding it a bit, set of operators available in FriCAS is fixed.
You can use "the same" operator for new types by overloading.
Due to limitations of FriCAS "interpreter" normally one would do
this by creating a new domain, that is writing Spad code.
Creating domains is explained in chapter 13 of the FriCAS book.

If you want just one specific operator you can "cheat". More
precisely, operator '**' is currently unused by FriCAS, so you
can hijack it for your use without bad effect. So, once you
put Groebner basis in gb you can do:

x ** y == normalForm(f*g, gb)

and it should do what you want. That is, for FriCAS, operator is
just a function, only its name is treated specially by the parser,
so (for infix operators) you write the operator name between
arguments.

BTW: By playing with argument types it should be possible to
make version of the above using just '*', but such coding is
dangerous because if you make a mistake your later commands
may use wrong '*'. Defining new domains is much safer.

BTW2: Trying the same with '#' does not work.

--
Waldek Hebisch

[Sid Andal]

The construction of the polynomial quotient algebra A = F13[X,Y,Z]/(p,q,r)
is actually an intermediate result. Its purpose is to be used to
define the main algebra B via ALGSC that is a module over A.

I was able to define such B over the one-indeterminate case A = R[X]/p(X),
with R = ZMOD(10) and some polynomial p(X):

Partial code:

R := ZMOD(10)

POR ==> POLY R
LSQ ==> List SQMATRIX(3, POR)

UPX := UP(X, R)
MOR : POR := X^5 - (X^4 + 5*X^3 + 2*X^2 + 7*X + 9)
AOR := SAE(R, UPX, MOR)

Then it loads the structure constants LSM, (of type LSQ), with entries
consisting of polynomials (in A) from file. The algebra is then
obtained the usual way:

B := ALGSC(AOR, 3, ['E, 'F, 'G], LSM)

And it works fine.

Is it possible to do the same with A = F13[X,Y,Z]/(p,q,r)?

Thanks,

Sid

[Waldek Hebisch]

On Mon, Apr 20, 2026 at 07:39:31AM -0700, Sid Andal wrote:
> The construction of the polynomial quotient algebra A = F13[X,Y,Z]/(p,q,r)
> is actually an intermediate result. Its purpose is to be used to
> define the main algebra B via ALGSC that is a module over A.
>
> I was able to define such B over the one-indeterminate case A = R[X]/p(X),
> with R = ZMOD(10) and some polynomial p(X):
>
> Partial code:
>
>
> R := ZMOD(10)
>
> POR ==> POLY R
> LSQ ==> List SQMATRIX(3, POR)
>
> UPX := UP(X, R)
> MOR : POR := X^5 - (X^4 + 5*X^3 + 2*X^2 + 7*X + 9)
> AOR := SAE(R, UPX, MOR)
>
> Then it loads the structure constants LSM, (of type LSQ), with entries
> consisting of polynomials (in A) from file. The algebra is then
> obtained the usual way:
>
> B := ALGSC(AOR, 3, ['E, 'F, 'G], LSM)
>
> And it works fine.
>
> Is it possible to do the same with A = F13[X,Y,Z]/(p,q,r)?

For this you need a domain. Best way is to create one. As
a workaround you can try tower is SAE-s. Tower is probably
less efficient than domain based on normalForm but should
work too.


--
Waldek Hebisch

[Ralf Hemmecke]

Sid,

I hoped, you are more abitious.

On 4/20/26 16:39, Sid Andal wrote:
> The construction of the polynomial quotient algebra A = F13[X,Y,Z]/(p,q,r)
> is actually an intermediate result.

> Is it possible to do the same with A = F13[X,Y,Z]/(p,q,r)?

The last question I cannot answer without looking deeper into ALGSC, but
my guess would be "yes".

But you asked for A = F13[X,Y,Z]/(p,q,r). And that is rather easy.
Otherwise I wouldn't have dared to pose this as an exercise for you.

OK, let me resolve that and give you the domain I hacked together to
produce the output from my last mail, see attachment.

The attached domain is probably not perfect. The reason is that I
thought that redefining '*' would be enough. It wasn't, because the
implementation of '^' was inherited from HDMP (with the old meaning of
'*'). In other words, there might be more functions that inherit the old
meaing of '*'. All those one would have to redefine/reimplement in
PolynomialQuotientAlgebra. Inheritance in SPAD/Aldor doesn't work the
same as in other object oriented langauges.

Hope that helps
Ralf