Generating the surtopes of an n-simplex

Discussion of tapertopes, uniform polytopes, and other shapes with flat hypercells.

Generating the surtopes of an n-simplex

Postby quickfur » Mon Aug 14, 2006 4:27 pm

Having found a really neat way of enumerating all surtopes of n-cubes and n-crosses using the base 3 expansion of 1...3<sup>n</sup>, I turned my attention to generating the n-simplex.

Unfortunately, this isn't as simple as it may sound (ha!). Although the tetrahedron has a special relationship with the cube, and therefore has completely integral coordinates, this only happens in a select few dimensions (and 4, 5, 6 dimensions are not included, although 7 and 8 are). For example, in 2D, the triangle does not have any obvious relationship with the square, and AFAIK can't have all integral coordinates.

Now, generating the face lattice of an n-simplex turns out to have a neat solution: the Hasse diagram of an n-simplex is isomorphic to the edge structure of an (n+1)-cube (see previous thread here... this was sometime early this year or late last year, I believe). So we can simply generate the edges of an (n+1)-cube, which is very easy, and we have the simplex's face lattice.

The tricky part is generating vertex coordinates so that you get an origin-centered, regular n-simplex. Here's one way to do it:

Define the vertices of the 1-simplex to be (-1) and (1). Let P<sub>1</sub>=1.
For each n>1, we take the vertices of the (n-1)-simplex and append -Q<sub>n</sub> as its n'th coordinate, and add a point (0,0,0,...,P<sub>n</sub>) as the new vertex, where P<sub>n</sub> = 2/sqrt(4-P<sub>n-1</sub><sup>2</sup>), and Q<sub>n</sub> = sqrt(4-P<sub>n-1</sub><sup>2</sup>)-P<sub>n</sub>.

It's left as an exercise for the reader that the resulting coordinates defines an origin-centered regular n-simplex.

The interesting recurrence P<sub>n</sub> converges to 1.1939365665... as n approaches infinity. The question is, is there a closed algebraic expression that defines P<sub>n</sub>? Does the limiting number 1.1939365665... have a closed algebraic expression? (Is it transcendental?)

Note: I corrected the definitions of P and Q, which were missing a square

Note(2): apparently I calculated the limit of P<sub>n</sub> using the old (wrong) definition of P and Q, so the limiting number is wrong. The real limiting number should be sqrt(2).

Note(3): I changed the title 'cos the number is wrong, so the old title is irrelevant now.
Last edited by quickfur on Tue Aug 15, 2006 4:19 am, edited 3 times in total.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Postby bo198214 » Mon Aug 14, 2006 5:12 pm

Yes the limiting number has a closed algebraic expression and is not trancendental, its the solution of
x=2/sqrt(4-x)
x sqrt(4-x) = 2
x^2 (4-x) = 4
which is a cubic equation :P
bo198214
Tetronian
 
Posts: 692
Joined: Tue Dec 06, 2005 11:03 pm
Location: Berlin - Germany

Postby quickfur » Mon Aug 14, 2006 7:14 pm

bo198214 wrote:Yes the limiting number has a closed algebraic expression and is not trancendental, its the solution of
x=2/sqrt(4-x)
x sqrt(4-x) = 2
x^2 (4-x) = 4
which is a cubic equation :P

Ummm... the solutions of your cubic are x=0 and x=4, not the limiting number.

Also, I found a mistake in the equation. it's supposed to be: P<sub>n</sub> = 2/sqrt(4-P<sub>n-1</sub><sup>2</sup>). At any rate, it's non-trivial, because if you expand the recursion, it's an infinite stack of inverse square roots.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Postby bo198214 » Mon Aug 14, 2006 8:29 pm

quickfur wrote:
bo198214 wrote:x^2 (4-x) = 4
which is a cubic equation :P

Ummm... the solutions of your cubic are x=0 and x=4, not the limiting number.

Hey, at the right side is a 4 not a 0. So neither x=0 nor x=4 are solutions. The equation has indeed 3 real solutions and of them is your limiting number.

At any rate, it's non-trivial, because if you expand the recursion, it's an infinite stack of inverse square roots.

The limit *is* trivial! If you have a recurrance a<sub>n+1</sub>=f(a<sub>n</sub>) then the limit is a solution of f(x)=x.

Also, I found a mistake in the equation. it's supposed to be: P<sub>n</sub> = 2/sqrt(4-P<sub>n-1</sub><sup>2</sup>).


