cyclic_latin_rank_polynomial
Given 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 the sum over all matching permutations π : Equiv.Perm (ZMod n) of (if is_stable_matching (cyclic_latin_market n a) π then (Polynomial.X : Polynomial ℤ) ^ (cyclic_latin_rank_sum n a π) else 0).
Statement
noncomputable def cyclic_latin_rank_polynomial (n : ℕ) [NeZero n] (a : Fin n ≃ ZMod n) : Polynomial ℤ
- Defined in
- OP-1351
- Verified
- 10 Nov 2026
- Axioms
- none listed
- Built on 3
- 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…
- 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…
- 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,…
- Used by 1
- cyclic_latin_stable_rank_polynomial_order_threeFor n = 3, any two ordering bijections a and b from Fin 3 to ZMod 3 have identical stable-matching rank polynomials:…
Read back from the Lean
Given a non-zero natural number $n$ and a bijection $a : \text{Fin } n \simeq \mathbb{Z}/n\mathbb{Z}$, cyclic_latin_rank_polynomial n a is the polynomial in $\mathbb{Z}[X]$ defined as the sum over all permutations $\pi \in \operatorname{Perm}(\mathbb{Z}/n\mathbb{Z})$ of:
- $X^{\text{cyclic\_latin\_rank\_sum}(n, a, \pi)}$ if $\pi$ is a stable matching in the marriage market cyclic_latin_market n a;
- $0$ otherwise.
Here:
1. The rank sum of $\pi$ is $\sum_{i \in \mathbb{Z}/n\mathbb{Z}} (a^{-1}(i + \pi(i)) : \mathbb{N})$.
2. The marriage market has men $\mathbb{Z}/n\mathbb{Z}$ and women $\mathbb{Z}/n\mathbb{Z}$. Man $i$ prefers woman $j$ to $j'$ iff $(a^{-1}(i + j) : \mathbb{N}) < (a^{-1}(i + j') : \mathbb{N})$. Woman $j$ prefers man $i$ to $i'$ iff $(a^{-1}(i' + j) : \mathbb{N}) < (a^{-1}(i + j) : \mathbb{N})$.
3. $\pi$ is a stable matching if there is no blocking pair $(m, w) \in \mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$, meaning there is no pair $(m, w)$ where $m$ prefers $w$ to $\pi(m)$ and $w$ prefers $m$ to $\pi^{-1}(w)$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Stable-matching proposer rank polynomial F_a(z) of cyclic Latin market a. -/ noncomputable def cyclic_latin_rank_polynomial (n : ℕ) [NeZero n] (a : Fin n ≃ ZMod n) : Polynomial ℤ := open scoped Classical BigOperators in ∑ π : Equiv.Perm (ZMod n), if is_stable_matching (cyclic_latin_market n a) π then (Polynomial.X : Polynomial ℤ) ^ (cyclic_latin_rank_sum n a π) else 0