AFTD Auto-Formalizing Theoretical Domains

row_solvable_mono

theoremverified

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.

  1. 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 π₁ = π₂.

    lines 4–5

    uses Fin.castLE

      rcases h with ⟨p, hp⟩
      refine ⟨fun v => Fin.castLE hnm (p v), fun x π₁ π₂ hview hmulti => ?_⟩
  2. 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.

    line 6

      apply hp x π₁ π₂ hview
  3. For 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.

    lines 7–12

    uses Multiset.map_map

      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
  4. 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.

    lines 13–14

    uses Fin.castLE_injective, Multiset.map_injective

      apply 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

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