row_sages_5R3E_implies_5R4E
If five sages in a row with unlabeled seats can solve the anonymous-slip puzzle using three symbols (RowProblemSolvable 5 3 (by decide)), then they can also solve it using four symbols (RowProblemSolvable 5 4 (by decide)).
Statement
theorem row_sages_5R3E_implies_5R4E (h : RowProblemSolvable 5 3 (by decide)) : RowProblemSolvable 5 4 (by decide)
- Source
- arXiv:2610.33032:543
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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 :…
- 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…
Read back from the Lean
If the row problem is solvable for 5 sages with 3 broadcast states/messages (i.e., RowProblemSolvable 5 3), then the row problem is solvable for 5 sages with 4 broadcast states/messages (RowProblemSolvable 5 4).
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
The theorem follows from the monotonicity of row problem solvability in the number of available symbols (`row_solvable_mono`). Given that the 5-sage problem is solvable with 3 symbols and 3 ≤ 4, it is solvable with 4 symbols.
The row problem instances with 5 sages are well-defined (2 ≤ 5). automation
The condition 2 ≤ 5 required by `RowProblemSolvable` for both the hypothesis (with 3 symbols) and the goal (with 4 symbols) is proved automatically by `decide`.
theorem row_sages_5R3E_implies_5R4E (h : RowProblemSolvable 5 3 (by decide)) : RowProblemSolvable 5 4 (by decide) := by
The five-sage row problem is solvable using 4 symbols.
Apply the monotonicity lemma `row_solvable_mono` to the hypothesis `h`, using the arithmetic facts 2 ≤ 5 and 3 ≤ 4, which are evaluated by `decide`.
uses
row_solvable_monoexact row_solvable_mono (by decide) (by decide) h
row_solvable_mono- If the row problem with S sages (where 2 ≤ S) is solvable using n symbols, and n ≤ m, then it is also solvable using m symbols.
- The well-formedness condition 2 ≤ 5 in the theorem signature and the inequality 3 ≤ 4 are verified automatically by `decide`.
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.
/-- If 5R3E is solvable, then 5R4E is solvable. -/theorem row_sages_5R3E_implies_5R4E (h : RowProblemSolvable 5 3 (by decide)) : RowProblemSolvable 5 4 (by decide) := by exact row_solvable_mono (by decide) (by decide) h