Generating subsets of a finite magma

Question

I am trying to write a program which, given a multiplication table of a finite magma $(G, *)$, should produce at least one (or all possible) generating subset $S$ of minimal cardinality.

More precisely $S \subset G, \ |G| = n \in \mathbb{N}$. Let $<S>$ be operational closure of $S$ in $G$. I am interested in outputting at least one $S$, such that $<S> = G$ and for every $S'$ with that property $|S| \le |S'|$.

So far I have tried to understand what is $<a>, a \in G$, but due to lack of even simple associativity this is non-trivial. I defined right-associative power operation $a^k := (k = 1) \ ?\ a \ :\ a * a^{k-1}$, for $k \ge 1$. I already know how to list the elements of a set $R_a := \{a^k \ |\ k \ge 1\}$, and of similarly defined set $L_a$, if $a^k$ is defined as left-associative. These are, in general case, proper subsets of $<a>$, and need not even be closed under multiplication (I have constructed counterexamples).

All in all, proper description of $<a>$ still evades me, but even then, I would have to figure out how to describe $<a_1,...,a_k>$ knowing the former. Is there a more intelligent way to write this program than absolute brute force search across subsets of $G$ and the definition of $<S>$ as intersection of all submagmas of $G$ that contain $S$?

Be aware that groupoid is used to refer to a different notion, and I believe this usage is much more common than how you've used it, which I think is to be a magma -- set with a binary operation. So it's worth defining the term when you use it, to make it easier for the reader to know what you mean. I've adjusted the tags to reflect what I think you mean. — , Sep 27 '18 at 12:29
This is what I had in mind. Magma. In my language it is called a groupoid. This was a real terminological surprise. Appreciate the heads-up! — Drinkwater, Sep 27 '18 at 12:43

score 1 · Accepted Answer · answered Sep 28 '18 at 17:20

First I wrote the algorithm which literally follows the mathematical definition:

Let $G$ be the magma.

    GeneratingSets := EmptySet; 
    Iterate A over the power set of G {
        S := G;
        Iterate B over the power set of G {
            if((A is contained in B) and (B is a submagma)) {
                S := S intersect B;
            }
        }
        if(card(S) equals card(G)) {
            GeneratingSets := GeneratingSets union Set(A);
        }
    }

There is, however, a more efficient way to do this. Since $G$ is finite, any subset $H$ of $G$ is finite as well, so the closure of $H$ can be computed with the following iterative procedure:

   Closure := H;

   do {
       m := card(Closure);
       R := EmptySet;
       Iterate over (a, b) where a, b are in Closure {
           R := R union Set(a * b);
       }
       Closure := Closure union R;
   } while(card(Closure) > m);

It is not difficult to see that it is guaranteed to stop, because $G$ is finite. So now we can iterate over all subsets of $G$ only once, also sparing us the tedious intersection computations.

This is the most efficient method I can think of for now, but I doubt much more can be done without any additional requirements imposed upon $(G, *)$.

Generating subsets of a finite magma

1 Answers1