A design is a Boolean function

The design count in dimension D matches OEIS A000616, the number of NP-equivalence classes of Boolean functions on D variables. That used to be an observation about shared terms. It is a theorem: there is an explicit bijection between designs and Boolean functions that carries cube symmetry onto NP-equivalence, so the two classifications are the same classification and the counts agree in every dimension. The term-matching survives below as a backstop, not as the argument.

Every claim on this page is tagged Proved (re-derived here), Verified (recomputed, not proved), or Conjecture (none appear).

The two objects

Fix a dimension D. The parity cube is {0,1}^D; its 2^D points are corners, indexed c_0 .. c_(2^D - 1) in binary order. A design is a subset F of the corners

• the filled ones - with code i(F) = sum of 2^k over k with c_k in F, so there are

exactly 2^(2^D) designs. A Boolean function on D variables is a map f : {0,1}^D -> {0,1}, and there are 2^(2^D) of those too.

Proved. The indicator map Phi(F) = 1_F is a bijection from designs to Boolean functions. A subset of a finite set and its {0,1}-indicator are the same datum: Phi^-1(f) = f^-1(1) inverts it. Read in corner order, the fill vector of a design is the truth table of its function, and the code i(F) is the integer whose binary digits are that truth table. The design and the function are one object under two names.

Cube symmetry is NP-equivalence

The cube symmetry group B_D is the group of signed permutations: permute the D axes by some pi, then flip parity on any subset of axes, i.e. XOR a fixed vector t. On corners,

g . c = (c_pi(0) xor t_0, ..., c_pi(D-1) xor t_(D-1))

which over GF(2) is the affine map c -> P*c xor t with P a permutation matrix. The NP group acts on Boolean functions by the two moves that preserve a function's shape: negate inputs (the N), permute inputs (the P). Two functions are NP-equivalent when f'(x) = f(P*x xor t) for some permutation matrix P and some t. You may relabel the input variables and complement any of them; you may not touch the output.

Proved. These are the same group, of order 2^D * D!, and Phi is equivariant for it. Same group: both consist of exactly the maps x -> P*x xor t, with D! free choices of P and 2^D free choices of t. Same action: for a design F with indicator f, 1_(g.F)(x) = 1 iff x is in g.F iff g^-1 . x is in F, so 1_(g.F) = f o g^-1, which is the NP substitution action on the function side. Hence Phi(g . F) = g . Phi(F), and two designs share a cube-symmetry orbit exactly when their indicators share an NP class.

Proved. The group is NP and not NPN. Cube symmetry moves corners, so it flips inputs; it never exchanges filled for void, which is the separate operation the project calls anti - bitwise complement of the code. Output complementation is the extra N that upgrades NP to NPN, and it appears nowhere in the argument above, so the count lands on NP exactly. Verified. The distinction is not cosmetic: adjoining the output flip and recounting orbits by brute force gives 2, 4, 14, 222 at D = 1..4, which is A000370 at offset 0, against 3, 6, 22, 402 for NP.

The count

Proved. The number of designs up to cube symmetry, in every dimension D, equals the number of NP-equivalence classes of Boolean functions on D variables. The equivariant bijection carries orbits onto classes one-to-one, and equal sets of orbits have equal cardinality. Verified. That class count is A000616: the entry's comment reads "number of NP-equivalence classes of switching functions of n or fewer variables", its offset is -1 with a conventional a(-1) = 1, and dimension D reads off at index D.

Three separately written routines were run against it here: an orbit enumeration over designs as corner subsets, an orbit enumeration over truth tables using the textbook NP substitution with no reference to designs, and the Burnside average below. Verified for every row.

Brute force stops at D = 4, where closing orbits over 65536 codes takes a fraction of a second; D = 5 would mean 2^32 codes, and Burnside costs nothing by comparison. The group orders check as 2^D * D! = 2, 8, 48, 384 for D = 1..4. A fourth confirmation sits in the lab: the base-2 rows of the fill-class census in lab/census/fillclasses/ report 6 canonical designs in dimension 2 and 22 in dimension 3, from a group built independently as one dihedral map per axis - at base 2 the residue rotation r -> r+1 is the parity flip, so that group is this one.

Burnside

Proved. Since Phi is equivariant for a finite group on a finite set, the Cauchy-Frobenius lemma applies on either side and returns the same number:

distinct(D) = (1/|B_D|) * sum over g in B_D of 2^c(g),   |B_D| = 2^D * D!

where c(g) is the number of cycles of g acting on the 2^D corners. The fixed-point count is 2^c(g) because a design is fixed by g exactly when it is a union of cycles of the corner permutation g induces, and each cycle is independently in or out. On the function side the same statement reads: f is fixed iff it is constant on each input orbit. Verified. Evaluated over the full group element by element, this reproduces A000616 for D = 0..7.

Burnside is not what proves the identity - the bijection does that, and it is uniform in D. Burnside is what makes the shared count computable past the point where orbits can be enumerated, and it is the form the project's counting code actually runs. Because the bijection and the Burnside formula both hold in every dimension, statements about how the design count grows are statements about one well-defined object per dimension rather than extrapolations from the three cases small enough to draw.

Where the honest line falls

The theorem is proved relative to one imported definition: that the symmetry of a design is the signed-permutation group of the cube, order 2^D * D!, acting on corners as above. Everything downstream of that definition is derived here. A different group would be a different theorem.

The identification with A000616 is Verified, not proved, and cannot be otherwise: that a particular OEIS entry counts NP classes is a fact about the entry. It was checked two ways - against the entry's own stated definition, and against its terms through D = 7 by recomputation. The sequence ledger records A000616 in its established-entries table, where it had been quoted from the research notes and not recomputed; this page closes that gap.