*Más comentarios al final en la búsqueda de los elementos del grupo con la pequeña longitud de palabra *
Si usted está dispuesto a aceptar un elemento del grupo (que se distingue de una palabra que expresa un elemento) no hay un algoritmo que va a producir un movimiento del elemento $P$ a en $\epsilon$ de % de $Q$ que es el polinomio como una función del número de bits de $\epsilon$, es decir, $|\log(\epsilon)|$. Si usted necesita una palabra, hay algoritmos que son al menos tan buena como polinomio en $1/\epsilon$.
La primera: este grupo es densa, porque la única finito subgrupos de $SO(3)$ que no están contenidas en $O(2) \times O(1)$ tienen elementos de órdenes 2, 3, 4 y 5. Hay buenas descripciones de todos los subgrupos en varios lugares, pero no voy a hablar sobre esto aquí --- I explicar si se presionan. Una rotación por $\pi/4$ es de orden 8, y el grupo, mediante la inspección no conserva una división. Por lo tanto, el grupo es infinito. Cualquier infinita subgrupo de cualquier Mentira grupo es denso en algunos cerrado subgrupo. La única posibilidad es la de que es denso en $SO(3)$.
El fenómeno básico que ayuda para la aproximación es que en cualquier Mentira grupo con cualquier métrica de Riemann, hay un radio $r$ tal que para $g, h \in B_r$ (la bola de radio $r$), el colector $[g, h]$ está contenido en la bola de $B_{2 r^2}$, que es mucho menor si $r$ es pequeña. Esto se deduce de la aproximación de Taylor de el colector en un barrio de $[1,1]$. Más concretamente,
$|[g,h]| < 2|g| |h|$ donde $||$ indica la distancia a partir de la identidad.
Además, para dos isometrías de $S^2$ que se mueven de un punto de $X$ a una pequeña distancia, $[g,h]$ es casi una traducción, ya que el grupo $SO(2)$ de las posibles primeras derivadas con respecto a algunos de los locales marco de campo es abelian.
Con esto, usted puede conseguir de $P$ a $Q$ por aproximaciones sucesivas. Si denotamos los dos generadores $X$ e $Z$, podemos en primer lugar, tome $Q$ aproximadamente dentro de una notable distancia de $P$ por algún elemento de la forma
$X^k Z^j$. O, use alguna otra palabra; este primer paso ha fijado finito costo, y se puede hacer mediante la búsqueda exhaustiva a través de un conjunto de palabras en $X$ e $Y$.
Ahora, utilice los conmutadores de pequeña elementos para encontrar todavía de elementos más pequeños, y el uso de estas
para traer a $Q$ aún más a $P$. Es fácil generar aproximado traducciones de todas las escalas, por la juiciosa elección de los conmutadores de elementos en mayor escala. Los cálculos en $O(3)$ a la precisión deseada se puede hacer en el polinomio de tiempo.
Un instrumento concreto para poner en práctica este sería reducir la cuestión para el caso de que $P$ es un punto fijo de un elemento $W$ de orden infinito. (Es fácil encontrar tales elementos, el uso de un $p$-ádico de valoración). Dada una traducción aproximada que se mueve a $P$ a una pequeña distancia, se conjuga de la misma por los poderes de $W$ son traducciones aproximar cualquier dirección deseada. Si usted toma del colector con un fijo de traducción aproximada de tamaño mediano, es una traducción aproximada de tamaño aproximadamente decir $1/3$ el original.
En este proceso, los elementos del grupo se generan de forma recursiva, y el wordlength en original generadores normalmente crece de manera exponencial en el número de pasos, pero tienen exponencialmente mayor precisión de movimiento $Q$ a $P$. Si usted desenrolle el proceso, que toma el polinomio de la longitud de las palabras en $1/\epsilon$ a moverse $Q$ a en $\epsilon$ de %de$P$.
Addendum. Cualquier finitely generado subgrupo de $SO(3)$ generado por las matrices algebraicas entero entradas (como este) tiene una fieles de acción individuales en un producto de esferas, planos hiperbólicos, y hiperbólico de 3 espacios, por un general de construcción para algebraica de los grupos, a partir de la cual se deduce que es virtualmente abelian o tiene un crecimiento exponencial y en el hecho de que contiene un libre subgrupo. Parece probable que estos elementos del grupo tienen órbitas en $S^2$ que son razonablemente distribuidas de manera uniforme, aunque no sé lo que es probado al respecto. Si es así, por sólo contar los elementos se seguiría que $P$ se pueden tomar para dentro de $\epsilon$ de % de $Q$ mediante el uso de una palabra de longitud lineal en $\log(\epsilon)|$.
Parece un reto interesante para tratar de encontrar un polinomio de tiempo de algoritmo que se va a encontrar una palabra. Una vez $P$ está dentro de un pequeño negihbrohood de $Q$ y tiene una modesta selección de moderada longitud de las palabras que se ven casi como las traducciones en una ampliación de este pequeño barrio, una estrategia sería hacer una primera aproximación una aproximación mediante la adición de vectores. Pero no son exactamente la adición de un vector, y los diferentes órdenes posibles en los que podría multiplicar dar muchos resultados diferentes.
Si se pudiera analizar sistemáticamente y control de los efectos de los cambios en el orde podría ser posible para mejorar sistemáticamente el approximtion. En otras palabras: en lugar de multiplicar
por más y más los conmutadores en la final, en realidad conmutar elementos en el produt.
Sin embargo, esto es más de un desafío que me siento como sumergirse en aquí.
