Lemma 6.1 — exact-cover orderings are exactly those with on
ProvedCountOrderings.NFree.lemma_6_1combinatoricslinear-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 ). Let . Then:
- If for some exact cover , then
- If induces no exact cover, then the set is non-empty.
In the proof of Theorem 6.3, a factor of vanishes at exactly when ; the lemma says that has a pole of order at exactly for the orderings that induce an exact cover, and of smaller order otherwise.
Formalization Note. Quantities as in CountOrderings.NFree.Reduction; " induces no exact cover" is "there is no with ".
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: 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_1 (I : X3CInstance) (hI : I.Standing) (σ : Fin (4 * I.n) ≃ OrigEdge I)
(hσ : σ ∈ omegaLE I) :
(∀ X ∈ I.exactCovers, σ ∈ omegaXC I X →
(∀ i ∈ Finset.Icc 1 (4 * I.h), Ccount σ i = i) ∧
∀ i ∈ Finset.Icc (4 * I.h + 1) (4 * I.n), Ccount σ i < i) ∧
((¬ ∃ X ∈ I.exactCovers, σ ∈ omegaXC I X) →
((Finset.Icc 1 (4 * I.h)).filter (fun i => Ccount σ i < i)).Nonempty) := by sorry
end CountOrderings.NFree
Source
Arenas, Schild and Subercaseaux, Hardness of Counting Orderings: Taking Gadget Amplification to the Limit, STOC 2027 submission, p. 18 (PDF p. 19), Lemma 6.1; proof in Appendix A.10, p. 35 (PDF p. 36)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.