Certified Depth–Width Frontiers for Reversible SELECT Circuits: Exact four-target curves, an all-width eight-target lower bound, and DRAT-certified boundary instances

Abstract

We study certified depth–width frontiers for coherent SELECT circuits in a declared classical-reversible model: gates {X, CNOT, Toffoli}, pairwise-disjoint-support layers, all-to-all connectivity, arbitrary data targets, and clean ancillae restored to zero. For four-target selection, the exact clean depth is 5 at width Q = 6 and 4 for every Q >= 7. The all-width result combines a normal-form reduction with an independently checked finite core. A causal argument gives D*(2^k,Q) >= k+1. For k >= 3, a conditional saturation obstruction strengthens this to k+2 when the specified carrier and minterm bounds hold. For eight-target selection, independent Python and C++ computations produce byte-identical complete relaxed frontiers with 57 and 18,215 states. Their relaxed maxima imply physical bounds C_3(3) <= 4 and S_3(3) <= 3, establishing D*(8,Q) >= 5 for every Q >= 11. An explicit k = 4 construction shows that this sufficient carrier criterion does not extend inductively; the general k+2 law remains open. Under the garbage-output basis-state contract, the minimum width permitting four-target selection at depth 3 is 12. At widths Q >= 12, the clean and garbage-output optima differ by one layer. This comparison does not imply that discarding input-dependent garbage preserves the intended logical unitary. For CNOT-only, ancilla-free fan-out with arbitrary target inputs, exact depths are obtained through seven targets; for d >= 2, 2^d - 1 targets require depth at least d+1. Minimum-width threshold depths are 2, 4 and 4 for m = 2, 3 and 4; the historical DRAT evidence establishes D*_THR(5) >= 5 and the exact payload depth D*_carry(6) = 6. Version 4 is a corrective revision of version 3 (DOI: 10.5281/zenodo.22079507). It corrects the threshold ANF statement, removes an invalid causal-depth inference, specifies the fan-out hypotheses, clarifies garbage-output coherence, and distinguishes relaxed-frontier maxima from physical upper bounds. The principal depth bounds are retained. Updated manuscript sources, Python/C++ code, Colab notebooks, preserved finite-check results and an audit trail accompany this version. This revision retains the historical certification basis of v3 and does not claim a newly completed thirteen-proof DRAT audit. Large DRAT proof files are not included in these companion archives; public access to their separate dataset has not been confirmed. The documentation distinguishes historical certification, newly preserved computations and outstanding verification work. This is a preprint. No external peer-review or priority claim is made.