Lemma 5.12 — combined coverage and normalized cost
ProvedMajorityDepthThree.Exact.combine_restrictionscircuit-complexityextremal-combinatoricsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a set system on , , and let be restrictions. For each , let index its compatible restrictions. Suppose and
For feasible residual weights , the combined weight is feasible and satisfies
Furthermore, for any real satisfying for every ,
All three conclusions are retained. The parameters are the fixed Section 5 values, and every is the actual covering minimum. This is the common statement used to combine residual budgets.
Differences from the source:
- encoding: A finite ground set V and its subsets → Finite subsets V of a variable type, with finite families of subsets; reason: Every source instance has this representation; all assignments and ambient isolated variables are retained
- encoding: Restrictions and the augmented restrictions of Note 5.3 → Disjoint positive and negative supports contained in V, plus optional clauses on unset variables; reason: An empty collection of extra clauses gives ordinary restrictions; residual families and lifted weights use strong consistency, while compatibility remains weaker
- encoding: Indices 1 through k → Fin k; reason: This changes only index names; the empty sum is allowed
Preamble
import Definitions.Def_MajorityDepthThree_Exact_Restrictions import Definitions.Def_MajorityDepthThree_Exact_Circuits set_option autoImplicit false open scoped Classical
Formal statement
namespace MajorityDepthThree.Exact
theorem combine_restrictions {α : Type} [DecidableEq α] (V : Finset α)
(A : Family α) (hA : ∀ S ∈ A, S ⊆ V) (k : ℕ)
(ρ : Fin k → Restriction V) (coeff : Fin k → ℝ)
(hcoeff : ∀ i, 0 ≤ coeff i)
(hc : ∀ S ∈ A,
1 ≤ ∑ i ∈ Finset.univ.filter (fun i => Compatible A (ρ i) S),
coeff i * q ^ (S ∩ (ρ i).neg).card)
(f : Fin k → Weight α) (hf : ∀ i, CoverFeasible (residual A (ρ i)) q (f i)) :
CoverFeasible A q (combinedWeight ρ coeff f) ∧
cost A r (combinedWeight ρ coeff f) =
∑ i, coeff i * r ^ (ρ i).pos.card * cost (residual A (ρ i)) r (f i) ∧
∀ omega : Fin k → ℝ,
(∀ i, coverValue (residual A (ρ i)) r q ≤ omega i * p ^ (V.card - (ρ i).support.card)) →
coverValue A r q / p ^ V.card ≤
∑ i, coeff i * omega i * r ^ (ρ i).pos.card / p ^ (ρ i).support.card ∧
(∑ i, coeff i * omega i * r ^ (ρ i).pos.card / p ^ (ρ i).support.card) =
∑ i, coeff i * omega i * (2 : ℝ) ^ (-((ρ i).pos.card : ℤ)) * q ^ (ρ i).neg.card := by sorry
end MajorityDepthThree.Exact
Source
Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher Rosin, Michael Saks, Navid Talebanfard, STOC 2027 submission #677 (October 2026), p.14, Lemma 5.12 (proof continues p.15)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.