Generating the surtopes of an n-cube

[quickfur]

Hi all! This is probably already known, but I discovered this today and thought it was neat anyway: the total number of surtopes in an n-hypercube is precisely 3ⁿ.

Proof. Let C be an n-cube, with coordinates (+/-1, +/-1, ... +/-1). Every m-surtope of C is characterized by the property that all its vertices are identical in (n-m) coordinates. The remaining coordinates are allowed to vary (and the number of possibilities determine the number of vertices the m-surtope has). In other words, by "fixing" (n-m) coordinates and allowing the rest to vary, we obtain an m-surtope of C.
Now, take all integers between 0 and 3ⁿ-1 (inclusive) and consider their digit expansion in base 3, prepending 0's as necessary to make all the numbers n digits long. Now, we search for all vertices that "match" the digit string, by interpreting a 0 in the i'th position as a "fixing" of the i'th coordinate to -1, a 1 in the i'th position as a "fixing" of the i'th coordinate to 1, and a 2 in the i'th position as a "wildcard" (it's free to vary). If there are no 2's in the digit string, we fix all coordinates: we get exactly 1 vertex. Otherwise, we get the vertices of some m-surtope of C. Since the digit strings from 0 to 3ⁿ-1 cover all possibilities, we have a bijection from digit strings to surtopes of C.
Therefore, C has exactly 3ⁿ surtopes. Note that this number includes C itself as an n-surtope; if we exclude this, we simply have 3ⁿ-1.

Application. The number of surtopes in itself isn't very interesting, since we could already obtain the result by summing the number of m-surtopes from 0 to n (this is well-known). However, the interesting thing about the above proof is that we can use it to compute the vertices of all surtopes of C. We simply loop from 0 to 3ⁿ-1, and for each digit string, we search for vertices that match the digit string (coordinate is -1 where the digit string is 0, coordinate is 1 where the digit string is 1, and we ignore the coordinate where the digit string is 2). All vertices that satisfy the criteria belong to this surtope. By doing this, we can generate the full face lattice of C.

[wendy]

The measure polytope, the tegum polytope, and the simplex, can all be shown to be powers of simple things, eg

tegum polytope = (2v+n)^N, the sum is 3^n-1
prism polytope = (e+2v)^N , the sum is 3^n-1
simplex polytope = (v+n)^(N+1), the sim is 2^(N+1)-2

One can see that Euler's characteristic is also solved for these.

W

[PWrong]

This is probably already known, but I discovered this today and thought it was neat anyway: the total number of surtopes in an n-hypercube is precisely 3n.

It is already known, but I haven't seen it worked out like that before.

Let me see if I understand by listing the surtopes of a square.

00 - vertex
01 - side
02 - vertex
10 - side
11 - face
12 - side
20 - vertex
21 - side
22 - vertex

So there are 4 vertices, 4 sides and 1 face.

I wonder if this can be extended to the forms and cells of a rotatope.

[quickfur]

[...]
00 - vertex
01 - side
02 - vertex
10 - side
11 - face
12 - side
20 - vertex
21 - side
22 - vertex

So there are 4 vertices, 4 sides and 1 face.

Actually, it should like this:
00 - vertex (-1,-1)
01 - vertex (-1,1)
02 - side (-1,-1)--(-1,1)
10 - vertex (1,-1)
11 - vertex (1,1)
12 - side (1,-1)--(1,1)
20 - side (-1,-1)--(1,-1)
21 - side (-1,1)--(1,1)
22 - face

This enumeration also works for cross-polytopes, except that the coordinates are interpreted dually, so that fixed coordinates are interpreted as selecting axes. Maybe listing the mapping would be clearer than a verbal explanation---here's an enumeration of the octahedron's surtopes:

000 - face (-1,0,0)--(0,-1,0)--(0,0,-1)
001 - face (-1,0,0)--(0,-1,0)--(0,0,1)
002 - edge (-1,0,0)--(0,-1,0)
010 - face (-1,0,0)--(0,1,0)--(0,0,-1)
011 - face (-1,0,0)--(0,1,0)--(0,0,1)
012 - edge (-1,0,0)--(0,1,0)
020 - edge (-1,0,0)--(0,0,-1)
021 - edge (-1,0,0)--(0,0,1)
022 - vertex (-1,0,0)
100 - face (1,0,0)--(0,-1,0)--(0,0,-1)
101 - face (1,0,0)--(0,-1,0)--(0,0,1)
102 - edge (1,0,0)--(0,-1,0)
110 - face (1,0,0)--(0,1,0)--(0,0,-1)
111 - face (1,0,0)--(0,1,0)--(0,0,1)
112 - edge (1,0,0)--(0,1,0)
120 - edge (1,0,0)--(0,0,-1)
121 - edge (1,0,0)--(0,0,1)
122 - vertex (1,0,0)
200 - edge (0,-1,0)--(0,0,-1)
201 - edge (0,-1,0)--(0,0,1)
202 - vertex (0,-1,0)
210 - edge (0,1,0)--(0,0,-1)
211 - edge (0,1,0)--(0,0,1)
212 - vertex (0,1,0)
220 - vertex (0,0,-1)
221 - vertex (0,0,1)
222 - octahedron

I guess the interesting thing about this result is not the count itself, since there are already many ways of arriving at 3ⁿ (by summing binomial coefficients, by geometric means, etc.). What is interesting about this is that it allows you to enumerate all the surtopes. This is very useful, since I am currently working on a program that deals with polytope representation, and it is very nice to be able to derive the full face lattice of cubes and crosses without needing to write a complex algorithm that solves it from vertices or halfspaces.

[bo198214]

This is very useful, since I am currently working on a program that deals with polytope representation

Tell more!

PS: "Surtope" is what usually is called facet?

[Keiji]

No. He means hypercell.

[quickfur]

This is very useful, since I am currently working on a program that deals with polytope representation

Tell more!

Well, it's basically a rewrite of my previous program which I've mentioned before, a calculator program that deals with vectors natively. The problem is that I didn't design the input language very well, and now it's an inefficient mess. Right now, I'm working on implementing native polytope support (hence the interest in representing face lattices, and generating them---I don't think I have the patience (or precision!) to generate face lattices by hand).

