10. HR WORKING IN GROUP THEORY

Please note that the results here are out of date, and we are planning another evaluation of HR in group theory.

Classification Tasks

We wanted HR to invent a calculation which is an invariant (so it gives the same results for any pair of isomorphic groups), and which classifies the groups up to six (so it gives different results for any pair of non-isomorphic groups). HR has achieved this goal. The following concepts (translated from HR's original output for the sake of brevity) have been found by HR to classify the groups up to order 6.

• The function: f(G) = |{(a,b) in G x G : bab = a}|
• The set:f(G) = {(m,n) : m = |{a in G : n = |{b in G : b=a²}|}|}
• The function: f(G) = |{(a,(ab)ⁿ) in G x G : n > 0, not(a=b=(ab)ⁿ)}|
• The function:f(G) = |G|x|{a in G : a = a^-1}|
• The set:f(G) = {(m,n) in N x N : m = |{(a,b) in G x G : n = |{c in G : c = bab}|}|}
• The function: f(G) = |{(a,aⁿb) in G x G : n >= 0, a =\= anⁿ⁺¹b}|
• The set: f(G) = {(|G|,n) : exists a,b in G x G s.t. n = |{ (a,a^mb) in G x G : m >= 0 }|}

(and there are more complicated ones than these). The first of these came as a surprise, as we had not expected such an easy to state concept to classify the groups up to order 6. The latex output HR produced for this classifying concept (and four other similar ones) can be found here:

The five classifying concepts given above are distinct core classifying concepts. HR is very good at turning one classifying concept into many others, by concentrating its efforts on the classifying concepts that it already has, or on a parent concept which has produced a classifying concept. For example, the concept which was an ancestor of the the last two classifying concepts above was concentrated on, and produced two more classifying concepts. HR can show graphically where these concepts came from, and their relation to each other.

We have also given HR other categorisations for it to classify groups into. As a tricky example, we wanted HR to find a property of the groups D(2) and D(3) which is not shared by any other group up to order six.

HR spotted that they are the only ones with this property:

for all a in G, there is an element b s.t. a =\= aⁿb for some n > 0.

(They are of course, also the only non-cyclic groups up to order 6 - it's left as an exercise to see whether the definition of non-cyclic and that given above are equivalent).

Reinventing Classically Interesting Concepts

For a paper delivered at the Machine Discovery workshop at ECAI last year, we looked at twenty concepts from standard group theory, and asked whether HR had re-invented them. We concluded that:

HR re-invented the classical definition of these concepts:

• Elements of a group
• Order of a group
• Cyclic groups
• The orders of elements
• The centre of a group
• Abelian groups
• The identity of a group
• Inverses of Elements
• Orders of Elements

HR needs to be able to work with two theories at once (namely group theory and number theory), to be able to re-invent these concepts:

• p-Groups
• Elementary Abelian groups

HR needs more production rules to be able re-invent these concepts:

• Left cosets
• Quotient groups
• Normal subgroups
• Simple groups
• The index of subgroups
• Commutators
• Derived Series
• Central Series

It is unlikely that HR will re-invent these concepts as they are taken from other theories (geometry and number theory):

• Dihedral groups
• Quarternion groups

As HR develops, the search space it uses will enlarge, so that more of the above concepts can be found. However, this will mean that better heuristics are required.