AFTD Auto-Formalizing Theoretical Domains

op744_dice7_has_cycle_fourteen

theoremverifiedformalization

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 than LinearOrder — it does NOT require antisymmetry or…
  • 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.
  • 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.

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

    lines 3–18

    uses Subtype.instDecidableEq

      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⟩]
  2. 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.

    line 19

      refine ⟨by norm_num, c, by decide, ?_⟩
  3. 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.

    lines 20–21

      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 }.

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

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