Theorem 1.6 -- tropical arity-elimination overhead
OpenCoRSuccGap.Supplement.theorem_1_6calculus-of-relationscircuit-lower-boundsfinite-variable-logicp2o-gran-per-chapterp2o-plan-paperp2o-v1succinctness
For every and for each of the min--plus semirings
the query has an expression of size , but every typed matrix circuit computing it on all finite nonempty inputs satisfies
In both semirings, addition is minimum, multiplication is ordinary addition, semiring zero is , and semiring one is .
Differences from the source:
- encoding: the source quantifies → Lean states a conjunction for Mathlib's two tropical carrier types; reason: type-valued finite-set membership is represented by the two exhaustive cases.
- encoding: the source uses → Lean uses a positive linear constant chosen before for each of the two fixed semirings; reason: explicit asymptotic quantifiers.
Preamble
import Definitions.Def_CoRSuccGap_Supplement_TypedMatrixCircuit set_option autoImplicit false
Formal statement
namespace CoRSuccGap
namespace Supplement
/-- **Theorem 1.6 (Tropical 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 1.6, p.42 (PDF 44).
For both the natural and integer min--plus semirings, `G_k` has a positive ARA(3) expression of
size `O(k)`, while every typed matrix circuit computing it on all finite nonempty inputs satisfies
`#mv + 3 #mm ≥ 2^k`. The two conjuncts below state the result separately for
`ℕ∪{+∞}` and `ℤ∪{+∞}` with tropical addition `min` and multiplication ordinary addition. -/
theorem theorem_1_6 :
(∃ c : ℕ, 0 < c ∧ ∀ k : ℕ, 1 ≤ k →
(∃ e : ARA3Expr (GSym k), ARA3RepresentsGk TropNat k e ∧ e.numNodes ≤ c * k) ∧
∀ C : TypedMatrixCircuit TropNat k, C.ComputesGk →
2 ^ k ≤ C.numMV + 3 * C.numMM) ∧
(∃ c : ℕ, 0 < c ∧ ∀ k : ℕ, 1 ≤ k →
(∃ e : ARA3Expr (GSym k), ARA3RepresentsGk TropInt k e ∧ e.numNodes ≤ c * k) ∧
∀ C : TypedMatrixCircuit TropInt k, C.ComputesGk →
2 ^ k ≤ C.numMV + 3 * C.numMM) := by sorry
end Supplement
end CoRSuccGap
Source
Uezato--Nakamura, arXiv:2609.26778 (held version, sha256 5ad6337d...), Theorem 1.6, p.42 (PDF 44)