# How to generate a net on a 8-dimensional sphere

Using Matlab, how to generate a net of 3^10 points that are evenly located (or distributed) on the 8-dimensional unit sphere?

-
How are you measuring evenness? In any case, you could just pick them uniformly at random... –  Mariano Suárez-Alvarez Jul 19 '10 at 5:12
Mariano, Probably use the euclidean distance to measure the evenness. But how to pick the points uniformly at random in matlab? –  user7738 Jul 19 '10 at 6:14
Google for "sample points uniformly on a sphere" and choose the link to Mathoverflow offered by google :P –  Mariano Suárez-Alvarez Jul 19 '10 at 6:26
MathOverflow is not a place where it is appropriate to ask for MATLAB code, but we welcome interesting questions in applied mathematics. I don't know the precise meaning of "evenly located" as you use it, but if you search for "mesh-generation algorithms" you will find a lot of information. In particular, I think Ruppert's algorithm can be adapted to your purposes, and you can set lower bounds on the dihedral angles you get. –  S. Carnahan Jul 19 '10 at 12:57

If it's really important for the points to be evenly distributed, and you don't mind doing a lot of calculation to get them that way, you can start with a randomly distributed set and then iterate over the entire set repeatedly, allowing each point in turn to make whatever small adjustment improves your chosen definition of uniformity, and repeat this until the set of points converges. If you're even pickier than that, and not satisfied by just a locally optimal arrangement, the canonical next thing to try is simulated annealing.

For picking points at random, I agree with Peter Shor that taking the time to implement a one-to-one volume-preserving map from a product of intervals to a high-dimensional sphere would be much more wasteful (of time; you would learn a lot) than throwing away 98% of your random numbers. It's an interesting question, though, whether systematically chosen points in a product of intervals can be well-distributed under one of these volume-preserving (but distance-destroying) maps. The first interesting case of such a map is the axial projection from the curved surface of a cylinder of height 2 and radius 1 to the surface of the unit sphere it contains: projecting straight to the axis, one direction gets stretched out in exact counterbalance to the compression of the other direction. Call the coordinates of the cylinder surface z ∈ [$-1$, $1$] and θ ∈ [$0$, $2\pi$]. Choosing an ordinary regular rectangular grid in z and θ does terrible things to the projection. On the other hand, for any $N$, setting zi = $(-N+2 i - 1)$/$N$ and θi = $2\pi (\phi i$ mod $1$), where $\phi$ is the golden mean, actually gives a very nice distribution of points after projection. It's possible that in any dimension there is such a lattice in the cube that projects nicely, for any N, to the sphere.

-

If you're looking for points on the 8-dimensional sphere, another thing you could do is go to Neil Sloane's table of spherical codes, scroll down until you get to dimension 8, and obtain a sphere covering which has 2160 points fairly evenly distributed (obtained from second shell of vectors in the E8 lattice). Now, if you apply $3^{10}/2160 \approx 27$ random orthogonal matrices to this set, you'll get a set of points distributed on the 8-dimensional sphere which is presumably somewhat more uniform than a set of random points. Since I don't know why you want these vectors, I don't know how much an improvement this is over random points, and whether it's worth all the extra work.

You can get random orthogonal transformations by starting with an $8 \times 8$ matrix with random Gaussian entries. First, normalize the top row to make it a length 1 vector. Next, subtract a multiple of the top row from the second row to make it perpendicular to the top row, and then normalize to make the second row a length 1 vector, and so on.

-
All of these operations should be straightforward using MATLAB. –  Peter Shor Jul 19 '10 at 17:34

In case the goal is to draw points inside the sphere, the discussion Intuitive proof that the first (n-2) coordinates on a sphere are uniform in a ball seems relevant.

In other words, one simply draws random points on the 10-dimensional sphere (by drawing a normal vector and normalizing it) and discards the last two coordinates.

-

Forgetting Matlab, the 'best' way to...hold on, do you mean -in- the sphere or -on- the sphere?

