General Approach--can 3D methods be generalized?

[ytrepus]

Hello,

I was just browsing an electronic version of Victor Zalgaller's paper Convex Polyhedra with Regular Faces, in which he proves that Johnson's 92 solids + uniforms is the full list of CRF polyhedra. The paper's in Russian, so I can't make much sense out of it (need to get hold of the English translation), but it looks like he enumerates all possible vertices and calculates angles to exhaustively identify the ways polygons could be combined to form the non-composite solids, and then he uses an algorithm to determine all the ways these could then be combined together while retaining convexity.

A similar approach is followed here, in this case allowing certain instances of coplanar faces (http://www.ams.org/spmj/2010-21-03/S106 ... 1105-2.pdf). For each non-composite solid, the author identifies which faces could possibly be augmented, and then they are systematically combined to create the composite solids, with a test to ensure duplicates are not counted.

I would guess finding the non-composite solids is the hard part, but then combining them must be relatively straightforward. Is there any particular reason that these approaches couldn't be modified appropriately for 4d and then an algorithm used to identify every possibility, using the uniforms + Johnson solids as the only possible cells? Obviously there will be many more possibilities, but processing power is much higher than the 60s when the 3d cases were catalogued. Or am I massively oversimplifying here? Just from browsing it seems like the current effort is a little bit random (I am not in any way criticizing it!), rather than concentrating on developing an exhaustive algorithm to find a complete set.

Really interested to get your insight.

Kind regards
Rob

[Marek14]

Well, my thoughts went roughly like this:

Let's start with vertices. Every vertex of a CRF polychoron is in a center of unit hypersphere with 4 or more other vertices. These vertices form a convex vertex figure (which can, in general case, include skew polygons) and every of its edges must correspond to a chord of polygon; moreover, every polygon must correspond to one Platonic, Archimedean, prismatic/antiprismatic or Johnson solid. There should be only finite number of possible combinations if we exclude the "rare" polygons (7, 9 and everything from 11 on); those require prismatic or antiprismatic cells so they are more constrained and could be explored later (though we know about duoprism augments and so on, so some results could be found even there).

So, step one, enumeration of vertices. Not sure what is maximum amount of edges per vertex, but 12 of 600-cell should be either the maximum or close to it.
The vertices should be fairly rigid. The faces of the vertex figure can't be continuously deformed since only a discrete set of polygons is actually allowed.

Now, once you have a single vertex, it can be "extended" -- you already know other vertices adjacent to it, but any polygon the first vertex is a part of can be completed. This gives a hint about other vertices. Every new vertex we explore comes with at least two edges already given which reduces the number of options it can have and fixes the orientation into finite amount of possibilities.

So this could, in theory, serve to enumerate CRF polychora, if some shortcut is found for rare polygons to reduce the number of possible vertices.

[student91]

One big problem with such an approach on finding all CRF-polytopes is that there are very much 4D CRF-polytopes. 3D has "only" 92, but in 4D, this number is probably over ten bilion. Furthermore I don't have enough spare time to make such an algorithm, I personally think making such algorithms is boring (although I have once made an algorithm that would've ennumerated all possible diminishings of the 600-cell, but it was incredibly slow (it gave the answers quite quickly, but it took a long time before it had the first million answers, and it needed 300-million answers). This program made me give up on short-term on the computer approach.

Furthermore in 4D, there are very few polytopes with the property that they are "CVP 3," (CVP is a measure for intrinsic complexity of polytopes, it takes the biggest prime factor of the exponents of the minimal polynominal that has the distance between two vertices as root). In fact the only found polytopes with this property are prisms of 3D CVP 3-polytopes. If we can prove that no other CVP 3 polytopes exist, our apprach can be much more economic than the apprach of the 92.

Besides, all Segmentochora have already been listed, they are a nice set of elementary CRF's. These can be seen as another step on the ladder of proving we've found all of them. however, I think in no way we can skip much rungs with our household computers.
Furthermore we have, quite recently, found the beginning of another set of polytopes, that can be derived by partial expansions of uniform polytopes from the .5.3.-class.

So I think finding most polytopes should be done before we try to prove we've found all. Otherwise we'll just be stuck with a lot of data of undiscovered polytopes that we can't process.

PS. @marek, does the verf really always give a polyhedron? the verf of the snub disphenoid is clearly not a polygon, so can't a similar thing happen for 4D? Anyway, I think the vertex-apprach might be the way to prove how many CVP3 things exist. but before we do that, we have to focus on the partial expansions

[wendy]

Not all johnson-figures have coplanar vertex figures, such as oxx3ooo&#xt. The vertices at the bases of the tetrahedra do not have a planar verf.

[Marek14]

Not all johnson-figures have coplanar vertex figures, such as oxx3ooo&#xt. The vertices at the bases of the tetrahedra do not have a planar verf.

That doesn't matter, though. While the vertices don't lie in a plane, they still lie on a sphere, and that's all that's needed for the algorithm I suggested.

student91: The approach I suggested puts a hypersphere around each vertex. Since every pair of adjacent vertices in CRF polychoron has to have unit distance, all vertices adjacent to a given one lie on a hypersphere. If the vertex figure forms a polyhedron, the vertices actually lie on a single 3D-sphere cut through the hypersphere, but this is not required or necessary in general case.

Here could be an interesting experiment for starters: the simplest kind of vertex in 4D is a tetraedric vertex with four edges, six faces and four cells. So, we could try to enumerate just this type of vertices and then enumerate CRF polychora made from them. This would be analogical to CRF polyhedra with only 3-degree vertices (3 Platonic, 7 Archimedean and all prisms).

If this works, we could then start to add other types of vertices until we achieve the goal.

[Marek14]

For reference, here are possible polygons appearing in vertex figure:

Code: Select all

3,3,3: tetrahedron, elongated triangular pyramid, triangular dipyramid, elongated triangular dipyramid, augmented tridiminished icosahedron
3,3,4: square pyramid
3,3,5: pentagonal pyramid
3,4,4: triangular prism, elongated triangular pyramid, gyrobifastigium, augmented triangular prism
3,4,6 (chiral): triangular cupola
3,4,8 (chiral): square cupola
3,4,10 (chiral): pentagonal cupola
3,5,5: metabidiminished icosahedron, tridiminished icosahedron [fits in 2 different ways], augmented tridiminished icosahedron, bilunabirotunda
3,5,10 (chiral): pentagonal rotunda
3,6,6: truncated tetrahedron, augmented truncated tetrahedron [fits in 2 different ways]
3,8,8: truncated cube, augmented truncated cube [fits in 4 different ways, 2 of them chiral], biaugmented truncated cube
3,10,10: truncated dodecahedron, augmented truncated dodecahedron [fits in 10 different ways, 6 of them chiral], parabiaugmented truncated dodecahedron [fits in 4 different ways, 2 of them chiral], metabiaugmented truncated dodecahedron [fits in 20 different ways, 16 of them chiral], triaugmented truncated dodecahedron [fits in 10 different ways, 6 of them chiral]
4,4,4: cube, elongated square pyramid [fits in 3 different ways]
4,4,5: pentagonal prism, elongated pentagonal pyramid, augmented pentagonal prism [fits in 3 different ways, 2 of them chiral], biaugmented pentagonal prism
4,4,6: hexagonal prism, elongated triangular cupola [fits in 2 chiral ways], augmented hexagonal prism [fits in 4 chiral ways], parabiaugmented hexagonal prism, metabiaugmented hexagonal prism [fits in 2 chiral ways]
4,4,7: heptagonal prism
4,4,8: octagonal prism, elongated square cupola [fits in 2 chiral ways]
4,4,9: enneagonal prism
4,4,10: decagonal prism, elongated pentagonal cupola [fits in 2 chiral ways], elongated pentagonal rotunda [fits in 2 chiral ways]
4,5,10 (chiral): diminished rhombicosidodecahedron, paragyrate diminished rhombicosidodecahedron, metagyrate diminished rhombicosidodecahedron [fits in 5 different ways], bigyrate diminished rhombicosidodecahedron [fits in 5 different ways], parabidiminished rhombicosidodecahedron, metabidiminished rhombicosidodecahedron [fits in 5 different ways], gyrate bidiminished rhombicosidodecahedron [fits in 10 different ways], trigyrate rhombicosidodecahedron [fits in 5 different ways]
4,6,6: truncated octahedron
4,6,8 (chiral): truncated cuboctahedron
4,6,10 (chiral): truncated icosidodecahedron
5,5,5: dodecahedron, augmented dodecahedron [fits in 9 different ways], parabiaugmented dodecahedron [fits in 3 different ways], metabiaugmented docecahedron [fits in 15 different ways, 6 of them chiral], triaugmented dodecahedron [fits in 5 different ways]
5,6,6: truncated icosahedron

3,3,3,3: octahedron, square pyramid, elongated square pyramid, gyroelongated square pyramid, elongated square dipyramid, gyroelongated square pyramid, augmented triangular prism [fits in 2 different ways], biaugmented triangular prism [fits in 4 different ways], triaugmented triangular prism [fits in 2 different ways], augmented pentagonal prism [fits in 2 different ways], biaugmented pentagonal prism [fits in 4 different ways], augmented hexagonal prism [fits in 2 different ways], parabiaugmented hexagonal prism [fits in 2 different ways], metabiaugmented hexagonal prism [fits in 4 different ways], triaugmented hexagonal prism [fits in 2 different ways], augmented sphenocorona [fits in 4 different ways]
3,3,3,3 (skew1): triangular dipyramid
3,3,3,3 (skew2): pentagonal dipyramid
3,3,3,3 (skew3): snub disphenoid [fits in 2 different ways]
3,3,3,3 (skew4): sphenomegacorona [fits in 2 different ways]
3,3,3,4: square antiprism, gyroelongated square pyramid
3,3,3,4 (skew1, chiral): augmented triangular prism, biaugmented triangular prism
3,3,3,4 (skew2, chiral): sphenocorona, augmented sphenocorona
3,3,3,5: pentagonal antiprism, gyroelongated pentagonal pyramid, metabidiminished icosahedron [fits in 3 different ways, 2 of them chiral], tridiminished icosahedron, augmented tridiminished icosahedron, triangular hebesphenorotunda
3,3,3,6: hexagonal antiprism, gyroelongated triangular cupola [fits in 2 different ways]
3,3,3,7: heptagonal antiprism
3,3,3,8: octagonal antiprism, gyroelongated square cupola [fits in 2 different ways]
3,3,3,9: enneagonal antiprism
3,3,3,10: decagonal antiprism, gyroelongated pentagonal cupola [fits in 2 different ways], gyroelongated pentagonal rotunda [fits in 2 different ways]
3,3,4,4: triangular orthobicupola
3,3,4,4 (skew1): elongated triangular pyramid, elongated triangular dipyramid
3,3,4,4 (skew2): elongated square pyramid, elongated square dipyramid, square orthobicupola
3,3,4,4 (skew3): elongated pentagonal pyramid, elongated pentagonal dipyramid
3,3,4,4 (skew4): pentagonal orthobicupola
3,3,4,4 (skew5): sphenocorona
3,3,4,4 (skew6): sphenomegacorona
3,3,4,4 (skew7): hebesphenomegacorona [fits in 2 chiral ways]
3,3,4,4 (skew8): disphenocingulum
3,4,3,4: cuboctahedron, triangular cupola [fits in 2 different ways], elongated triangular cupola [fits in 2 different ways], gyroelongated triangular cupola [fits in 2 different ways], triangular orthobicupola [fits in 2 different ways], elongated triangular orthobicupola [fits in 2 different ways], elongated triangular gyrobicupola [fits in 2 different ways], gyroelongated triangular bicupola [fits in 4 chiral ways], augmented truncated tetrahedron [fits in 2 different ways]
3,4,3,4 (skew1, chiral): gyrobifastigium
3,4,3,4 (skew2, chiral): square gyrobicupola
3,4,3,4 (skew3, chiral): pentagonal gyrobicupola
3,3,4,5 (skew1, chiral): pentagonal gyrocupolarotunda
3,3,4,5 (skew2, chiral): augmented pentagonal prism, biaugmented pentagonal prism [fits in 2 different ways]
3,4,3,5 (skew, chiral): pentagonal orthocupolarotunda, bilunabirotunda, triangular hebesphenorotunda
3,3,4,6 (skew1, chiral): augmented hexagonal prism, parabiaugmented hexagonal prism, metabiaugmented hexagonal prism [fits in 2 different ways], triaugmented hexagonal prism
3,3,4,6 (skew2, chiral): triangular hebesphenorotunda
3,4,3,6 (skew, chiral): augmented truncated tetrahedron
3,4,3,8 (skew, chiral): augmented truncated cube, biaugmented truncated cube
3,4,3,10 (skew, chiral): augmented truncated dodecahedron, parabiaugmented truncated dodecahedron, metabiaugmented truncated dodecahedron [fits in 5 different ways], triaugmented truncated dodecahedron [fits in 5 different ways]
3,3,5,5: pentagonal orthobirotunda
3,3,5,5 (skew1): augmented dodecahedron, parabiaugmented dodecahedron, metabiaugmented docecahedron [fits in 5 different ways, 4 of them chiral], triaugmented dodecahedron [fits in 5 different ways, 4 of them chiral]
3,3,5,5 (skew2): augmented tridiminished icosahedron
3,5,3,5: icosidodecahedron, pentagonal rotunda [fits in 4 different ways], elongated pentagonal rotunda [fits in 4 different ways], gyroelongated pentagonal rotunda [fits in 4 different ways], pentagonal orthocupolarotunda [fits in 4 different ways], pentagonal gyrocupolarotunda [fits in 4 different ways], pentagonal orthobirotunda [fits in 4 different ways], elongated pentagonal orthocupolarotunda [fits in 4 different ways], elongated pentagonal gyrocupolarotunda [fits in 4 different ways], elongated pentagonal orthobirotunda [fits in 4 different ways], elongated pentagonal gyrobirotunda [fits in 4 different ways], gyroelongated pentagonal cupolarotunda [fits in 8 chiral ways], gyroelongated pentagonal birotunda [fits in 8 chiral ways], bilunabirotunda, triangular hebesphenorotunda [fits in 2 different ways]
3,4,4,4: rhombicuboctahedron, square cupola, elongated square cupola [fits in 3 different ways, 2 of them chiral], gyroelongated square cupola, square orthobicupola, square gyrobicupola, elongated square gyrobicupola [fits in 3 different ways, 2 of them chiral], gyroelongated square bicupola [fits in 2 chiral ways], augmented truncated cube, biaugmented truncated cube
3,4,4,4 (skew1, chiral): elongated triangular cupola, elongated triangular orthobicupola, elongated triangular gyrobicupola
3,4,4,4 (skew2, chiral): elongated pentagonal cupola, elongated pentagonal orthobicupola, elongated pentagonal gyrobicupola, elongated pentagonal orthocupolarotunda, elongated pentagonal gyrocupolarotunda
3,4,4,5 (chiral): gyrate rhombicosidodecahedron, parabigyrate rhombicosidodecahedron, metabigyrate rhombicosidodecahedron [fits in 5 different ways], trigyrate rhombicosidodecahedron [fits in 5 different ways], paragyrate diminished rhombicosidodecahedron, metagyrate diminished rhombicosidodecahedron [fits in 5 different ways], bigyrate diminished rhombicosidodecahedron [fits in 10 different ways], gyrate bidiminished rhombicosidodecahedron [fits in 5 different ways]
3,4,4,5 (skew, chiral): elongated pentagonal rotunda, elongated pentagonal orthocupolarotunda, elongated pentagonal gyrocupolarotunda, elongated pentagonal orthobirotunda, elongated pentagonal gyrobirotunda
3,4,5,4: rhombicosidodecahedron, pentagonal cupola, elongated pentagonal cupola, gyroelongated pentagonal cupola, pentagonal orthobicupola, pentagonal gyrobicupola, pentagonal orthocupolarotunda, pentagonal gyrocupolarotunda, elongated pentagonal orthobicupola, elongated pentagonal gyrobicupola, elongated pentagonal orthocupolarotunda, elongated pentagonal gyrocupolarotunda, gyroelongated pentagonal bicupola [fits in 2 chiral ways], gyroelongated pentagonal cupolarotunda [fits in 2 chiral ways], augmented truncated dodecahedron, parabiaugmented truncated dodecahedron, metabiaugmented truncated dodecahedron [fits in 5 ways, 4 of them chiral], triaugmented truncated dodecahedron [fits in 5 ways, 4 of them chiral], gyrate rhombicosidodecahedron [fits in 10 different ways, 6 of them chiral], parabigyrate rhombicosidodecahedron [fits in 6 different ways, 4 of them chiral], metabigyrate rhombicosidodecahedron [fits in 20 different ways, 16 of them chiral], trigyrate rhombicosidodecahedron [fits in 10 different ways, 6 of them chiral], diminished rhombicosidodecahedron [fits in 9 different ways, 6 of them chiral], paragyrate diminished rhombicosidodecahedron [fits in 7 different ways, 4 of them chiral], metagyrate diminished rhombicosidodecahedron [fits in 35 different ways, 32 of them chiral], bigyrate diminished rhombicosidodecahedron [fits in 25 different ways, 22 of them chiral], parabidiminished rhombicosidodecahedron [fits in 3 different ways, 2 of them chiral], metabidiminished rhombicosidodecahedron [fits in 15 different ways, 12 of them chiral], gyrate bidiminished rhombicosidodecahedron [fits in 20 different ways, 16 of them chiral], trigyrate rhombicosidodecahedron [fits in 5 different ways, 2 of them chiral]

3,3,3,3,3: icosahedron, pentagonal pyramid, elongated pentagonal pyramid, gyroelongated pentagonal pyramid [fits in 6 different ways], pentagonal dipyramid, elongated pentagonal dipyramid, augmented dodecahedron, parabiaugmented dodecahedron, metabiaugmented dodecahedron [fits in 5 different ways], triaugmented dodecahedron [fits in 5 different ways], metabidiminished icosahedron [fits in 5 different ways]
3,3,3,3,3 (skew1): gyroelongated square pyramid, gyroelongated square pyramid
3,3,3,3,3 (skew2): biaugmented triangular prism, triaugmented triangular prism
3,3,3,3,3 (skew3): snub disphenoid
3,3,3,3,3 (skew4): snub square antiprism
3,3,3,3,3 (skew5): sphenocorona, augmented sphenocorona [fits in 2 chiral ways]
3,3,3,3,3 (skew6): sphenocorona, augmented sphenocorona [fits in 2 different ways]
3,3,3,3,3 (skew7, chiral): augmented sphenocorona
3,3,3,3,3 (skew8): sphenomegacorona
3,3,3,3,3 (skew9): sphenomegacorona
3,3,3,3,3 (skew10): hebesphenomegacorona [fits in 2 different ways]
3,3,3,3,3 (skew11): hebesphenomegacorona
3,3,3,3,3 (skew12): disphenocingulum
3,3,3,3,4: snub cube [fits in 2 chiral ways]
3,3,3,3,4 (skew1, chiral): gyroelongated triangular cupola, gyroelongated triangular bicupola [fits in 2 chiral ways]
3,3,3,3,4 (skew2, chiral): gyroelongated square cupola, gyroelongated square bicupola [fits in 2 chiral ways]
3,3,3,3,4 (skew3, chiral): gyroelongated pentagonal cupola, gyroelongated pentagonal bicupola [fits in 2 chiral ways], gyroelongated pentagonal cupolarotunda [fits in 2 chiral ways]
3,3,3,3,4 (skew4): snub square antiprism
3,3,3,3,4 (skew5, chiral): augmented sphenocorona
3,3,3,3,4 (skew6, chiral): sphenomegacorona
3,3,3,3,4 (skew7, chiral): hebesphenomegacorona
3,3,3,3,4 (skew8, chiral): disphenocingulum
3,3,3,3,5: snub dodecahedron [fits in 2 chiral ways]
3,3,3,3,5 (skew, chiral): gyroelongated pentagonal rotunda, gyroelongated pentagonal cupolarotunda [fits in 2 chiral ways], gyroelongated pentagonal birotunda [fits in 2 chiral ways]


The "skew" marker signifies that the "polygon" is nonplanar. Basically, although there is infinitely many ways to create a skew polygon with given edge lengths, there's only limited amount of these that fit an existing Johnson solid. This can be specified by, for example, length of the diagonals.

[quickfur]

[...]
I would guess finding the non-composite solids is the hard part, but then combining them must be relatively straightforward. Is there any particular reason that these approaches couldn't be modified appropriately for 4d and then an algorithm used to identify every possibility, using the uniforms + Johnson solids as the only possible cells? Obviously there will be many more possibilities, but processing power is much higher than the 60s when the 3d cases were catalogued. Or am I massively oversimplifying here? Just from browsing it seems like the current effort is a little bit random (I am not in any way criticizing it!), rather than concentrating on developing an exhaustive algorithm to find a complete set.
[...]

The trouble with automated algorithms is how to weed out all those "uninteresting" combinations... because there are a LOT (and I do mean a LOT) of 4D CRFs. The non-adjacent 600-cell diminishings alone number more than 300 million up to isomorphism (as calculated by Sikirić and Myrvold in 2007), and there must be many more adjacent diminishings of the 600-cell than that. My preliminary calculations (yet to be independently confirmed) indicate that the augmented m,n-duoprisms number at least 12 million, up to isomorphism. There may be analogues of the 600-cell diminishings in a good number of other uniform polytopes in the 600-cell family, which means we may be looking at the 300 million figure multiplied several times. Most of these figures are not that interesting; they arise primarily from combinatorial explosion of only a small number of unique cell combinations. Their sheer number, unfortunately, overwhelm the more "interesting" CRFs, such as the BT polychora that were discovered since CRFebruary (i.e., February 2014 ), and perhaps some as-yet undiscovered crown jewels that sport unique structures. Most of the output of a brute-force search algorithm would be overwhelmed by some 600-cell diminishing or duoprism augmentation, so 99% of the program's running time would be "wasted" just enumerating "uninteresting" combinations that are already known.

Now, obviously some kind of brute-force algorithm will eventually be needed to prove that the set of CRFs is complete, but I think at the present moment it's more practical to narrow down the scope of the search to something more manageable -- such as enumerating all duoprism augmentations, or 600-cell diminishings, or BT polychora (once we figure out the fundamental principles that underlie their constructions). And of course, the ever-elusive category of crown jewels is something that I think we all look forward to discovering.

Perhaps a middle ground is possible: if we can somehow fine-tune the algorithm to recognize cell combinations that lead to known large families like the 600-cell diminishings or duoprism augmentations, then we can prune away those combinations, leaving only the "more interesting" CRFs to be discovered. Or, postpone known huge families to the end, so that the initial outputs will be the most interesting.

In any case, one major challenge of a brute-force algorithm is how to know whether a given partial cell complex will close up in a CRF way or not. I think Marek has worked on this, but there are still some tricky corners left to be resolved. The main problem is that edges of degree >3 are flexible: they have additional degrees of freedom that preclude fixing the surrounding dichoral angles immediately, so some kind of quadratic equation system solver will be needed to truly cover all possibilities. Since the general system of quadratic equations has no practical solution method (it is equivalent to solving polynomials of arbitrarily large degree), we either have to prove that only a solvable subset of such systems will ever occur, or we have to use numerical approximation methods, which are both slow and error-prone (a given CRF candidate may appear to close up in a CRF way, but algebraically the angles are actually off by, say, 0.00001 units, so it is actually not CRF -- numerical models cannot be used to prove its validity). I suspect that for finding CRFs, we don't actually need a fully general quadratic system solver, but until we can prove this, it must still be considered a possibility, which means a fully general brute-force search for 4D CRFs is still somewhat beyond our reach right now.

[Marek14]

As for separating interesting CRF's from uninteresting, one way could be cell counts. The diminishings of 600-cell, for example, would all consist of tetrahedra and icosahedra and all diminishings by the same number would have identical cell counts for both. On the other hand, unique CRF's would also have unusual cell counts, either by amounts of certain cells or by the presence of unusual cells.

Thinking about the edges. The vertex is a point surrounded by other vertices on hypersphere, and those other points form a polyhedron (which may be skew).
Now, imagine we fix a second point as well. Even if the polyheron on hypersphere is skew, there should still be a unique way to connect its vertices (since it has to be convex). So, one vertex of polyhedron is highlighted, and we create a polygon formed by adjacent vertices. This polygon might be skew as well, but all its vertices should lie on a 3D sphere.

I think that if we repeat this process from the other side (starting from originally highlighted vertex and having the previous origin vertex on the hypersphere), a polygon thus constructed will be the same, even if vertex figure of the two adjacent vertices will generally not be (it has to have the same edge lengths because the polygons around the edge are connected to both of the adjacent vertices on both sides).

What does this mean? That just as we can catalogize the vertex figures of CRF polychora, we can also catalogize possible "vertex figures of vertex figures", i.e. edge figures, and they can be used for connecting the vertices (two vertices can only be adjacent if they have the same edge figure somewhere). And this means that if the vertices are not "squishy" (and they shouldn't be), then the edges aren't free to move either! They can only take one of a finite number of configurations, regardless of number of faces around them.

EDIT: One more note about skewing -- even if the polyhedra or polygons we work with are skew in Euclidean space, they must be flat in spherical space -- and this is where we should work with them since that would simplify things a lot.

[quickfur]

As for separating interesting CRF's from uninteresting, one way could be cell counts. The diminishings of 600-cell, for example, would all consist of tetrahedra and icosahedra and all diminishings by the same number would have identical cell counts for both. On the other hand, unique CRF's would also have unusual cell counts, either by amounts of certain cells or by the presence of unusual cells.
[...]

But in order to get the cell counts in the first place, you'll have to construct the polytope first. Which means 99% of your computational power is spent constructing and then discarding these polytopes. OTOH there doesn't seem to be a way around this, since potentially a crown jewel could have parts that locally look identical to a 600-cell diminishing, but with other parts that are unique, so you wouldn't want to discard something just because one part looks like a 600-cell diminishing. But perhaps it's OK to discard such constructions, since the brute force algorithm will eventually get to cell combinations representing the more interesting part of the same polytope.

Which brings up another point: how to tell if a given polytope has already been constructed before. This seems to be reducible to the graph isomorphism problem, which is NP-complete. Which means large polytopes like the "uninteresting" 600-cell diminishings will waste most of the computational time just because we keep having to determine whether or not they're identical to something previously constructed. Combinational explosion is a nasty beast to tame.

[Marek14]

As for separating interesting CRF's from uninteresting, one way could be cell counts. The diminishings of 600-cell, for example, would all consist of tetrahedra and icosahedra and all diminishings by the same number would have identical cell counts for both. On the other hand, unique CRF's would also have unusual cell counts, either by amounts of certain cells or by the presence of unusual cells.
[...]

But in order to get the cell counts in the first place, you'll have to construct the polytope first. Which means 99% of your computational power is spent constructing and then discarding these polytopes. OTOH there doesn't seem to be a way around this, since potentially a crown jewel could have parts that locally look identical to a 600-cell diminishing, but with other parts that are unique, so you wouldn't want to discard something just because one part looks like a 600-cell diminishing. But perhaps it's OK to discard such constructions, since the brute force algorithm will eventually get to cell combinations representing the more interesting part of the same polytope.

Which brings up another point: how to tell if a given polytope has already been constructed before. This seems to be reducible to the graph isomorphism problem, which is NP-complete. Which means large polytopes like the "uninteresting" 600-cell diminishings will waste most of the computational time just because we keep having to determine whether or not they're identical to something previously constructed. Combinational explosion is a nasty beast to tame.

Well, yes, that is always a problem. Of course, doing things like comparing lists of cells and lists of vertex types will eliminate a lot of possibilities, but the 600-cell diminishings will still require a lot of comparings.

Here's an interesting question: what is the upper limit for number of vertices of CRF polychoron? I would guess that there will be none (except very large members of infinite families) that will surpass 14,400 of omnitruncated 600-cell, just as there's no Johnson solid with more than 120 vertices of truncated icosidodecahedron. But 600-cell diminishings in particular are limited to no more than 120 vertices, so perhaps the comparing wouldn't be that time-intensive.

[student91]

But what if we only checked for polytopes which would give CVP 3 polytopes? Then we would either prove CVP3's don't exist (except for prisms and other trivial things) or we would find loads of things that are "interesting."
I'm not sure how these skew verfs work yet, but I do know for sure that non-skew verfs that are CVP3 will need CVP3 cells. therefore as a start, we could search for things with cells that are CVP 3.

[Marek14]

But what if we only checked for polytopes which would give CVP 3 polytopes? Then we would either prove CVP3's don't exist (except for prisms and other trivial things) or we would find loads of things that are "interesting."
I'm not sure how these skew verfs work yet, but I do know for sure that non-skew verfs that are CVP3 will need CVP3 cells. therefore as a start, we could search for things with cells that are CVP 3.

Problem here is that every CVP3 Johnson solid has skew verfs. Only snub cube and snub dodecahedron don't (are they CVP3?).

[quickfur]

[...]
Here's an interesting question: what is the upper limit for number of vertices of CRF polychoron? I would guess that there will be none (except very large members of infinite families) that will surpass 14,400 of omnitruncated 600-cell, just as there's no Johnson solid with more than 120 vertices of truncated icosidodecahedron.

Yeah, that is also my suspicion. But I don't have a proof for that. The 4D case is a lot more tricky because of the presence of Johnson solid cell shapes, which may lead to even flatter dichoral angles than possible in any uniform construction.

This does give an idea for discovering new crown jewels, though: perhaps there may exist CRFs with unusually flat cell configurations, flatter than the omnitruncated 600-cell? If a brute force search program could be made for searching cell combinations with large dichoral angles, we might discover such CRFs, if they exist.

But 600-cell diminishings in particular are limited to no more than 120 vertices, so perhaps the comparing wouldn't be that time-intensive.

Not true. The problem is that given two possibly isomorphic polytopes, their concrete vertex coordinates may be completely unrelated numerically, due to being constructed in a different position and orientation in 4-space. For example, if you constructed coordinates like apacs(2,0,0,0) and apecs(1,1,1,1), how would the program find an isomorphism between them? In order to check for isomorphism, you'd first have to canonicalize the coordinates by translating and rotating them into canonical position -- but given an arbitrary set of coordinates, it's unclear what target orientation would constitute the "canonical" orientation. Ultimately, the solution to this would be no different in essence from the NP-complete graph isomorphism problem -- so we might as well just start by extracting the face lattices and comparing those instead. Which, of course, is NP-complete.

That's not to say that it can't be done, of course. Just that we should not expect the program to necessarily finish running in any reasonable amount of time (since, as far as we know, we can't solve an NP-complete problem in less than exponential time -- which is very bad news when we're looking at problem sizes up to 14400 vertices, since that's a running time of k¹⁴⁴⁰⁰, which is an intractible number even for cases as small as k=2 -- it's a number with more than 4000 digits!).

So it would appear that in order for brute force search to be tractible, we will have to first significantly reduce the problem space analytically, perhaps by rigorously proving the impossibility of certain classes of figures, thereby eliminating large portions of the search space and hopefully narrowing it down enough to be of a more manageable size.

[quickfur]

But what if we only checked for polytopes which would give CVP 3 polytopes? Then we would either prove CVP3's don't exist (except for prisms and other trivial things) or we would find loads of things that are "interesting."
I'm not sure how these skew verfs work yet, but I do know for sure that non-skew verfs that are CVP3 will need CVP3 cells. therefore as a start, we could search for things with cells that are CVP 3.

Problem here is that every CVP3 Johnson solid has skew verfs. Only snub cube and snub dodecahedron don't (are they CVP3?).

AFAICT, they are CVP3. The snub cube's coordinates are dependent upon the root of the polynomial x^3 + x^2 + x = 1 (the reciprocal of the so-called "tribonacci constant"), and the snub dodecahedron's coordinates are dependent upon the root of the polynomial x^3 - 2x = phi (where phi = (1+√5)/2 is the golden ratio).

One thing to be aware of in searching for CVP3 polytopes, is that they may have CVP2-only parts, so this may not necessarily eliminate "uninteresting" large classes like 600-cell diminishings (what if there's a CVP3 polytope where part of the surface is identical to one of the 600-cell diminishings?).

But perhaps we should attack this problem from a slightly different angle. Suppose we want to find a CVP3 4D CRF. Does the fact that it is CVP3 impose any requirements on its construction? One thing that immediately comes to mind, is that at least part of its surface must be CVP3 (obviously), so we can without loss of generality start with a cell complex that's CVP3 (i.e., assume that's the CVP3 part of the polytope we're trying to construct) and then continuing with the general brute-force search algorithm. In this case, we would know for sure that we aren't going to run into things like the 600-cell diminishings or duoprism augmentations, since they can't have any CVP3 parts in their surface. This might be a possible practical approach to discovering CVP3 polytopes, if they exist, since it narrows the search space to only the "interesting" (i.e. CVP3) regions.

[Marek14]

quickfur: Do we really have to check coordinates for isomorphism, though? Wouldn't the graph structure be enough?

Alternate way is to make an algorithm that would create a "canonic orientation" for a polychoron...

[quickfur]

quickfur: Do we really have to check coordinates for isomorphism, though? Wouldn't the graph structure be enough?

Alternate way is to make an algorithm that would create a "canonic orientation" for a polychoron...

Well, you said to use vertices to determine equivalence, so I thought you meant checking vertex coordinates? Or did I misunderstand what you meant?

In any case, you should be aware that it is known that the complexity of a polytope can be exponential w.r.t. the number of vertices, so having up to 120 vertices may actually be quite intractible! Not to mention, each non-adjacent 600-cell diminishing has corresponding counterparts in other uniform members in the 600-cell family, so we're looking at potentially the same number of diminishings applied to a uniform with many more vertices than merely 120.

I've thought about creating canonical orientations before... unfortunately, it turns out that it's equivalent to the graph isomorphism problem. So it does not give us any extra advantage over plain graph isomorphism itself. (If you think about it, creating a canonical layout of a graph will also solve the graph isomorphism problem, since once two graphs are in canonical orientation it's trivial to check for equivalence. Similarly, there's no essential difference between solving polytope equivalence vs. creating a canonical polytope orientation.)

Of course, just because graph isomorphism is NP-complete doesn't mean it's unsolvable; it just requires a lot of resources (both CPU power and time). Perhaps a distributed SETI-like project would be able to attack the problem effectively.

[Marek14]

quickfur: Do we really have to check coordinates for isomorphism, though? Wouldn't the graph structure be enough?

Alternate way is to make an algorithm that would create a "canonic orientation" for a polychoron...

Well, you said to use vertices to determine equivalence, so I thought you meant checking vertex coordinates? Or did I misunderstand what you meant?

In any case, you should be aware that it is known that the complexity of a polytope can be exponential w.r.t. the number of vertices, so having up to 120 vertices may actually be quite intractible! Not to mention, each non-adjacent 600-cell diminishing has corresponding counterparts in other uniform members in the 600-cell family, so we're looking at potentially the same number of diminishings applied to a uniform with many more vertices than merely 120.

I've thought about creating canonical orientations before... unfortunately, it turns out that it's equivalent to the graph isomorphism problem. So it does not give us any extra advantage over plain graph isomorphism itself. (If you think about it, creating a canonical layout of a graph will also solve the graph isomorphism problem, since once two graphs are in canonical orientation it's trivial to check for equivalence. Similarly, there's no essential difference between solving polytope equivalence vs. creating a canonical polytope orientation.)

Of course, just because graph isomorphism is NP-complete doesn't mean it's unsolvable; it just requires a lot of resources (both CPU power and time). Perhaps a distributed SETI-like project would be able to attack the problem effectively.

It might, yes. As for using vertices, I meant just the abstract graph structure of polytope -- no two different CRF polychora could have the same abstract structure, though the abstract structure might have to include more than just vertices and edges -- I suspect that there still wouldn't be two CRF polychora with identical structure (differing in faces and cells, but with isomorphic vertex/edge graphs), but don't know how to prove it.

[quickfur]

There's no need to prove anything, this is already a known result. Since we're dealing with CRFs, all edges are equal, and all cells are flat, so face lattice equivalence == polytope equivalence. But yes, you do need the entire face lattice (i.e., vertices, edges, polygons, cells); it's not enough to have only vertices and edges.

P.S. Note that vertices alone are enough to construct the entire face lattice, via a convex hull algorithm (since we're dealing with CRFs). Unfortunately, convex hull algorithms thus far have exponential worst-case running times, even if most of the time they are better-behaved. So you're potentially looking at vertices + convex hull + graph isomorphism, which is quite a big task, computationally speaking, for each generated CRF candidate. If you consider that there are 300 million 600-cell diminishings, every one of which will need to undergo the above process, then you can see why this problem can quickly become intractible. And the primary problem with brute force search is that we can't tell if something is a 600-cell diminishing until after we've already done the above process, so it doesn't really help save any computational costs to recognize them in the first place.

Keep in mind, though, that we may not need to do a full convex hull solve on CRF candidates, if we're already constructing them as cell complexes rather than raw vertices. In this case, the cell complex itself will already give us an easy way to extract the face lattice without requiring a full convex hull algorithm. (In fact, I generally dislike working directly with vertices when higher-level structures can be used.) But that still leaves the graph isomorphism problem, which is NP-complete.

[Marek14]

There's no need to prove anything, this is already a known result. Since we're dealing with CRFs, all edges are equal, and all cells are flat, so face lattice equivalence == polytope equivalence. But yes, you do need the entire face lattice (i.e., vertices, edges, polygons, cells); it's not enough to have only vertices and edges.

I meant a proof whether the entire lattice is necessary under CRF limitations.

[quickfur]

There's no need to prove anything, this is already a known result. Since we're dealing with CRFs, all edges are equal, and all cells are flat, so face lattice equivalence == polytope equivalence. But yes, you do need the entire face lattice (i.e., vertices, edges, polygons, cells); it's not enough to have only vertices and edges.

I meant a proof whether the entire lattice is necessary under CRF limitations.

Oh I see. Hmm... I'm not sure, but I suspect in some cases you might need more than just vertices and edges? But in any case, if we're already constructing CRF candidates as cell complexes to begin with, then we should already be able to easily extract the face lattice, right?

[Marek14]

There's no need to prove anything, this is already a known result. Since we're dealing with CRFs, all edges are equal, and all cells are flat, so face lattice equivalence == polytope equivalence. But yes, you do need the entire face lattice (i.e., vertices, edges, polygons, cells); it's not enough to have only vertices and edges.

I meant a proof whether the entire lattice is necessary under CRF limitations.

Oh I see. Hmm... I'm not sure, but I suspect in some cases you might need more than just vertices and edges? But in any case, if we're already constructing CRF candidates as cell complexes to begin with, then we should already be able to easily extract the face lattice, right?

Yes. I wonder if that makes the isomorphism comparisons easier or harder. Easier to prove non-isomorphism, harder to prove isomorphism, I'd expect...

[quickfur]

I dunno, I think it amounts to the same thing. Working with cell complexes is equivalent to working with the vertices of the dual polytope, so I would expect the graph isomorphism problem to require about the same amount of effort. (Of course, there are cases where it's easier to with the dual vs. the original polytope, but if you amortize it across a large number of constructions, I'd expect both approaches to be roughly equal.)

[Marek14]

I dunno, I think it amounts to the same thing. Working with cell complexes is equivalent to working with the vertices of the dual polytope, so I would expect the graph isomorphism problem to require about the same amount of effort. (Of course, there are cases where it's easier to with the dual vs. the original polytope, but if you amortize it across a large number of constructions, I'd expect both approaches to be roughly equal.)

Though the question arises -- yes, there is huge amount of 600-cell diminishings, but what new things could the algorithm discover before even reaching their heights?

BTW, when I was looking at my list of vertex figures of 3D CRFs, I realized that pentagonal orthocupolarotunda contains vertices identical to those that appear in bilbro and thawro -- this would probably explain why this Johnson solid suddenly appeared in some figures.

Similarly, there should be a relationship between elongated square bipyramid and square orthobicupola, but of course we haven't found anything nontrivial that would contain these...

[quickfur]

I dunno, I think it amounts to the same thing. Working with cell complexes is equivalent to working with the vertices of the dual polytope, so I would expect the graph isomorphism problem to require about the same amount of effort. (Of course, there are cases where it's easier to with the dual vs. the original polytope, but if you amortize it across a large number of constructions, I'd expect both approaches to be roughly equal.)

Though the question arises -- yes, there is huge amount of 600-cell diminishings, but what new things could the algorithm discover before even reaching their heights?

BTW, when I was looking at my list of vertex figures of 3D CRFs, I realized that pentagonal orthocupolarotunda contains vertices identical to those that appear in bilbro and thawro -- this would probably explain why this Johnson solid suddenly appeared in some figures.

You might have missed some of our recent discoveries, but basically, bilbiro, thawro, and pentagonal orthocupolarotunda can be directly produced by Stott expansion from an appropriate faceting of the icosahedron. So they are definitely related to each other in a fundamental way.

Similarly, there should be a relationship between elongated square bipyramid and square orthobicupola, but of course we haven't found anything nontrivial that would contain these...

The elongated square bipyramid does occur in this cutie:



It's an augmentation of the cantellated cantitruncated 16-cell with octahedron||cuboctahedron.

I haven't tried constructing it yet, but I'm pretty sure a Stott expansion of this polychoron is possible, and will contain elongated square orthobicupola cells.

In general, the n-pyramid has a direct relationship with the n-cupola via Stott expansion perpendicular to its axis of symmetry, which means the dihedral angles between the bottom face and the triangular faces are identical in both the n-pyramid and the n-cupola, and their heights are also identical. This in turn means that there is a direct relationship between the 4D cube pyramid and the segmentochoron 8-prism||square, and between the square pyramid-pyramid and the square orthobicupolic ring, etc.. All of these are related via Stott expansions along their symmetry groups.

This also happens with 4D basis objects: a subsymmetrical Stott expansion of the 5-cell produces cuboctahedron||tetrahedron, for example. The resulting CRF retains the same dichoral angles between the cuboctahedron and tetrahedra as between the tetrahedra in the 5-cell; and it has the same height, etc.. Stott expansion is a very useful operator in producing more CRFs from existing CRFs.

[Marek14]

The elongated square bipyramid does occur in this cutie:



It's an augmentation of the cantellated 16-cell with octahedron||cuboctahedron.

I haven't tried constructing it yet, but I'm pretty sure a Stott expansion of this polychoron is possible, and will contain elongated square orthobicupola cells.

In general, the n-pyramid has a direct relationship with the n-cupola via Stott expansion perpendicular to its axis of symmetry, which means the dihedral angles between the bottom face and the triangular faces are identical in both the n-pyramid and the n-cupola, and their heights are also identical. This in turn means that there is a direct relationship between the 4D cube pyramid and the segmentochoron 8-prism||square, and between the square pyramid-pyramid and the square orthobicupolic ring, etc.. All of these are related via Stott expansions along their symmetry groups.

This also happens with 4D basis objects: a subsymmetrical Stott expansion of the 5-cell produces cuboctahedron||tetrahedron, for example. The resulting CRF retains the same dichoral angles between the cuboctahedron and tetrahedra as between the tetrahedra in the 5-cell; and it has the same height, etc.. Stott expansion is a very useful operator in producing more CRFs from existing CRFs.

Well, "elongated square orthobicupola" is just rhombicuboctahedron. This is not what I had in mind. I was talking about unelongated square orthobicupola, though it's also an expansion of elongated square bipyramid, of course...

[quickfur]

[...]
I was talking about unelongated square orthobicupola, though it's also an expansion of elongated square bipyramid, of course...

Hmm. The most obvious construction that has the unelongated square orthobicupola, is the truncated tesseract augmented with truncated_cube||cube. This produces a polychoron with 24 square orthobicupola. However, it is not CRF, because the region around the original tetrahedral cells has unequal edges.

[quickfur]

Haha, it appears that using cuboctahedron||truncated_cube instead of cube||truncated_cube to augment the truncated tesseract works; it produces a nice CRF with 24 square orthobicupolae. Here's a render of this cutie:



Here are the coordinates:

Code: Select all

apacs<1, 1+√2, 1+√2, 1+√2>
apacs<0, √2, √2, 2+√2>


It appears to be some kind of Stott-contracted version of the augmented cantellated 16-cell that I posted earlier. Perhaps Klitzing may even have considered this CRF before when he did the research on partial Stott expansions? EDIT 2: This seems to be a Stott contraction of the cantellated 24-cell x3o4x3o, not of the augmented cantellated 16-cell.

EDIT: Added software models to Octaaugmented truncated tesseract, for Marek's viewing pleasure.

[Marek14]

Looks great, thanks

[Klitzing]

EDIT 2: This seems to be a Stott contraction of the cantellated 24-cell x3o4x3o.

Indeed. x3o4x3o is srico (small rhombated icositetrachoron).
Accordingly I called that one in those days of my find pocsric (partially contracted srico).

--- rk

[quickfur]

The real challenge, though, is to find a CRF that contains square gyrobicupolae. I can't think of any, in fact. Even a seemingly innocuous operation like gyration messes up the dichoral angles in a way that breaks the connection with existing constructions with the orthobicupolae, so probably a radically different approach would have to be taken to close it up in a CRF way.

But, this is veering off-topic a bit... perhaps what we need for brute-force searching is a more directed approach, like searching for all maximal augmentations of the uniforms, or all maximal diminishings, etc.. I've gone through most of the uniforms looking for maximal diminishings, and I think I have collected fairly good data on what the possibilities are for all except the overly-large 120-cell family. Maybe it's time to start looking at the maximal augmentations now. In either case, programmatic exhaustive search might be a good way of proving that the currently known set of maximal diminishings (other than the 120-cell family) are complete. It should be a lot more tractible than brute-forcing the completely general 4D CRFs.

My current definition of maximal diminishing is a CRF that cannot have any more vertices deleted from it without (1) becoming non-CRF; (2) losing its current edge length. Condition (2) is to prevent trivialities like deleting all except 24 vertices from a 600-cell to get a 24-cell of different edge length. I don't have a working definition of maximal augmentation yet; but probably it should be something like: a CRF that can no longer have any more vertices added to it without (1) becoming non-CRF; or (2) changing in edge length. (Again, condition (2) is to prevent silliness like adding the vertices of a 600-cell to a tesseract that lies inside their convex hull.)