In August last year I started a thread called 'Another problem with finite fields and polynomials' where I posted a problem I was having with FriCAS and finite fields. Ralf Hemmecke was very kind in responding to me, but we left the problem not quite resolved, with me promising to look further into it.

Well, only 9 months later, I am now looking further into it! :-)

In order to isolate the problem I have written a small SPAD file containing two definitions of finite field constructors, modelled on those that I found in the distribution. The first constructs a field directly, the second constructs a field as an extension of a given base field. The file is:

)abbrev domain MYFF MyFiniteField
MyFiniteField(p:PositiveInteger, n:PositiveInteger): FiniteAlgebraicExtensionField(PrimeField p) ==_
 FiniteFieldExtensionByPolynomial(PrimeField p, createIrreduciblePoly(n)$FiniteFieldPolynomialPackage(PrimeField p))

)abbrev domain MYFFX MyFiniteFieldExtension
MyFiniteFieldExtension(GF : FiniteFieldCategory, n : PositiveInteger): FiniteAlgebraicExtensionField(GF) ==_
 FiniteFieldExtensionByPolynomial(GF, createIrreduciblePoly(n)$FiniteFieldPolynomialPackage(GF))

then I have a small input file to construct two polynomials over a field, and compute the remainder of one modulo the other:

MyGF16 := MyFiniteField(2,4)
a := primitiveElement()$MyGF16
p : POLY MyGF16 := a*x + 1
q : POLY MyGF16 := a*x
p rem q

which works and returns the answer 1 as expected. The problem arises when I change the first line to:

MyGF16 := MyFiniteFieldExtension(PrimeField(2),4)

because then I get the error message:

 Error detected within library code:
 coerce: element doesn't belong to smaller field

Now, I'm not asking anyone to dig around and tell me what the problem is, because that is something I promised to do (and which I think will gain me a better understanding of FriCAS), but I *am* asking for advice on how to look into this. Specifically, is there a way to get FriCAS to tell me what it is doing? That is, debug information such as what coercions are being applied and which functions in which domains are being called?

this is not a problem of the Finite Field code (which I contributed to very long ago) and to find the error, it is also not neccessary to encapsulate in new domains as your MYFF etc.

It is indeed a problem of function selection of the interpreter. Use:

)set mess sel on

The reason is the following: rem and quo are defined for Euclidean Domains, which Polynomial of a Field is not.
Therefore, if you change your variable definition to e.g.

p : UP(x. MYFFX) := a*x+1

etc. it will work! The interpreter has no extra work todo.

This also works if you define the polynomals of POLY MYFF or if you simply drop this domain in the definition of p and q.

Then the interpreter selects (by coercion facilities) as follows (using the fact that there is only one variable around):

 Function Selection for rem
      Arguments: (POLY(FF(2,4)),POLY(FF(2,4)))
   -> no function rem found for arguments (POLY(FF(2,4)),POLY(FF(2,4)))

 Function Selection for rem
      Arguments: (UP(x,FF(2,4)),UP(x,FF(2,4)))

 [1]  signature:   (UP(x,FF(2,4)),UP(x,FF(2,4))) -> UP(x,FF(2,4))
      implemented: slot $$$ from UP(x,FF(2,4))

However, for strange reason: THIS PROBLEM MUST BE HANDED TO EXPERTS OF THE INTERPRETER FUNCTION SELECTION FACILITIES AND COERCION FACILITIES,
the interpreter - in case of FFX(PF 2, 4) finds a coefficent coercion/retraction to transfer to POLY(PF 2) using a retraction (partial function) to the prime field, which is
here explicitly exhibited in FFX contrary to FF, where this is hidden for the interpreter I guess. For some strange reason, the heurisitic seems to think that transfer the problem to POLY PF 2, it will solve it from there. Actually this is not the case, as the transfer to the Polynomials over the prime field must fail (your observed error message).

(15) -> p' rem q'

 Function Selection for rem
      Arguments: (POLY(FFX(PF(2),4)),POLY(FFX(PF(2),4)))
   -> no function rem found for arguments (POLY(FFX(PF(2),4)),POLY(FFX(PF(2),4)))

 Function Selection for map by coercion facility (map)
      Arguments: ((FFX(PF(2),4) -> PF(2)),POLY(FFX(PF(2),4)))
      Target type: POLY(PF(2))

 [1]  signature:   ((FFX(PF(2),4) -> PF(2)),POLY(FFX(PF(2),4))) -> POLY(PF(2))
      implemented: slot (Polynomial (PrimeField 2))(Mapping (PrimeField 2) (FiniteFieldExtension (PrimeField 2) 4))(Polynomial (FiniteFieldExtension (PrimeField 2) 4)) from POLY2(FFX(PF(2),4),PF(2))

   >> Error detected within library code:
   coerce: element doesn't belong to smaller field

Am 14.05.2012 um 00:19 schrieb Paul Onions:

Johannes Grabmeier

It is indeed a problem of function selection of the interpreter. Use:

< ... >