PS: "Surtope" is what usually is called facet?

I'm using Wendy's terminology: a surtope is a surface polytope: cell, face, edge, vertex, etc.. Basically a polytope of lesser dimensions on the surface of a higher dimensional polytope.

Oh, and BTW, a face lattice is simply a graph that describes the relationship between the surtopes of a polytope. For example, a cube contains 6 squares, each square is connected to 4 edges, and each edge is connected to 2 vertices. The face lattice describes which face/edge/vertex is connected to which other face/edge/vertex. Face lattices are extremely useful when projecting polytopes into lower dimensions, because they allow you to do hidden surface removal without having to recompute the convex hull of the projection.

(The reason a face lattice is called that, is because the relationships between surtopes can be described by set inclusion, with maximal/minimal elements for every subset of related surtopes. In mathematics, such a structure is called a lattice.)

[bo198214]

Yes, I know (a bit) about lattices
The mathematicians word for surtope is face. That means every polytope on the surface no matter what dimension (including edges and vertices). Thatswhy the term 'face lattice'. The faces of maximal dimension are called facets all other faces are called proper faces.

[quickfur]

Yes, I know (a bit) about lattices
The mathematicians word for surtope is face. That means every polytope on the surface no matter what dimension (including edges and vertices). Thatswhy the term 'face lattice'. The faces of maximal dimension are called facets all other faces are called proper faces.

I'm aware of this usage. But I dislike the term "face", because some people equate them with 2-surtopes, and others equate them with facets, causing a lot of confusion. "Surtope" is the least ambiguous term I know of, by far.
I also dislike the term "proper face", because it seems to imply that facets aren't "proper", whatever that means. Anyway, I'm not trying to nitpick over terminology, but it does aggravate me when a perfectly good term like "face" gets overused or overloaded with mutually incompatible meanings, so that you can't use it without risking confusion on the part of the reader.

[bo198214]

As long as I understand you it doesnt matter for me

[wendy]

The trouble with modern mathematical terminology, is that lots of terms get used inappropriately, and that no over-all rhyme or reason goes into this. That is, one meerly thinks of some inspiration that is going through when one picks a word, even if the meaning is invalid in higher dimensions.

The polygloss is as much a linguistic work as a mathematical work. That is, it produces words that one can analyse the root stems to assert the meaning.

Although George Olshevsky invented the word /surtope/, with the PG meaning of "perimeter", the word analyses in the PG as /sur/ ON + /tope/ CUT: that is a surtope is a "surface polytope", ie the general member of vertex, edge, hedron, ..., margin, face...

Much of the mathematical terminology does not conform with the general usage, and the PG has attempted to fix this. A face presents a solid part of the view, (eg the part facing me). A 2d element does this in 3d only. Because the mathematical use of face is (PG surhedron), a new word had to be invented for (PG face): facet. Correspondingly, in six dimensions, a face would be 2d, while a little face is 5d.

Lots of this sort of thing goes on. The latest one i heard is, because cell is taken as 3-edge (ie surchoron), what everyone else calls a cell (eg a square on a gaming-board, or any solid tile in a tiling), becomes a new, and equally confusing "cellule" (from <= cellulation),

