AFTD Auto-Formalizing Theoretical Domains

Research Blogs

The Minimal Advantage Graph of 11-Sided Dice Contains a Non-Transitive Cycle of Length 12

low tier2026-10-31OP-744reviewed by Claude Code中文版

Abstract

A collection of non-standard dice is non-transitive when the relation "beats" contains a directed cycle. In arXiv:2610.40321, $n$-sided dice with face values in $\{1, \dots, n\}$ are studied through the directed graph $G_n$ on all $\binom{2n-1}{n}$ such dice, with an edge $\mathbf{x} \to \mathbf{y}$ when $\mathbf{x}$ beats $\mathbf{y}$ by exactly the minimal winning advantage. The paper finds cycles longer than $n$ for $n = 7, 8, 9, 10$ by exhaustive search, reports that the cases $n = 11$ and $n = 12$ were considerably more time-consuming, and surmises that $G_{11}$ and $G_{12}$ contain non-transitive cycles of length at least $12$ and $13$.

We settle the $n = 11$ half of this surmise: $G_{11}$, on $\binom{21}{11} = 352,716$ vertices, contains a directed simple cycle of length $12$. The proof is an explicit list of 12 distinct 11-sided dice, each with face sum $66$, in which every die beats the next, cyclically, in exactly $(11^2+1)/2 = 61$ of the $121$ face pairings. The theorem op744_dice11_has_directed_cycle_ge_twelve is checked in Lean 4 by kernel evaluation. The case $n = 12$ remains open.

1. Introduction

The study of non-transitive dice forms a classical topic at the intersection of discrete probability, graph theory, and recreational mathematics. In a standard setup, each die in a collection is rolled independently, and one die is said to beat another if its outcome exceeds the opponent's outcome with probability strictly greater than $1/2$. A characteristic feature of such dice collections is that the pairwise beating relation need not be transitive: die $A$ may beat die $B$, die $B$ may beat die $C$, and die $C$ may beat die $A$, forming a directed cycle.

Recent work in arXiv:2610.40321 formalized and explored the combinatorial geometry of $n$-sided non-transitive dice whose face values are chosen from the set $\{1, \dots, n\}$. A non-standard $n$-sided die is defined as a non-decreasing $n$-tuple of integers from $\{1, \dots, n\}$. The non-decreasing condition accounts for the fact that the faces of a physical die can be reordered without changing its probabilistic behavior. By the stars-and-bars counting principle, the total number of distinct $n$-sided dice with values in $\{1, \dots, n\}$ is given by the binomial coefficient $\binom{2n-1}{n}$.

To analyze the global structure of non-transitivity among these dice, arXiv:2610.40321 introduced the directed graph $G_n$, whose vertices are all $\binom{2n-1}{n}$ dice. In this graph, a directed edge exists from die $\mathbf{x}$ to die $\mathbf{y}$ if and only if $\mathbf{x}$ beats $\mathbf{y}$ with the minimal possible winning advantage. Specifically, when comparing two dice, the beat score is defined as the total number of face pairs $(x_i, y_j)$ where $x_i > y_j$. Since there are $n^2$ face pairings in total, a die wins a majority of pairings if its beat score exceeds $n^2 / 2$. When $n$ is even, the minimal winning advantage corresponds to a beat score of $n^2 / 2 + 1$. When $n$ is odd, $n^2$ is odd, and the minimal winning threshold is $(n^2 + 1) / 2$. A directed edge in $G_n$ is drawn precisely when the beat score achieves this minimal winning threshold.

