row_solvable_mono
If 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 also solvable with m symbols (RowProblemSolvable S m hS) for any n ≤ m.
Statement
theorem row_solvable_mono {S n m : ℕ} (hS : 2 ≤ S) (hnm : n ≤ m)
(h : RowProblemSolvable S n hS) : RowProblemSolvable S m hS- Source
- arXiv:2610.33032:180
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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 :…
- RowProtocolSolvesA 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…
- 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 1
- row_sages_5R3E_implies_5R4EIf five sages in a row with unlabeled seats can solve the anonymous-slip puzzle using three symbols (RowProblemSolvable 5 3 (by decide)),…
Read back from the Lean
For all natural numbers S, n, and m, assuming 2 ≤ S and n ≤ m: if the row problem of size S is solvable using n labels (that is, there exists a protocol p : RowLocalView (Fin S) → Fin n such that RowProtocolSolves S hS p), then the row problem of size S is also solvable using m labels (there exists p' : RowLocalView (Fin S) → Fin m such that RowProtocolSolves S hS p').
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that puzzle solvability is monotonic in the number of symbols, we embed the solution protocol for n symbols into the larger alphabet of m symbols via the canonical injection Fin n ↪ Fin m. The multiset of announcements under this protocol is simply the image under the injection of the announcements under the original protocol. Since the injection preserves distinctness of multisets, equality of the announcements under the new protocol implies equality under the original protocol, so the correctness of the n-symbol protocol implies the correctness of the m-symbol protocol.
Given a solution protocol p for n symbols, propose the protocol obtained by embedding each output into Fin m, and set up the verification that it solves the m-symbol puzzle.
From the assumption that the puzzle is solvable with n symbols, we extract a protocol p that solves it. Since n ≤ m, we embed the values of p into Fin m via Fin.castLE. To show this new protocol solves the puzzle, we assume two permutations π₁ and π₂ give some sage x the same local view and yield identical multisets of announcements under the new protocol, and we must show π₁ = π₂.
uses
Fin.castLErcases h with ⟨p, hp⟩ refine ⟨fun v => Fin.castLE hnm (p v), fun x π₁ π₂ hview hmulti => ?_⟩
It suffices to show that π₁ and π₂ produce the same multiset of announcements under the original protocol p.
Because protocol p solves the n-symbol puzzle, any two permutations that agree on sage x's view and yield identical announcement multisets under p must be identical. Applying this to π₁, π₂, and x reduces the goal π₁ = π₂ to showing that the multisets under p coincide.
apply hp x π₁ π₂ hviewFor any permutation π, the multiset of announcements under the new protocol equals the multiset under p mapped by the inclusion Fin.castLE hnm.
By definition, the multiset of announcements under the composed protocol is obtained by evaluating the composition (Fin.castLE hnm ∘ p) at each seat's local view. By Multiset.map_map, this is identical to mapping Fin.castLE hnm over the multiset of values produced by p.
uses
Multiset.map_maphave hmap (π : Equiv.Perm (Fin S)) : rowMultiset hS (fun v => Fin.castLE hnm (p v)) π = Multiset.map (Fin.castLE hnm) (rowMultiset hS p π) := by dsimp [rowMultiset] rw [Multiset.map_map] rfl
The multisets under the original protocol p are equal, concluding that π₁ = π₂.
Because Fin.castLE hnm is injective (Fin.castLE_injective), the induced map on multisets is also injective (Multiset.map_injective). Thus, equality of the multisets under p reduces to equality of their images under Fin.castLE hnm. Rewriting with the lemma established in the previous step, this matches the hypothesis that the announcements under the new protocol are identical.
uses
Fin.castLE_injective,Multiset.map_injectiveapply Multiset.map_injective (Fin.castLE_injective hnm) rwa [← hmap, ← hmap]
Fin.castLE- The canonical inclusion of Fin n into Fin m for n ≤ m.
Fin.castLE_injective- The canonical inclusion of Fin n into Fin m is injective.
Multiset.map_map- Mapping two functions f and g consecutively over a multiset equals mapping their composition g ∘ f.
Multiset.map_injective- If a function f is injective, then Multiset.map f is also injective.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Monotonicity of row puzzle solvability in the number of symbols. -/theorem row_solvable_mono {S n m : ℕ} (hS : 2 ≤ S) (hnm : n ≤ m) (h : RowProblemSolvable S n hS) : RowProblemSolvable S m hS := by rcases h with ⟨p, hp⟩ refine ⟨fun v => Fin.castLE hnm (p v), fun x π₁ π₂ hview hmulti => ?_⟩ apply hp x π₁ π₂ hview have hmap (π : Equiv.Perm (Fin S)) : rowMultiset hS (fun v => Fin.castLE hnm (p v)) π = Multiset.map (Fin.castLE hnm) (rowMultiset hS p π) := by dsimp [rowMultiset] rw [Multiset.map_map] rfl apply Multiset.map_injective (Fin.castLE_injective hnm) rwa [← hmap, ← hmap]