Why does GAP not know that $\mathbb{Q}[x] / (x^2 + 1)$ is a field?

by Markus Pfeiffer

A mild­ly con­fus­ing ex­am­ple

The following question from GAP users comes up frequently in different guises. Consider the following GAP interaction

1
2
3
4
5
6
7
gap> x := In­de­ter­mi­nate(Ra­tio­nals, "x");;
gap> R := Poly­no­mi­al­Ring(Ra­tio­nals, [x]);;
gap> f := x^2 + 1;;
gap> F := R / Ide­al(R, [f]);
<ring Ra­tio­nals, (1), (x)>
gap> Is­Field(F);
false

Now, some undergrad algebra tells us that, since f is irreducible over \mathbb{Q}, the quotient \mathbb{Q}[x] / (x^2 + 1) should in fact be a field.

So GAP seems to be wrong. Except this is intentional, if a bit unfortunate.

How GAP or­gan­is­es ob­jects

In a previous post I introduced filters, categories, and properties in GAP. Filters form a hierarchy on objects, and for every given object a filter can be set, or not set.

Categoriesremember that GAP categories are NOT categories in the sense of category theory are implemented using filters, and these filters are set at object creation and do not change during the lifetime of an object. For algebraic structures it is best to think of the category of an object as the signature of the structure:

GAP follows this paradigm, hence IsMagma, IsMagmaWithOne, and IsMagmaWithInverses are categories. Now if we try to determine whether groups form a category, we find out that they don’t

1
2
3
4
5
6
gap> Is­Group
<Fil­ter "(Is­Mag­ma­With­In­vers­es and Is­As­so­cia­tive)">
gap> Is­Mag­ma­With­In­vers­es;
<Cat­e­go­ry "Is­Mag­ma­With­In­vers­es">
gap> Is­As­so­cia­tive
<Prop­er­ty "Is­As­so­cia­tive">

A group in GAP is a magma with inverses (and a one) such that the binary operation is associative.

From algebra we also know that every group is a (simple) semigroup, even a monoid, yet

1
2
3
4
5
6
gap> G := Semi­group(Trans­for­ma­tion([2,3,1]));
<com­mu­ta­tive trans­for­ma­tion semi­group of de­gree 3 with 1 gen­er­a­tor>
gap> Is­Group(G);
false
gap> Is­Monoid(G);
false

We created the object G as a semigroup, hence it is an associative magma. Without proving that G is a group and providing an isomorphism to a group we can’t get GAP to treat G as a group: the category must not change!And one could and should consider this a feature: It might be very expensive or impossible for GAP to figure out whether a semigroup is a group

Loading the GAP package semigroups we get exactly this functionality:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
gap> Load­Pack­age("semi­groups");;
gap> S := Semi­group(Trans­for­ma­tion([2,3,1]));
<com­mu­ta­tive trans­for­ma­tion semi­group of de­gree 3 with 1 gen­er­a­tor>
gap> Is­Group­As­Semi­group(S);
true
gap> Iso­mor­phism­Perm­Group(S);
Map­ping­By­Func­tion( <trans­for­ma­tion group of de­gree 3 with 1 gen­er­a­tor>, Group([ (1,2,3) ]), func­tion( f ) ... end, func­tion( x ) ... end )
gap> G := As­Group(S);
<group of size 3 with 1 gen­er­a­tors>
gap> Is­Group(G);
true

More on the un­der­ly­ing prob­lem

One reason for the confusion caused is that in GAP by convention almost allThere are things CanEasilyCompareElements and HasProperty filters have a name beginning with Is, and properties are implemented using filters, too.

It is easy to mistake a category for a property, and vice versa.

What about the con­fus­ing in­tro­duc­to­ry ex­am­ple?

The introductory example has exactly the same underlying causes, unfortunately there is as yet no function (that I know of) to turn a ring quotient into a field if it is easy to prove that this is possible. Maybe you want to provide a pull-request?

If you have further questions, feel free to ask us GAP people, either on the support mailing list github, or ask to be added to our Slack.