op744_dice7_has_cycle_fourteen
The relation (dice_graph 7).Adj has a directed simple cycle of length 14, has_directed_cycle (dice_graph 7).Adj 14.
Statement
theorem op744_dice7_has_cycle_fourteen : has_directed_cycle (dice_graph 7).Adj 14- Formalizes
- arXiv:2610.40321 Sec 3
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - 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 7 contains a directed cycle of length 14.
Explicitly, it asserts that 3 ≤ 14 and that there exists an injective map c : Fin 14 → Die 7 (a sequence of 14 distinct dice of size 7) such that for every i : Fin 14, there is a directed edge from c i to c (finRotate 14 i) in dice_graph 7, meaning beat_score (c i) (c (finRotate 14 i)) = minimal_advantage 7 (which evaluates to 25).
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 is proved by exhibiting an explicit directed cycle of length 14 in the graph of 7-sided dice. Fourteen concrete non-decreasing 7-tuples are defined, and the proof shows that $3 \le 14$, that all 14 dice are pairwise distinct (injectivity), and that each die beats the next in cyclic order with minimal advantage (a beat score of 25 out of 49). All structural conditions and edge comparisons are verified directly by finite computation.
Define an explicit sequence c of 14 valid 7-sided dice.
To enable computational verification on the subtype `Die 7`, we first equip it with decidable equality using `Subtype.instDecidableEq`. We then construct the candidate cycle $c : \text{Fin } 14 \to \text{Die } 7$ as a sequence of 14 concrete 7-tuples with face values in $\{0, \dots, 6\}$. Each die is verified to have non-decreasing faces (the monotonicity predicate) via finite evaluation (`decide`).
uses
Subtype.instDecidableEqlet _ : DecidableEq (Die 7) := fun a b => Subtype.instDecidableEq a b let c : Fin 14 → Die 7 := ![⟨![0,2,2,2,4,5,5], by decide⟩, ⟨![0,1,2,3,3,4,4], by decide⟩, ⟨![1,1,1,2,2,3,5], by decide⟩, ⟨![0,0,0,2,4,4,5], by decide⟩, ⟨![0,0,1,1,3,3,3], by decide⟩, ⟨![0,0,2,2,2,2,2], by decide⟩, ⟨![1,1,1,1,1,3,5], by decide⟩, ⟨![0,0,0,2,4,4,6], by decide⟩, ⟨![1,1,1,1,1,1,5], by decide⟩, ⟨![0,0,0,3,3,3,4], by decide⟩, ⟨![0,1,2,2,2,2,3], by decide⟩, ⟨![1,1,1,1,1,6,6], by decide⟩, ⟨![0,0,0,4,5,6,6], by decide⟩, ⟨![1,3,3,3,4,4,4], by decide⟩]
Reduce the existence of the directed cycle to verifying the 14 cyclic adjacency conditions.
By definition, a directed cycle of length 14 requires $3 \le 14$, an injective map from $\text{Fin } 14$, and directed edges between cyclically successive vertices. Using `refine`, the inequality $3 \le 14$ is verified by arithmetic (`norm_num`), $c$ is supplied as the witness, and injectivity (confirming that all 14 dice are distinct) is confirmed by `decide`. This leaves the cyclic edge conditions as the remaining goal.
refine ⟨by norm_num, c, by decide, ?_⟩
Each die in the cycle beats the cyclically next die with minimal advantage. automation
We introduce the index $i$ and perform a case split over all 14 indices in $\text{Fin } 14$ using `fin_cases`. For each case, simplifying with the definitions of `dice_graph` and $c$ reduces the goal to checking that the beat score $\sum_{j=0}^6 \sum_{k=0}^6 [c(i)_j > c((i+1) \bmod 14)_k]$ equals the minimal winning advantage of 25. Because this is an arithmetic identity over concrete finite tuples, `decide` closes each case by direct computation.
intro i fin_cases i <;> (simp only [dice_graph, c]; decide)
Subtype.instDecidableEq- If equality is decidable on a type α, then equality is also decidable on any subtype { x : α // p x }.
- Line 3 explicitly introduces a decidable equality instance on the subtype `Die 7` so that Lean's computational evaluator (`decide`) can verify the injectivity of the sequence and the graph adjacency conditions. This is a technical formal requirement with no paper counterpart.
- The verification that all 14 dice are pairwise distinct and that each of the 14 adjacent pairs achieves a beat score of exactly 25 out of 49 is handled by automated finite evaluation (`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.
/-- The 7-sided dice graph contains a directed simple cycle of length 14. -/theorem op744_dice7_has_cycle_fourteen : has_directed_cycle (dice_graph 7).Adj 14 := by let _ : DecidableEq (Die 7) := fun a b => Subtype.instDecidableEq a b let c : Fin 14 → Die 7 := ![⟨![0,2,2,2,4,5,5], by decide⟩, ⟨![0,1,2,3,3,4,4], by decide⟩, ⟨![1,1,1,2,2,3,5], by decide⟩, ⟨![0,0,0,2,4,4,5], by decide⟩, ⟨![0,0,1,1,3,3,3], by decide⟩, ⟨![0,0,2,2,2,2,2], by decide⟩, ⟨![1,1,1,1,1,3,5], by decide⟩, ⟨![0,0,0,2,4,4,6], by decide⟩, ⟨![1,1,1,1,1,1,5], by decide⟩, ⟨![0,0,0,3,3,3,4], by decide⟩, ⟨![0,1,2,2,2,2,3], by decide⟩, ⟨![1,1,1,1,1,6,6], by decide⟩, ⟨![0,0,0,4,5,6,6], by decide⟩, ⟨![1,3,3,3,4,4,4], by decide⟩] refine ⟨by norm_num, c, by decide, ?_⟩ intro i fin_cases i <;> (simp only [dice_graph, c]; decide)