¿Cuál es la longitud de la $f(n)$ de la menor no trivial grupo de palabras $w_n$ $x_1,\ldots,x_n$ que se derrumba a $1$ cuando se sustituye $x_i=1$ cualquier $i$?
Por ejemplo, $f(2)=4$, con el colector $[x_1,x_2]=x_1 x_2 x_1^{-1} x_2^{-1}$ alcanzar el límite.
Para cualquier $m,n \ge 1$, la construcción $w_{m+n}(\vec{x},\vec{y}):=[w_m(\vec{x}),w_n(\vec{y})]$ muestra que $f(m+n) \le 2 f(m) + 2 f(n)$.
Es $f(1),f(2),\ldots$ la misma que la secuencia de A073121: $$ 1,4,10,16,28,40,52,64,88,112,136,\ldots ?$$
Motivación: Batir la iterada de conmutacion de la construcción mejoraría el más conocido de los límites en el tamaño de la más pequeña del grupo de la no satisfacción de una identidad.
Respuestas
¿Demasiados anuncios?
camh
Puntos
101
En un manuscrito inédito "para Colgar cuadros Rompecabezas" de Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, y Joseph S. B. Mitchell, vamos a comprobar el $O(n^2)$ límite superior que viene a afirmar colector con una equilibrada división, lo mismo que la secuencia de A073121. (De hecho, el manuscrito de la cites que secuencia.) Se conjetura que hay un $\Omega(n^2)$ límite inferior (y, de hecho, que A073121 es exactamente apretado), pero no he probado. Si usted viene para arriba con una prueba, podría respirar un poco de vida a ese manuscrito y podríamos considerar la posibilidad de unirse.
