A few questions about checking whether a set in C++ is an algebraic group

Question

I've started making a library for doing things with abstract algebra. Right now I'm trying to make a function that checks whether a set is a group. It should be self-explanatory:

In mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element satisfying four conditions called the group axioms, namely closure, associativity, identity and invertibility. One of the most familiar examples of a group is the set of integers together with the addition operation; the addition of any two integers forms another integer. (http://en.wikipedia.org/wiki/Group_(mathematics))

#include <set>
#include <iostream>

template <typename ObType, typename BinaryFunction>
bool isGroup(const std::set<ObType> & S, BinaryFunction & op)
{
    /*
       isGroup returns true or false depending on whether the set S
       along with the operator op is a group in the Algebraic sense.
       That is, S is a group if and only if all the 4 following
       conditions are true: 
            (1) If a, b in S, then a op b in S
            (2) If a, b, c in S, then (a + b) + c = a + (b + c)
            (3) There is an element 0 in S such that a + 0 = 0 + a for all a in S
            (4) If a in S, then there is a b in S such that a + b = b + a = 0
    */
    typename std::set<ObType>::const_iterator beg(S.cbegin()), offend(S.cend());
    bool noProblems = true;
    for (std::set<ObType>::const_iterator ia = beg; ia != offend && noProblems; ++ia)
    {
        for (std::set<ObType>::const_iterator ia = beg; ib != offend && noProblems; ++ib)
        {
            // ---------- (1) --------------
            if (S.count(op(*ia, *ib)) == 0) 
                noProblems = false;
            // -----------------------------
            for (std::set<ObType>::const_iterator ic = beg; ic != offend && noProblems; ++ic)
            {
                // ---------- (2) -------------
                if (((*ia + *ib) + *ic) != (*ia + (*ib + *ic)))
                    noProblems = false;
                // ----------------------------
            }
        }
    }

    return noProblems;
}

template <typename T>
class Plus
{
    public:
        T operator() (const T & x, const T & y) { return x + y; };  
};

int main()
{
    std::set<int> S1 = { 0, 1, -1 };
    std::set<int> S2 = { 0 };
    class Plus<int> p;
    std::cout << isGroup(S1, p);
    return 0;

}

No compiler errors, but I have a few questions:

How can I check for (3) and (4) inside my nest of loops? I
Later, I'd like to check whether entire sets of native objects like int and long are groups. How can I set S1 equal to an std::set of all longs?

There's a simple algorithm I'll tell you in exchange for a copy of Vol. 5. — Kerrek SB, May 28 '14 at 21:46
2. I don't know of any simpler way than iterating over all such values and inserting them one by one. Keep in mind there are way too many `long`s to do it, though. As for whether native types form groups - for unsigned integer types, yes. It's undefined for signed types (integer overflow is UB), and, assuming IEEE 754, false for floating point values (e.g. addition is not associative). — Marcin Łoś, May 28 '14 at 21:52
Maybe a question for the Computer Science section, but awesome question. I love stuff that is stated simply and yet awe-inspiringly difficult. — Matt Coubrough, May 28 '14 at 21:55
I'm not sure checking all the group axioms by brute fore for certain sets is tractable. — geometrian, May 29 '14 at 21:58
One approach to finding the identity element if the set is finite: take an element `a`, and combine |S| copies of `a` using `op`. The result must be the identity. Of course, this will really only work if |S| is small (but so will everything else here). — Teepeemm, Jun 01 '14 at 21:29

4pie0 · Accepted Answer · 2014-06-03T21:41:56.193

You should create a class to express notion of a set with an operation op (+) (note: this "+" is not ordinary arithmetic + so

// ---------- (2) -------------
if (((*ia + *ib) + *ic) != (*ia + (*ib + *ic)))
    noProblems = false;

is wrong, this should be

// ---------- (2) -------------
if ( op( op(*ia,*ib), *ic) != op( *ia, op( *ib, *ic)))
    noProblems = false;

), values (or rather elements) of this set (a container), and a special element called 1 (or e) element (it is 0 for integers R with (operation called) addition +, but 1 for integers R\0 with multiplication "x"). You need to add a 1 to your class. It is absolutely necessary to check (3) and (4). Further, identity 1 is not an integer 0 in general but a description of some special identity element that will yield same element x if x itself is subject to operation + with 1 ,(e), and 1 + x = x. (you can skip one expression if the operation "+" is commutative, what is true if S is abelian group).

Now what you will do depends on the thing if you would like to introduce hint parameter or not. To find identity element in a given set with hint you can write

template <typename ObType, typename BinaryFunction>
bool isGroup( const std::set<ObType> & S, BinaryFunction & op, ObType e)
{
 //... important define BinaryFunction as taking const args !
typename std::set<ObType>::const_iterator beg(S.cbegin()), offend(S.cend());
bool isGroup = true;
for (std::set<ObType>::const_iterator ia = beg; ia != offend && noProblems; ++ia)
{

        // ---------- (3) --------------
        if( op( *ia, e)) != *ia  || op( e, *ia)) != *ia) 
            isGroup = false;
        // -----------------------------

This is not straightforward to indicate identity element in general. Simple example of integers or other arithmetic types with our well known + is just one of the simplest and not extensible, i.e. in the field of fractions of ring Z, the Q(Z), e for + is given by a pair [0,1] and for "x" by [1,1]. So to make this more general you have to iterate over elements, choose e and call op to check if (3) holds for all elements.

template <typename ObType, typename BinaryFunction>
bool isGroup( const std::set<ObType> & S, BinaryFunction & op)
{
     //... important define BinaryFunction as taking const args !
    typename std::set<ObType>::const_iterator beg(S.cbegin()), offend(S.cend());

    for (std::set<ObType>::const_iterator ia = beg; ia != offend; ++ia)
    {

        // ---------- (3) -------------
        /* let e be an *ia */
        ObType e = *ia; 
        bool isGroup = true;
        for ( auto ia2 : S) {

            if( op( ia2, e)) != ia2  || op( e, ia2)) != ia2) {
                isGroup = false;
                break;
            }

            // identity found, set e_ in class to e and return
            if( isGroup) {
                e_ = e;
               return true;
            }
        }
    }

    /* identity not found, this is not a group */
    return false;
}

