2025-08-09

n-cubes (hypercubes)

definition

  • n-dimensional euclidean figure with vertices in [0,1]^n (or {±1}^n under symmetry convention)
  • edges equal in length and mutually orthogonal
  • each k-face is itself a k-cube
  • requires full n-dimensional space to preserve orthogonality
  • symmetry group: hyperoctahedral group (permutations and sign flips of axes)

construction

  • iterative orthogonal extrusion:

    • start with a point (0-cube)
    • extend in a new orthogonal direction to form a segment (1-cube)
    • repeat: duplicate current figure in new direction, connect corresponding vertices

  • generative unit: 1-cube

    • n-cube = n-fold Cartesian product of 1-cube

    • vertex set: {0,1}^n

    • square (2-cube) is first case with visible combinatorial structure

coordinate representation

  • vertices indexed by integers v ∈ [0, 2^n)

  • binary digits give coordinates:

    • bit d = 0 -> -1

    • bit d = 1 -> +1

    • vertex(v) = (coord_0, coord_1, …, coord_{n-1})

enumeration

  • all vertices:

    • loop v from 0 to 2^n - 1
    • output vertex(v)
    • time complexity Θ(2^n)

  • vertices of a k-face:

    • choose k coordinate positions to vary
    • fix remaining n - k positions
    • enumerate all 2^k bit patterns on varying positions
    • merge fixed and varying bits to form vertices

  • face pattern templates:

    • example: 2-cube faces of a 4-cube (f=fixed, v=variable): ffvv, fvfv, fvvf, vffv, vfvf, vvff

    • example face (pattern vfvf, fixed bits v0v1): 0001, 0011, 1001, 1011

    • k-face counts by (vary, fix):

      • 3-cube: edges (1,2), squares (2,1), cubes (3,0)

      • 4-cube: edges (1,3), squares (2,2), cubes (3,1)

algorithms

  • gospers hack for k-combination masks
  • merge_bits to combine fixed and varying coordinates

combinatorial counts

  • 2-cube:

    • 0-cells: 4 vertices
    • 1-cells: 4 edges
    • 2-cell: 1

  • 3-cube:

    • 0-cells: 8 vertices
    • 1-cells: 12 edges
    • 2-cells: 6 squares
    • 3-cell: 1 cube
    • adjacency: vertex->3 edges, edge->2 faces

  • 4-cube:

    • 0-cells: 16 vertices
    • 1-cells: 32 edges
    • 2-cells: 24 squares
    • 3-cells: 8 cubes
    • 4-cell: 1 tesseract
    • adjacency: vertex->4 edges, edge->3 faces
  • general volume: (side_length)^n
  • facets (n-1-faces) terminology

geometric analogies

  • square -> cube: extrude perpendicular to plane
  • circle -> cylinder: extrude perpendicular to plane
  • circle -> sphere: rotate around diameter
  • square -> cylindrical surface: rotate around edge

notes

  • edges of faces overlap; cannot traverse all squares without revisiting edges

algorithms

coordinate representation

# map integer vertex index v ∈ [0, 2^n) to coordinate array in { -1, +1 }^n
# input: v (integer), n (dimensions)
# output: array of length n, each element = -1 or +1

bits_to_array = (v, n) ->  # [±1, ±1, ±1, ...]
  [0...n].map (d) ->
    if (v >> d & 1) == 0 then -1 else 1

gospers hack for k-combinations

# generate all k-combinations of {0,...,n-1} as binary bitmasks
# input: n (set size), k (subset size)
# output: array of integers, each bitmask has exactly k bits set

get_bit_combinations = (n, k) ->  # [integer, ...]
  result = []
  a = (1 << k) - 1
  while a < (1 << n)
    result.push a
    b = a & -a
    c = a + b
    a = (((c ^ a) >> 2) / b) | c
  result

group vertices into k-faces

# partition a set of vertex indices into all k-faces of the n-cube
# input:
#   vertices: array of integer vertex bitmasks (length = 2^n)
#   indices: array of vertex indices to consider
#   n: cube dimension
#   k: number of varying coordinates in each face
#   cell_length: number of vertices per k-face (= 2^k)
# output: array of k-faces, each face = array of vertex indices

group_n_cells = (vertices, indices, n, k, cell_length) ->  # [[integer, ...], ...]
  fixed_combinations = get_bit_combinations n, k
  cell_indices = []
  for fixed in fixed_combinations
    cell_vertices = {}
    for i in indices
      key = fixed & vertices[i]
      if cell_vertices[key]
        cell_vertices[key].push i
      else
        cell_vertices[key] = [i]
    new_cells = Object.values(cell_vertices).filter (a) -> cell_length == a.length
    cell_indices = cell_indices.concat new_cells
  cell_indices

enumerate all cells recursively

# enumerate all cells of an n-cube, grouped by dimension
# input:
#   vertices: array of integer vertex bitmasks
#   n: cube dimension
# output:
#   nested arrays; level 0 = 1-faces (edges), ..., level n-1 = n-faces (the cube itself)
#   each cell represented as array of vertex indices

get_cells = (vertices, n) ->  # [[[integer, ...], ...], [[integer, ...], ...], ...]
  subcells = (indices, k) ->
    return indices unless k < n
    indices = group_n_cells vertices, indices, n, k, 2 ** (n - k)
    subcells a, k + 1 for a in indices
  subcells [0...vertices.length], 1

enumeration example

n = 4
bit_vertices = [0...2 ** n]

# vertices as coordinate arrays in { -1, +1 }^n
vertices = bit_vertices.map (v) -> bits_to_array v, n

# all cells, grouped by dimension (edges, squares, cubes, hypercubes)
cells = get_cells bit_vertices, n