pmms3c_verify
def
Checks a violation certificate w = i + 3j + 9T for allocation σ: i ≠ j, the bitmask T lies inside X_i ∪ X_j, and both T and (X_i ∪ X_j) \ T cost agent i strictly less than X_i.
Statement
def pmms3c_verify (σ : Fin 9 → Fin 3) (w : ℕ) : Bool- Source
- step towards pmms_chores_three_agents_may_not_exist (three-agent chores PMMS, not posed in arXiv:2609.10493) (violation-certificate machinery and instance data)
- Verified
- 26 Oct 2026
- Axioms
- none listed
- Built on 2
- pmms3c_agent_ofThe agent w mod 3.
- pmms3c_cost_natThe cost to agent i of the set of chores {g : P g}, as a natural number.
- Used by 29
- pmms3c_check_022Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 0, 2, 2.
- pmms3c_check_122Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 1, 2, 2.
- pmms3c_check_200Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 2, 0, 0.
- pmms3c_checkEvery one of the 3^9 allocations passes the certificate check.
- pmms3c_verify_soundIf the certificate check accepts w for allocation σ, then σ is not PMMS for agent w mod 3.
- pmms3c_check_220Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 2, 2, 0.
- pmms3c_check_002Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 0, 0, 2.
- pmms3c_check_011Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 0, 1, 1.
- pmms3c_check_020Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 0, 2, 0.
- pmms3c_check_010Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 0, 1, 0.
- pmms3c_check_210Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 2, 1, 0.
- pmms3c_check_211Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 2, 1, 1.
- pmms3c_check_001Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 0, 0, 1.
- pmms3c_check_111Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 1, 1, 1.
- pmms3c_check_120Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 1, 2, 0.
- pmms3c_check_112Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 1, 1, 2.
- pmms3c_check_121Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 1, 2, 1.
- pmms3c_check_202Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 2, 0, 2.
- pmms3c_check_201Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 2, 0, 1.
- pmms3c_check_021Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 0, 2, 1.
- pmms3c_check_110Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 1, 1, 0.
- pmms3c_check_100Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 1, 0, 0.
- pmms3c_check_102Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 1, 0, 2.
- pmms3c_check_212Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 2, 1, 2.
- pmms3c_check_222Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 2, 2, 2.
- pmms3c_check_101Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 1, 0, 1.
- pmms3c_check_221Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 2, 2, 1.
- pmms3c_check_000Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 0, 0, 0.
- pmms3c_check_012Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 0, 1, 2.
Lean source view module on GitHub
/-- Certificate check: `w = i + 3 j + 9 T` with `T` a bitmask inside `X_i ∪ X_j` whose two parts both cost agent `i` strictly less than her own bundle. -/ def pmms3c_verify (σ : Fin 9 → Fin 3) (w : ℕ) : Bool := let i := pmms3c_agent_of w let j := pmms3c_agent_of (w / 3) let m := w / 9 decide (i ≠ j) && (List.finRange 9).all (fun g => !(m.testBit g) || σ g == i || σ g == j) && decide (max (pmms3c_cost_nat i fun g => m.testBit g) (pmms3c_cost_nat i fun g => (σ g == i || σ g == j) && !(m.testBit g)) < pmms3c_cost_nat i fun g => σ g == i)