30
$\begingroup$

Suppose someone (person B) knows a finite group $G$ of order $n$. You (person A) know only the order $n$, and that $1$ is the name of the identity element. The group elements are named $1,2,\ldots,n$ in arbitrary order, arbitrary except that $1$ is the identity. You are permitted to make queries of this form to B, who answers truthfully:

Tell me which element $c$ of $G$ is the product (group operation) of elements $a$ and $b$, i.e., $a \circ b =\;$?

  • Q. How many queries always suffice (and are sometimes needed) to determine $G$?

This has likely been studied but I must not be using the accepted terminology in my searches.

As a simple example, how many queries are needed to distinguish between the two groups of order $4$, $K_4$ and $Z_4$? I believe that two queries suffice:

  • $2 \circ 2 =\;$?
  • $3 \circ 3 =\;$?

This is because in the Klein group, $a^2 = 1$ for all $a$, but in $Z_4$, only one of the three non-identity elements has a square of $1$. The first query could (unluckily) yield $2 \circ 2 = 1$, but then the second query settles it.

Added. By "determine $G$," I mean identify which of the $k$ non-isomorphic groups of order $n$ is $G$. For example, there are $5$ groups of order-$8$; there are $14$ groups of order-$16$. The goal of the queries would be to pinpoint which of these groups is $G$, up to group isomorphism.

$\endgroup$
  • 11
    $\begingroup$ At least $cn$, for some constant $c$ - certainly for $n/12$ your total queries and outputs only involve a quarter of the elements, so you can't distinguish between $H \times \mathbb Z/4$ and $H \times \mathbb Z/2 \times \mathbb Z/2$ for any group $H$. $\endgroup$ – Will Sawin Apr 29 '15 at 1:33
  • 8
    $\begingroup$ What do you mean by "determine $G$"? Do you mean find the isomorphism type, or find the full multiplication table. (I'm not sure if the answer is different, I just want to clarify). In any case, the phrase "black-box group" will probably help in looking for references. See for example: math.uzh.ch/fileadmin/user/rosen/publikation/zu08p.pdf $\endgroup$ – verret Apr 29 '15 at 1:58
  • 2
    $\begingroup$ I think it would be natural to also ask how many queries are necessary to determine the group law itself (not only the isomorphism class), since this does not rely on the classification of all groups of order $n$. Also we could wonder the generic number of necessary steps rather than the worst case (typically in a group that is a direct product of a subgroup $H$ with a group $L$ of order 4 I could accidentally ask for the whole law of $H$ and get no information on $L$, but this is unlikely)... and even in the worst case I have several understanding of "how many queries suffice". $\endgroup$ – YCor Apr 29 '15 at 10:31
  • 5
    $\begingroup$ Similar questions have been asked and (modulo certain number-theoretic conjectures) answered for identifying isomorphisms with specific groups: see, e.g. math.ucla.edu/~pak/papers/recfin.pdf. $\endgroup$ – Sam Hopkins Apr 29 '15 at 13:54
  • 2
    $\begingroup$ @SamHopkins: Thanks. Here's the full reference: Bratus, Sergey, and Igor Pak. "Fast constructive recognition of a black box group isomorphic to Sn or An using Goldbach's Conjecture." J. Symbolic Computation. 29.1 (2000): 33-57. $\endgroup$ – Joseph O'Rourke Apr 29 '15 at 14:39
6
$\begingroup$

I can determine the multiplication table of $G$ in at most $n\log_2n$ queries.

Pick an element $g_1\in G\setminus\{1\}$ and compute the values of $g_1\circ h$ for all $h\in G$. This determines the values of $g\circ h$ for all $g\in\langle g_1\rangle$ and $h\in G$. If $\langle g_1\rangle=G$ then we are done. Otherwise, pick an element $g_2\in G\setminus\langle g_1\rangle$ and compute the values of $g_2\circ h$ for all $h\in G$. This determines the values of $g\circ h$ for all $g\in\langle g_1,g_2\rangle$ and $h\in G$. If $\langle g_1,g_2\rangle=G$ then we are done. Otherwise, pick an element $g_3\in G\setminus\langle g_1,g_2\rangle$ and repeat this process until $\langle g_1,\ldots,g_k\rangle=G$.

The total number of queries will be $kn$, where $k$ was the number of $g_j$ required to generate $G$ (perhaps suboptimally). By induction, $\lvert\langle g_1,\ldots,g_j\rangle\rvert\geq2^j$. Then $n\geq2^k$ so $k\leq\log_2n$.

$\endgroup$
  • $\begingroup$ It's easy to reduce this to $(n-2)\log_2n$ by not computing the values of $g_j\circ1=g_j$ and $g_j\circ g_j$ (which can be determined by process of elimination). Reducing the factor of $\log_2n$ would require a more sophisticated strategy for picking the $g_j$ (presumably, after some precomputation). $\endgroup$ – Thomas Browning Aug 12 at 6:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.