Theorem 1.4 -- exponential quantifier lower bound from to
OpenCoRSuccGap.Supplement.theorem_1_4calculus-of-relationscircuit-lower-boundsfinite-variable-logicp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1succinctness
Let . Every unrestricted formula whose binary assignment relation agrees with on every finite nonempty structure has at least
existential or universal quantifier occurrences. The count is total occurrences, not quantifier depth, relation atoms or total syntax nodes.
This is the exact lower bound: the paper's displayed expansion uses quantifiers.
Differences from the source:
- generalization: means agreement on every nonempty structure → Lean assumes agreement only on every finite nonempty structure; reason: the paper explicitly states that its proof gives this stronger finite-structure form on p.33.
Preamble
import Definitions.Def_CoRSuccGap_Gk import Definitions.Def_CoRSuccGap_Supplement_FiniteVariableLogic set_option autoImplicit false
Formal statement
namespace CoRSuccGap
namespace Supplement
/-- **Theorem 1.4 (Exponential lower bound from FO³ to FO²).** 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.4, p.32 (PDF 34).
For every `k ≥ 1`, an unrestricted FO² formula over `P₁,…,Pₖ,Q₁,…,Qₖ` whose binary
assignment relation agrees with `G_k` on every finite nonempty structure contains at least `2^k`
existential or universal quantifier occurrences. -/
theorem theorem_1_4 (k : ℕ) (hk : 1 ≤ k) (p : FOFormula (GSym k) (Fin 2))
(hagree : ∀ (D : Type) [Fintype D] [Nonempty D]
(M : GSym k → D → D → Prop), p.query2 M = Gk k M) :
2 ^ k ≤ p.numQuantifiers := by sorry
end Supplement
end CoRSuccGap
Source
Uezato--Nakamura, arXiv:2609.26778 (held version, sha256 5ad6337d...), Theorem 1.4, p.32 (PDF 34), finite-structure strengthening p.33 (PDF 35)