As example let us compute the limit of this recurrance. It must be (only if existing of course) a solution of
x=2/sqrt(4-x^2)
x^2(4-x^2)=4
this is biquadratic. y=x^2, y(4-y)=4, 0=y^2-4y+4, double solution at y=2, hence x=+/-sqrt(2)

So your magic number is sqrt(2) ;)
bo198214
Tetronian
 
Posts: 692
Joined: Tue Dec 06, 2005 11:03 pm
Location: Berlin - Germany

Postby quickfur » Mon Aug 14, 2006 8:39 pm

bo198214 wrote:
quickfur wrote:
bo198214 wrote:x^2 (4-x) = 4
which is a cubic equation :P

Ummm... the solutions of your cubic are x=0 and x=4, not the limiting number.

Hey, at the right side is a 4 not a 0. So neither x=0 nor x=4 are solutions. The equation has indeed 3 real solutions and of them is your limiting number.

Ahhh, that's what I did wrong. :-)

At any rate, it's non-trivial, because if you expand the recursion, it's an infinite stack of inverse square roots.

The limit *is* trivial! If you have a recurrance a<sub>n+1</sub>=f(a<sub>n</sub>) then the limit is a solution of f(x)=x.

True. Hmm, my math is rusty... :?

Also, I found a mistake in the equation. it's supposed to be: P<sub>n</sub> = 2/sqrt(4-P<sub>n-1</sub><sup>2</sup>).


As example let us compute the limit of this recurrance. It must be (only if existing of course) a solution of
x=2/sqrt(4-x^2)
x^2(4-x^2)=4
this is biquadratic. y=x^2, y(4-y)=4, 0=y^2-4y+4, double solution at y=2, hence x=+/-sqrt(2)

So your magic number is sqrt(2) ;)

Except that sqrt(2)=1.414 but this number is 1.1939...
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Postby quickfur » Mon Aug 14, 2006 8:44 pm

quickfur wrote:[...]
Except that sqrt(2)=1.414 but this number is 1.1939...

Ack!!! I know what's wrong... I made the mistake in the equation while I was computing its values, not while I was writing this thread. So you're right, the limit is actually sqrt(2). :oops:
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Postby bo198214 » Mon Aug 14, 2006 8:48 pm

quickfur wrote:
The limit *is* trivial! If you have a recurrance a<sub>n+1</sub>=f(a<sub>n</sub>) then the limit is a solution of f(x)=x.

True. Hmm, my math is rusty... :?

but its easy to see, the limit is where the sequence does no more change. And it does no more change when application of f yields the same result.
You can also draw the graph of the function f, the recurrance is then drawn by a staircase between the graph of f and id (i.e. the straight line with 45 degrees slope). Draw it on a paper! And you will see that the limit is at the fixed point.


Except that sqrt(2)=1.414 but this number is 1.1939...

The limit was 1.1939... with the old recurrance.
bo198214
Tetronian
 
Posts: 692
Joined: Tue Dec 06, 2005 11:03 pm
Location: Berlin - Germany

Postby quickfur » Mon Aug 14, 2006 10:48 pm

bo198214 wrote:[...]
The limit was 1.1939... with the old recurrance.

Yeah, you're right. I made a dumb mistake. :-)

Anyway, I solved the recurrence, and it turns out to have a nice closed form: P<sub>n</sub> = sqrt(2n/(n+1)).

The interesting thing is that if you rearrange it to take the limit as n->infinity, you get sqrt(2/(1+1/n)), which reminds me very much of the expression that yields e.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Postby bo198214 » Tue Aug 15, 2006 12:42 am

quickfur wrote:P<sub>n</sub> = sqrt(2n/(n+1))

Well done! Even true after my inductive verification ;)

The interesting thing is that if you rearrange it to take the limit as n->infinity, you get sqrt(2/(1+1/n)), which reminds me very much of the expression that yields e.


Haha, still on the transcendental hunt! Well, there merely lacks an n in the exponent ... a little innocent n ... but its not there ... instead its only a simple fraction 1+1/n doomed to be going to 1 instead of the glorious e ...
bo198214
Tetronian
 
Posts: 692
Joined: Tue Dec 06, 2005 11:03 pm
Location: Berlin - Germany

Postby quickfur » Tue Aug 15, 2006 1:55 am

bo198214 wrote:
quickfur wrote:P<sub>n</sub> = sqrt(2n/(n+1))

Well done! Even true after my inductive verification ;)

For once, I did something right. :-)