The polygloss words for tilings, is the easy-to-recall cells have walls, walls have sills, for T, T-1 and T-2 elements of a tiling covering T-space.

It does little good to present the user with this sort of thing, because cells and faces (in the mathematical context), have little meaning when the meaning is kept in six dimensions. One might not regard a point as "facing" you, or have a edge as a "solid room".

One notes that the PG reforms are much more extensive than this. One can not "delineate" something in 4d, since a line is not a thing that divides a surface. Instead, one "demarks" something, since mark/margin is allocated to this meaning.

The meanings of in/out (surround) vs (arround) have rather precise meanings as well: one surrounds a city, [which lies in the same space as the army], but dances around the maypole [the maypole is vertical: you dance in the plane orthogonal to it!].

[bo198214]

An allegory:

I know that the english language is in many cases not optimal (for one example, you mostly can not conclude the pronunciation), Esperanto fixes many of the drawbacks of the english language (and probably you even can conclude meaning from the stems in Esperanto).

Nonetheless nearly nobody speaks Esperanto, and so do I.

[quickfur]

An allegory:

I know that the english language is in many cases not optimal (for one example, you mostly can not conclude the pronunciation), Esperanto fixes many of the drawbacks of the english language (and probably you even can conclude meaning from the stems in Esperanto).

Nonetheless nearly nobody speaks Esperanto, and so do I.

"If you've not appreciated the beauty of language, you're not worthy to bemoan its flaws (much less fix them)." :wink:

[quickfur]

On the other hand, though, it is true that specialized language is needed to express concepts in a certain subject area in a precise way. For example, scientific terminology vs. English as spoken by an average person on the street. Many mathematical terms (such as terms referring to 4D objects!) have very precise meanings that are narrower than what the word means in general parlance. Since Wendy's polygloss is supposed to work in very high dimensions, it only makes sense that the terms it uses must be suitably tuned to work better with those higher dimensions.

In higher dimensions, many things that are conflated in lower dimensions are no longer so, so you need separate terms for them. But for people who work mainly with lower dimensions, this seems like unnecessary hair-splitting, so they continue using the ambiguous terms they are used to. You just have to define your playing field, and stick with it.

[quickfur]

[...]
Lots of this sort of thing goes on. The latest one i heard is, because cell is taken as 3-edge (ie surchoron), what everyone else calls a cell (eg a square on a gaming-board, or any solid tile in a tiling), becomes a new, and equally confusing "cellule" (from <= cellulation),

Personally, I don't quite like the use of the word "cell" for the facets of a 4-polytope. It seems to imply a hollow, closed room, but in reality, a "cell" on a 4-polytope (or above) is completely solid and as "flat" as a 2D surface in 3D. Even though a 4-polytope is made of "cells", this in no way means that its surface consists of interconnected "rooms" like the rooms in a 3D building!

This unintended connotation of the word "cell" has led to some inaccurate depiction of 4-polytopes, along the lines of "if we lived on a 600-cell, we'd see nice tetrahedral mountains"---not true, 'cos if we lived on a 600-cell as a 3D being, we would see empty space that's curved in a strange way at the ridges and edges, sorta like quantized space curvature. If we lived on a 600-cell as a 4D being, the tetrahedra would just be flat (hyper)planes to us, joined at angles. There are no "tetrahedral mountains" anywhere.

[bo198214]

Mathematics is anyway not the right place to enjoy language.
I personally dont like the word ring. Because its misleading to mean only structures like Z/nZ, i.e. if one sometimes add or multiplies numbers than one returns to smaller numbers.
Hey, the words in mathematics are not designed to make any sense, they are simply place holder for definitions with sometimes some vague relation to usual meanings.
And I can not see any hassle if I define cell to be a simplex, then to regard a cube as a collection of cells (the only hassle would be to not use instead the word simplex) because in this mind world is everything splitted down to simplices.

Though I admit I am neither a linguist nor have real sense for the beauty of language...

[quickfur]

Mathematics is anyway not the right place to enjoy language.
I personally dont like the word ring. Because its misleading to mean only structures like Z/nZ, i.e. if one sometimes add or multiplies numbers than one returns to smaller numbers.
Hey, the words in mathematics are not designed to make any sense, they are simply place holder for definitions with sometimes some vague relation to usual meanings.

Technically, yes, mathematical terms are really just placeholders to refer to particular concepts, and they can really be anything. But practically speaking, they can't be completely arbitrary... otherwise, why not call a vertex "apple", an edge "orange", and a 2-face "pear"? They should at least have some relation to the use of the same word in common parlance. And since it has to be so, why not choose the word that is closest in meaning to the mathematical concept? Otherwise, let's name polytopes after fruits.

