Adivinar ese grupo mediante consultas de productos

Question

Supongamos que alguien (persona B) conoce un grupo finito $G$ de orden $n$ . Usted (persona A) sólo conoce el orden $n$ , y que $1$ es el nombre del elemento de identidad. Los elementos del grupo se denominan $1,2,\ldots,n$ en orden arbitrario orden arbitrario, arbitrario excepto que $1$ es la identidad. Se le permite hacer preguntas de esta forma a B, que responde con la verdad:

Dígame qué elemento $c$ de $G$ es el producto (operación de grupo) de los elementos $a$ y $b$ es decir, $a \circ b =\;$ ?

• Q . ¿Cuántas consultas bastan siempre (y a veces son necesarias) para determinar $G$ ?

Es probable que esto se haya estudiado, pero no debo estar utilizando la terminología aceptada en mis búsquedas.

Como ejemplo sencillo, ¿cuántas consultas se necesitan para distinguir entre los dos grupos de orden $4$ , $K_4$ y $Z_4$ ? Creo que dos consultas son suficientes:

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

Esto se debe a que en el grupo Klein, $a^2 = 1$ para todos $a$ , pero en $Z_4$ , sólo uno de los tres elementos no identitarios tiene un cuadrado de $1$ . La primera consulta podría (desafortunadamente) dar como resultado $2 \circ 2 = 1$ , pero entonces la segunda consulta lo resuelve.

Añadido . Por "determinar $G$ Me refiero a identificar cuál de los $k$ no isomorfo grupos de orden $n$ es $G$ . Por ejemplo, hay $5$ grupos de orden- $8$ ; hay $14$ grupos de orden- $16$ . El objetivo de las consultas sería señalar cuál de estos grupos es $G$ hasta el isomorfismo de grupo.

Answer 1

Puedo determinar la tabla de multiplicar de $G$ en un máximo de $n\log_2n$ preguntas.

Elige un elemento $g_1\in G\setminus\{1\}$ y calcular los valores de $g_1\circ h$ para todos $h\in G$ . Esto determina los valores de $g\circ h$ para todos $g\in\langle g_1\rangle$ y $h\in G$ . Si $\langle g_1\rangle=G$ entonces hemos terminado. Si no, elige un elemento $g_2\in G\setminus\langle g_1\rangle$ y calcular los valores de $g_2\circ h$ para todos $h\in G$ . Esto determina los valores de $g\circ h$ para todos $g\in\langle g_1,g_2\rangle$ y $h\in G$ . Si $\langle g_1,g_2\rangle=G$ entonces hemos terminado. Si no, elige un elemento $g_3\in G\setminus\langle g_1,g_2\rangle$ y repetir este proceso hasta que $\langle g_1,\ldots,g_k\rangle=G$ .

El número total de consultas será $kn$ , donde $k$ era el número de $g_j$ necesario para generar $G$ (quizás de forma subóptima). Por inducción, $\lvert\langle g_1,\ldots,g_j\rangle\rvert\geq2^j$ . Entonces $n\geq2^k$ así que $k\leq\log_2n$ .