arrows_pos_grundy_eq_mod_two_of_class
Strategy 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 a class of positions such that from every position in S with e >= 1 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 every position p in S has fuel-bounded Grundy value e(p) mod 2 at every fuel greater than e(p).
Statement
theorem arrows_pos_grundy_eq_mod_two_of_class {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (S : ArrowsPos V → Prop) (e : ArrowsPos V → ℕ) (he : ∀ p q, ArrowsLegalMove G p q → e q + 1 = e p) (hex : ∀ p, S p → 1 ≤ e p → ∃ q, ArrowsLegalMove G p q ∧ S q) (hcl : ∀ p q, S p → ArrowsLegalMove G p q → S q ∨ ∃ r, ArrowsLegalMove G q r ∧ S r) : ∀ fuel p, S p → e p < fuel → arrows_pos_grundy G fuel p = e p % 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 8
- arrows_pos_grundyThe Grundy value of a position p : ArrowsPos V in the Game of Arrows on G at recursion depth fuel, defined as 0 when fuel = 0 and as the…
- 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…
- nat_mex_set_eq_zero_of_not_memIf 0 is not in a set s of natural numbers, the mex of s is 0.
- nat_mex_set_eq_one_of_memIf 0 is in a set s of natural numbers and 1 is not, the mex of s is 1.
- nat_mex_set_ne_of_memThe mex of a finite set s of natural numbers is not an element of s.
- arrows_pos_grundy_options_finiteFor any fuel and position p of the Game of Arrows on a finite graph, the set of fuel-bounded Grundy values of the legal options of p is…
- nat_mex_setThe minimum excluded natural number of a set s of natural numbers is the infimum of the set of natural numbers not in s.
- 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…
- Used by 1
- arrows_parity_of_strategy_classLet 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…
The proof, explained
The proof proceeds by strong induction on fuel. The core step establishes that from any position $p \in S$, no legal move can lead to an option with Grundy value equal to $e(p) \bmod 2$: if the move stays in $S$, the parity of $e$ alternates; if it leaves $S$, a legal reply move back into $S$ shows that $e(p) \bmod 2$ is already among the options from that neighbor, preventing the neighbor's Grundy value (the mex of its options) from equaling $e(p) \bmod 2$. A case split on $e(p) \bmod 2$ then shows the mex of the options from $p$ is 0 when $e(p)$ is even (as 0 is excluded) and 1 when $e(p)$ is odd (as 0 is reachable and 1 is excluded).
We set up strong induction on `fuel` and express `fuel` as a successor $n + 1$.
We proceed by strong induction on `fuel`. For any position $p \in S$ satisfying $e(p) < \text{fuel}$, the condition $0 \le e(p) < \text{fuel}$ implies $\text{fuel} \ge 1$. Hence, we can write $\text{fuel} = n + 1$ with $n = \text{fuel} - 1$, preparing to unfold the definition of the fuel-bounded Grundy value.
uses
Nat.strong_induction_onintro fuel induction fuel using Nat.strong_induction_on with | _ fuel ih => intro p hp hlt obtain ⟨n, rfl⟩ : ∃ n, fuel = n + 1 := ⟨fuel - 1, by omega⟩
No legal move from $p$ leads to a position whose Grundy value with fuel $n$ equals $e(p) \bmod 2$.
Suppose for contradiction that some legal move $p \to q$ yields a position $q$ with Grundy value $e(p) \bmod 2$. The hypothesis `he` gives $e(q) = e(p) - 1$. By the closure hypothesis `hcl`, either $q \in S$ or there exists a reply move $q \to r$ with $r \in S$: - If $q \in S$, the induction hypothesis applies to $q$ with fuel $n$ (since $n < \text{fuel}$ and $e(q) < n$), showing its Grundy value is $e(q) \bmod 2$. But $e(p) \equiv e(q) + 1 \not\equiv e(q) \pmod 2$, a contradiction. - If there is a reply move $q \to r$ with $r \in S$, then $e(r) = e(q) - 1 = e(p) - 2$, so $e(r) \equiv e(p) \pmod 2$. Writing $n = n' + 1$, the induction hypothesis applied to $r$ with fuel $n'$ shows its Grundy value is $e(r) \bmod 2 = e(p) \bmod 2$. Thus, $e(p) \bmod 2$ is an option value from $q$. Since the Grundy value of $q$ with fuel $n = n' + 1$ is the mex of its options, it cannot equal any element in that finite set by `nat_mex_set_ne_of_mem` and `arrows_pos_grundy_options_finite`, contradicting our assumption.
uses
arrows_pos_grundy_options_finite,nat_mex_set_ne_of_memhave hnot : e p % 2 ∉ { m : ℕ | ∃ q, ArrowsLegalMove G p q ∧ m = arrows_pos_grundy G n q } := by rintro ⟨q, hq, hm⟩ have heq := he p q hq rcases hcl p q hp hq with hS | ⟨r, hr, hSr⟩ · rw [ih n (by omega) q hS (by omega)] at hm; omega · have her := he q r hr obtain ⟨n', rfl⟩ : ∃ n', n = n' + 1 := ⟨n - 1, by omega⟩ have hrv : arrows_pos_grundy G n' r = e p % 2 := by rw [ih n' (by omega) r hSr (by omega)]; omega have hg : arrows_pos_grundy G (n' + 1) q = nat_mex_set { m : ℕ | ∃ q', ArrowsLegalMove G q q' ∧ m = arrows_pos_grundy G n' q' } := rfl exact nat_mex_set_ne_of_mem (arrows_pos_grundy_options_finite G n' q) ⟨r, hr, hrv.symm⟩ (hg ▸ hm.symm)
If $e(p) \equiv 0 \pmod 2$, the Grundy value of $p$ with fuel $n + 1$ is $0$.
By definition, the Grundy value with fuel $n + 1$ is the mex of the option values from $p$. Using `Nat.mod_two_eq_zero_or_one`, we split on the parity of $e(p)$. In the case $e(p) \equiv 0 \pmod 2$, the previous step showed that $0$ is not among the option values (`hnot`). By `nat_mex_set_eq_zero_of_not_mem`, the mex of any set of natural numbers not containing $0$ is $0$.
uses
Nat.mod_two_eq_zero_or_one,nat_mex_set_eq_zero_of_not_memshow nat_mex_set _ = _ rcases Nat.mod_two_eq_zero_or_one (e p) with h0 | h1 · rw [h0] at hnot ⊢; exact nat_mex_set_eq_zero_of_not_mem hnot
If $e(p) \equiv 1 \pmod 2$, the Grundy value of $p$ with fuel $n + 1$ is $1$.
When $e(p) \equiv 1 \pmod 2$, we have $e(p) \ge 1$. The existence hypothesis `hex` guarantees a legal move $p \to q$ with $q \in S$. Since $e(q) = e(p) - 1$, we have $e(q) \equiv 0 \pmod 2$, and by the induction hypothesis the Grundy value of $q$ with fuel $n$ is $0$. Thus $0$ is in the option set of $p$. Because $0$ is present and $1$ is excluded (by `hnot`), the mex of the option set is $1$ by `nat_mex_set_eq_one_of_mem`.
uses
nat_mex_set_eq_one_of_mem· rw [h1] at hnot ⊢ obtain ⟨q, hq, hSq⟩ := hex p hp (by omega) have heq := he p q hq exact nat_mex_set_eq_one_of_mem ⟨q, hq, by rw [ih n (by omega) q hSq (by omega)]; omega⟩ hnot
Nat.strong_induction_on- Principle of strong induction on natural numbers: to prove a property holds for all $n$, it suffices to show it holds for $n$ assuming it holds for all $m < n$.
arrows_pos_grundy_options_finite- The set of Grundy values of all positions legally reachable in one move from a given position is finite.
nat_mex_set_ne_of_mem- The minimum excluded value (mex) of a finite set of natural numbers is not an element of that set.
Nat.mod_two_eq_zero_or_one- Every natural number modulo 2 is either 0 or 1.
nat_mex_set_eq_zero_of_not_mem- If 0 does not belong to a set of natural numbers, its minimum excluded value is 0.
nat_mex_set_eq_one_of_mem- If 0 belongs to a set of natural numbers and 1 does not, its minimum excluded value is 1.
- The parameter `fuel` is a formal recursion-depth budget used to define `arrows_pos_grundy` in Lean. Since $e$ decreases by exactly 1 on every legal move, any game starting at $p$ terminates in at most $e(p)$ steps, so the condition $e(p) < \text{fuel}$ ensures that the fuel bound is never reached.
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_pos_grundy_eq_mod_two_of_class {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (S : ArrowsPos V → Prop) (e : ArrowsPos V → ℕ) (he : ∀ p q, ArrowsLegalMove G p q → e q + 1 = e p) (hex : ∀ p, S p → 1 ≤ e p → ∃ q, ArrowsLegalMove G p q ∧ S q) (hcl : ∀ p q, S p → ArrowsLegalMove G p q → S q ∨ ∃ r, ArrowsLegalMove G q r ∧ S r) : ∀ fuel p, S p → e p < fuel → arrows_pos_grundy G fuel p = e p % 2 := by intro fuel induction fuel using Nat.strong_induction_on with | _ fuel ih => intro p hp hlt obtain ⟨n, rfl⟩ : ∃ n, fuel = n + 1 := ⟨fuel - 1, by omega⟩ have hnot : e p % 2 ∉ { m : ℕ | ∃ q, ArrowsLegalMove G p q ∧ m = arrows_pos_grundy G n q } := by rintro ⟨q, hq, hm⟩ have heq := he p q hq rcases hcl p q hp hq with hS | ⟨r, hr, hSr⟩ · rw [ih n (by omega) q hS (by omega)] at hm; omega · have her := he q r hr obtain ⟨n', rfl⟩ : ∃ n', n = n' + 1 := ⟨n - 1, by omega⟩ have hrv : arrows_pos_grundy G n' r = e p % 2 := by rw [ih n' (by omega) r hSr (by omega)]; omega have hg : arrows_pos_grundy G (n' + 1) q = nat_mex_set { m : ℕ | ∃ q', ArrowsLegalMove G q q' ∧ m = arrows_pos_grundy G n' q' } := rfl exact nat_mex_set_ne_of_mem (arrows_pos_grundy_options_finite G n' q) ⟨r, hr, hrv.symm⟩ (hg ▸ hm.symm) show nat_mex_set _ = _ rcases Nat.mod_two_eq_zero_or_one (e p) with h0 | h1 · rw [h0] at hnot ⊢; exact nat_mex_set_eq_zero_of_not_mem hnot · rw [h1] at hnot ⊢ obtain ⟨q, hq, hSq⟩ := hex p hp (by omega) have heq := he p q hq exact nat_mex_set_eq_one_of_mem ⟨q, hq, by rw [ih n (by omega) q hSq (by omega)]; omega⟩ hnot