row_protocol_solves_of_injective
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.
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.
intro x π₁ π₂ hview hmulti apply hp x π₁ π₂ hview
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.
uses
Multiset.map_maphave 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
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.
uses
Multiset.map_injectiveapply 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
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.
/-- 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]