AFTD Auto-Formalizing Theoretical Domains

cyclic_latin_rank_polynomial

def

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

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