Theorem 4.1 -- test--cost theorem
OpenCoRSuccGap.Supplement.theorem_4_1Let and fix a test system with . If a deterministic circuit is correct at both observations of every test, then
Let one circuit be sampled from an input-independent probability distribution. If each reference or folded observation in every test is incorrect with probability at most , where , then
The same sampled circuit is used on both structures of a test and no independence among tests or errors is required. This is the abstract counting principle behind the later relational and matrix lower bounds.
Formalization Note Expected cost is a nonnegative Lebesgue integral in , so an infinite expectation remains infinite instead of receiving a default value. The cost random variable and both error events are explicitly required to be measurable.
Differences from the source:
- encoding: the source treats a circuit over the permitted operations as semantically evaluated by definition → Lean stores its reference and folded gate values and restricts to the subtype satisfying
TestCircuit.Valid; reason:Validsays exactly that the stored values are obtained gate-by-gate from the labels, so this changes no circuit instance. - encoding: the source writes an ordinary expectation of the finite circuit cost → Lean uses the nonnegative extended-real integral; reason: this preserves the same finite expectations and also gives the intended value for an unbounded input-independent distribution.
- encoding: the source uses probabilities and expectation without spelling out measurability → Lean explicitly requires the two error events and the cost random variable to be measurable; reason: these are exactly the well-posedness conditions implicit in the source's probability notation.
import Definitions.Def_CoRSuccGap_Supplement_TestSystem set_option autoImplicit false open MeasureTheory
namespace CoRSuccGap
namespace Supplement
/-- **Theorem 4.1 (Test--cost theorem).** Uezato--Nakamura, *An Exponential Succinctness Gap
between Three-Variable Logic and the Calculus of Relations*, arXiv:2609.26778 (held version,
sha256 5ad6337d…c9b6), Theorem 4.1, p.24 (PDF 26).
For a test system with `2^k` tests, a deterministic circuit correct at the reference and folded
observation of every test has cost at least `2^k`. For one input-independent probability
distribution of valid circuits, if each of the two observations of each test is wrong with
probability at most `ε < 1/2`, then expected cost is at least `(1-2ε)2^k`.
**Formalization Note.** The expectation is a nonnegative Lebesgue integral in `ℝ≥0∞`, avoiding the
Bochner convention that assigns zero to a nonintegrable function. Measurability of the cost and
error events is stated explicitly. The same measure and the same sampled circuit are used for both
observations of every test; no independence is assumed. -/
theorem theorem_4_1 (k : ℕ) (hk : 1 ≤ k) (S : TestSystem k) :
(∀ C : TestCircuit S, C.Valid → C.Correct → 2 ^ k ≤ C.cost) ∧
(∀ ε : ℝ, 0 ≤ ε → ε < 1 / 2 →
∀ [MeasurableSpace {C : TestCircuit S // C.Valid}]
(μ : Measure {C : TestCircuit S // C.Valid}), IsProbabilityMeasure μ →
Measurable (fun C : {C : TestCircuit S // C.Valid} => (C.val.cost : ENNReal)) →
(∀ lam : S.Palette,
MeasurableSet {C : {C : TestCircuit S // C.Valid} | ¬ C.1.CorrectBase lam} ∧
MeasurableSet {C : {C : TestCircuit S // C.Valid} | ¬ C.1.CorrectFold lam} ∧
μ {C : {C : TestCircuit S // C.Valid} | ¬ C.1.CorrectBase lam} ≤ ENNReal.ofReal ε ∧
μ {C : {C : TestCircuit S // C.Valid} | ¬ C.1.CorrectFold lam} ≤ ENNReal.ofReal ε) →
ENNReal.ofReal ((1 - 2 * ε) * (2 ^ k : ℝ)) ≤
MeasureTheory.lintegral μ
(fun C : {C : TestCircuit S // C.Valid} => (C.val.cost : ENNReal))) := by sorry
end Supplement
end CoRSuccGap