Number of CRF polychora

[mr_e_man]

Now I've added more functions to my program, with short explanations and examples. It still uses bit operations, though.

Code: Select all

n1,n2 = 10,10

disallow_pyramids1 = True
disallow_magbicups1 = False
disallow_adjacents1 = False

disallow_pyramids2 = True
disallow_magbicups2 = False
disallow_adjacents2 = False

disallow_simultaneous1and2 = False

# Keep in mind the operator precedence:
# arithmetic operations (+ - * //) are evaluated first, then
# bit shifts (<< >>), then other bitwise operations (& | ^).

# no augment = 00, pyramid augment = 01,
# ortho augment = 10, gyro augment = 11 (binary)

m = max(n1, n2)
all_bits = (1 << 2*m) - 1   # 1111...1111
even_bits = all_bits // 3   # 0101...0101
odd_bits = even_bits << 1   # 1010...1010
limit1 = 1 << 2*n1
limit2 = 1 << 2*n2

def pyramids(x):
    """Keep the '01' bit-pairs in x, and set '10' and '11' to '00'.

    >>> pyramids(0b00101101) == 0b00000001
    True
    """
    return x & even_bits & ~(x & odd_bits)>>1

def magbicups(x):
    """Keep the '10' and '11' bit-pairs in x, and set '01' to '00'.

    >>> magbicups(0b00101101) == 0b00101100
    True
    """
    return (x & odd_bits) | (x & even_bits & (x & odd_bits)>>1)

def gyrate(x):
    """Keep the '01' bit-pairs in x, and swap '10' and '11'.

    >>> gyrate(0b00101101) == 0b00111001
    True
    """
    return (x & odd_bits) | ((x & even_bits) ^ (x & odd_bits)>>1)

def rotate(x, num_places, total_places):
    """Shift bit-pairs in x right num_places; carry the remainder left.

    It's assumed that x has total_places many bit-pairs, and that
    num_places is between 0 and total_places (inclusive).

    >>> rotate(0b00101101, 1, 4) == 0b01001011
    True
    """
    return x >> 2*num_places | (
        (x & ((1<<2*num_places)-1)) << 2*(total_places - num_places))

def reverse(x, total_places):
    """Reverse the order of bit-pairs in x.

    This doesn't completely reverse the order of bits; '01' gets moved,
    but not flipped to '10'.

    It's assumed that x has total_places many bit-pairs.

    >>> reverse(0b00101101, 4) == 0b01111000
    True
    """
    y = 0
    for i in range(total_places):
        y |= (x>>2*i & 3) << 2*(total_places - 1 - i)
    return y

def adjacents(x, total_places):
    """Keep each bit-pair in x with a non-zero bit-pair to its left.

    This is cyclic; the leftmost bit-pair is kept if the rightmost
    bit-pair is non-zero.

    It's assumed that x has total_places many bit-pairs.

    >>> adjacents(0b00101101, 4) == 0b00001101
    True
    """
    x_left = rotate(x, 1, total_places)
    # The bit-pair in x_left at the kth place is the bit-pair in x to
    # the left of the kth place.  It moved from left to right.
    x_left_nonzero = (x_left & even_bits) | (x_left & odd_bits)>>1
    # Multiply by 3 to replace each '01' with '11'.
    return x & x_left_nonzero*3