For -in- the sphere, create 8-tuples where each element is from the uniform distribution from 0 to 1. Ignore those tuples whose Euclidean norm $\sqrt{\sum x_i^2}$ is greater than 1. Do this until you have $3^{10}$ points. This is a uniform distribution over the sphere.

For -on- the sphere, create 8-tuples as before, but then divide each point by the norm (of course throw out $\langle 0,0,0,0,0,0,0,0\rangle$ ). This will place a point on the surface. Do this $3^{10}$ times. This is not an exact uniform distribution but is a very good approximation to one, and is very easy to do.

-
Because the volume of an $n$-sphere is small when $n$ is large, I believe there will be significant inefficiencies your first method: more than 97% of the volume of the cube is exterior to the enclosed 8-ball. –  Joseph O'Rourke Jul 19 '10 at 17:27
Actually, 98%, as Peter's calculation shows! –  Joseph O'Rourke Jul 19 '10 at 17:29
If I did the calculation right, only 1.6% of the points given by this method will be inside the sphere. However, in this case the overhead of choosing 60 times as many points as you need is pretty much negligible compared to the cost of programming a better method. –  Peter Shor Jul 19 '10 at 17:30
I believe you meant to say draw 8-tuples from the uniform distribution from $-1$ to $1$, otherwise you are picking from just 1/256th of the the volume of the 8-sphere by limiting it to the region of space with all positive coordinates. Alternately, you could pick from the uniform distribution from 0 to 1 but change your selection criteria to accepting only those points where $$\sqrt{\sum (x_i-0.5)^2} \le 0.5$$. –  sleepless in beantown Aug 29 '10 at 14:40

In general, for generating extra-regular but not-too-regular distributions of points (in a technical sense, "low discrepancy", meaning that the variance in the length of gaps between points is smaller than a uniform distribution), you can use a class of methods called quasi monte carlo methods. There are libraries in MATLAB.

http://en.wikipedia.org/wiki/Quasi-Monte_Carlo_method

http://www.mathworks.com/matlabcentral/fileexchange/17457-quasi-montecarlo-halton-sequence-generator

Though if you want a totally uniform set of points, these won't help you.

-

Talking out of my depth so I am not sure this work, but here is a start of an idea... Say you were finding points uniformly on $S^3$, couldn't you use Hopf fibration? The idea is you select Hopf fiber uniformly from $S^2$ then it is easy to populate points uniformly on the Hopf fiber, which is a circle in this case. Unfortunately, there is no such relation for $S^8$.

Instead one could potentially use the following

$S^1\hookrightarrow S^3 \rightarrow S^2$

and then

$S^3\hookrightarrow S^7 \rightarrow S^4$

but then one needs to construct uniformly spaced points on $S^4$ from uniformly spaced points in $S^3$ and same for $S^8$ and $S^7$, which doesn't seem that hard.

-

Shells of evenly spaced lattice points:

To generate evenly spaced sets of non-random points on an n-sphere, start with the permutations of { 0 1 1 ... 2 2 ... }, then make 2^n flips of that. For example, in 4-space start with the 12 permutations of { 0 1 1 2 }. Each point is √6 from the origin, and each has 4 neighbours √2 away (+1 here, -1 there):

0 1 1 2

0 1 2 1
0 2 1 1
1 0 1 2
1 1 0 2


Make 2^4 sign-flipped copies of this, i.e. multiply by { 1 1 1 1 } .. { -1 -1 -1 -1 } except where there's a 0. This gives a shell of 96 points, 0 1 1 2 .. 0 -1 -1 -2. Each is √6 from the origin, and each now has 6 neighbours √2 away.

For the 8-sphere, start with the 280 permutations of { 0 1 1 1 1 2 2 2 }. Each has of course the same distance from the origin, and each has 12 neighbours √2 away — a nice, regular graph. The shell of 280 * 2^7 = 35840 sign-flipped points is not quite 3^10, but.

(I'd appreciate links to papers or programs on such graphs.)

-