op744_dice6_has_cycle_six
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.
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).
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⟩
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.
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, ?_⟩
Introduce an arbitrary step in the cycle
We introduce the index i of the vertex in the cycle.
intro iVerify 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.
uses
dice_graphfin_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
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.
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)