Revisiting a problem with finite fields and polynomials

[Paul Onions]

Hello,

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?

Thanks in advance,
Paul

[Prof. Dr. Johannes Grabmeier]

Hallo Paul,

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))

> --
> You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> To post to this group, send email to fricas...@googlegroups.com.
> To unsubscribe from this group, send email to fricas-devel...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/fricas-devel?hl=en.
>

Mit freundlichen Grüßen

Johannes Grabmeier

Prof. Dr. Johannes Grabmeier
Köckstraße 1, D-94469 Deggendorf
Tel. +49-(0)-991-2979584, Tel. +49-(0)-171-5503789
Tel. +49-(0)-991-3615-100 (d), Fax: +49-(0)-1803-5518-17745

[Paul Onions]

On Monday, 14 May 2012 15:50:07 UTC+1, jg wrote:

Hallo Paul,

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.

I created the MYFF and MYFFX domains so that I could control exactly how they differ. When called from my input file, the only difference really was where the PrimeField(2) constructor was called: for MYFF it is called in the MYFF constructor, for MYFFX it is called by the interpreter and the result passed to the MYFFX constructor.

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

)set mess sel on

Ahh, so that's the magic incantation I needed, thanks. 

 

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.

Yes, that's what I ended up doing to get things working 9 months ago.

 

< ... >

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).

Okay, I wonder how difficult it is to understand the interpreter... :-o

Thanks very much for your help,

Paul