arrows_pos_grundy
The 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 minimum excluded natural number (nat_mex_set) of the values of legal moves q at depth fuel' when fuel = fuel' + 1.
Statement
noncomputable def arrows_pos_grundy {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (fuel : ℕ) (p : ArrowsPos V) : ℕ
- Defined in
- arXiv:2610.15145 Section 2.2
- Verified
- 24 Oct 2026
- Axioms
- none listed
- Built on 3
- 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…
- 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_setThe minimum excluded natural number of a set s of natural numbers is the infimum of the set of natural numbers not in s.
- Used by 3
- 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…
- 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…
- 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…
Read back from the Lean
arrows_pos_grundy is a function that, given a type V with decidable equality and a Fintype instance, a simple graph G on V with decidable adjacency, a recursion depth bound fuel : ℕ, and a partial orientation p : ArrowsPos V, recursively computes a natural number (the Grundy / mex-value bounded by fuel) as follows:
- When fuel = 0, it returns 0.
- When fuel = fuel' + 1, it returns the minimum excluded natural number (nat_mex_set) of the set of values arrows_pos_grundy G fuel' q over all positions q : ArrowsPos V such that ArrowsLegalMove G p q holds.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The Grundy value of a Game of Arrows position p under fuel recursion, using the minimum excluded value over all legal moves. -/ noncomputable def arrows_pos_grundy {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (fuel : ℕ) (p : ArrowsPos V) : ℕ := match fuel with | 0 => 0 | fuel + 1 => nat_mex_set { n : ℕ | ∃ q, ArrowsLegalMove G p q ∧ n = arrows_pos_grundy G fuel q }