AFTD Auto-Formalizing Theoretical Domains

op744_dice11_has_directed_cycle_ge_twelve

theoremverifiedformalization

There exists an integer k ≥ 12 such that has_directed_cycle (dice_graph 11).Adj k holds.

Statement

theorem op744_dice11_has_directed_cycle_ge_twelve : ∃ k ≥ 12, has_directed_cycle (dice_graph 11).Adj k
Formalizes
arXiv:2610.40321 Sec 3
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…
  • 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.
  • 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.

Read back from the Lean

There exists a natural number $k \ge 12$ such that the directed graph dice_graph 11 contains a simple directed cycle of length $k$. Explicitly: 1. There exists $k \in \mathbb{N}$ with $k \ge 12$ (which also trivially satisfies $3 \le k$). 2. There exists an injective function $c : \text{Fin } k \to \text{Die } 11$ such that for every $i \in \text{Fin } k$, there is an edge from $c(i)$ to $c(\text{finRotate } k \, i)$ in dice_graph 11. 3. An edge exists from die $x$ to die $y$ in dice_graph 11 if and only if $\text{beat\_score}(x, y) = \text{minimal\_advantage}(11)$ (which equals $(11^2 + 1)/2 = 61$). 4. A die $x \in \text{Die } 11$ is a monotone function $x : \text{Fin } 11 \to \text{Fin } 11$. 5. The beat score $\text{beat\_score}(x, y)$ is the number of pairs $(i, j) \in \text{Fin } 11 \times \text{Fin } 11$ such that $x(i) > y(j)$.

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 asserts the existence of a simple directed cycle of length at least 12 in the 11-sided dice graph, where a directed edge indicates that one die beats another with the minimal majority margin (61 out of 121 pairwise face matchups). The proof constructs 12 concrete 11-sided dice and verifies their monotonicity. It then instantiates the existential claim with cycle length k = 12, proves that the sequence of 12 dice is injective, and verifies by finite kernel computation that each die beats the next in the cyclic order with minimal advantage.

  1. Twelve candidate 11-sided dice are defined with non-decreasing face values.

    Each of the twelve dice (op744_dice11_die0 through op744_dice11_die11) is defined by an explicit 11-tuple of face values in {0, ..., 10}. The subtype requirement that the face values be weakly monotonically increasing (the condition defining Die 11) is discharged for each die by finite evaluation (`decide`).

    lines 1–12

    private def op744_dice11_die0 : Die 11 := ⟨![0, 2, 3, 3, 3, 6, 6, 6, 6, 10, 10], by decide⟩
    private def op744_dice11_die1 : Die 11 := ⟨![2, 2, 2, 2, 2, 4, 7, 7, 9, 9, 9], by decide⟩
    private def op744_dice11_die2 : Die 11 := ⟨![0, 1, 1, 4, 5, 5, 6, 6, 8, 9, 10], by decide⟩
    private def op744_dice11_die3 : Die 11 := ⟨![1, 3, 3, 4, 4, 4, 4, 4, 9, 9, 10], by decide⟩
    private def op744_dice11_die4 : Die 11 := ⟨![0, 1, 2, 2, 2, 6, 6, 7, 9, 10, 10], by decide⟩
    private def op744_dice11_die5 : Die 11 := ⟨![0, 0, 4, 5, 5, 5, 5, 5, 7, 9, 10], by decide⟩
    private def op744_dice11_die6 : Die 11 := ⟨![1, 3, 3, 3, 3, 4, 5, 7, 7, 9, 10], by decide⟩
    private def op744_dice11_die7 : Die 11 := ⟨![1, 1, 1, 2, 2, 3, 9, 9, 9, 9, 9], by decide⟩
    private def op744_dice11_die8 : Die 11 := ⟨![1, 1, 3, 3, 4, 6, 7, 7, 7, 8, 8], by decide⟩
    private def op744_dice11_die9 : Die 11 := ⟨![1, 2, 2, 2, 2, 4, 6, 6, 10, 10, 10], by decide⟩
    private def op744_dice11_die10 : Die 11 := ⟨![0, 0, 1, 3, 4, 7, 8, 8, 8, 8, 8], by decide⟩
    private def op744_dice11_die11 : Die 11 := ⟨![2, 3, 3, 4, 4, 4, 4, 7, 7, 7, 10], by decide⟩
  2. The candidate cycle length k = 12 satisfies k ≥ 12 and k ≥ 3, and the cycle formed by the 12 dice is injective.

    The existential quantifier is instantiated with k = 12. The inequality 12 ≥ 12 holds by reflexivity (`le_rfl`), and the condition 3 ≤ 12 required by `has_directed_cycle` is discharged by numerical evaluation (`norm_num`). The cycle map c : Fin 12 → Die 11 looks up the corresponding pre-defined die for each index i. Injectivity of c, which asserts that all 12 dice are pairwise distinct, is verified by exhaustive computation in the Lean kernel (`decide +kernel`).

    lines 18–23

    uses le_rfl

      set_option maxRecDepth 100000 in
      refine ⟨12, le_rfl, by norm_num, fun i =>
        ![op744_dice11_die0, op744_dice11_die1, op744_dice11_die2, op744_dice11_die3,
          op744_dice11_die4, op744_dice11_die5, op744_dice11_die6, op744_dice11_die7,
          op744_dice11_die8, op744_dice11_die9, op744_dice11_die10, op744_dice11_die11] i,
        by decide +kernel, ?_⟩
  3. Every consecutive pair of dice along the 12-cycle forms a directed edge in the 11-sided dice graph.

    For an arbitrary index i introduced by `intro i`, the proof exhausts all 12 cases i = 0, ..., 11 (`fin_cases i`). In each case, unfolding the definition of the graph adjacency (`simp only [dice_graph]`) reduces the goal to checking that the beat score between die i and die (i + 1 mod 12) equals the minimal advantage, which for n = 11 is (11² + 1) / 2 = 61. The kernel computation (`decide +kernel`) evaluates all 121 pairwise face comparisons and confirms that the beat score is exactly 61 in every case.

    lines 24–25

      intro i
      fin_cases i <;> (simp only [dice_graph]; decide +kernel)
