RowProtocolSolves
A protocol p : RowLocalView (Fin S) → α solves the anonymous-slip puzzle for S sages in a row with 2 ≤ S without seat labels if for every sage x : Fin S and all seatings π₁ π₂ : Equiv.Perm (Fin S) such that rowViewOfSage hS π₁ x = rowViewOfSage hS π₂ x, if rowMultiset hS p π₁ = rowMultiset hS p π₂ then π₁ = π₂.
Statement
def RowProtocolSolves (S : ℕ) {α : Type*} (hS : 2 ≤ S) (p : RowLocalView (Fin S) → α) : Prop
- Defined in
- arXiv:2610.33032:180
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Built on 4
- RowLocalViewFor sages of type α, a local view in an unlabeled row consists of the sage's own identity together with an optional left neighbor and an…
- rowViewGiven a row seating of S sages represented as a permutation π with 2 ≤ S, the local view at position i is the sage π i along with their…
- rowViewOfSageThe local view of sage x in a row seating π is the local view at the position π.symm x occupied by x.
- rowMultisetGiven a hypothesis 2 ≤ S, the public multiset of values produced by a protocol p : RowLocalView (Fin S) → α on a row seating π :…
- Used by 4
- row_solvable_monoIf the anonymous-slip puzzle for S sages in a row with unlabeled seats is solvable with n symbols (RowProblemSolvable S n hS), then it is…
- row_protocol_solves_of_injectiveIf a protocol with announcements in α solves the row puzzle, then composing it with any injective map α → β gives a protocol with…
- RowProblemSolvableThe anonymous-slip puzzle for S sages in a row with n symbols and unlabeled seats (with 2 ≤ S) is solvable if there exists a protocol p :…
- sages_row_upper_bound_binomialFor every integer S ≥ 3, the anonymous-slip puzzle for S sages in a row with unlabeled seats can be solved using Nat.choose S 2 symbols.
Read back from the Lean
For a natural number S with 2 ≤ S, a type α, and a protocol function p : RowLocalView (Fin S) → α, RowProtocolSolves S hS p is the proposition asserting that for every sage x : Fin S and every pair of permutations π₁, π₂ of Fin S, if:
1. the view of sage x under π₁ (rowViewOfSage hS π₁ x) equals the view of sage x under π₂ (rowViewOfSage hS π₂ x), and
2. the multiset of protocol messages evaluated across all positions under π₁ (rowMultiset hS p π₁) equals that under π₂ (rowMultiset hS p π₂),
then π₁ = π₂.
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
/-- A protocol solves the unlabeled row anonymous-slip puzzle if every sage can uniquely recover the true seating. -/ def RowProtocolSolves (S : ℕ) {α : Type*} (hS : 2 ≤ S) (p : RowLocalView (Fin S) → α) : Prop := ∀ (x : Fin S) (π₁ π₂ : Equiv.Perm (Fin S)), rowViewOfSage hS π₁ x = rowViewOfSage hS π₂ x → rowMultiset hS p π₁ = rowMultiset hS p π₂ → π₁ = π₂