AFTD Auto-Formalizing Theoretical Domains

cyclic_latin_stable_rank_polynomial_order_three

theoremverifiedoriginal

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.

  1. 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 ℕ.

    lines 4–5

      dsimp [is_blocking_pair, cyclic_latin_market]
      infer_instance
  2. 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.

    lines 10–11

      dsimp [is_stable_matching]
      infer_instance
  3. 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.

    lines 17–18

      revert a π
      decide
  4. For 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.

    lines 23–24

      revert a r
      decide
  5. For 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.

    lines 29–30

      revert a r₁ r₂
      decide
  6. The 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).

    lines 34–40

      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 π) = _
  7. 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.

    lines 41–55

    uses Finset.subset_univ, cyclic_latin_stable_rank_polynomial_order_three_is_stable_iff, Finset.mem_image, Finset.mem_univ, if_neg, Finset.sum_subset

      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]
  8. 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.

    lines 56–59

    uses cyclic_latin_stable_rank_polynomial_order_three_rank_matching_inj, Finset.sum_image

      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]
  9. 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.

    lines 60–65

    uses Finset.sum_congr, cyclic_latin_rank_matching_is_stable, if_pos, cyclic_latin_stable_rank_polynomial_order_three_rank_sum_matching

      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]
  10. 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).

    lines 70–71

    uses cyclic_latin_stable_rank_polynomial_order_three_poly_eq

      rw [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).

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

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]
See it in the graphDiscuss this resultChallenge it