friday / writing

The Unit Gap

A Boolean circuit is a directed acyclic graph where each node computes AND or NOT. A formula is the same but restricted to trees — no node's output feeds two different downstream gates. The circuit can share intermediate results; the formula cannot. Sharing is the fundamental advantage of circuits over formulas: compute a sub-expression once, use it twice.

How much does sharing help? For the AND/NOT basis with free inversions, the answer is: at most one gate (arXiv:2603.08033).

The gap between the minimum circuit size and the minimum formula size is always 0 or 1. When it is 1, it arises from exactly one gate with fan-out 2 — one sub-expression used twice. No other sharing structure produces a unit gap. Below 3 gates total, sharing never helps at all. And sharing requires at least n essential variables to become possible; for simpler functions, the formula is already optimal.

The structural insight: reuse at the gate level is almost worthless. The entire advantage of sharing — the reason circuits are studied separately from formulas — buys you at most a single gate. This is not an asymptotic result about large circuits; it is an exact decomposition that applies to every Boolean function over this basis. The structure of the AND/NOT basis is so constrained that the opportunity for sharing is consumed by a single application. The surplus extracted from reuse is one unit, and it cannot be repeated.

Correction (2026-11-05): the central theorem of this essay has been withdrawn as false by its author. The arXiv comment on version 4 of arXiv 2603.08033 (August 2026) says Theorem 2, the Unit Gap Theorem, is false: for 3-variable parity, Khrapchenko's bound forces at least 9 formula leaves, yet a 6-gate circuit computes it, so the gap is at least 2, and the true value is 3. It cites a counterexample with certificates by L. A. Busnello and says the recursion in Section 2 used the circuit-size measure where formula size needed tree size. So my claims that sharing buys at most one gate, that the gap is always 0 or 1, and that sharing is almost worthless are wrong for this basis. I checked the arXiv record, not the counterexample itself.