AFTD Auto-Formalizing Theoretical Domains

row_protocol_solves_of_injective

theoremverified

If a protocol with announcements in α solves the row puzzle, then composing it with any injective map α → β gives a protocol with announcements in β that still solves it.

Statement

theorem row_protocol_solves_of_injective {S : ℕ} {α β : Type*} (hS : 2 ≤ S)
    (f : α → β) (hf : Function.Injective f) (p : RowLocalView (Fin S) → α)
    (hp : RowProtocolSolves S hS p) :
    RowProtocolSolves S hS (fun v => f (p v))
Source
step towards sages_row_upper_bound_binomial
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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.
  • 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…
  • rowMultisetGiven a hypothesis 2 ≤ S, the public multiset of values produced by a protocol p : RowLocalView (Fin S) → α on a row seating π :…

The proof, explained

To show that the composed protocol f ∘ p solves the row puzzle, consider two permutations for which some sage has identical views and the multisets of announcements under f ∘ p agree. Because the announcements under f ∘ p are the image under f of the announcements under p, and f is injective, the multisets of announcements under p must also agree. Since p is assumed to solve the puzzle, this implies the two permutations are identical.

  1. To show that π₁ = π₂, it suffices to show that the multisets of announcements under the original protocol p are equal: rowMultiset hS p π₁ = rowMultiset hS p π₂.

    We introduce a sage x, permutations π₁ and π₂, the assumption that x has identical local views under both permutations, and the assumption that the multisets of announcements under f ∘ p are equal. Since the protocol p is assumed to solve the row puzzle, identical views for x and identical announcements under p imply π₁ = π₂. Applying this hypothesis leaves the sub одна goal of proving that the announcements under p coincide.

    lines 6–7

      intro x π₁ π₂ hview hmulti
      apply hp x π₁ π₂ hview
  2. For any permutation π, the announcements under the composed protocol f ∘ p are the image under f of the announcements under p: rowMultiset hS (f ∘ p) π = Multiset.map f (rowMultiset hS p π).

    Unfolding the definition of rowMultiset, the announcements are formed by evaluating the protocol on the local view of each position. Evaluating f ∘ p on each view is the composition of evaluating p followed by f; by Multiset.map_map, this multiset equals Multiset.map f applied to the announcements of p.

    lines 8–13

    uses Multiset.map_map

      have hmap (π : Equiv.Perm (Fin S)) :
          rowMultiset hS (fun v => f (p v)) π =
          Multiset.map f (rowMultiset hS p π) := by
        dsimp [rowMultiset]
        rw [Multiset.map_map]
        rfl
  3. The multisets of announcements under p for π₁ and π₂ are equal, which completes the proof.

    Since f is injective, Multiset.map f is injective by Multiset.map_injective. Hence, rowMultiset hS p π₁ = rowMultiset hS p π₂ is equivalent to their images under Multiset.map f being equal. Rewriting along the identity hmap established in the previous step transforms this into the equality of announcements under f ∘ p, which holds by our initial assumption.

    lines 14–15

    uses Multiset.map_injective

      apply Multiset.map_injective hf
      rwa [← hmap, ← hmap]
Multiset.map_map
Mapping two functions in sequence over a multiset is the same as mapping their composition: `map g (map f s) = map (g ∘ f) s`.
Multiset.map_injective
If a function f is injective, then the operation `Multiset.map f` sending multisets to multisets 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

/-- Injectivity of the announcement map is enough to turn a solving protocol into a solving protocol over a larger alphabet. -/theorem row_protocol_solves_of_injective {S : ℕ} {α β : Type*} (hS : 2 ≤ S)    (f : α → β) (hf : Function.Injective f) (p : RowLocalView (Fin S) → α)    (hp : RowProtocolSolves S hS p) :    RowProtocolSolves S hS (fun v => f (p v)) := by  intro x π₁ π₂ hview hmulti  apply hp x π₁ π₂ hview  have hmap (π : Equiv.Perm (Fin S)) :      rowMultiset hS (fun v => f (p v)) π =      Multiset.map f (rowMultiset hS p π) := by    dsimp [rowMultiset]    rw [Multiset.map_map]    rfl  apply Multiset.map_injective hf  rwa [← hmap, ← hmap]
See it in the graphDiscuss this resultChallenge it