The interesting thing is that if you rearrange it to take the limit as n->infinity, you get sqrt(2/(1+1/n)), which reminds me very much of the expression that yields e.


Haha, still on the transcendental hunt! Well, there merely lacks an n in the exponent ... a little innocent n ... but its not there ... instead its only a simple fraction 1+1/n doomed to be going to 1 instead of the glorious e ...

Yep. That little innocent n makes all the difference between a boring old natural number and the wild, untameable transcendental e. :-)

Anyways, I've implemented this vertex generation scheme in a Perl script, and it works really well. If you expand the recursive definition I outlined above, you get a nice pattern for the vertices which allows a single-pass algorithm (no actual recursion needed!) that prints out the vertices.

I've also implemented the mapping from (n+1)-cube vertices to n-simplex surtopes. This one turns out to be dead easy after all: you just loop from i=1 to 2<sup>n+1</sup>, and where there is a 1 in the binary expansion of i, you add that to the vertex set of the surtope. The dimension of the surtope then is the number of elements in the vertex set - 1. (The lattice is formed by the surtopes' vertex sets under the subset relation.)

The only thing missing now is a way to generate the facet normals... for this, I could probably just use an n-dimensional cross product, but I'm going to see if there's a simpler underlying pattern that I can make use of.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Simplex normals

Postby quickfur » Tue Aug 15, 2006 5:59 am

OK, I've found out how to generate facet normals for n-simplices. It's so trivially easy I don't know why I didn't see it before. Basically, every facet in an n-simplex includes all except 1 vertex. When the simplex is origin-centered, the vector from the origin to this vertex is orthogonal to the facet. Hence, simply reversing this vector yields the facet normal.

Also, the dot product of any two distinct vectors in an n-simplex is always the same. For simplices generated using P<sub>n</sub> and Q<sub>n</sub> as described above, the dot product is always -2/(n+1). Inverting the sign gives the constant factor that together with the facet normals defines the bounding halfspace for each simplex facet.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Postby wendy » Tue Aug 15, 2006 6:56 am

The usual way of generating a simplex with zero centre, is to use the oblique coordinate system, and use the hyperplane sigma(x_i)=0. This gives a set of axies that behave as a set of right-angled lines, because it really is.

We then see that the coordinate of the various simplexes are

simplex: (n,-1,-1,-1,....), all permitations.
runcinated simplex (1,-1,0,0....) all permutations

The second system in 4d gives the 20 adjacent spherees in the t-basic tiling, the dual of this has the 30 vertices of that zonohedron i spoke of earlier. (m3o3o3o3m).

W
The dream you dream alone is only a dream
the dream we dream together is reality.

\ ( \(\LaTeX\ \) \ ) [no spaces] at https://greasyfork.org/en/users/188714-wendy-krieger
User avatar
wendy
Pentonian
 
Posts: 2014
Joined: Tue Jan 18, 2005 12:42 pm
Location: Brisbane, Australia

Postby quickfur » Tue Aug 15, 2006 4:04 pm

wendy wrote:The usual way of generating a simplex with zero centre, is to use the oblique coordinate system, and use the hyperplane sigma(x_i)=0. This gives a set of axies that behave as a set of right-angled lines, because it really is.

Are you referring to barycentric coordinates?

We then see that the coordinate of the various simplexes are

simplex: (n,-1,-1,-1,....), all permitations.
runcinated simplex (1,-1,0,0....) all permutations

The reason I use Cartesian coordinates is 'cos I want to use the same projection code I use for other polytopes.

The second system in 4d gives the 20 adjacent spherees in the t-basic tiling, the dual of this has the 30 vertices of that zonohedron i spoke of earlier. (m3o3o3o3m).

W

Runcinated simplex... that's the one that projects onto a cuboctahedron, right? And its dual is a projection of a 5-cube? Very interesting.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Postby wendy » Wed Aug 16, 2006 7:32 am

The figure m3o3o3..o3m is indeed the projection of the measure polytope in every dimension. This is to be expected: You should note that this symmetry is the vertex-first projection of the cubic.
The dream you dream alone is only a dream
the dream we dream together is reality.

\ ( \(\LaTeX\ \) \ ) [no spaces] at https://greasyfork.org/en/users/188714-wendy-krieger
User avatar
wendy
Pentonian
 
Posts: 2014
Joined: Tue Jan 18, 2005 12:42 pm
Location: Brisbane, Australia


Return to Other Polytopes

Who is online

Users browsing this forum: No registered users and 9 guests