Forced Multiple Reconvergence at Unit Gap
Krinkin's Theorem 7 asserts that when the minimum formula size of a Boolean function exceeds its minimum circuit size by exactly one gate, the sharing responsible is a single fan-out-two gate, and that no other sharing structure produces a unit gap. The per-gate dichotomy it rests on holds; the uniqueness does not. There are functions for which every size-optimal And-Inverter Graph carries at least two reconvergent gates. For those functions a single reconvergence is impossible, which is a stronger failure than non-uniqueness. We call them forced-multiple-reconvergence, and each is certified by one unsatisfiability result that quantifies over every encoded optimum rather than by exhibiting circuits; that the encoding reaches every size-optimal circuit is a prose argument, the only one of its kind here (§4.2). At n = 4 there are exactly six such NPN classes, established exhaustively. A closure theorem, machine-checked in Lean 4 and corroborated independently by certificates at n = 4 and 5, and only partially at n = 6, shows that conjoining or disjoining a fresh variable preserves both the unit gap and the forcedness, so the family is non-empty at every n ≥ 4. Its inductive step is proved from the kernel axioms alone; the n = 4 base it stands on is the one place a compiled decision procedure enters the trust base, and that base carries an independent unsatisfiability certificate outside the proof assistant. Reading the formal result in the paper's designated-output convention, forcedness included, takes one short paper argument (§5.5), the single modelling step not checked by machine. At n = 5 the family is strictly richer than that closure: at least 85 classes, of which eleven lie in the closure of the six and 74 do not, which refutes the natural conjecture that the family is its own lift tower and nothing more. Counting that closure rather than applying it reaches one arity further. The two lift directions of a seed coincide exactly when the seed is NP-self-complementary (equivalent to its dual under permutation and negation of inputs alone), and lifting the established classes at n = 5 gives F₆ ≥ 167, a bound obtained without deciding any instance at an arity where a census is beyond the solver's reach. The projection is from the decision curve measured over the 222 classes of n = 4 in §7½, not from a measurement at n = 6, and §5.10 carries an n = 6 instance whose lower-bound legs are certified as far as k = 4, to show that individual instances there can decide. A sibling construction, which absorbs the fresh variable into a term with an existing one rather than conjoining it, separates the two properties the closure theorem preserves together. Its gap behaviour is all-or-nothing: across the 8592 applications to essential 3-variable seeds whose result is 4-essential, the result's gap is either the seed's or zero, never intermediate and never larger. At the arity that matters it decides both ways, since of eighteen constructions on the six n = 4 seeds, eleven keep the unit gap and seven collapse it. Whether forcedness survives depends on the construction as well as the seed: on those eighteen the split fell by seed, but each seed admits sixteen ways of attaching the fresh variable, and over all ninety-six constructions six of the six seeds yield both outcomes, and for five of them every class reached inside the family is certified on every leg. The sixth is 0x07bc. So this is a weaker closure rather than a counterexample to closure, and the eighteen-construction sweep supplies two of the 74 classes outside the lift tower. Which property of the pair decides is open. The family is rare, within the limits of what the rarity measurement can support: a biased census of 5-variable functions yields a single forced class among the independent gap-one candidates it produced, and that yield is not a density. Every count above traces to a committed artefact, every unsatisfiability step behind a counted class to a DRAT proof checked by drat-trim (for four classes at opt = 10, to 2,400 checked cube proofs whose cover is verified by script), and no headline claim depends on the symmetry-breaking lemma the encoder can optionally use. Single-author preprint. The machine-checkable artefacts (DRAT proofs, Lean sources, census files) are in the unit-gap artefact deposit, doi:10.5281/zenodo.21630762.
Authors
- Luiz Antonio Busnello (ORCID: https://orcid.org/0009-0007-5911-8141)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-20
- DOI
- https://doi.org/10.5281/zenodo.24408786
- Citations
- 1
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint