AFTD Auto-Formalizing Theoretical Domains

row_sages_5R3E_implies_5R4E

theoremverified

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.

  1. 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`.

    lines 2–3

    theorem row_sages_5R3E_implies_5R4E (h : RowProblemSolvable 5 3 (by decide)) :
        RowProblemSolvable 5 4 (by decide) := by
  2. 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`.

    line 4

    uses row_solvable_mono

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

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

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