An Exact Small-n Map of Circuit Complexity: What Cheap Statistics See — and What They Miss

We map the exact gate complexity of all Boolean functions on up to five inputs and use this ground truth to quantify, at small scale, a central intuition behind the natural-proofs barrier: that efficiently computable, "large" statistical properties cannot separate hard functions from easy ones. Exact circuit sizes are computed for all 65,536 functions on four inputs with a SAT-based synthesis pipeline (validated against independent brute force and against Knuth's data); Knuth's BOOLCHAINS database covers all 616,126 NPN classes on five inputs via an independently validated parser. Main findings, each preregistered with explicit failure criteria: A decay law for spectral statistics: R² of (average sensitivity, Fourier support) → C falls 0.517 → 0.263 → 0.160 for n=3,4,5; the n=5 value was predicted in advance as 0.13±0.05 and hit. Invisibility of the hard tail: no tested cheap statistic or combination detects the top complexity tail under honest evaluation (cross-validated AUC < 0.8); an apparent detector (0.854 in-sample) collapses under cross-validation. One exception: an n-stable average-sensitivity band signal (AUC ≈ 0.70). Structure beats spectrum: minimal ROBDD size retains R² 0.515 → 0.414; a computational-depth norm predicts circuit size (0.305) where an additive Reed–Muller norm carries almost none (0.007). The inhabited landscape: 55,232 cut functions from real ISCAS85 circuits avoid the hard tail by a factor of ~400, while component functions of 192 real 4-bit S-boxes populate it at random-bijection level — tail avoidance is a signature of gate-level composition, not of human design in general. Verification by-products: first independent check of the lower-bound half of Knuth's n=5 database (60/60 sampled optimality values reproduced) and the first structural profile of the unique maximally hard five-input function (C=12: sensitivity 3.0, NL=10, ANF degree 4, stabilizer of order 4). All complexity values are exact; all statistical claims carry confidence intervals; negative results are reported. Code, exact tables (including the n=4 depth table and the DeMorgan table), and the internal research ledger (in German) are included in the data archive. Version 3 replaces the v2 report with a full paper.