The Enumeration and Space-Tiling Motifs of Marked Polyhedra

Scientific Paper
Title	The Enumeration and Space-Tiling Motifs of Marked Polyhedra
Read in full	Link to paper
Author(s)	Forrest Bishop
Keywords	cube, space tiling, marked polyhedra, local orientation class, kinematic cellular automata, Bishop Cubes
Published	2007
No. of pages	22

Read the full paper here

Abstract

Although polyhedra with various markings on them are certainly not unknown, the rigorous enumeration and codification of these kinds of objects does not appear to have been done before. These objects share various unifying properties partly described by group theory, complexity theory, and space tilings.

Overview

This January 2007 paper by Forrest Bishop is not a physics paper but a combinatorial-geometry one, written in the numbered-paragraph style of a patent specification and described by the author as "my first public disclosure, aside from various patents applied for or issued, of apparently previously unknown classes and properties of some of these geometric objects". Its subject is the enumeration of marked polyhedra — cubes whose six faces each carry a stripe, a colour, or a directed arrow — and the classification of the ways such marked cubes can tile three-dimensional space.

The motivation is engineering rather than pure mathematics. Bishop's target is a "multi-cellular, shape-shifting robot composed of an arbitrary number of similar or identical parts", in which the individual cells "need have no moving parts themselves, as the geometry of the cell's interface alone suffices to constrain its motion". The face markings are, physically, the directions in which a cell is free to slide against its neighbours; the tiling question is therefore the question of which cell designs can be assembled into an aggregate whose parts can move relative to one another. The objects are trademarked as Bishop Cubes, and the paper reports that working prototypes exist, a companion paper being promised on the "X Active Cell Aggregate". A glossary of some thirty terms — Aggregate, Cell Metric, Configuration Space, Figure Game, Terminus, X/XY/XZ/XYZ Active Cell — is appended, carried over from a 1995 paper on space-filling polyhedra for active mesostructures.

The enumeration

Local Orientation Classes

The base case is a cube marked so that each of the six faces carries exactly one stripe parallel to an edge of that face. Bishop uses lower-case {x,y,z} for global (world) axes and upper-case {X,Y,Z} for the local frame on each face, Z being the outward normal — a convention he notes is standard in motion control and aerospace.

Each face admits two mutually perpendicular stripe orientations, so there are 2⁶ = 64 patterns on an oriented cube. Fixing one face relative to global coordinates halves this to 32, the other 32 being obtained by a 90-degree rotation of the whole array about the vertical axis, which "doesn't add any new information". The array of 32 is generated by an ordered binary-adder process over the remaining faces and then searched by inspection for coincidences. Exactly eight distinct objects survive, and these are the Local Orientation Classes (LOCs), named after the letters their stripe patterns suggest: 6I, IOI, IO-I, U3I, 2U, IUL, and the mirror pair R-3L and L-3L. Since the array of 32 exhausts the possibilities, Bishop takes this to complete the proof.

Two measures of "complexity or disorder" are then extracted. The first is frequency of appearance in the 32-array: IUL appears twelve times and 6I only once, making IUL the most disordered and 6I the most ordered. The second is the number of cells needed to form a unit cell of the tiling: 6I and IOI need one, IUL needs four in four orientations, and the mirror pair R-3L/L-3L must join up as an eight-member checkerboard. Bishop also treats the eight LOCs as "a group of sorts" under the operation "rotate one stripe about its local Z axis": six ways out of each node, forty-eight transformations in all, of which twenty-four lead to IUL, ten to U3I, five to IOI, three to IO-I, and one each to 6I, R-3L and L-3L. He notes that this gives IUL a formation probability of 0.5 against the 0.375 implied by the frequency count, and attributes the discrepancy to path dependence.

The four tiling motifs

Each marked cube tiles space trivially. To get a kinematically compatible array, Bishop imposes a chain of matching conditions: oriented lines on adjoining faces must match; the stripes on the other four adjacent faces of each pair must be oriented alike in individual pairings; and the two joined cubes must have parallel stripes on their furthest-removed parallel faces. The first two conditions each still leave an infinity of crystal-like tilings; the third reduces the LOC tilings to exactly seven. Decorated with sliding interfaces, these are Minimal Kinematically-Compatible Arrays (MKCAs).

The smallest periodic unit cell depends on how many pairs of opposite faces match, and the eight LOCs exhaust the cases of three, two, one and zero such pairs. This yields the paper's four named tiling motifs:

3M — "Adjacent 3 × 3", or Whorl (1, 2, 4 or 8 cells)
2M — Adjacent 2 × 4 (2, 4 or 8 cells)
1M — Baseball (4 or 8 cells)
0M — Jigsaw (always 8 cells)