le_rfl
Every element in a preorder is less than or equal to itself: a ≤ a.

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

private def op744_dice11_die0 : Die 11 := ⟨![0, 2, 3, 3, 3, 6, 6, 6, 6, 10, 10], by decide⟩private def op744_dice11_die1 : Die 11 := ⟨![2, 2, 2, 2, 2, 4, 7, 7, 9, 9, 9], by decide⟩private def op744_dice11_die2 : Die 11 := ⟨![0, 1, 1, 4, 5, 5, 6, 6, 8, 9, 10], by decide⟩private def op744_dice11_die3 : Die 11 := ⟨![1, 3, 3, 4, 4, 4, 4, 4, 9, 9, 10], by decide⟩private def op744_dice11_die4 : Die 11 := ⟨![0, 1, 2, 2, 2, 6, 6, 7, 9, 10, 10], by decide⟩private def op744_dice11_die5 : Die 11 := ⟨![0, 0, 4, 5, 5, 5, 5, 5, 7, 9, 10], by decide⟩private def op744_dice11_die6 : Die 11 := ⟨![1, 3, 3, 3, 3, 4, 5, 7, 7, 9, 10], by decide⟩private def op744_dice11_die7 : Die 11 := ⟨![1, 1, 1, 2, 2, 3, 9, 9, 9, 9, 9], by decide⟩private def op744_dice11_die8 : Die 11 := ⟨![1, 1, 3, 3, 4, 6, 7, 7, 7, 8, 8], by decide⟩private def op744_dice11_die9 : Die 11 := ⟨![1, 2, 2, 2, 2, 4, 6, 6, 10, 10, 10], by decide⟩private def op744_dice11_die10 : Die 11 := ⟨![0, 0, 1, 3, 4, 7, 8, 8, 8, 8, 8], by decide⟩private def op744_dice11_die11 : Die 11 := ⟨![2, 3, 3, 4, 4, 4, 4, 7, 7, 7, 10], by decide⟩private instance op744_dice11_instDecidableEqDie : DecidableEq (Die 11) :=  fun a b => decidable_of_iff (a.val = b.val) Subtype.ext_iff.symm/-- Existence of a simple directed cycle of length at least 12 in the 11-sided dice graph. -/theorem op744_dice11_has_directed_cycle_ge_twelve : ∃ k ≥ 12, has_directed_cycle (dice_graph 11).Adj k := by  set_option maxRecDepth 100000 in  refine ⟨12, le_rfl, by norm_num, fun i =>    ![op744_dice11_die0, op744_dice11_die1, op744_dice11_die2, op744_dice11_die3,      op744_dice11_die4, op744_dice11_die5, op744_dice11_die6, op744_dice11_die7,      op744_dice11_die8, op744_dice11_die9, op744_dice11_die10, op744_dice11_die11] i,    by decide +kernel, ?_⟩  intro i  fin_cases i <;> (simp only [dice_graph]; decide +kernel)
See it in the graphDiscuss this resultChallenge it