op744_dice3_no_cycle_three
The relation (dice_graph 3).Adj contains no directed simple cycle of length 3, that is, ¬ has_directed_cycle (dice_graph 3).Adj 3.
Statement
theorem op744_dice3_no_cycle_three : ¬ has_directed_cycle (dice_graph 3).Adj 3- Formalizes
- arXiv:2610.40321 Sec 2
- 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… - 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.
- 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.
- 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 theorem asserts that there is no directed 3-cycle in the directed graph dice_graph 3.
Specifically, it asserts that it is false that there exist three pairwise distinct dice $c_0, c_1, c_2 \in \text{Die } 3$ such that:
- dice_graph 3 has a directed edge from $c_0$ to $c_1$,
- a directed edge from $c_1$ to $c_2$, and
- a directed edge from $c_2$ to $c_0$.
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 states that the directed graph of 3-sided dice under the minimal advantage relation contains no directed cycle of length 3. Because a 3-sided die is defined as a monotone sequence from $\{0, 1, 2\}$ to $\{0, 1, 2\}$, the vertex set of the graph is finite with only 10 elements. Unfolding the definition of `has_directed_cycle` reduces the statement to checking that no injective map of 3 vertices forms a directed cycle. Lean's `decide` tactic performs an exhaustive search over all candidate triples and confirms by finite computation that no 3-cycle exists.
The goal is reformulated as the nonexistence of an injective sequence of 3 vertices forming a directed cycle in `dice_graph 3`.
Unfolding `has_directed_cycle` replaces the cycle predicate with its explicit definition: the conjunction of $3 \le 3$ and the existence of an injective map $c : \text{Fin } 3 \to \text{Die } 3$ such that each $c(i)$ is adjacent to $c(i+1 \pmod 3)$ in `dice_graph 3`.
unfold has_directed_cycleExhaustive evaluation confirms that no such directed 3-cycle exists, closing the goal. automation
Because the type `Die 3` has only 10 elements and adjacency in `dice_graph 3` is decidable, the negated existential statement over functions $\text{Fin } 3 \to \text{Die } 3$ is a finite decidable problem. The `decide` tactic tests all possible candidate triples by computation and determines that none form a directed cycle.
decide
- The proof relies on the typeclass instances declared in lines 3–10 (`DecidableEq (Die 3)`, `Fintype (Die 3)`, and `Decidable ((dice_graph n).Adj x y)`), which establish that the vertex set `Die 3` is finite and that the edge relation is decidable. This enables the `decide` tactic on line 15 to discharge the goal purely by computational evaluation.
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.
set_option maxRecDepth 5000instance op744_dice3_no_cycle_three_decidableEq_die3 : DecidableEq (Die 3) := inferInstanceAs (DecidableEq { d : Fin 3 → Fin 3 // Monotone d })instance op744_dice3_no_cycle_three_fintype_die3 : Fintype (Die 3) := inferInstanceAs (Fintype { d : Fin 3 → Fin 3 // Monotone d })instance op744_dice3_no_cycle_three_decidable_adj (n : ℕ) (x y : Die n) : Decidable ((dice_graph n).Adj x y) := inferInstanceAs (Decidable (beat_score x y = minimal_advantage n))/-- The 3-sided dice graph has no directed simple cycle of length 3. -/theorem op744_dice3_no_cycle_three : ¬ has_directed_cycle (dice_graph 3).Adj 3 := by unfold has_directed_cycle decide