Symbolic computations in finite fields of unspecified order

Question

The general setting is that I want to multiply some matrices (to many to do it by hands) over a finite field. The problem is that these matrices depend on certain parameters taken from the field and that the order of the field is not specified (say it equals $q=2^m$, $m$ odd, if that matters).

Surprisingly, I couldn't find a CAS that can do such calculations (or at least I can't see how to make it). All I want is that the system knows about Child Binomial Theorem, $a^q=a$ and such things and can use them to simplify expression. Maple assume is not of much help here, for example.

Any suggestions?

Answer 1

In my master thesis, I encountered a similar problem: I was looking at fields of square order $q^2$, and needed to study the involutory automorphism $x\mapsto x^q$, and simplify expressions involving it. What I ended up doing was using Mathematica and writing a custom transformation map which did what I needed:

Frob[x_?IntegerQ] := x
Frob[-x_] := -Frob[x]
Frob[x_^y_] := Frob[x]^y
Frob[Frob[x_]] := x
Frob[x_ + y_] := Frob[x] + Frob[y]
Frob[x_ y_] := Frob[x] Frob[y]
Frob[x_List] := Frob /@ x

Here, Frob represents the involutory automorphism, and the above rules express that it is additive, multiplicative, and involutory. With this, I was then able to describe a unitary form on (in my case) 6x6 matrices, and proof some nice results.

For your application, you could try to following a similar route, but now instead you try to write a function which simplifies expressions the way you need it. It lets products and sums through, and maps through lists (including matrices), but changes $q$-th powers. Finally, if no other rule matches, it leaves the object untouched. So this is a possible starting point:

MySimplify[x_^ y_] := MySimplify[x]^(y /. q -> 1) /; PolynomialQ[y, {q}]

MySimplify[-x_] := -MySimplify[x]
MySimplify[x_ + y_] := MySimplify[x] + MySimplify[y]
MySimplify[x_ y_] := MySimplify[x] MySimplify[y]
MySimplify[x_List] := MySimplify /@ x
MySimplify[x_] := x

Now you get this:

In: MySimplify[7 + x^q + a^(2 q) + a^(q^2) + b^(4 q^3)]
Out: 7 + a + a^2 + b^4 + x

This also works if the parameter is a matrix. Note that you likely will still want to call the usual Simplify. And you may need to add more rules or tweak the existing ones.

EDIT: I modified the rules a bit to deal with arbitrary polynomials in $q$ occurring in the exponent. I guess one should also add a check to verify that all coefficients of those polynomials are integral, but I'll leave that as an exercise to the actual user, who hopefully actually knows whether this is something that could occur in his/her specific application.