Lemma 5.2 — Counting subsets with a forced prefix
ProvedPermanentStars.Counting.lemma_5_2algebraic-complexitydynamic-programmingp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1permanent
Let and be integers, and let be real with and . For , let be the largest initial-segment length contained in . Then
The empty subset and the full prefix are included. This bounds the covered-set choices of the small-star dynamic program.
Differences from the source:
- encoding: cardinality bars around the subset family in (19) → Finset.card of all subsets satisfying the prefix condition; reason: finite subsets of Fin N represent exactly the source family; the PDF already displays cardinality bars, which the text extraction loses
- encoding: initial segment [p] → indices i in Fin N with i.val<p; reason: this is the same ordered prefix after shifting indices by one
Preamble
import Definitions.Def_PermanentStars_Counting_Partitions
Formal statement
namespace PermanentStars.Counting
/-- Lemma 5.2, (19), p.10; braces are a cardinality, as in its counting proof. -/
theorem lemma_5_2 (N r : ℕ) (hr : 1 ≤ r) (c : ℝ)
(hc : 1 < c) (hc2 : c < 2) (hprod : 1 ≤ c * (c - 1) ^ (r - 1)) :
(prefixCount N r : ℝ) ≤ (N + 1 : ℝ) * c ^ N := by sorry
end PermanentStars.Counting
Source
Radu Curticapean, STOC 2027 submission #1331 (October 2026), Lemma 5.2, PDF/printed p.10
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.