Lemma 6.2 — every exact cover carries total weight
ProvedCountOrderings.NFree.lemma_6_2combinatoricslinear-extensionsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be an instance of #X3C with sets and , satisfying the standing assumptions (every element of lies in some set, and ). For every exact cover of ,
By Lemma 6.1 every factor here is a positive integer. The right-hand side does not depend on : each exact cover contributes the same weight to the limit of the proof of Theorem 6.3, which is what lets that limit count exact covers.
Formalization Note. Quantities as in CountOrderings.NFree.Reduction; the sum is computed in .
Differences from the source:
- generalization: a family of (distinct) 3-sets → an indexed family in which two indices may carry the same 3-set; reason: the lemma only uses indices; for distinct sets this is exactly the paper's instance.
- encoding: defined as → the linear extensions of the edge poset of ; reason: the paper proves the two sets equal on p. 16.
- encoding: the sum of reciprocals → the sum in ℝ; reason: every denominator is a positive integer (Lemma 6.1); same value.
- encoding: sets, universe elements and ordering positions numbered from 1 → zero-based Fin indices, with position p represented in rho and Ccount by p + 1 and the product index i still starting at 1; reason: bijective relabeling preserves the last i edges and every count.
Preamble
import Mathlib import Definitions.Def_CountOrderings_NFree_Reduction
Formal statement
namespace CountOrderings.NFree
theorem lemma_6_2 (I : X3CInstance) (hI : I.Standing) (X : Finset (Fin I.n))
(hX : X ∈ I.exactCovers) :
∑ σ ∈ omegaXC I X,
∏ i ∈ Finset.Icc (4 * I.h + 1) (4 * I.n), 1 / ((i : ℝ) - (Ccount σ i : ℝ)) =
((4 * I.h).factorial : ℝ) / ((4 : ℝ) ^ I.h * (3 : ℝ) ^ (I.n - I.h)) := by sorry
end CountOrderings.NFree
Source
Arenas, Schild and Subercaseaux, Hardness of Counting Orderings: Taking Gadget Amplification to the Limit, STOC 2027 submission, p. 19 (PDF p. 20), Lemma 6.2; proof in Appendix A.11, pp. 35–37 (PDF pp. 36–38)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.