AFTD Auto-Formalizing Theoretical Domains

op744_dice6_has_cycle_six

theoremverifiedformalization

The relation (dice_graph 6).Adj has a directed simple cycle of length 6, has_directed_cycle (dice_graph 6).Adj 6.

Statement

theorem op744_dice6_has_cycle_six : has_directed_cycle (dice_graph 6).Adj 6
Formalizes
arXiv:2610.40321 Thm 1
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • dice_graphFor an explicit parameter n : ℕ, dice_graph n is the bundled Digraph on Die n whose adjacency relation Adj x y holds if and only if…
  • has_directed_cycleA directed graph with adjacency relation Adj has a directed simple cycle of length k (with 3 ≤ k) if there exists an injective map c : Fin…
  • beat_scoreThe beat score of die x against die y, defined as the sum over all face indices i and j in Fin n of 1 if x(i) > y(j) and 0 otherwise.
  • minimal_advantageThe minimal winning advantage threshold for an n-sided die: n^2 / 2 + 1 if n is even, and (n^2 + 1) / 2 if n is odd.
  • DieThe type of non-standard n-sided dice with face values in Fin n, represented as non-decreasing functions from Fin n to Fin n.

Read back from the Lean

The directed graph dice_graph 6 contains a directed cycle of length 6. Specifically, there exists a sequence of 6 distinct dice c : Fin 6 → Die 6 (where a die is a monotone function from Fin 6 to Fin 6) such that for every i : Fin 6, the beat score of c i against c (finRotate 6 i) is exactly equal to minimal_advantage 6 (which evaluates to 19), and 3 ≤ 6.

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 proof exhibits an explicit directed 6-cycle in the 6-sided dice graph. Injectivity and the adjacency condition (that each die beats the next with minimal advantage 19) are verified by finite computation.

  1. Define six 6-sided dice by non-decreasing face sequences automation

    Each die is defined by a 6-tuple of face values in Fin 6, and decision procedures verify that the sequences are non-decreasing (monotone).

    lines 1–6

    private def op744_dice6_has_cycle_six_die0 : Die 6 := ⟨![0,0,1,4,4,4], by decide⟩
    private def op744_dice6_has_cycle_six_die1 : Die 6 := ⟨![0,2,3,3,3,3], by decide⟩
    private def op744_dice6_has_cycle_six_die2 : Die 6 := ⟨![1,1,1,2,5,5], by decide⟩
    private def op744_dice6_has_cycle_six_die3 : Die 6 := ⟨![0,0,1,4,4,5], by decide⟩
    private def op744_dice6_has_cycle_six_die4 : Die 6 := ⟨![0,2,2,3,3,3], by decide⟩
    private def op744_dice6_has_cycle_six_die5 : Die 6 := ⟨![1,1,2,2,2,5], by decide⟩
  2. Construct the candidate cycle of six dice and verify the cycle length and injectivity

    We provide an explicit sequence of six dice, verify that 3 ≤ 6 by arithmetic, and verify injectivity by finite evaluation.

    lines 13–16

      refine ⟨by norm_num, fun i =>
        ![op744_dice6_has_cycle_six_die0, op744_dice6_has_cycle_six_die1,
          op744_dice6_has_cycle_six_die2, op744_dice6_has_cycle_six_die3,
          op744_dice6_has_cycle_six_die4, op744_dice6_has_cycle_six_die5] i, by decide, ?_⟩
  3. Introduce an arbitrary step in the cycle

    We introduce the index i of the vertex in the cycle.

    line 17

      intro i
  4. Verify each of the six directed edges in the dice graph automation

    For each of the six indices, we unfold the definition of adjacency in the dice graph and verify by finite computation that the beat score equals the minimal advantage 19.

    line 18

    uses dice_graph

      fin_cases i <;> (simp only [dice_graph]; decide)
dice_graph
The directed graph whose vertices are n-sided dice and whose edges indicate that one die beats another with the minimal winning advantage.

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

private def op744_dice6_has_cycle_six_die0 : Die 6 := ⟨![0,0,1,4,4,4], by decide⟩private def op744_dice6_has_cycle_six_die1 : Die 6 := ⟨![0,2,3,3,3,3], by decide⟩private def op744_dice6_has_cycle_six_die2 : Die 6 := ⟨![1,1,1,2,5,5], by decide⟩private def op744_dice6_has_cycle_six_die3 : Die 6 := ⟨![0,0,1,4,4,5], by decide⟩private def op744_dice6_has_cycle_six_die4 : Die 6 := ⟨![0,2,2,3,3,3], by decide⟩private def op744_dice6_has_cycle_six_die5 : Die 6 := ⟨![1,1,2,2,2,5], by decide⟩private instance op744_dice6_has_cycle_six_instDecidableEqDie :    DecidableEq (Die 6) :=  fun a b => decidable_of_iff (a.val = b.val) Subtype.ext_iff.symm/-- The 6-sided dice graph contains a directed simple cycle of length 6. -/theorem op744_dice6_has_cycle_six : has_directed_cycle (dice_graph 6).Adj 6 := by  refine ⟨by norm_num, fun i =>    ![op744_dice6_has_cycle_six_die0, op744_dice6_has_cycle_six_die1,      op744_dice6_has_cycle_six_die2, op744_dice6_has_cycle_six_die3,      op744_dice6_has_cycle_six_die4, op744_dice6_has_cycle_six_die5] i, by decide, ?_⟩  intro i  fin_cases i <;> (simp only [dice_graph]; decide)
See it in the graphDiscuss this resultChallenge it