Fact 4.2 — Deleting small blocks preserves assignment
ProvedPermanentStars.Counting.fact_4_2algebraic-complexitydynamic-programmingp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1permanent
Fix valid positive cutoffs and rational fractions as in Definition 4.1, and assume every partition of has an admissible cutoff. Let partition any subset of , fix , and set . Then
Both assignments use the ambient . This identifies the assignment test needed when the deferred large blocks are formed.
Differences from the source:
- encoding: largest admissible cutoff on the covered domain → Option-valued assignment, with none on uncovered inputs; reason: the standing coverage hypothesis ensures that no relevant partition uses the default case
- encoding: partitions of subsets of [n] → Mathlib Finpartition of subsets of Fin n; reason: shifting labels preserves all blocks, cardinalities and the ambient n
Preamble
import Definitions.Def_PermanentStars_Counting_Partitions
Formal statement
namespace PermanentStars.Counting
/-- Fact 4.2, p.9, including the standing coverage assumption of Definition 4.1. -/
theorem fact_4_2 (P : Cutoffs) (hP : P.Valid) (n : ℕ) (coverage : Covers P n)
(S : Finset (Fin n)) (pi : Finpartition S) (r : ℕ) (hr : r ∈ P.R) :
assigned P n pi.parts = some r ↔
assigned P n (pi.parts.filter (fun B => r < B.card)) = some r := by sorry
end PermanentStars.Counting
Source
Radu Curticapean, STOC 2027 submission #1331 (October 2026), Fact 4.2, PDF/printed p.9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.