cyclic_latin_stable_rank_polynomial_order_three
For n = 3, any two ordering bijections a and b from Fin 3 to ZMod 3 have identical stable-matching rank polynomials: cyclic_latin_rank_polynomial 3 a = cyclic_latin_rank_polynomial 3 b.
Statement
theorem cyclic_latin_stable_rank_polynomial_order_three (a b : Fin 3 ≃ ZMod 3) :
cyclic_latin_rank_polynomial 3 a = cyclic_latin_rank_polynomial 3 b- Related work
- folklore
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- cyclic_latin_rank_polynomialGiven an order n with [NeZero n] and a bijection a : Fin n ≃ ZMod n, cyclic_latin_rank_polynomial n a is the polynomial in ℤ[X] defined by…
- is_stable_matchingIn a marriage market with agent types M and W, a matching μ : M ≃ W is stable when no man m and woman w form a blocking pair, that is,…
- cyclic_latin_rank_matchingGiven a natural number n, an ordering bijection a : Fin n ≃ ZMod n, and an index r : Fin n, cyclic_latin_rank_matching n a r is the…
- cyclic_latin_rank_matching_is_stableFor every natural number n, ordering bijection a : Fin n ≃ ZMod n, and rank r : Fin n, the matching cyclic_latin_rank_matching n a r is…
- is_blocking_pairIn a marriage market with agent types M and W and a matching μ : M ≃ W, a man m and a woman w form a blocking pair when m strictly prefers…
- cyclic_latin_rank_sumGiven an order n with [NeZero n], a bijection a : Fin n ≃ ZMod n, and a matching permutation π : Equiv.Perm (ZMod n), the aggregate…
- cyclic_latin_marketFor an ordering a of Z/nZ, the opposed cyclic Latin marriage market has men and women Z/nZ where man i ranks woman j by increasing rank…
Read back from the Lean
For any two bijections $a, b : \text{Fin } 3 \simeq \mathbb{Z}/3\mathbb{Z}$, the cyclic Latin rank polynomial of order 3 associated with $a$ is equal to the cyclic Latin rank polynomial of order 3 associated with $b$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
For order n = 3, the stable-matching rank polynomial is shown to be independent of the ordering bijection a : Fin 3 ≃ ZMod 3 by proving that it always equals the canonical polynomial ∑_{r ∈ Fin 3} X^(3r). Exhaustive computation via the decide tactic establishes that for n = 3, the stable matchings are precisely the three rank matchings, that these matchings are distinct, and that their rank sums are exactly 3r. The defining sum of the polynomial over all permutations then collapses to a sum over the rank matchings (since non-stable matchings contribute 0), which re-indexes to ∑_{r ∈ Fin 3} X^(3r); as this target is independent of a, the polynomials for any two orderings a and b coincide.
The property that a pair (m, w) blocks a matching μ in an order-3 cyclic Latin market is decidable.
Unfolding the definitions of a blocking pair and of cyclic_latin_market reduces the condition to a conjunction of strict inequalities between natural numbers. Typeclass synthesis infers decidability from the decidability of inequality on ℕ.
dsimp [is_blocking_pair, cyclic_latin_market] infer_instance
The property that a permutation μ is a stable matching in an order-3 cyclic Latin market is decidable.
Unfolding the definition of is_stable_matching expresses stability as a universal quantification over m, w : ZMod 3 of the negation of a blocking pair. Because ZMod 3 is finite and blocking pairs are decidable, typeclass inference synthesizes decidability.
dsimp [is_stable_matching] infer_instance
For n = 3, a permutation π is a stable matching under bijection a if and only if π is the rank matching for some r ∈ Fin 3. automation
Reverting the parameters a and π transforms the equivalence into a universally quantified proposition over the finite types Fin 3 ≃ ZMod 3 and Equiv.Perm (ZMod 3). The decide tactic verifies the claim by exhaustive evaluation over all cases.
revert a π decideFor n = 3, the rank sum of the rank matching at r under bijection a is 3r. automation
Reverting a and r sets up a finite identity, which the decide tactic proves by direct computation across all bijections and index choices.
revert a r decideFor n = 3, the rank matching map r ↦ cyclic_latin_rank_matching 3 a r is injective. automation
Reverting a, r₁, and r₂ reduces injectivity to a finite check, which the decide tactic verifies by exhaustion.
revert a r₁ r₂ decideThe rank polynomial is expressed as the sum ∑_{π ∈ S₃} f(π), where f(π) = X^(rank_sum(π)) if π is stable and 0 otherwise.
Unfolding cyclic_latin_rank_polynomial and defining f as the conditional summand puts the goal in the form (∑ π, f π) = ∑ r, X^(3r).
unfold cyclic_latin_rank_polynomial let f : Equiv.Perm (ZMod 3) → Polynomial ℤ := fun π => @ite (Polynomial ℤ) (is_stable_matching (cyclic_latin_market 3 a) π) (Classical.propDecidable _) ((Polynomial.X : Polynomial ℤ) ^ (cyclic_latin_rank_sum 3 a π)) 0 change (∑ π : Equiv.Perm (ZMod 3), f π) = _
The sum over all permutations restricts to the sum over the image S of the rank matchings: ∑_π f(π) = ∑_{π ∈ S} f(π).
Let S be the image of Finset.univ under cyclic_latin_rank_matching 3 a. If π ∉ S, then π cannot be stable: by cyclic_latin_stable_rank_polynomial_order_three_is_stable_iff any stable matching is a rank matching, which would place π in S by Finset.mem_image and Finset.mem_univ, a contradiction. Because π is not stable, if_neg shows f(π) = 0. Therefore, by Finset.subset_univ and Finset.sum_subset, all terms outside S vanish and the sum restricts to S.
uses
Finset.subset_univ,cyclic_latin_stable_rank_polynomial_order_three_is_stable_iff,Finset.mem_image,Finset.mem_univ,if_neg,Finset.sum_subsetlet S := Finset.univ.image (cyclic_latin_rank_matching 3 a) have h_sub : S ⊆ Finset.univ := Finset.subset_univ _ have h_zero : ∀ π ∈ Finset.univ, π ∉ S → f π = 0 := by intro π _ hπ have h_not_stable : ¬ is_stable_matching (cyclic_latin_market 3 a) π := by intro hst rw [cyclic_latin_stable_rank_polynomial_order_three_is_stable_iff] at hst rcases hst with ⟨r, hr⟩ apply hπ rw [Finset.mem_image] exact ⟨r, Finset.mem_univ _, hr.symm⟩ dsimp [f] rw [if_neg h_not_stable] have h_step1 : (∑ π : Equiv.Perm (ZMod 3), f π) = ∑ π ∈ S, f π := (Finset.sum_subset h_sub h_zero).symm rw [h_step1]
The sum over S is re-indexed as a sum over r ∈ Fin 3: ∑_{π ∈ S} f(π) = ∑_{r ∈ Fin 3} f(cyclic_latin_rank_matching 3 a r).
Injectivity of the rank matching map on Fin 3 is provided by cyclic_latin_stable_rank_polynomial_order_three_rank_matching_inj. By Finset.sum_image, the sum over the image set S re-indexes to a sum over the domain Fin 3.
uses
cyclic_latin_stable_rank_polynomial_order_three_rank_matching_inj,Finset.sum_imagehave h_inj : Set.InjOn (cyclic_latin_rank_matching 3 a) ↑(Finset.univ : Finset (Fin 3)) := by intro r₁ _ r₂ _ hr rwa [cyclic_latin_stable_rank_polynomial_order_three_rank_matching_inj] at hr rw [Finset.sum_image h_inj]
For each r ∈ Fin 3, the summand evaluates to X^(3r), showing cyclic_latin_rank_polynomial 3 a = ∑_{r ∈ Fin 3} X^(3r).
Applying Finset.sum_congr reduces the claim to comparing summands pointwise. For each r, the rank matching is stable by cyclic_latin_rank_matching_is_stable, so if_pos simplifies f to X^(rank_sum). Then cyclic_latin_stable_rank_polynomial_order_three_rank_sum_matching simplifies the exponent to 3r.
uses
Finset.sum_congr,cyclic_latin_rank_matching_is_stable,if_pos,cyclic_latin_stable_rank_polynomial_order_three_rank_sum_matchingapply Finset.sum_congr rfl intro r _ dsimp [f] have hst : is_stable_matching (cyclic_latin_market 3 a) (cyclic_latin_rank_matching 3 a r) := cyclic_latin_rank_matching_is_stable 3 a r rw [if_pos hst, cyclic_latin_stable_rank_polynomial_order_three_rank_sum_matching]
Any two ordering bijections a and b produce identical stable-matching rank polynomials.
Rewriting both sides with cyclic_latin_stable_rank_polynomial_order_three_poly_eq shows that both cyclic_latin_rank_polynomial 3 a and cyclic_latin_rank_polynomial 3 b equal the identical polynomial ∑_{r ∈ Fin 3} X^(3r).
uses
cyclic_latin_stable_rank_polynomial_order_three_poly_eqrw [cyclic_latin_stable_rank_polynomial_order_three_poly_eq a, cyclic_latin_stable_rank_polynomial_order_three_poly_eq b]
Finset.subset_univ- Every finite subset of a finite type is a subset of the universal finset.
cyclic_latin_stable_rank_polynomial_order_three_is_stable_iff- For n = 3 and ordering bijection a, a permutation π is a stable matching if and only if π equals the cyclic Latin rank matching for some r ∈ Fin 3.
Finset.mem_image- An element belongs to the image of a finset under a function if and only if it is the image of some element in the finset.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
if_neg- If a condition c is false, then the conditional expression (if c then t else e) evaluates to the else-branch e.
Finset.sum_subset- If s₁ ⊆ s₂ and the summand vanishes on s₂ \ s₁, the sum over s₁ equals the sum over s₂.
cyclic_latin_stable_rank_polynomial_order_three_rank_matching_inj- For n = 3, two rank matchings are equal if and only if their index parameters in Fin 3 are equal (the rank matching map is injective).
Finset.sum_image- Summing a function over the image of a finset under an injective map equals summing the composed function over the original finset.
Finset.sum_congr- Two finite sums are equal if their index sets are identical and their summands agree on every element of the index set.
cyclic_latin_rank_matching_is_stable- In any cyclic Latin market, every cyclic Latin rank matching is a stable matching.
if_pos- If a condition c is true, then the conditional expression (if c then t else e) evaluates to the then-branch t.
cyclic_latin_stable_rank_polynomial_order_three_rank_sum_matching- For n = 3 and ordering bijection a, the rank sum of the rank matching at index r is 3r.
cyclic_latin_stable_rank_polynomial_order_three_poly_eq- For n = 3 and any ordering bijection a, the cyclic Latin stable-matching rank polynomial equals ∑_{r ∈ Fin 3} X^(3r).
- The classification of stable matchings, the calculation of their rank sums, and the injectivity of the rank matching map for n = 3 (the three auxiliary theorems) are proved computationally by Lean's decide tactic via finite exhaustion over the 6 bijections and 6 permutations, rather than by general combinatorial arguments.
- The first two instances in the file establish Decidable instances needed by Lean to evaluate propositions involving blocking pairs and stable matchings algorithmically.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
instance cyclic_latin_stable_rank_polynomial_order_three_dec_block (a : Fin 3 ≃ ZMod 3) (m : ZMod 3) (w : ZMod 3) (μ : Equiv.Perm (ZMod 3)) : Decidable (is_blocking_pair (cyclic_latin_market 3 a) μ m w) := by dsimp [is_blocking_pair, cyclic_latin_market] infer_instanceinstance cyclic_latin_stable_rank_polynomial_order_three_dec_stable (a : Fin 3 ≃ ZMod 3) (μ : Equiv.Perm (ZMod 3)) : Decidable (is_stable_matching (cyclic_latin_market 3 a) μ) := by dsimp [is_stable_matching] infer_instancetheorem cyclic_latin_stable_rank_polynomial_order_three_is_stable_iff (a : Fin 3 ≃ ZMod 3) (π : Equiv.Perm (ZMod 3)) : is_stable_matching (cyclic_latin_market 3 a) π ↔ ∃ r : Fin 3, π = cyclic_latin_rank_matching 3 a r := by revert a π decidetheorem cyclic_latin_stable_rank_polynomial_order_three_rank_sum_matching (a : Fin 3 ≃ ZMod 3) (r : Fin 3) : cyclic_latin_rank_sum 3 a (cyclic_latin_rank_matching 3 a r) = 3 * (r : ℕ) := by revert a r decidetheorem cyclic_latin_stable_rank_polynomial_order_three_rank_matching_inj (a : Fin 3 ≃ ZMod 3) (r₁ r₂ : Fin 3) : cyclic_latin_rank_matching 3 a r₁ = cyclic_latin_rank_matching 3 a r₂ ↔ r₁ = r₂ := by revert a r₁ r₂ decidelemma cyclic_latin_stable_rank_polynomial_order_three_poly_eq (a : Fin 3 ≃ ZMod 3) : cyclic_latin_rank_polynomial 3 a = ∑ r : Fin 3, (Polynomial.X : Polynomial ℤ) ^ (3 * (r : ℕ)) := by unfold cyclic_latin_rank_polynomial let f : Equiv.Perm (ZMod 3) → Polynomial ℤ := fun π => @ite (Polynomial ℤ) (is_stable_matching (cyclic_latin_market 3 a) π) (Classical.propDecidable _) ((Polynomial.X : Polynomial ℤ) ^ (cyclic_latin_rank_sum 3 a π)) 0 change (∑ π : Equiv.Perm (ZMod 3), f π) = _ let S := Finset.univ.image (cyclic_latin_rank_matching 3 a) have h_sub : S ⊆ Finset.univ := Finset.subset_univ _ have h_zero : ∀ π ∈ Finset.univ, π ∉ S → f π = 0 := by intro π _ hπ have h_not_stable : ¬ is_stable_matching (cyclic_latin_market 3 a) π := by intro hst rw [cyclic_latin_stable_rank_polynomial_order_three_is_stable_iff] at hst rcases hst with ⟨r, hr⟩ apply hπ rw [Finset.mem_image] exact ⟨r, Finset.mem_univ _, hr.symm⟩ dsimp [f] rw [if_neg h_not_stable] have h_step1 : (∑ π : Equiv.Perm (ZMod 3), f π) = ∑ π ∈ S, f π := (Finset.sum_subset h_sub h_zero).symm rw [h_step1] have h_inj : Set.InjOn (cyclic_latin_rank_matching 3 a) ↑(Finset.univ : Finset (Fin 3)) := by intro r₁ _ r₂ _ hr rwa [cyclic_latin_stable_rank_polynomial_order_three_rank_matching_inj] at hr rw [Finset.sum_image h_inj] apply Finset.sum_congr rfl intro r _ dsimp [f] have hst : is_stable_matching (cyclic_latin_market 3 a) (cyclic_latin_rank_matching 3 a r) := cyclic_latin_rank_matching_is_stable 3 a r rw [if_pos hst, cyclic_latin_stable_rank_polynomial_order_three_rank_sum_matching]/-- OP-1351 holds for n = 3: all orderings have identical stable-matching rank polynomial. -/theorem cyclic_latin_stable_rank_polynomial_order_three (a b : Fin 3 ≃ ZMod 3) : cyclic_latin_rank_polynomial 3 a = cyclic_latin_rank_polynomial 3 b := by rw [cyclic_latin_stable_rank_polynomial_order_three_poly_eq a, cyclic_latin_stable_rank_polynomial_order_three_poly_eq b]