count = 0
for ring1 in range(limit1):
    if (disallow_pyramids1 and pyramids(ring1)
            or disallow_magbicups1 and magbicups(ring1)
            or disallow_adjacents1 and adjacents(ring1, n1)):
        continue
    for ring2 in range(limit2):
        if (disallow_pyramids2 and pyramids(ring2)
                or disallow_magbicups2 and magbicups(ring2)
                or disallow_adjacents2 and adjacents(ring2, n2)
                or disallow_simultaneous1and2 and ring1 and ring2):
            continue

        rings1and2 = ring1 << 2*n2 | ring2
        is_least = True
        i = 0
        while i < 2 and is_least:
            ring1_i = reverse(ring1, n1) if i else ring1
            ring2_i = gyrate(ring2) if i else ring2
            j = 0
            while j < 2 and is_least:
                ring2_ij = reverse(ring2_i, n2) if j else ring2_i
                ring1_ij = gyrate(ring1_i) if j else ring1_i
                k = 0
                while k < n1 and is_least:
                    ring1_ijk = rotate(ring1_ij, k, n1)
                    ring2_ijk = gyrate(ring2_ij) if k & 1 else ring2_ij
                    l = 0
                    while l < n2 and is_least:
                        ring2_ijkl = rotate(ring2_ijk, l, n2)
                        ring1_ijkl = gyrate(ring1_ijk) if l & 1 else ring1_ijk
                        new_rings1and2 = ring1_ijkl << 2*n2 | ring2_ijkl
                        new_rings2and1 = ring2_ijkl << 2*n1 | ring1_ijkl
                        is_least &= rings1and2 <= new_rings1and2
                        is_least &= n1 != n2 or rings1and2 <= new_rings2and1
                        l += 1
                    k += 1
                j += 1
            i += 1
        count += is_least

print(count)


