AFTD Auto-Formalizing Theoretical Domains

op744_dice3_no_cycle_three

theoremverifiedformalization

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 than LinearOrder — 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 LinearOrder is a TotalPreorder.
  • 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.

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

    line 14

      unfold has_directed_cycle
  2. Exhaustive 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.

    line 15

      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

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