[bo198214]

First we can only find a meaning-close word if the concept is part of common life. For example ring, group, field is arbitrary, because these concepts are uncommon to the normal human experience.

But then face and facet is quite close, while surtope is not even a common word. And as non-linguist I can not profit from reduction to stems because with latrix and hedrix, is simply dont know what the stems are, nor what they mean. My first association of surtope was a polytope that surrounds this polytope in some way, i.e. the construction of a new bigger polytope based on the original one. So the reconstruction of meaning does not work for me and then Id rather stick to the common mathematical parlance, if I anyway have to lookup the meaning.

[quickfur]

First we can only find a meaning-close word if the concept is part of common life. For example ring, group, field is arbitrary, because these concepts are uncommon to the normal human experience.

Fair enough.

But then face and facet is quite close, while surtope is not even a common word. And as non-linguist I can not profit from reduction to stems because with latrix and hedrix, is simply dont know what the stems are, nor what they mean. My first association of surtope was a polytope that surrounds this polytope in some way, i.e. the construction of a new bigger polytope based on the original one. So the reconstruction of meaning does not work for me and then Id rather stick to the common mathematical parlance, if I anyway have to lookup the meaning.

Well, with "surtope", I was looking for a more precise term that applies to n-dimensions. I avoided "face" because it is too ambiguous and too overloaded, although I think "facet" is pretty unambiguous. I chose "surtope" because Wendy did define it very precisely, for the exact meaning that I was looking for, and because it can be decomposed as "sur(face)" + "(poly)tope", which seems suggestive of a polytopic shape on the surface of another polytope.

With the other PG terms like "latrix" and "hedrix", however, I hesitate a bit. Not because they're not good, but because they sound too obscure and you have to think twice about what they refer to exactly. But then again, my main interest is 4D, and the current 4D terminology seems to suffice, so I don't really have too much reason to look for more precise terms. I suspect that if ever I were to work with higher dimensions frequently as Wendy does, then I would prefer the PG terms because they allow me to talk about the large number of possible dimensions very easily and very precisely. In this particular thread, I did use "surtope", because I'm dealing with generic n-dimensions as opposed to some particular number, so I needed a precise term for it.

Again, my whole point here is that it really depends on what your playing field is. If you work mainly with lower dimensions, or focus on a specific dimension (e.g. 4, or 3, etc.), then you choose your terminology to be most efficient in speaking of your subject. If you work with high dimensions, you do run into cases where the common terms are too broad or not precise enough, so then you need to invent better terminology. So, pick your playing field, and choose your terms accordingly.

[wendy]

The point with "latrix" etc, is that the stem is not meant to displace every instance of one-dimensional usage (eg edge, line). What it does do is make a regular root for 1d, for all the stems that have higher dimensions.

It is true that one is hesitant of changing established usage willy-nilly. But sometimes, the established usages can be protected if there is means to create words for adjacent meanings. The word "line", for example, can be a complete line (latrix), or a segment (latron). It can serve as an edge, (ie joining things, eg bus-line, tram-line), or as a margin (dividing things, eg dead-line, line in the sand, delineate) .

latrix, and teelix, appeared only very late in the process. None the same, a point is a singular thing, while a glomoteelix is a surface made of two points.

One notes that there are many words that are count-up or count-down words. A wall is useless unless it separates: thus in 4d, a wall of 2d is as useful as a pole of 1d in our own space. When one looks at the great variety of words, one asks what is really meant here.

A sword cuts, because the sweep of the blade makes a solid gash. In four dimensions, the sword would have a blade-edge of 2d, since this is swept by time over 3d, which is useful to cut. So to call the blade an edge is wrong: it's a margin.

And so on.

Words like "latrix" are of course obscure, because the stem consist is unfamiliar. But when one understands that latr- is always 1d, and -ix is always fabric, one is looking at _any_ one-dimensional fabric. Any thread tangled and tossed in the corner, still makes a latrix, although i doubt it makes a line.

When one has words a 2d sheet waving in a four-dimensional graph, names like "surface" or "plane" can not do it justice. On the other hand, a hedrix or 2-cloth, does the very thing. By its obscurity, it does not suggest that the hedrix divides four-space. That's the point of things.

If you work in a specific dimension, it is always useful to mind whether the words are "top-hung" (ie relate to the solid), or "bottom-hung" (ie relate to the particular dimension). It is no problem to call, in four dimensions, a surchoron a face. But it is true only in four dimensions.

The underlying strength of the PG terminology is that it uses a small set of stems, and that one can create a great variety of words, by joining stems together.