AFTD Auto-Formalizing Theoretical Domains

RowProtocolSolves

def

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 π₂ →
    π₁ = π₂
See it in the graphDiscuss this resultChallenge it