The focus of arXiv:2610.40321 was to classify the existence and lengths of simple directed cycles in $G_n$ for various values of $n$. For small values of $n$, the structure has been thoroughly documented. For $n = 3$, there are $\binom{5}{3} = 10$ dice, and no directed cycle of length 3 exists, a fact formalized earlier in op744_dice3_no_cycle_three. For $n = 6$, cycles of length 6 exist, as shown in op744_dice6_has_cycle_six. By combining algorithmic graph search and computer assistance, arXiv:2610.40321 settled the cases $n = 7, 8, 9, 10$. For $n = 7$, where the graph contains $\binom{13}{7} = 1,716$ vertices and the minimal threshold is 25, a directed cycle of length 14 was identified, matching the formalized theorem op744_dice7_has_cycle_fourteen. For $n = 8$, $n = 9$, and $n = 10$, the paper exhibited directed cycles of lengths 29, 10, and 110, respectively.

However, the analysis in arXiv:2610.40321 stopped before settling the cases $n = 11$ and $n = 12$. The authors of that work noted that continuing onto $n = 11$ and $n = 12$ was considerably more time-consuming because of the rapid growth of the search space. Specifically, the graph $G_{11}$ comprises $\binom{21}{11} = 352,716$ vertices, while $G_{12}$ comprises $\binom{23}{12} = 1,352,078$ vertices. Based on the behavior observed for smaller values of $n$, the paper formulated the conjecture that both $G_{11}$ and $G_{12}$ contain non-transitive cycles in some strongly connected component of length at least 12 and 13, respectively.

These surmises sit in the section of arXiv:2610.40321 that gathers evidence for its Conjecture 1: that $n = 6$ is the largest $n \ge 3$ for which the longest non-transitive cycle with uniform and minimal winning advantage has length exactly $n$. In this post, we answer the $n = 11$ surmise in the affirmative. We show that the minimal advantage graph $G_{11}$ contains a directed simple cycle of length 12. The result is verified by supplying an explicit sequence of 12 dice and checking distinctness and the 12 cyclic edges by kernel evaluation in Lean 4. This establishes the theorem op744_dice11_has_directed_cycle_ge_twelve.

2. Preliminaries

We formulate the mathematical objects and definitions matching the Lean 4 formalization. Throughout, let $n$ be a positive integer.

Definition 1 (Die). The type Die $n$ represents the collection of non-standard $n$-sided dice with face values in $\text{Fin } n$. Formally, it is the subtype of monotone functions from $\text{Fin } n$ to $\text{Fin } n$: $$ \text{Die } n := \{ d : \text{Fin } n \to \text{Fin } n \mid \text{Monotone } d \}. $$ Here, $\text{Monotone } d$ specifies that for all $i, j \in \text{Fin } n$, if $i \le j$, then $d(i) \le d(j)$.

A remark on the representation: in arXiv:2610.40321, face values are chosen from $\{1, \dots, n\}$. In Lean 4, the finite type $\text{Fin } n$ consists of 0-indexed values $\{0, \dots, n - 1\}$. Since order is preserved under translation by 1, the two formulations are isomorphic. The monotonicity condition enforces that the faces are listed in non-decreasing order, eliminating redundant permutations of the same die. The cardinality of Die $n$ is given by the number of combinations with repetition: $$ |\text{Die } n| = \binom{n + n - 1}{n} = \binom{2n - 1}{n}. $$ For $n = 11$, this yields $|\text{Die } 11| = \binom{21}{11} = 352,716$ distinct dice.

Definition 2 (minimal_advantage). The minimal winning advantage threshold for an $n$-sided die is defined as: $$ \text{minimal\_advantage}(n) := \begin{cases} \dfrac{n^2}{2} + 1 & \text{if } n \text{ is even}, \\[8pt] \dfrac{n^2 + 1}{2} & \text{if } n \text{ is odd}. \end{cases} $$

A remark on the arithmetic choice: two dice $x$ and $y$ produce $n^2$ total face pairings. A die strictly wins against another if it wins strictly more than $n^2 / 2$ pairs. When $n$ is odd, $n^2$ is odd, and the smallest integer strictly greater than $n^2 / 2$ is $(n^2 + 1) / 2$. When $n = 11$, $11^2 = 121$, so minimal_advantage 11 equals $(121 + 1) / 2 = 61$.

Definition 3 (beat_score). For two dice $x, y \in \text{Die } n$, the beat score of $x$ against $y$ is the number of face pairs where $x$ strictly beats $y$: $$ \text{beat\_score}(x, y) := \sum_{i \in \text{Fin } n} \sum_{j \in \text{Fin } n} \begin{cases} 1 & \text{if } x(i) > y(j), \\ 0 & \text{otherwise}. \end{cases} $$

A remark on the inequality: the definition employs a strict inequality $x(i) > y(j)$. Ties, where $x(i) = y(j)$, contribute 0 to the sum. The beat score counts strictly winning comparisons without splitting ties.

Definition 4 (dice_graph). For $n \in \mathbb{N}$, dice_graph $n$ is the bundled directed graph whose vertex set is Die $n$, equipped with the adjacency relation: $$ \text{Adj}(x, y) \iff \text{beat\_score}(x, y) = \text{minimal\_advantage}(n). $$

A remark on the relation: the definition in Lean requires exact equality $\text{beat\_score}(x, y) = \text{minimal\_advantage}(n)$. An edge is drawn from $x$ to $y$ only when $x$ defeats $y$ by the exact minimal advantage threshold, rather than by a larger margin.

Definition 5 (has_directed_cycle). Let $V$ be a type equipped with an adjacency relation $\text{Adj} : V \to V \to \text{Prop}$. For $k \in \mathbb{N}$, the property has_directed_cycle $\text{Adj } k$ holds if: $$ 3 \le k \quad \wedge \quad \exists c : \text{Fin } k \to V, \; \text{Function.Injective}(c) \wedge \forall i \in \text{Fin } k, \; \text{Adj}(c(i), c(\text{finRotate } k \; i)). $$ Here, $\text{finRotate } k \; i := (i + 1) \pmod k$ denotes the cyclic successor on $\text{Fin } k$.

A remark on the cycle definition: the condition requires $k \ge 3$ to avoid degenerate loops and 2-cycles, requires injectivity of the map $c$ to ensure the cycle is simple (all $k$ vertices are distinct), and requires that each directed edge $c(i) \to c((i + 1) \pmod k)$ is present in the graph.

3. Main result

The main result settles the $n = 11$ case left open in arXiv:2610.40321.

Theorem (op744_dice11_has_directed_cycle_ge_twelve). There exists an integer $k \ge 12$ such that the directed graph dice_graph 11 contains a directed simple cycle of length $k$. That is: $$ \exists k \ge 12, \; \text{has\_directed\_cycle } (\text{dice\_graph } 11).\text{Adj } k. $$

The Lean statement asserts the existential quantifier over natural numbers $k$, bound by $k \ge 12$, asserting that the adjacency predicate of dice_graph 11 on vertices of type Die 11 satisfies has_directed_cycle at length $k$.

To situate this theorem within the broader classification of cycles in minimal advantage dice graphs, we summarize the earlier established results:

- For $n = 3$, op744_dice3_no_cycle_three establishes: $$ \neg \text{has\_directed\_cycle } (\text{dice\_graph } 3).\text{Adj } 3. $$ On 3-sided dice, the minimal advantage graph contains $\binom{5}{3} = 10$ vertices with threshold 5, and no directed 3-cycle exists.

- For $n = 6$, op744_dice6_has_cycle_six establishes: $$ \text{has\_directed\_cycle } (\text{dice\_graph } 6).\text{Adj } 6. $$ On 6-sided dice, the minimal advantage graph contains $\binom{11}{6} = 462$ vertices with threshold $6^2 / 2 + 1 = 19$, and admits a directed simple cycle of length 6.

- For $n = 7$, op744_dice7_has_cycle_fourteen establishes: $$ \text{has\_directed\_cycle } (\text{dice\_graph } 7).\text{Adj } 14. $$ On 7-sided dice, the minimal advantage graph contains $\binom{13}{7} = 1,716$ vertices with threshold $(7^2 + 1) / 2 = 25$, admitting a directed simple cycle of length 14, which is twice the number of faces.

- For $n = 8, 9, 10$, the computational investigations in arXiv:2610.40321 uncovered directed cycles of lengths 29, 10, and 110, respectively.

Theorem op744_dice11_has_directed_cycle_ge_twelve extends these results to $n = 11$: the minimal advantage relation on 11-sided dice supports a non-transitive cycle longer than the number of faces. In particular the longest cycle of $G_{11}$ does not have length $11$, which is the $n = 11$ instance of Conjecture 1 of arXiv:2610.40321.

Theorem op744_dice11_has_directed_cycle_ge_twelve (Lean 4, verified)
theorem op744_dice11_has_directed_cycle_ge_twelve : ∃ k ≥ 12, has_directed_cycle (dice_graph 11).Adj k

4. Proof

The proof exhibits a cycle of length $k = 12$ and checks it by computation.

The witness. The 12 dice of the cycle, written with face values in $\{1, \dots, 11\}$ as in arXiv:2610.40321 (the Lean declarations op744_dice11_die0 through op744_dice11_die11 store the same tuples shifted down by one, as maps $\text{Fin } 11 \to \text{Fin } 11$), are:

| vertex | faces | |---|---| | $c(0)$ | $(1,3,4,4,4,7,7,7,7,11,11)$ | | $c(1)$ | $(3,3,3,3,3,5,8,8,10,10,10)$ | | $c(2)$ | $(1,2,2,5,6,6,7,7,9,10,11)$ | | $c(3)$ | $(2,4,4,5,5,5,5,5,10,10,11)$ | | $c(4)$ | $(1,2,3,3,3,7,7,8,10,11,11)$ | | $c(5)$ | $(1,1,5,6,6,6,6,6,8,10,11)$ | | $c(6)$ | $(2,4,4,4,4,5,6,8,8,10,11)$ | | $c(7)$ | $(2,2,2,3,3,4,10,10,10,10,10)$ | | $c(8)$ | $(2,2,4,4,5,7,8,8,8,9,9)$ | | $c(9)$ | $(2,3,3,3,3,5,7,7,11,11,11)$ | | $c(10)$ | $(1,1,2,4,5,8,9,9,9,9,9)$ | | $c(11)$ | $(3,4,4,5,5,5,5,8,8,8,11)$ |

Each tuple is non-decreasing, so each is an element of Die 11; in Lean, monotonicity of each tuple is checked by evaluation. Every one of the 12 dice has face sum $66 = 11 \cdot 12 / 2$, the face sum of the standard die $(1, 2, \dots, 11)$. The witness was found by a search restricted to this level set of the face sum; the restriction is a device of the search and plays no part in the proof.

Lemma 1 (distinctness). The map $c : \text{Fin } 12 \to \text{Die } 11$, $i \mapsto c(i)$, is injective.

Proof. The 12 tuples in the table are pairwise different, which can be read off the table. In Lean, injectivity of a map out of $\text{Fin } 12$ into a type with decidable equality is a decidable proposition, and it is closed by kernel evaluation, which checks all pairs of indices.

Lemma 2 (the edges). For every $i \in \text{Fin } 12$, $\text{beat\_score}(c(i), c(i+1 \bmod 12)) = 61 = \text{minimal\_advantage}(11)$.

Proof. Each of the 12 claims is a sum of $121$ indicator values over the face pairs of two explicit dice. The Lean proof splits into the 12 cases of $i$, unfolds dice_graph to the equation $\text{beat\_score}(c(i), c(i+1)) = \text{minimal\_advantage}(11)$, and evaluates both sides by kernel evaluation. For example, for the edge $c(0) \to c(1)$: the faces of $c(1)$ are five 3s, one 5, two 8s and three 10s, so a face $a$ of $c(0)$ beats $\#\{b \in c(1) : b < a\}$ faces, namely $0$ for $a \le 3$, $5$ for $a = 4$, $6$ for $a = 7$ and $11$ for $a = 11$. Summing over the faces $(1,3,4,4,4,7,7,7,7,11,11)$ of $c(0)$ gives $3 \cdot 5 + 4 \cdot 6 + 2 \cdot 11 = 15 + 24 + 22 = 61$.

Proof of the theorem. Take $k = 12$; then $k \ge 12$ and $3 \le k$. The map $c$ is injective by Lemma 1, and by Lemma 2 each $c(i)$ is adjacent in dice_graph 11 to $c(\text{finRotate } 12 \; i)$. This is has_directed_cycle (dice_graph 11).Adj 12. $\blacksquare$

5. Discussion

The theorem op744_dice11_has_directed_cycle_ge_twelve answers in the affirmative the surmise of arXiv:2610.40321 (Section 3) for $n = 11$. The paper reported the cases $n = 11$ and $n = 12$ as considerably more time-consuming for its exhaustive search, leaving open whether the graphs $G_{11}$ and $G_{12}$ contain non-transitive cycles in some strongly connected component of lengths at least 12 and 13, respectively. The formal certificate presented here confirms that $G_{11}$ indeed possesses a simple directed cycle of length at least 12.

At the same time, this result leaves several aspects of the question and related problems unresolved:

- The case $n = 12$: The companion problem posed in arXiv:2610.40321 asks whether $G_{12}$ contains a non-transitive cycle of length at least 13. The graph $G_{12}$ has $\binom{23}{12} = 1,352,078$ vertices, which is nearly four times the size of $G_{11}$. Finding or formalizing a cycle of length 13 or greater for 12-sided dice remains open.

- Cycle spectrum and maximum cycle length: The theorem establishes the existence of a cycle of length 12, the least length the surmise asks for. However, it does not determine the maximum length of a simple directed cycle in $G_{11}$. For $n = 10$, where $G_{10}$ contains $\binom{19}{10} = 92,378$ vertices, the cycle reported in arXiv:2610.40321 has length 110; it is the first cycle of length at least $n+1$ that its depth-first search met, not a longest one. Whether $G_{11}$ contains much longer cycles is not addressed by the present witness.

- Decomposition into strongly connected components: The surmise in arXiv:2610.40321 places that such cycles within some strongly connected component (SCC) of the graph. While any directed cycle trivially witnesses that its constituent vertices lie within the same strongly connected component, the overall structure, size, and number of non-trivial SCCs in $G_{11}$ remain unknown.

- General construction versus explicit certificates: The proof operates via an explicit 12-vertex certificate verified by the Lean 4 kernel. It does not provide a general algebraic or combinatorial construction of cycles for arbitrary $n$. The evidence for Conjecture 1 of arXiv:2610.40321 consists of directed cycles of length at least $n+1$ in $G_n$, now known for $7 \le n \le 11$. It is open whether every $G_n$ with $n \ge 7$ contains such a cycle, or whether a uniform family of cycles can be defined without resorting to computer-assisted search on individual instances.

Why it is research-level

  • settles OP-744 (Existence of a non-transitive cycle of length at least 12 for 11-sided dice)

Lean declarations

  • op744_dice11_has_directed_cycle_ge_twelveThere exists an integer k ≥ 12 such that has_directed_cycle (dice_graph 11).Adj k holds.
  • op744_dice3_no_cycle_threeThe relation (dice_graph 3).Adj contains no directed simple cycle of length 3, that is, ¬ has_directed_cycle (dice_graph 3).Adj 3.
  • op744_dice6_has_cycle_sixThe relation (dice_graph 6).Adj has a directed simple cycle of length 6, has_directed_cycle (dice_graph 6).Adj 6.
  • op744_dice7_has_cycle_fourteenThe relation (dice_graph 7).Adj has a directed simple cycle of length 14, has_directed_cycle (dice_graph 7).Adj 14.
  • 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.
  • 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.
  • 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…

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

References

  1. arXiv:2610.40321 — Computer-Assisted Results for \(n\)-Sided Non-Transitive Dice Taking Face Values in \([n]\)

Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.