Encontrar 'verbalmente menor elemento de un finitely generado grupo

Question

Deje $G = ({\Large\ast}^n\mathbb{Z})/K$ ser un grupo, y para cada una de las $g \in G$ definir $l(g)$ como el menor entero positivo $m$ tal que $g = g_1 \ldots g_m$, donde cada una de las $g_i$ es un generador de $G$. Ahora vamos a $H < G$. El problema es encontrar $\operatorname{arg\,min}_{g \in H \setminus \{1\}} l(g)$.

Mi motivación es el colector-base de la magia' puzzle publicado por Gil Kalai aquí, que se reduce a la búsqueda de un no-trivial elemento de $\bigcap_{i=1}^n \operatorname{ker}p_i$ donde $p_i: {\Large\ast}_{j = 1}^n \mathbb{Z}a_j \to {\Large\ast}_{j \neq i}\mathbb{Z}a_j$ está definido por $p_i(a_j) = a_j$ al$i \neq j$$p_i(a_i) = 1$. Uno no trivial elemento es $[\ldots[a_1, a_2], a_3], \ldots], a_n]$, pero he escuchado a gente quejándose de que es demasiado largo y el bucle correspondiente será demasiado duro para dibujar, así que ahora estoy interesado en encontrar una solución más pequeña, si es que existe.

¿Se conocen los teoremas respecto a este tipo de problemas o de cualquiera de las técnicas que se podría tratar o las eventuales referencias que se podía leer?

Answer 1

Yo no conozco a ninguna teoremas, pero la búsqueda simple de los rendimientos de la dada colector es óptimo para n ≤ 3:

• n = 1: $a_1$, un simple bucle
• n = 2: $[a_1,a_2]$, el contorno de Pochhammer
• n = 3: $[[a_1,a_2],a_3]$, Poch-Loop-ReversePoch-ReverseLoop

Sospecho que esto es óptima en general, ya K es la contenida en el nésimo término de la parte inferior central de la serie, por lo que los elementos de K son productos de conmutadores de longitud n de todos modos.

Estoy un poco impresionado con n = 5, sin embargo: que es una longitud de 46. No es tan malo para hacer de forma recursiva (al menos para n=3), pero no estoy seguro de que me gustaría tener la paciencia para 46 devanados. El dado colector tiene una longitud de $3\cdot(2^{n-1})-2$, por lo que este, sin duda consigue inmanejable rápidamente.

Sugiero dibujo de los bucles más como las trenzas, así que tiene n horizontal, palitos de iniciar el bucle a la izquierda, y tiene el viento lentamente a la derecha, que muestra si se está por encima o debajo de cada palo de como va. El final en el extremo derecho se conecta de nuevo a la izquierda por debajo (supongo que sería un buen lugar para que la foto se bloquea).

El tex también está disponible y se utiliza Andrew Stacey del nudos en tikz código.