arrows_parity_of_strategy_class
Let T be a finite tree and S a class of positions of the Game of Arrows on T that contains the empty position, such that from every position in S with an unmarked markable edge some legal move stays in S, and every legal move from a position in S lands in S or admits a legal reply back into S. Then the Grundy value of the Game of Arrows on T equals the number of markable edges of T modulo 2.
Statement
theorem arrows_parity_of_strategy_class {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) [DecidableRel T.Adj] (hT : T.IsTree) (S : ArrowsPos V → Prop) (h0 : S (ArrowsEmptyPos V)) (hex : ∀ p, S p → 1 ≤ arrows_markable_unmarked T p → ∃ q, ArrowsLegalMove T p q ∧ S q) (hcl : ∀ p q, S p → ArrowsLegalMove T p q → S q ∨ ∃ r, ArrowsLegalMove T q r ∧ S r) : arrows_tree_grundy T = tree_markable_edges T % 2
- Source
- Helper for arrows_parity_of_threads_le_two, arXiv:2610.15145 Theorem 10.3 / Corollary 10.4 (the induction in the proof of Theorem 10.3: every option has value (e-1) mod 2 or an option of value e mod 2), done directly on positions of T without the sum decomposition
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- arrows_tree_grundyThe Grundy value of the Game of Arrows on a finite simple graph G is the Grundy value of the empty position ArrowsEmptyPos V at fuel…
- tree_markable_edgesThe number of markable edges of a graph is the number of edges not incident to any leaf.
- arrows_markable_unmarkedThe number of unmarked markable edges of a position p of the Game of Arrows on G: edges of G neither of whose endpoints has degree 1 and…
- arrows_markable_unmarked_emptyIn the empty position the number of unmarked markable edges equals the number of markable (non-pendant) edges, tree_markable_edges.
- arrows_markable_unmarked_of_legalEvery legal move of the Game of Arrows decreases the number of unmarked markable edges by exactly one.
- arrows_pos_grundy_eq_mod_two_of_classStrategy lemma for parity in the Game of Arrows: let e be a function on positions that drops by exactly one along every legal move, and S…
- ArrowsEmptyPosThe empty starting position in ArrowsPos V whose boolean relation is everywhere false.
- ArrowsLegalMoveIn a simple graph G, a transition from position p to q in ArrowsPos V is a legal move if there exist u, v with ArrowsUnmarked G p u v such…
- ArrowsPosGiven a type V, ArrowsPos V is the subtype of boolean-valued binary relations p : V → V → Bool that are asymmetric, meaning that for all…
The proof, explained
The proof reduces the computation of the Grundy value of the Game of Arrows on a tree $T$ to the general invariant-class lemma `arrows_pos_grundy_eq_mod_two_of_class`. By hypothesis, the class of positions $S$ contains the empty position, and every legal move decreases the count of unmarked markable edges by one while preserving or restoring membership in $S$. Rewriting the initial number of markable edges as the unmarked markable edge count in the empty position, the result follows once we verify that this edge count is strictly less than the recursion fuel $|V|^2$. That bound holds because the markable edges are a subset of the graph's edges, and any simple graph on $|V|$ vertices has at most $\binom{|V|}{2} \le |V|(|V|-1) < |V|^2$ edges.
The Grundy value equals the number of markable edges modulo 2, provided that the number of unmarked markable edges in the empty position is strictly less than the recursion fuel $|V|^2$.
We enable classical logic and rewrite the total number of markable edges of $T$ as the count of unmarked markable edges in the empty position using `arrows_markable_unmarked_empty`. By definition, `arrows_tree_grundy T` evaluates the Grundy value at the empty position with fuel $|V|^2$. Applying `arrows_pos_grundy_eq_mod_two_of_class` with invariant class $S$ and edge-count function `arrows_markable_unmarked T`, the Grundy value is congruent to the edge count modulo 2. The required preconditions hold: each legal move decreases the count by 1 (`arrows_markable_unmarked_of_legal`), positions in $S$ with positive count admit moves staying in $S$ (hypothesis `hex`), replies can return to $S$ (hypothesis `hcl`), and the empty position belongs to $S$ (hypothesis `h0`). This leaves only the obligation that the initial edge count is strictly less than the fuel $|V|^2$.
uses
arrows_markable_unmarked_empty,arrows_pos_grundy_eq_mod_two_of_class,arrows_markable_unmarked_of_legalclassical rw [← arrows_markable_unmarked_empty T] apply arrows_pos_grundy_eq_mod_two_of_class T S _ (arrows_markable_unmarked_of_legal T) hex hcl _ _ h0
The vertex set $V$ has strictly positive cardinality ($0 < |V|$), and the number of unmarked markable edges in the empty position is at most the total number of edges $|E(T)|$.
Because $T$ is a tree, it is connected, so its vertex type $V$ is nonempty (`hT.1.nonempty`). By `Fintype.card_pos`, a nonempty finite type has strictly positive cardinality $0 < |V|$. Furthermore, unfolding `arrows_markable_unmarked`, the unmarked markable edges form a sub-finset of $T$'s edge set; by `Finset.card_filter_le`, any filtered subset has cardinality at most the total number of edges $|E(T)|$.
uses
Fintype.card_pos,Finset.card_filter_lehave hne : Nonempty V := hT.1.nonempty have hpos : 0 < Fintype.card V := Fintype.card_pos have h1 : arrows_markable_unmarked T (ArrowsEmptyPos V) ≤ T.edgeFinset.card := by unfold arrows_markable_unmarked; exact Finset.card_filter_le _ _
The number of edges of $T$ satisfies $|E(T)| \le \frac{|V|(|V|-1)}{2} \le |V|(|V|-1)$.
In any simple graph on $V$, the number of edges is at most $\binom{|V|}{2}$. Rewriting with `Nat.choose_two_right` gives $|E(T)| \le \frac{|V|(|V|-1)}{2}$. By `Nat.div_le_self`, dividing a natural number by 2 is at most the number itself, so $\frac{|V|(|V|-1)}{2} \le |V|(|V|-1)$.
uses
Nat.choose_two_right,Nat.div_le_selfhave h2 := T.card_edgeFinset_le_card_choose_two rw [Nat.choose_two_right] at h2 have h3 : Fintype.card V * (Fintype.card V - 1) / 2 ≤ Fintype.card V * (Fintype.card V - 1) := Nat.div_le_self _ _
The number of unmarked markable edges in the empty position is strictly less than $|V|^2$, completing the proof.
Since $0 < |V|$, we have $|V| - 1 < |V|$. Multiplying both sides by the positive quantity $|V|$ using `Nat.mul_lt_mul_of_pos_left` gives $|V|(|V|-1) < |V|^2$. Finally, linear arithmetic (`omega`) chains this strict inequality with the previous bounds: the unmarked markable edge count is at most $|E(T)| \le \frac{|V|(|V|-1)}{2} \le |V|(|V|-1) < |V|^2$. This verifies the fuel condition and closes the goal.
uses
Nat.mul_lt_mul_of_pos_lefthave h4 : Fintype.card V * (Fintype.card V - 1) < Fintype.card V * Fintype.card V := Nat.mul_lt_mul_of_pos_left (by omega) hpos omega
arrows_markable_unmarked_empty- In the empty position of the Game of Arrows, the number of unmarked markable edges equals the total number of markable edges of the graph.
arrows_pos_grundy_eq_mod_two_of_class- If an edge-counting measure decreases by 1 on every legal move and a class of positions S contains an initial position, permits legal moves from positions with positive count, and is closed under replies, then the Grundy value of any position in S whose count is less than the recursion fuel equals that count modulo 2.
arrows_markable_unmarked_of_legal- Every legal move in the Game of Arrows decreases the number of unmarked markable edges by exactly 1.
Fintype.card_pos- A finite type that is nonempty has strictly positive cardinality.
Finset.card_filter_le- The cardinality of any filtered sub-finset is at most the cardinality of the original finset.
Nat.choose_two_right- The binomial coefficient n choose 2 equals n * (n - 1) / 2 for any natural number n.
Nat.div_le_self- Integer division of a natural number n by k is at most n.
Nat.mul_lt_mul_of_pos_left- Multiplying a strict inequality between natural numbers on the left by a strictly positive number preserves the strict inequality.
- In this formalisation, `arrows_tree_grundy` is defined via bounded recursion with a fuel parameter set to $|V|^2$. On paper, no fuel is needed because the game on a finite graph terminates; here, lines 10–20 establish the technical bound that the initial number of unmarked markable edges is strictly less than $|V|^2$, a formal artifact with no counterpart in ordinary mathematics.
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.
theorem arrows_parity_of_strategy_class {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) [DecidableRel T.Adj] (hT : T.IsTree) (S : ArrowsPos V → Prop) (h0 : S (ArrowsEmptyPos V)) (hex : ∀ p, S p → 1 ≤ arrows_markable_unmarked T p → ∃ q, ArrowsLegalMove T p q ∧ S q) (hcl : ∀ p q, S p → ArrowsLegalMove T p q → S q ∨ ∃ r, ArrowsLegalMove T q r ∧ S r) : arrows_tree_grundy T = tree_markable_edges T % 2 := by classical rw [← arrows_markable_unmarked_empty T] apply arrows_pos_grundy_eq_mod_two_of_class T S _ (arrows_markable_unmarked_of_legal T) hex hcl _ _ h0 have hne : Nonempty V := hT.1.nonempty have hpos : 0 < Fintype.card V := Fintype.card_pos have h1 : arrows_markable_unmarked T (ArrowsEmptyPos V) ≤ T.edgeFinset.card := by unfold arrows_markable_unmarked; exact Finset.card_filter_le _ _ have h2 := T.card_edgeFinset_le_card_choose_two rw [Nat.choose_two_right] at h2 have h3 : Fintype.card V * (Fintype.card V - 1) / 2 ≤ Fintype.card V * (Fintype.card V - 1) := Nat.div_le_self _ _ have h4 : Fintype.card V * (Fintype.card V - 1) < Fintype.card V * Fintype.card V := Nat.mul_lt_mul_of_pos_left (by omega) hpos omega