Theorem 7.4 -- Boolean arity-elimination overhead
OpenCoRSuccGap.Supplement.theorem_7_4calculus-of-relationscircuit-lower-boundsfinite-variable-logicp2o-gran-per-chapterp2o-plan-paperp2o-v1succinctness
Let . Over the Boolean semiring, every typed matrix circuit computing on all finite nonempty inputs satisfies the sharper bound
The circuit model includes arbitrary uniform entrywise functions and arbitrary fixed aggregation kernels ; kernels need not be associative, monotone or zero-preserving. All non-aggregation operations, vector inner products and singleton-index contractions remain uncharged.
Differences from the source:
- encoding: the Boolean semiring is written abstractly → Lean realizes it as the powerset semiring of a singleton, with union and set product; reason: this is a two-element commutative idempotent semiring isomorphic to .
Preamble
import Definitions.Def_CoRSuccGap_Supplement_TypedMatrixCircuit set_option autoImplicit false
Formal statement
namespace CoRSuccGap
namespace Supplement
/-- **Theorem 7.4 (Boolean arity-elimination overhead).** Uezato--Nakamura,
*An Exponential Succinctness Gap between Three-Variable Logic and the Calculus of Relations*,
arXiv:2609.26778 (held version, sha256 5ad6337d…c9b6), Theorem 7.4, p.43 (PDF 45).
Over the Boolean semiring, every typed matrix circuit computing `G_k` on every finite nonempty
input satisfies `#mv + 2 #mm ≥ 2^k`. `TypedMatrixCircuit` permits arbitrary uniform entrywise
functions and an arbitrary fixed binary kernel at each contraction gate; neither is required to be
associative, monotone, or zero-preserving. -/
theorem theorem_7_4 (k : ℕ) (hk : 1 ≤ k) (C : TypedMatrixCircuit BoolSemiring k)
(hC : C.ComputesGk) :
2 ^ k ≤ C.numMV + 2 * C.numMM := by sorry
end Supplement
end CoRSuccGap
Source
Uezato--Nakamura, arXiv:2609.26778 (held version, sha256 5ad6337d...), Theorem 7.4, p.43 (PDF 45)