# C++ function to tell whether a group is cyclic

1. Jun 4, 2014

### Jamin2112

Is there anything wrong with my logic and is there any way to further optimize this potentially long-running function? I've put a lot of comments to explain what's going on.

Code (Text):

template <typename ObType, typename BinaryFunction>
bool isCyclic(const std::set<ObType> & G, BinaryFunction & op, ObType & g)
{
/*
isCyclic returns true or false depending on whether the group G
is an cyclic group, that is, whether it can be generated from
one its elements. Formally, G is cyclic if there exists an
element g in G such that, for all elements h in g,
h = g^n for some n.
*/
bool foundGenerator = false;
size_t maxN = G.size();
/*
Guaranteed that for each x in G, x^(maxN + 1) will be in the set
{x, x^2, ..., x^maxN}. That is the meaning of maxN.
*/

for (typename std::set<ObType>::const_iterator it(G.cbegin()), offend(G.cend()); it != offend && !foundGenerator; ++it)
{
ObType e0 = *it;
ObType e = e0;
std::set<ObType> powSet = {e};
size_t k = 2;
while (k <= maxN)
{
e = op(e, e0); /* Sets e equal to e^i */
if (powSet.count(e) == 0)
powSet.insert(e);
else
break;
/* Why the break statement?
If e is already in powSet, then we've found a cycle but
powSet != G; therefore e cannot generate G.
*/
++k;
}
if (k == maxN) /* true iff (powSet == G) */
{
foundGenerator = true;
g = e;
}
}
return foundGenerator;
}

Last edited: Jun 4, 2014
2. Jun 4, 2014

### jbunniii

A couple of observations:

1. Your algorithm could be more efficient. If $e$ does not generate $G$, then no power of $e$ can generate $G$ either. Proof: if $\langle e\rangle$ is the subgroup generated by $e$, then $e^n \in \langle e \rangle$ and so $\langle e^n \rangle \subset \langle e \rangle$. So you don't have to test all of the elements.

2. Why don't you break out of the for loop when you set foundGenerator = true? [edit I just noticed the !foundGenerator condition on the for loop - I hadn't scrolled far enough to the right to notice it at first. So disregard this observation.]

I haven't checked your logic carefully, so I don't claim that these are the only problems. :tongue:

Last edited: Jun 4, 2014
3. Jun 4, 2014

### jbunniii

Here is another optimization. Let $|G|$ denote the size (order) of $G$. Then for any element, $|\langle e \rangle|$ must be a divisor of $|G|$. So, in order to determine whether $e$ is a generator, you just need to check $e^n$ for each divisor $n$ of $|G|$. So let $n$ be the smallest divisor of $|G|$ such that $e^n$ equals the identity, or equivalently, $e^{n+1} = e$. There are only two possibilities:

1. $n$ is a proper divisor of $|G|$, in which case $e$ does not generate $G$

2. $n = |G|$, in which case $e$ generates $G$

Last edited: Jun 4, 2014
4. Jun 4, 2014

### jbunniii

[edited previous post for clarity]

5. Jun 5, 2014

### rcgldr

Isn't there a potential issue in the case $e^{(n/k)}$ % G == 1, where k could be 2, 3, ... ? I don't know if there is a fast way to determine the smallest m such that $e^m$ % G == 1.

Also, is this potential cyclic field based on a prime number, a Galios field, a Galios binary field, or something else?

Last edited: Jun 5, 2014
6. Jun 5, 2014

### jbunniii

I'm not sure what you mean with the notation $e^{(n/k)}$ % G == 1. In general, a group only has one operation, multiplication. (Exponentiation is just repeated multiplication.) What do you mean by the % operation?

In any case, he doesn't need to find the smallest positive $n$ such that $e^n = 1$, he just needs to determine whether there are any such $n$ which are smaller than (hence strict divisors of) $|G|$. This is true if and only if the element is NOT a generator. A brute force way to do this would be (pardon my pseudocode):

Code (Text):

isGenerator = true; // until proven otherwise
for (n = 1; n <= N/2; n++) // N = |G|; we only need to loop to N/2 since this is the largest possible strict divisor of N
{
if (n is not a divisor of N)
{
continue;
}
if (e^n == 1)
{
isGenerator = false;
break;
}
}

 OK, I think I see your point: it might be more work to check "if (n is not a divisor of N)" than simply to check "if (e^n == 1)" for every n, in which case it might actually be faster without the first "if" block.

I've been assuming that it's just an arbitrary finite group, and that the OP has a C++ class which "implements" the group, i.e. a finite set and a binary operation on the set which obey the group axioms. Jamin - is that correct?

Last edited: Jun 5, 2014
7. Jun 5, 2014

### rcgldr

It appears that the goal here is to find at least a muliplicative cyclic group or possibly a finite field where addition, multiplication and their inverses work with a finite set of elements. I did some testing with a binary Galios field composed of 8 bit elements modulo the thirty possible 9 bit "prime" polynomials. A generator e raised to m = $2^8$ - 1 = 255 results in $e^m$ % G == 1. The largest value I could get for m for a non-generator e such that $e^m$ % G == 1, was m = 85 = 255/3. So in the case of binary fields, jbunniii's for loop might be able to stop at n <= N/3, and n <= N/2 should be safe for most types of fields.

Last edited: Jun 5, 2014
8. Jun 6, 2014

### Jamin2112

Updated it to incorporate that:

Code (Text):

template <typename ObType, typename BinaryFunction>
bool GroupTheorizer::isCyclic(std::set<ObType> G, BinaryFunction & op, ObType & g) const
{
/*
isCyclic returns true or false depending on whether the group G
is an cyclic group, that is, whether it can be generated from
one its elements. Formally, G is cyclic if there exists an
element g in G such that, for all elements h in g,
h = g^n for some n.
*/
bool foundGenerator = false;
size_t maxN = G.size();
/*
Guaranteed that for each x in G, x^(maxN + 1) will be in the set
{x, x^2, ..., x^maxN}. That is the meaning of maxN.
*/
for (typename std::set<ObType>::iterator it(G.begin()); it != G.cend() && !foundGenerator; ++it)
{
ObType e0 = *it;
ObType e = e0;
std::set<ObType> powSet = {e};
size_t k = 2;
while (k <= maxN)
{
e = op(e, e0); /* Sets e equal to e^i */
if (powSet.count(e) == 0)
powSet.insert(e);
else
break;
/* Why the break statement?
If e is already in powSet, then we've found a cycle but
powSet != G; therefore e cannot generate G.
*/
++k;
}
if (k == maxN) /* true iff (powSet == G) */
{
foundGenerator = true;
g = e;
}
else
{
for (std::set<ObType>::iterator i(powSet.begin()), j(powSet.end()); i != j; ++i)
G.erase(*i)
/* Why?
powSet is the set of all powers of e0. If e0 does not generate G, then neither
does any of its powers.
*/
}
}
return foundGenerator;
}

9. Jun 6, 2014

### rcgldr

For most fields, even if e is not a generator, it should cycle through a sub-set of the elements. The inner loop could be changed to something like this:

Code (Text):

e = e0
for(k = 2; k <= maxN; ++k)
{
e = op(e, e0);   // Sets e equal to e^k
if(e == e0)      // break if e cycled back to e0
break;
}
if(k == (maxN-1))    // maxN-1 == # of non-zero elements in the group
{
// found a generator
}

Last edited: Jun 6, 2014