@Donald Knuth is there something more I can explain to you? ;p — 4pie0, May 29 '14 at 19:07
If the group is finite, then for any `a`, `op^n(a)=e` will give the identity element. — Teepeemm, Jun 03 '14 at 22:58
I think you mean op( e, e)^(kn) where k is integer and n is order of a finite group, which is true but again: first you have to find the e (as we don't know if this is the group) and the fact that there is more identity elements has no meaning - we need just one of them — 4pie0, Jun 03 '14 at 23:16
No. For any group element `a`, with `n` is the order of the group, then `a^n=e` (where `^` means "combine `n` of these using `op`"). This is because the order of an element divides the order of the group. Consequently, if the set is finite, we can get a candidate for `e` in `O(n)` time. — Teepeemm, Jun 04 '14 at 17:32

score 0 · Answer 2 · answered May 28 '14 at 21:50

First an error: associativity requires op too, not +.
Closure looks ok.

Neutral element: Well, you have to search for a elment N
so that each element A of the set fulfills op(A,N)=A and op(N,A)=A
(these two things are not the same)
There have to be such a N, or it isn´t a group.
Try every element for N, and in the N loop every A...

And inverse elements: For each element A there has to be a B (can be the same as A)
so that op(A,B)=N (N from before).
These things will fit easy in your loops.
Every A {Every B {...}}
N is known.

BUT: If you want to work with big data sets like all long (or even infinite stuff)
you can´t use such simple methods anymore (even the associativity etc. is bad)
And asking about reimplementing Mathematica etc. is a bit much...

The neutral element is unique. Proof: Suppose `E1.A = A` and `B.E2 = B` for all `A, B`. Now take `A = E2` and `B = E1`. Then we have `E1 = E1.E2 = E2`. — Kerrek SB, May 28 '14 at 21:59
@bits_international But if you implement Z_m correctly, you'll have `0 == m`. So there's one identity value (which can maybe be constructed in different ways, but can only be in a `std::set` once). — aschepler, May 29 '14 at 00:17

A few questions about checking whether a set in C++ is an algebraic group

2 Answers2