show/hide this revision's text 3 Added comments on short words

*More comments at end on finding group elements with small word length *

Addendum. Any finitely-generated subgroup of $SO(3)$ generated by matrices with algebraic integer entries (such as this) has a faithful discrete action on a product of spheres, hyperbolic planes, and hyperbolic 3-spaces, by a general construction for algebraic groups, from which it follows that it is either virtually abelian or has exponential growth and in fact it contains a free subgroup. It seems likely that these group elements have orbits on $S^2$ that are reasonably uniformly distributed, although I don't know what's proven about it. If so, by just counting elements it would follow that $P$ can be take to within $\epsilon$ of $Q$ using a word of length linear in $\log(\epsilon)|$.

It looks like an interesting challenge to try to find a polynomial-time algorithm that will find such a word. Once $P$ is within a small negihbrohood of $Q$ and you have a modest selection of moderate-length words that look almost like translations in a magnification of this small neighborhood, one strategy would be to make a first approximation of getting closer by adding vectors. But they are not exactly addition of a vector, and the many different possible orders in which you could multiply them give many different results.If you could systematically analyze and control the effects of changing the orde it might be possible to systematically improve the approximtion. In other words: instead of multiplyingby higher and higher commutators at the end, actually commute elements in the produt.

However, this is more of a challenge than I feel like plunging in to here.
show/hide this revision's text 2 Typos, omitted logic

If you're willing to accept an element of the group (as distinguished from a word expressing an element) there is an algorithm that will produce such an element moving $P$ to within $\epsilon$ of $Q$ that is polynomial as a function of the number of bits of $\epsilon$, that is, $|\log(\epsilon)|$. If you need a word, there are algorithms that are at least as good as polynomial in $1/\epsilon$.

First: this group is dense, because the only finite subgroups of $SO(3)$ that do are not contained in $O(2) \times O(1)$ have elements of orders only 2, 3, 4 and 5. There are good descriptions of all such subgroups in various places, but I won't go over this here --- I an explain if pressed. A rotation by $\pi/4$ has order 8, and the group, by inspection does not preserve a splitting. Therefore, the group is infinite. Any infinite subgroup of any Lie group is dense in some closed subgroup. By inspection, this group does not preserve any splitting, so The only possibility is that it is dense in $SO(3)$.

The basic phenomenon that helps for approximation is that in any Lie group with any Riemannian metric, there is a radius $r$ such that for $g, h \in B_r$ (the ball of radius $r$), the commutator $[g, h]$ is contained in the much ball $B_{2 r^2}$, which is much smaller if $r$ is small. This follows from Taylor approximation of the commutator in a neighborhood of $[1,1]$. More concretely, $|[g,h]| < 2|g| |h|$, where $||$ denotes distance from the identity.

Furthermore, for two isometries of $S^2$ that move a point $X$ a small distance, $[g,h]$ is nearly a translation, since the group $SO(2)$ of possible first derivatives with respect to some local frame field is abelian.

Using this, you can get from $P$ to $Q$ by successive approximation. If we denote the two generators $X$ and $Z$, we can first, take $Q$ roughly to within striking distance of $P$ by some element of the form $X^k Z^j$. Or, use some other word; this first step has fixed finite cost, and can be done by exhaustive search through some set of words in $X$ and $Y$.

Now, use commutators of smallish elements to find still smaller elements, and use these to bring $Q$ still closer to $P$. It is easy to generate approximate translations of all scales, by judiciously choosing commutators of elements on larger scales. The computations in $O(3)$ to desired accuracy can be done in polynomial time.

One concrete tool to actually implement this would be to reduce the question to the case that $P$ is a fixed point of an element $W$ of infinite order. (It is easy to find such elements, using a $p$-adic valuation). Given one approximate translation that moves $P$ a small distance, conjugates of it by powers of $W$ are translations approximating any desired direction. If you take the commutator with a fixed approximate translation of medium size, it is an approximate translation of size approximately say $1/3$ the original.

In this process, elements of the group are generated recursively, and the wordlength in original generators typically grows exponentially in the number of steps, but they have exponentially increasing accuracy of moving $Q$ to $P$. If you unroll the process, it takes polynomial length words in $1/\epsilon$ to move $Q$ to within $\epsilon$ of $P$.
show/hide this revision's text 1

If you're willing to accept an element of the group (as distinguished from a word expressing an element) there is an algorithm that will produce such an element moving $P$ to within $\epsilon$ of $Q$ that is polynomial as a function of the number of bits of $\epsilon$, that is, $|\log(\epsilon)|$. If you need a word, there are algorithms that are at least as good as polynomial in $1/\epsilon$.

First: this group is dense, because the only finite subgroups of $SO(3)$ that do not contained in $O(2) \times O(1)$ have elements of orders only 2, 3, 4 and 5. There are good descriptions of all such subgroups in various places, but I won't go over this here --- I an explain if pressed. Therefore, the group is infinite. Any infinite subgroup of any Lie group is dense in some closed subgroup. By inspection, this group does not preserve any splitting, so it is dense in $SO(3)$.

The basic phenomenon is that in any Lie group with any Riemannian metric, there is a radius $r$ such that for $g, h \in B_r$ (the ball of radius $r$), the commutator $[g, h]$ is contained in the much ball $B_{2 r^2}$, which is much smaller if $r$ is small. This follows from Taylor approximation of the commutator in a neighborhood of $[1,1]$. More concretely, $|[g,h]| < 2|g| |h|$, where $||$ denotes distance from the identity.

Furthermore, for two isometries of $S^2$ that move a point $X$ a small distance, $[g,h]$ is nearly a translation, since the group $SO(2)$ of possible first derivatives with respect to some local frame field is abelian.

Using this, you can get from $P$ to $Q$ by successive approximation. If we denote the two generators $X$ and $Z$, we can first, take $Q$ roughly to within striking distance of $P$ by some element of the form $X^k Z^j$. Or, use some other word; this first step has fixed finite cost, and can be done by exhaustive search through some set of words in $X$ and $Y$.

Now, use commutators of smallish elements to find still smaller elements, and use these to bring $Q$ still closer to $P$. It is easy to generate approximate translations of all scales, by judiciously choosing commutators of elements on larger scales. The computations in $O(3)$ to desired accuracy can be done in polynomial time.

One concrete tool to actually implement this would be to reduce the question to the case that $P$ is a fixed point of an element $W$ of infinite order. (It is easy to find such elements, using a $p$-adic valuation). Given one approximate translation that moves $P$ a small distance, conjugates of it by powers of $W$ are translations approximating any desired direction. If you take the commutator with a fixed approximate translation of medium size, it is an approximate translation of size approximately say $1/3$ the original.

In this process, elements of the group are generated recursively, and the wordlength in original generators typically grows exponentially in the number of steps, but they have exponentially increasing accuracy of moving $Q$ to $P$. If you unroll the process, it takes polynomial length words in $1/\epsilon$ to move $Q$ to within $\epsilon$ of $P$.