How to choose set in Group Isomorphism Algorithm( Quasipolynomial time)

85 Views Asked by At

In the paper titled "On the $n^{log_2(n)}$ Isomorphism Technique" by Gary L. Miller, it is written

A group is a binary operation * , satisfying 1) and 2) .

1)
a)$ \exists! x(a*b = x)$

b) $\exists! x(a*x = b)$

c) $ \exists! x(x*a = b)$

2) $(a*b)*c = a*(b*c)$

Theorem 1: Quasigroup isomorphism can be solved in $O(n^{log_2(n) + > 0(1)})$ steps.

Proof: Property 1a) says the binary operation is a well-defined function. Now, 1b) and 1c) give two other well-defined functions associated with a quasigroup. We shall say that a set of elements generates the quasigroup if their closure under these three functions is the whole quasigroup.Thus, using this definition, we prove a generalization(Lemma 1) of the observation about the size of the minimal generator set.

Lemma 1: A quasigroup is generated by a set containing at most $log_2(n)$ elements.

To finish the proof of Theorem 1 we give a short description of the algorithm with two quasigroups, $G$ and $G'$, as input:

1) Find a set of generators for $G$, containing at most $log_2(n)$ elements, say, $a_1,···,a_m$.

2) For each set of $m$ elements in $G'$, say, $\{b_1 ,···,b_m \}$ check to see if the map induced by $a_i \mapsto b_i , 1\leq i\leq m$ is a well-defined isomorphism of $G$ onto $G'$

3) If a set of $m$ elements of $G'$ is found in 2) accept;otherwise reject.

I could not understand-

2) For each set of $m$ elements in $G'$, say, $\{b_1 ,···,b_m \}$ check to see if the map induced by $a_i \mapsto b_i , 1\leq i\leq m$ is a well-defined isomorphism of $G$ onto $G'$

I can choose ${n}\choose{m} $ different set, each having $m$ elements where order does not matter. In that case, the problem can't be solved in $O(n^{log_2(n) + 0(1)})$ steps.

So, how "each set of $m$ elements in $G'$, say, $\{b_1 ,···,b_m \}$ check to see if the map induced by $a_i \mapsto b_i , 1\leq i\leq m$ is a well-defined isomorphism of $G$ onto $G'$ " gives a Quasipoloynomial Algorithm? To be precise, how I choose "each set of $m$ elements" ?