Two structural results are stated. The Genetrix Property: any Member of an MKCA can generate all the other Members of the same MKCA, so any Member may be taken as its genetrix. And the consequent Exclusion Property: a Cell Type belonging to one kind of MKCA cannot belong to a different kind — which, with the four-motif result, gives an independent cross-check on the counts. Mixing LOCs is precluded by the matching conditions; mixed-LOC arrays that are kinematically compatible exist but are non-minimal (NKCAs) and of "excessive complexity and questionable utility".

Variant markings

Three further families are enumerated. Diagonal stripes on each face give eight unique cubes, one of which is the familiar inscribed tetrahedron; under the same matching conditions these tile space in exactly five ways, and here — unlike the parallel case — different LOCs sometimes must be mixed. Two-colour face labelling gives ten types, a previously known set corresponding to a magnetic colour group, labelled 0T, 1T, 2TA, 2TO, 3TA, 3TO, 4TA, 4TO, 5T, 6T according to how many faces are 'T' and whether they are adjacent or opposite; these ten form the same four unit cells, requiring fifteen cells in total so that some types recur in different orientations.

Combining parallel stripes with two colours gives the TS Cells, tabulated as 224 types distributed over the eight LOCs (12 for 6I, 28 for IOI, 16 each for R-3L and L-3L, 40 for U3I, 24 each for 2U and IO-I, 64 for IUL). Replacing colours with directed arrows gives the TT Cells. Here Bishop flags a genuine difficulty: because an arrow is asymmetric, mirroring a single face changes the Cell Type, and this "cannot be discovered by mirroring the cells themselves, and possibly not by a group-theoretic approach either" — the resulting sets "may or may not be isomorphic to any known group". His solution is enumeration by construction: 4⁶ = 4096 arrangements, reduced to 1024 by fixing the bottom mark, split into a 512P block (top and bottom marks parallel) and a 512X block (orthogonal). The method preserves the relationships between LOC-constrained cell types that a bare parsing would destroy — R-3L and L-3L can appear only in 512X, where they again form a three-dimensional checkerboard, while 6I and IOI appear only in 512P. The prototype reported in the paper uses twenty-seven identical cells of the type "6I-TT 3×3 SEAM", one of 416 kinds of parallel-LOC Bishop Cube.

Assessment

Judged as what it is, this is a careful and unusually concrete piece of enumerative geometry. The eight-LOC result is proved properly — by exhaustive construction over a set shown to be complete — and the reduction of infinitely many tilings to seven by successively tightening the face-matching conditions is a clean argument. The Genetrix and Exclusion properties are the paper's best ideas: together they turn a brute-force count into something with internal structure, and Bishop uses them exactly as one should, as a cross-check on the enumeration rather than as decoration. The observation in paragraph 30 — that directed markings break the mirror symmetry in a way that may put the resulting sets outside any known group, so that construction must replace group theory — is an honest statement of a real obstruction, and the 1024-array method that follows from it is a sensible response that also preserves information a quotient would lose. Unlike most heterodox papers in this archive, its central claims are finite, checkable and, in principle, verifiable by anyone with cardboard and patience.

The difficulties are of execution rather than conception. The arithmetic does not everywhere close. The 192 TT Cell Types of Table 3 are broken down as 8 + 18 + 16 + 16 + 32 + 20 + 20 + 64, which sums to 194, not 192; the introduction independently gives the count as 6 × 32 = 192, so at least one of the three figures is wrong and the paper does not reconcile them. Table 2 is described as covering all eight parallel LOCs but carries only seven totals (5, 9, 5, 10, 7, 8, 12), and while these do sum to the stated 56, the column headings and entries have plainly slipped — the same defect recurs in Table 4, which is explicitly incomplete, with five of eight columns left blank and the remainder marked with question marks. Paragraph 26 introduces the 224 TS types as "7 * 32", a factorisation that matches neither the table's structure nor the 8 × 64 = 512 upper bound of paragraph 27. Bishop's own conjecture that Table 4 will turn out identical to Table 2 is stated as unverified.

The paper is also, by its own admission, unfinished. The Appendix promising hyperlinks to images of all MKCAs, cell-type sets and animations reads "Not completed in this draft"; the companion paper on the X Active Cell Aggregate is referenced but not supplied; and much of the argument depends on figures that the reader must accept on inspection, several of which involve distinctions of colour and arrow direction that the reproduction does not always carry. The claim of priority — that "the rigorous enumeration and codification of these kinds of objects does not appear to have been done before, to the best of my knowledge" — is properly hedged, and Bishop's own notes point to the neighbouring literature (Wang tiles and Wang cubes, Séquin's interlocking toroidal tile), but no comparison with that literature is actually made, and the relation between his ten two-colour cubes and the "previously-known" magnetic colour group he identifies them with is asserted rather than worked out. None of this touches the core enumeration, which stands on its own; it does mean the tables should be recomputed before being relied on.