(And I have other chunks of code to more efficiently handle special cases, such as when both rings can't be augmented at the same time, or when only pyramid augments are possible.)

Using this (with the first few lines changed), I got mostly the same results as in quickfur's list. The only exceptions had both rings augmentable at the same time, and at least one ring gyratably augmentable:

4,8-duoprism: 152 augmentations
5,6-duoprism: 66 augmentations
5,8-duoprism: 162 augmentations
5,10-duoprism: 2702 augmentations
8,8-duoprism: 429 augmentations (possibly wrong, because of relation to tesseract)
10,10-duoprism: 4924629 augmentations (took about 9 hours with the code in this post, vs. 4 hours with the previous version)

Again, these counts include the un-augmented duoprisms.

If only one ring is augmentable at a time, then quickfur's operation of reversing both rings has the same effect as reversing one and gyrating the other. (Reversing no augments is the same as gyrating no augments.) So the false symmetry happens to be equivalent to the true symmetry, and the count is correct, in this case.

If both rings are augmentable at the same time, but only with pyramids (so both have size at most 5), then reversing both has the same effect as reversing and gyrating both. This is a true symmetry of the duoprism, but still the reflection is missing. It turns out that the augmentations of a ring with size 3, 4, or 5 all have reflection symmetry anyway; i.e. reversing it has the same effect as rotating it. So the reflection symmetry doesn't need to be included explicitly, and the count is correct, in this case.

[mr_e_man]

There are other possible augments that we haven't considered.

One is the digonal magnabicupolic ring, i.e. cube || line segment. Instead of ortho and gyro, it actually has three orientations, corresponding to the three axes of the cube. But in the third orientation, it can be considered as a square pyramid prism, and grouped with other n-gon pyramid prisms.

Then there are n-gon cupola prisms, as well.

And a duoprism could even be augmented with another duoprism. But it seems that the only possibility is 3,4 being augmented with another 3,4, producing two gyrobifastigia.

...Never mind; they have been considered. viewtopic.php?f=32&t=1947&start=30#p24865
I agree that these won't contribute significantly to the number of duoprism augmentations.

If we include other augment shapes such as n-pyramid prisms, the counts will have to be adjusted accordingly. Though I doubt it will add significantly more augmentations to the total, because the 90° dichoral angles of the n-pyramid prisms would mean that only 3,n-duoprisms and 4,n-duoprisms are augmentable with them, so they would not experience the same kind of combinatorial explosion the augmented 10,10-duoprism and 20,20-duoprism exhibits.

[quickfur]

There are other possible augments that we haven't considered.

One is the digonal magnabicupolic ring, i.e. cube || line segment. Instead of ortho and gyro, it actually has three orientations, corresponding to the three axes of the cube. But in the third orientation, it can be considered as a square pyramid prism, and grouped with other n-gon pyramid prisms.
[...]

In this third orientation, its square pyramid cells would be corealmar with the prisms from the other ring, so they should fuse into augmented prisms. So it becomes just the extrusion of 3D augmented prisms.

[mr_e_man]

The pentagons in x5o3x3o correspond to the vertices in o5o3x3o, or the edges in o5o3o3x. There's a total of 720.

Consider the 120 pentagons in x5o3x3o corresponding to the vertices in o5o3x3o which are deleted to get spidrox. Any of these pentagons (with their magnabicupolic rings) can be deleted, or gyrated, or left alone. This gives us at least 3^120 / 14400 ≈ 10^53 different CRFs!

We can do a little better, I think!

Divide the vertices of o5o3o3x into 5 groups of 24, as in the construction of sadi or bidex. Take 2 groups of 24 vertices, and connect them with 72 edges (corresponding to the 72 pentagons in bidex). Take another 2 groups of 24, and do the same, for a total of 144 edges. The last group of 24 remains disconnected.

Consider the 144 pentagons in x5o3x3o corresponding to those edges in o5o3o3x. Any of these pentagons (with their magnabicupolic rings) can be deleted, or gyrated, or left alone. This gives us at least 3^144 / 14400 ≈ 10^64 different CRFs.


I wonder if it will hit a googol.

[quickfur]

Wow. Yeah, we're looking at an absolutely humongous number of CRFs in 4D. And just to imagine, each of these could be the basis for building 5D CRFs...

This leads to the interesting question: what's the growth rate of the function f(n) that maps each dimension to the number of CRFs in that dimension? Seems like it'd be a pretty fast-growing function. (Of course, we'd have to exclude infinite families somehow... not sure how to do that in a dimension-independent, well-defined way.)

[mr_e_man]

(Of course, we'd have to exclude infinite families somehow... not sure how to do that in a dimension-independent, well-defined way.)

That's easy. Just restrict the polygons to 3,4,5,6,8,10.

Given a finite set of (n-1)-dimensional polytopes, there are only finitely many n-dimensional convex polytopes having those as faces. See this MO question.
Then, by induction on the dimension, given a finite set of 2-dimensional polytopes, there are only finitely many n-dimensional convex polytopes having those as faces.

Of course, this would exclude many duoprism augmentations. And it would exclude possible crown jewels with larger polygons (in 5D or higher; I think I've ruled them out in 4D).
It's conceivable that there are infinitely many crown jewels with large polygons, that don't fit into any "family".

[quickfur]

Yeah, I'm not sure how to rigorously prove that there exists some upper bound M such that for n > M, the only CRFs that can exist containing a regular n-gon is one of the prisms. Intuitively, I'm almost certain such a bound exists, though. As n grows without bound, the internal angle of the regular n-gon approaches 180°. This implies that any n-facet attached to the edge must have lateral surtopes that are increasingly constrained towards 90°. But since CRFs with such sharp angles are finite (the infinite families have angles to grow towards 180°; small angles close to 90° are few and probably easily enumerable), so as the angle is constrained towards 90° you have fewer and fewer options left, until the only option that would remain CRF is the corresponding prism.

The augmentations of the 10,20-duoprism are kind of an outlier. They are caused by the extreme shallowness of the height of the pentagonal orthobicupolic ring. I'm not sure how many higher-dimensional pyramids would have similar low height relative to edge length; I doubt there's an infinite family of them, so correspondingly any higher-dimensional polyprisms must have an upper limit beyond which they can no longer be CRF-augmented.

[mr_e_man]

Divide the vertices of o5o3o3x into 5 groups of 24, as in the construction of sadi or bidex. Take 2 groups of 24 vertices, and connect them with 72 edges (corresponding to the 72 pentagons in bidex). Take another 2 groups of 24, and do the same, for a total of 144 edges. The last group of 24 remains disconnected.

This produces some new CRFs which might be interesting:

72-diminished or 144-diminished o5o3x3o
72-diminished or 144-diminished x5o3x3o
72-gyrated or 144-gyrated x5o3x3o
72-gyrated 72-diminished x5o3x3o

Examining these could give us a better understanding of that 5*24 structure.