Complexity
A design is a parity rule on the corners of a cube. Read its fill vector in corner order and it is the truth table of a Boolean function — that is the theorem of the bijection page, and it means the whole apparatus of Boolean complexity applies to the catalog without translation. Sensitivity, certificate complexity, decision-tree depth: these are properties of a design, computable from its filled corners with nothing but parity-cube combinatorics.
The question this page answers is how much of that complexity the geometry can see. The census already carries genus, degree, popcount and the odd-side fill polynomial. Do they determine how hard the function is? At D = 3 yes, but only because the catalog is too small for the question to bite. At D = 4 no — and the failure is exhibited by two named designs that draw indistinguishable fractals and differ in six of seven complexity measures.
A second sense of complexity closes the page: the spectrum of the fractal a design builds. The graph Laplacian of the Sierpinski triangle that mrly_07 draws is degenerate to a degree that is itself a law, and that law now runs to level 8.
Every claim carries a tag. Proved means a proof is given here; Verified means recomputed from scratch for this page; Conjecture means neither.
Seven measures on a finite catalog
Fix D. There are 2^(2^D) designs and, up to cube symmetry, A000616(D) classes — 22 at D = 3, 402 at D = 4. Both catalogs are small enough to measure exhaustively and exactly: no sampling, no approximation.
s, sensitivity: the largest number of single-bit flips at one input
that change the value.
bs, block sensitivity: the largest number of pairwise disjoint blocks
of coordinates whose flip changes the value.
C, certificate complexity,max(C_0, C_1): the fewest bits that pin
the value down.
dt, decision-tree depth: the exact minimum depth of a deterministic
query tree.
deg, real degree: the degree of the unique multilinear real polynomial
representing f. This is not the GF(2) algebraic degree of the core page, and the two genuinely differ — the carpet mrly_023 has GF(2) degree 2 and real degree 3.
dnfandcnf: the minimum number of terms in a DNF, and of clauses in a
CNF, by exact prime-implicant cover.
All seven are constant on a hyperoctahedral orbit, so they descend to the classes unambiguously. (Proved: cube symmetry is permutation and negation of the input variables, and every measure above is defined by a property of the truth table that survives relabelling and complementing inputs — the output is never touched, which is what would swap dnf and cnf. Verified orbit-wide over all 256 designs at D = 3.) Hand cases pin the code down — the dictator has every measure 1, the 3-bit AND has s = bs = C = dt = deg = 3 but dnf = 1, parity has s = bs = C = dt = deg = 3 with GF(2) degree 1. (Verified.)
The 3D catalog, fully measured
Twenty-two classes, every measure exact. (Verified twice, by two generators written separately and diffed cell by cell — 286 cells at D = 3 and 5226 at D = 4, zero mismatches. The lab RUN.txt states which stages of the second generator are genuinely independent of the first, and which are not.)
| name | genus | gf2deg | pop | s | bs | C | dt | deg | dnf | cnf |
|---|---|---|---|---|---|---|---|---|---|---|
mrly_000 | iso | -1 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 1 |
mrly_001 | iso | 3 | 1 | 3 | 3 | 3 | 3 | 3 | 1 | 3 |
mrly_003 | axis | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 2 |
mrly_006 | comp | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 2 | 3 |
mrly_007 | comp | 3 | 3 | 2 | 2 | 2 | 3 | 3 | 2 | 2 |
mrly_015 | axis | 1 | 4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
mrly_022 | iso | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 4 |
mrly_023 | iso | 2 | 4 | 2 | 2 | 2 | 3 | 3 | 3 | 3 |
mrly_024 | iso | 2 | 2 | 3 | 3 | 3 | 3 | 2 | 2 | 3 |
mrly_025 | comp | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 3 |
mrly_027 | comp | 2 | 4 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
mrly_030 | comp | 2 | 4 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
mrly_031 | comp | 3 | 5 | 2 | 2 | 2 | 3 | 3 | 2 | 2 |
mrly_060 | comp | 1 | 4 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
mrly_061 | comp | 3 | 5 | 3 | 3 | 3 | 3 | 3 | 3 | 2 |
mrly_063 | comp | 2 | 6 | 2 | 2 | 2 | 2 | 2 | 2 | 1 |
mrly_105 | iso | 1 | 4 | 3 | 3 | 3 | 3 | 3 | 4 | 4 |
mrly_107 | iso | 3 | 5 | 3 | 3 | 3 | 3 | 3 | 4 | 3 |
mrly_111 | comp | 2 | 6 | 3 | 3 | 3 | 3 | 3 | 3 | 2 |
mrly_126 | iso | 2 | 6 | 3 | 3 | 3 | 3 | 2 | 3 | 2 |
mrly_127 | iso | 3 | 7 | 3 | 3 | 3 | 3 | 3 | 3 | 1 |
mrly_255 | iso | 0 | 8 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
The genus column reads iso 10, axis 2, comp 10 and the GF(2) degree histogram reads -1: 1, 0: 1, 1: 3, 2: 9, 3: 8, both matching the core page exactly. (Verified — a crossref, recomputed here rather than copied.)
One structural fact is already visible: dt > bs happens. Three classes — mrly_007, mrly_031, and the carpet mrly_023 — have bs = 2 but dt = 3. The query tree is deeper than block sensitivity, which is the first place the query chain comes apart. (Verified.)
The pin family: where geometry wins
The D + 1 axis designs are the ones that say "these r named axes must be even". Such a design is the AND of r literals, and every classical measure of an r-bit AND is known in closed form.
Proved. For the design pinning r of the D axes, s = bs = C = dt = deg = deg_GF2 = r, in every dimension. The function is x_1 AND ... AND x_r. At the input where all r literals hold, flipping any one of them changes the value and flipping anything else does not, so s = r; querying those r literals decides the function, so dt <= r. With s <= bs <= C <= dt — proved below — the chain closes: r = s <= bs <= C <= dt <= r. The multilinear real form is the monomial x_1 * ... * x_r, of degree r, and so is the GF(2) form. (Verified at D = 3 and D = 4, all r.)
The research notes state this as "every measure equals r", and that is wrong on the last two: the DNF size is 1 for every r — one term is the whole function — and only the CNF size is r. (Verified: dnf = 1, cnf = r, at D = 3 and D = 4, all r.) The corrected statement covers six measures, not eight.
The isotropic designs are tame for a related reason: a level-set is symmetric under permuting coordinates, so its measures are forced by its level structure. The compounds are where the geometry runs out — and by the core page's own asymptotic count, almost every design is a compound.
Where geometry stops
Make "determine" precise. Group the catalog by a key, a tuple of geometric data. The key determines a measure when every group carries a single value of it. A group carrying two values is a certificate that the geometry cannot see the measure.
The finest key available is (genus, GF(2) degree, popcount, fill polynomial), the fill polynomial being the odd-side polynomial of the method page — which, by that page's corollary, is equivalent to knowing how many filled corners sit at each Hamming weight. That is as much as the fractal geometry knows about a design's fill at every side and every level.
Verified. At D = 3 this key determines all seven measures. It does so vacuously: the fill polynomial alone separates 21 of the 22 classes, and the single collision (mrly_015 against mrly_027, both with polynomial 4k^3 - 4k^2 + k) is broken by genus and degree. There is nothing to test.
Verified. At D = 4 the same key determines none of the seven. Nor does any coarser key: not genus, not GF(2) degree, not popcount, not the fill polynomial alone. The fill polynomial sends 402 classes to 183 distinct values, 94 of them shared by two or more classes; under the full key, 92 groups hold two or more classes, 81 of those split at least one measure, and there are 279 measure-splits in total.
The smallest witness, by code:
| name | genus | gf2deg | pop | fill polynomial | s | bs | C | dt | deg | dnf | cnf |
|---|---|---|---|---|---|---|---|---|---|---|---|
mrly_00027 | comp | 3 | 4 | 4k^4 - 4k^3 + k^2 | 3 | 3 | 3 | 3 | 3 | 2 | 3 |
mrly_00281 | comp | 3 | 4 | 4k^4 - 4k^3 + k^2 | 4 | 4 | 4 | 4 | 3 | 3 | 5 |
Verified. Two designs with identical genus, identical GF(2) degree, identical popcount and identical fill polynomial, separated by six of the seven measures — only the real degree agrees. Their ANFs are 1 + x + z + xz + yw + zw + xyw + xzw and 1 + w + z + xy + xyw + xyz + xzw + yzw, and theirs is one of 14 groups of size two at D = 4 in which block sensitivity splits — the one with the smallest code.
Two honest qualifications. First, the fill polynomial is not a symmetry invariant: its leading coefficient is the popcount and is invariant, but the lower coefficients are not, because parity flips fix the infinite tiling and move a truncation to a finite side. The column belongs to the canonical representative of the class. That only strengthens the result — the key used here is finer than any genuine invariant, and it still determines nothing. Second, this is a statement about D = 4, verified exhaustively there, and not a theorem about all D.
The reading: the fill polynomial is a real geometric coordinate on the catalog, and it bounds complexity — it fixes the leading term, hence the popcount, hence the fractal dimension. It does not compute complexity. Past its resolution there is no geometry-to-complexity map, and two designs are the proof.
The catalog on the inequality web
The standard relations, and where the designs sit on them.
Proved. s <= bs <= C <= dt. Single-bit flips are disjoint blocks, which gives the first. For the second, a certificate for an input must intersect every sensitive block of that input — otherwise the block could be flipped without leaving the certified subcube, changing the value — and the blocks realising bs are pairwise disjoint, so the certificate has at least bs bits. For the third, the path a depth-dt tree takes on an input is itself a certificate for that input, of at most dt bits.
Verified. C = bs for every class at D = 3 and D = 4 — 424 classes, no certificate gap anywhere. A seeded spot check of 50000 uniformly random designs at D = 5 found no exception either. This is reported as verified for D <= 4 and open beyond: nothing here rules out a certificate gap in higher dimension, and no general theorem is claimed.
Verified. s = bs for every class at D = 3. At D = 4 there is exactly one exception, mrly_07128, with s = 2 and bs = 3 — orbit size 24, ANF x + y + xy + xz + yw + zw. It is the family's first separation between sensitivity and block sensitivity, and it is unique. In the D = 5 spot check, 216 of the 50000 designs had s != bs, every one of them at s = 3, bs = 4; nothing wider appeared in a random sample.
Verified. deg <= s^2 holds across both catalogs, and exactly two classes with s >= 2 meet it with equality: mrly_00855 and mrly_01911, both with deg = 4, s = 2, both of orbit size 48.
Proved. mrly_01911 is the textbook extremal function. Its ANF is 1 + xy + zw + xyzw, and expanding (1 + xy)(1 + zw) over GF(2) gives 1 + zw + xy + xyzw — the same polynomial. So the design is an AND of two 2-bit NANDs, which over the reals is an AND of two ORs: the standard construction attaining deg = s^2, found here as a single orbit of the catalog with a geometric address.
On the literature. Huang's theorem — that a Boolean function's sensitivity and degree are polynomially related, resolving the Sensitivity Conjecture — was opened and read for this page: Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, Hao Huang, 2019. Its Theorem 1.4 is s(f) >= sqrt(deg(f)), which is the deg <= s^2 used above; the paper notes the bound is tight for AND-of-ORs, which is exactly the function found here. Its Theorem 1.5 is bs(f) <= s(f)^4, and it reports the Nisan-Szegedy bound as bs(f) <= 2*deg(f)^2, adding that this was later improved to bs(f) <= deg(f)^2 by Tal. The research notes state bs(f) <= deg(f)^2 and hang it on Nisan-Szegedy: by Huang's account that is the later, sharper bound, so what the notes get wrong is the attribution and not the inequality. The papers of Nisan-Szegedy and of Tal were not opened for this page, so nothing here rests on them beyond what Huang's own text says.
Average sensitivity is exact
The uniform distribution on designs — each of the 2^(2^D) codes equally likely — is on classes the orbit-size-weighted distribution, which is precisely the measure Burnside's count integrates. So an average-over-designs statement is a statement about the class catalog, reweighted by orbit size.
Under that measure the value at each corner is an independent fair bit.
Proved. For a fixed input x, the point sensitivity s(f, x) — the number of neighbours of x that disagree with it — is Binomial(D, 1/2). The D neighbours are distinct corners, so their bits are independent of x's bit and of each other, and each disagrees with probability 1/2.
The maximum over x does not concentrate, because neighbouring inputs share edges. Verified by exhaustive enumeration: the probability that a design attains the full sensitivity D is 1/2, 5/8, 69/128, 18253/32768 at D = 1, 2, 3, 4 — between 0.50 and 0.63, with no sign of climbing to 1.
What does concentrate is the average, the total influence I(f) = 2^-D * sum over x of s(f, x).
Proved. Under uniform-over-designs, E[I] = D/2 and Var[I] = D/2^(D+1). Let U count the bichromatic edges of the hypercube Q_D, the edges whose endpoints get different values. Each such edge is counted once at each endpoint in the sum over x, so I = 2U/2^D = U/2^(D-1). The cube has m = D*2^(D-1) edges. The indicator of an edge {a,b} is X_a xor X_b, a fair bit; and for two distinct edges the two indicators are independent, since together they involve three or four distinct corners and are two linearly independent parities of independent fair bits. Pairwise independence is all the first two moments need: E[U] = m/2 and Var[U] = sum of the variances = m/4, giving E[I] = D*2^(D-2)/2^(D-1) = D/2 and Var[I] = D*2^(D-3)/2^(2D-2) = D/2^(D+1).
The research notes prove this by asserting U ~ Binomial(m, 1/2), and that step is false. The edge indicators are not mutually independent: around any 4-cycle of the hypercube they XOR to 0, so some values of U are unreachable. (Verified: at D = 3 no design at all has exactly one bichromatic edge, where Binomial(12, 1/2) would put 12 of the 256 there; the realised values of U are 0, 3, 4, 5, 6, 7, 8, 9, 12 and nothing else.) The moments survive because they only need pairwise independence, which does hold — but the distribution claimed does not, and the corrected proof above uses only what is true.
Verified by full enumeration of all 2^(2^D) designs in exact rational arithmetic at D = 1, 2, 3, 4: mean 1/2, 1, 3/2, 2 and variance 1/4, 1/4, 3/16, 1/8, matching the closed forms with no rounding.
The relative spread is sqrt(2/(D*2^D)), which goes to 0, so a uniformly random design has total influence D/2 up to a vanishing fraction. That E[I] = D/2 for a random Boolean function is standard; the closed-form variance and its tie to the hypercube edge count are what this page adds, and they are modest.
The other complexity: the triangle's spectrum
The second sense of complexity is spectral, and it belongs to the fractal rather than the rule. Take mrly_07 in dimension 2 — the parity rule filling three of the four corners of {0,1}^2, tile
1 1
1 0— and substitute it into itself L times. The level-L array is 2^L on a side with 3^L filled cells, and a cell (i, j) survives exactly when i AND j = 0: the Sierpinski triangle. (Verified at L = 1..8: the Kronecker construction is executed literally and the i AND j = 0 characterisation is then checked against it, never assumed.)
Let G_L be the graph on the filled cells, with an edge between axis-nearest neighbours and no diagonals. The operator is the normalised Laplacian I - D^-1/2 A D^-1/2, whose spectrum lies in [0, 2]. (The combinatorial Laplacian D - A is a different operator with a different spectrum; the laws below are about the normalised one.)
The spectrum is extraordinarily degenerate, and the degeneracy is structured.
L | nodes | distinct | degenerate classes | repeated fraction | mult of 1 | mult of 1 -/+ sqrt(30)/6 |
|---|---|---|---|---|---|---|
| 1 | 3 | 3 | 0 | 0.0000 | 1 | 0 |
| 2 | 9 | 7 | 1 | 0.3333 | 3 | 1 |
| 3 | 27 | 17 | 3 | 0.4815 | 9 | 2 |
| 4 | 81 | 43 | 9 | 0.5802 | 27 | 4 |
| 5 | 243 | 111 | 25 | 0.6461 | 81 | 10 |
| 6 | 729 | 289 | 67 | 0.6955 | 243 | 28 |
| 7 | 2187 | 755 | 177 | 0.7357 | 729 | 82 |
| 8 | 6561 | 1975 | 465 | 0.7699 | 2187 | 244 |
(Verified: computed twice by generators sharing no code — one building the fractal by Kronecker product, reading adjacency off shifted array slices and clustering eigenvalues by gap; the other expanding blocks over a coordinate set, building adjacency cell by cell through a dictionary and clustering by rounding. Every column agrees at every level. The research notes carried L = 5, 6, 7 only; L = 1..4 and L = 8 are new here.)
Verified. The second family's eigenvalues are 1 -/+ sqrt(30)/6, matching to within 4 * 10^-15 at every level from 2 to 8. Equivalently, the corresponding eigenvalues of D^-1/2 A D^-1/2 are the roots of 6x^2 - 5. This is a numerical identification at machine precision, not a derivation.
Conjecture. The multiplicity of eigenvalue 1 is 3^(L-1). It holds at L = 1..8: 1, 3, 9, 27, 81, 243, 729, 2187. At L = 8 that is one third of the entire spectrum pinned at a single value.
Conjecture. The multiplicity of each member of the 1 -/+ sqrt(30)/6 pair is 3^(L-3) + 1, holding at L = 3..8: 2, 4, 10, 28, 82, 244.
Conjecture. The cascade continues one step: a third family at 1 -/+ 0.988332421566 carries 3^(L-4) + 1, holding at L = 4..8: 2, 4, 10, 28, 82. This is weaker than it looks. Six distinct classes at L = 8 carry multiplicity 82, so the multiplicity alone does not pick the family out — it is tracked by its eigenvalue across levels, and only then is the multiplicity read. No closed form for that eigenvalue was found.
Conjecture. The distinct-eigenvalue count is 2*Fibonacci(2L) + 1 and the degenerate-class count is 2*Fibonacci(2L-3) - 1, fitting all eight and all seven available levels respectively. Both are existing OEIS entries, opened and read live for this page: A192908 matches the distinct count at index L+1 (its name is not a Fibonacci formula — the Fibonacci expression is a formula listed on the entry, contributed by Bruno Berselli), and A069403, whose name is a(n) = 2*Fibonacci(2*n+1) - 1, matches the degenerate-class count at index L-2. No novelty is claimed for either sequence. The fit is a fit, not a proof.
Two cautions. The multiplicities are integers read off a floating-point spectrum: the widest degenerate class at L = 8 spans 5.4 * 10^-14, the class at eigenvalue 1 is isolated by 0.442 on both sides, and the counts are flat across seven decades of clustering tolerance — convincing, and not a proof by exact arithmetic. And L = 9 is out of reach by this method: 19683 nodes means a 3.1 GB dense matrix before the eigensolver's workspace. Reaching it needs a different method — the multiplicity of eigenvalue 1 is the nullity of A, a rank computation rather than a diagonalisation.
Both multiplicity laws stay conjectures. The natural reason to expect a mechanism is the graph's self-similarity, and the honest state of that argument is that no spectral-decimation polynomial for this graph is known, so there is nothing yet to run an induction on.
What is new here
| result | status |
|---|---|
pin family: six measures equal r, dnf = 1, cnf = r | known family (AND); the geometric handle and the DNF correction are the additions |
deg = s^2 extremal pair, (1 + xy)(1 + zw) | known construction, located as an orbit of the catalog |
C = bs across both catalogs | empirical for D <= 4, not claimed in general |
E[I] = D/2 | known, the random-function average sensitivity |
Var[I] = D/2^(D+1), and the orbit-weighting bridge | modest, exact, enumeration-checked; the notes' Binomial derivation is false and is repaired here |
the geometry under-determines complexity at D = 4, with witness | new structural fact about this family |
Laplacian degeneracy at L = 8 | extends a three-point conjecture to eight points; still a conjecture |
No claim about P versus NP is made or implied.
Where the numbers live
lab/complexity/ holds both generators — measures.py and the independent recheck.py — the two catalog files measures_d3.csv and measures_d4.csv, their PASS logs, and a RUN.txt that states exactly which stages of the second generator are independent of the first and which are not.
lab/spectra/ holds degeneracy.py, its independent recheck.py, the per-class table degeneracy.csv, and a RUN.txt carrying the tolerance sweep, the timings, and the reason L = 9 stops.
The definitions of design, genus, code and fill polynomial are the core page; the identity that licenses this whole page is the bijection page; the odd-side fill polynomial is worked through end to end in the method page. The standard every sequence in this project has to meet is the sequence ledger — none of the spectral sequences above are claimed as new entries there, since both are existing OEIS sequences and the two multiplicity laws are conjectures rather than verified generators.