The (4 - ε) n lower bound #
Assembling the cut-counting lemma, the wiring graph, and the proved cubic
bisection and pathwidth bounds gives the circuit lower bound. A K-rectangle-free function with
at least 2 ^ (n - 2) accepting inputs and log₂ K = o(n) needs more than
(4 - ε) n gates over the full binary basis, for every ε > 0 and all
sufficiently large n. Polynomial thresholds are a special case.
eventually_lt_size_of_rectangleFree has no graph hypothesis. Its remaining
application obligation is a family f n with log₂ K(n) = o(n) satisfying
RectangleFree and the accepting-input bound. The downstream module
Extractor.SourceReduction.Construction.Hardness supplies a concrete uniform
polynomial-time family and proves its unconditional coefficient-four lower bound.
The counting argument is generic in the graph-ordering coefficient: with
Multigraph.OrderingBound A η C for every slack η > 0, where A > 0, the
circuit coefficient is 1 + 1/A (eventually_lt_size_of_orderingBound, with
fixed-n core lt_size_of_orderingBound and numeric core
false_of_accepting_bound_of_log_coefficient). A cubic cutwidth or pathwidth
bound with coefficient c gives A = 2 c and hence 1 + 1/(2c)
(eventually_lt_size_of_cutwidthBound,
eventually_lt_size_of_pathwidthCoefficient). The proved Monien–Preis and
Fomin–Høie bounds give c = 1/6, A = 1/3, and the coefficient four.
The coefficient-four graph-ordering interface remains
eventually_lt_size_of_log_sublinear, with fixed-n core
lt_size_of_log_bounds. The original eventually_lt_size and
lt_size_of_bounds specialize these to polynomial thresholds.
The proof organization, the threshold-edge charging, the application of a sumset extractor as the hard family, and the merge-tree restoration argument follow Ryan Williams's private working note A (4 − ε)n lower bound for Boolean circuits (September 2026), which uses the circuit-to-read-once compiler of the author's counting note. The formalization is the author's.
Increasing the total coefficient A + η or the additive constant weakens
the ordering hypothesis.
The coefficient-four ordering hypothesis from a cubic pathwidth bound with
coefficient 1/6 at every positive slack.
The graph-ordering hypothesis with coefficient 1/3. It follows from
the proved Fomin–Høie cubic pathwidth bound.
A rectangle-free function with many accepting inputs cannot ignore
⌈log₂ K⌉ coordinates.
The circuit-level bound: for a circuit with output gate out, either the
final past set is small, so that fewer than K · 2 ^ (n - n') inputs are
accepted, or the accepted inputs are bounded through the ordering hypothesis.
Here n' is the number of inputs with a path to the output.
The numeric core with a general ordering coefficient. Let A > 0
be the ordering coefficient, θ ≤ 1/A the circuit slack, and
0 ≤ η ≤ A² θ / 2 the ordering slack. A K-rectangle-free function with at
least 2 ^ (n - 2) accepting inputs cannot satisfy the accepting-input bound
of the cut-counting lemma for a circuit with s ≤ (1 + 1/A - θ) n gates
reading n' inputs, when n - n' < ⌈log₂ K⌉, the wiring graph has at most
M n vertices, and n is large enough. The bound is taken as a hypothesis so
that the deterministic and nondeterministic assemblies share this argument.
The numeric core. A K-rectangle-free function with at least
2 ^ (n - 2) accepting inputs cannot satisfy the accepting-input bound of
the cut-counting lemma for a circuit with s ≤ (4 - 18 η) n gates reading
n' inputs, when n - n' < ⌈log₂ K⌉ and n is large enough. This is the
general core at coefficient A = 1/3 with θ = 18 η.
The polynomial-threshold numeric core follows from the logarithmic core; this preserves the original deterministic and nondeterministic interface.
The fixed-n core with a general ordering coefficient. With the
graph-ordering hypothesis for coefficient A > 0 and slack 0 ≤ η ≤ A² θ / 2,
where θ ≤ 1/A, a K-rectangle-free function with at least 2 ^ (n - 2)
accepting inputs needs more than (1 + 1/A - θ) n binary gates, provided its
threshold and the logarithmic overhead satisfy the stated numeric conditions.
The fixed-n core of the lower bound. With the graph-ordering
hypothesis for slack η ≤ 1/18, a K-rectangle-free function with at least
2 ^ (n - 2) accepting inputs needs more than (4 - 18 η) n binary gates,
provided its threshold and the logarithmic overhead satisfy the stated
numeric conditions. No polynomial-threshold assumption is needed.
The original polynomial-threshold circuit bound, obtained by bounding
the logarithm of the threshold in lt_size_of_log_bounds.
A sublinear logarithmic threshold eventually satisfies the finite square bound needed to recover almost all input coordinates.
A subexponential threshold fits in either half of the input cube for all sufficiently large input lengths.
Slack selection for the general asymptotic bounds. Given the
graph-ordering hypothesis with coefficient A > 0 at every positive slack, a
threshold with log₂ K(n) = o(n), and ε > 0, some circuit slack
θ ≤ min(ε, 1/A), ordering slack η, and constant C ≥ 0 satisfy the
hypotheses of the general fixed-n cores, and their logarithmic condition
holds for all sufficiently large n.
The circuit bound with a general ordering coefficient. Assume the
graph-ordering hypothesis with coefficient A > 0 for every slack η > 0,
and a family f n that is K n-rectangle-free with log₂ K(n) = o(n) and
has at least 2 ^ (n - 2) accepting inputs for all large n. Then for every
ε > 0 and all sufficiently large n, every binary circuit computing f n
has more than (1 + 1/A - ε) n gates.
The circuit bound from a cubic cutwidth bound. If for every slack
ξ > 0 all sufficiently large simple cubic graphs on h vertices have
orderings whose prefix cuts have at most (c + ξ) h edges, then the
hypotheses of eventually_lt_size_of_orderingBound give more than
(1 + 1/(2c) - ε) n gates.
The circuit bound from a cubic pathwidth bound with coefficient p.
If for every slack ξ > 0 all sufficiently large simple cubic graphs on h
vertices have path decompositions of width at most (p + ξ) h, then the
hypotheses of eventually_lt_size_of_orderingBound give more than
(1 + 1/(2p) - ε) n gates.
Subexponential-threshold circuit bound. The coefficient four only
needs log₂ K(n) = o(n); the threshold itself need not be polynomial.
The graph-ordering theorem and the hard-family properties are still explicit
hypotheses. This is eventually_lt_size_of_orderingBound at A = 1/3.
Theorem 1. Assume the graph-ordering lemma for every slack η > 0 and
a family of functions f n that is K n-rectangle-free with K n ≤ n ^ c
and at least 2 ^ (n - 2) accepting inputs, for all large n. Then for every
ε > 0 and all sufficiently large n, every binary circuit computing f n
has more than (4 - ε) n gates.
The subexponential-threshold lower bound from the cubic pathwidth theorem.
The coefficient-four lower bound with only the cubic bisection theorem and the hard-family properties as hypotheses. The pathwidth reduction is proved.
Theorem 1 from the pathwidth hypothesis. The graph-ordering hypothesis
is replaced by the pathwidth bound for simple cubic graphs: for every ξ > 0
there is a threshold beyond which every simple 3-regular graph on h
vertices has a path decomposition of width at most (1/6 + ξ) h.
A dense rectangle-free family with sublinear logarithmic threshold has the coefficient-four circuit lower bound. The graph bounds are proved; only the stated hard-family properties remain to be supplied.