Maneuvering with limited moves on $S^2$

This question comes to me via a friend, and apparently has something to do with quantum physics. However, stripped of all physics, it seems interesting enough on its own. I assume someone has asked this question before, but I have no idea what to search for:

Suppose we have points $P$ and $Q$ on $S^2$, and two available rotations: specifically, I am interested in rotations by $\pi/4$ radians about the $x$ and $z$ axes. Given $\varepsilon > 0$, is there an effective algorithm for applying these rotations to $P$ so that it is within Euclidean distance $\varepsilon$ of $Q$?

Edit: Update retracted. I'm curious about the general situation as well, where the two rotations are arbitrary (and, obviously, send $P$ to a dense subset of $S^2$).

• Very cute question! – André Henriques Apr 18 '11 at 18:52
• I think this amounts to a word problem for a certain subgroup of (whatever spatial group, SO2 or SL3 or something like that). For general rotations in place of yours, I suspect there is no such algorithm. For your specific case, I suspect the subgroup is finite, and so there is an algorithm to get it as close as possible, but it may not be within \epsilon. Gerhard "Needs Signing For Algebro-Geometrically Impaired" Paseman, 2011.04.18 – Gerhard Paseman Apr 18 '11 at 18:58
• ... unless you are willing to do breadth-first search and move the neighborhood around a lot. Even then, it is a matter of opinion whether brute force can be considered effective. Gerhard "Putting Another Spin On It" Paseman, 2011.04.18 – Gerhard Paseman Apr 18 '11 at 19:05
• One way would be to first construct rotations of irrational multiples of $\pi$ about two axes distinct axes X,Y. As the multiples of an irrational modulo 1 is equidistributed, you can do the following. Keep rotating X about axis Y (or vice versa) until it lies close to the great circle equidistant from P,Q. Then rotate P about this rotated axis until it is close to Q. By equidistribution, you would expect about $O(1/\epsilon)$ individual rotations are required in each of these steps. So, combining them, about $O(1/\epsilon^2)$ individual rotations overall. – George Lowther Apr 18 '11 at 22:39
• One context this question comes up is in quantum computation. Is that the context of interest here? – Dylan Thurston Apr 19 '11 at 18:32

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

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 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. 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$.

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 multiplying by 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.

• Thank you for the detailed answer, this problem had been stumping me for quite some time. – Eric Tressler Apr 20 '11 at 1:12

Using properties of commutators in a neighborhood of identity (beautifully described in Bill Thurston's answer, on which the following is a comment), Solovay-Kitaev algorithm in quantum computation produces words of length $O(\log^{2+}(1/\epsilon))$ for any dense subgroup; see, for example,  for a very nice exposition.

For dense subgroups generated by elements with algebraic entries, the spectral gap result proved in  implies existence of words of length $O(\log(1/\epsilon))$.

 C.M. Dawson and M.A. Nielsen, The Solovay-Kitaev algorithm, Quantum Inf. Comput., 6, 81-95, 2006.

J. Bourgain and A. Gamburd, On the spectral gap for finitely generated subgroups of SU(2), Inv. Math. 171, 83-121, 2008.

(It appears to be of interest (and challenge) to extend the result in  to arbitrary dense subgroups, and to find an effective algorithm producing words of length $O(\log(1/\epsilon))$).