1

I'm writing an algorithm that takes as input a finite set of matrices in SU(2) and consequently tries to generate an '$\epsilon$-net' by computing all possible matrix products (up to a given depth). If, in this process, a matrix is encountered that is within a distance $\epsilon$ of a previously generated matrix (w.r.t. the 2-norm), it is discarded and its 'branches' will not be walked anymore.

So far, everything works well, but I was wondering whether there is a feasible way of computing an upper bound to the number of matrices in a net of a given 'tightness' (i.e. value for $\epsilon$. My first intuition was that this upper bound is $(2/\epsilon)^3$, since the maximum distance in SU(2) is 2 and the space is 3-dimensional (in the same way that a 2x2x2 box can contain at most $(2/\epsilon)^3$ points with a distance of at least $\epsilon$ from each other). However, this seems too naive a view, as the nets I'm currently generating end up way larger than this.

I'm probably thinking too 'Euclidean' about SU(2), so I'm very much interested if anyone can point out to me where my reasoning fails.

JorenB
  • 549

1 Answers1

2

$SU(2)$ can be parametrized by $S^3$, and in this parametrization the $2$-norm you're using is simply the Euclidean norm in $\mathbb R^4$. The surface of $S^3$ is $2\pi^2$ (see Wikipedia). The matrices sit in non-overlapping hyperspherical caps of radius $\epsilon/2$, and for small $\epsilon$ these are approximately $2$-spheres with volume $\frac43\pi(\epsilon/2)^3$ each. Thus you can fit at most approximately

$$ \frac{2\pi^2}{\frac43\pi(\epsilon/2)^3}=\frac{12\pi}{\epsilon^3} $$

matrices with minimal distance $\epsilon$ into $SU(2)$. To make this a rigorous upper bound, you'd have to take into account the fact that the hyperspherical caps aren't exactly spheres, but this effect becomes negligible for small $\epsilon$, and anyway we're wasting a lot of space in between the spherical caps, so I'd expect this to be a proper upper bound.

Asymptotically, I'd expect that you can pack the hyperspherical caps about as tightly as you can pack spheres in $\mathbb R^3$, which is achieved by face-centred cubic and hexagonal close-packed lattices, with a density of

$$ \frac\pi{3\sqrt2}\approx0.74048\;, $$

so in that case the number of matrices you can fit into $SU(2)$ would asymptotically be

$$ \frac{12\pi}{\epsilon^3}\frac\pi{3\sqrt2}=\frac{4\pi^2}{\sqrt2}\frac1{\epsilon^3}\approx28\epsilon^{-3}\;, $$

quite a bit more than the $8\epsilon^{-3}$ you'd estimated.

joriki
  • 238,052
  • Thank you, sounds like a solid answer! However, it might mean that my algorithm is off. For example, setting $\epsilon=1$, a specific dense set of generators gives me no less than 56 matrices, twice the expected amount. With a tightness of 0.5, I even get 608 matrices, where we'd only expect 224. I've looped through the result and this confirms that the minimum inter-element distance is indeed $\epsilon$. Might there be a straightforward explanation for this? – JorenB Mar 24 '13 at 16:18