AFTD Auto-Formalizing Theoretical Domains

arrows_tree_grundy

def

The 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 (Fintype.card V * Fintype.card V).

Statement

noncomputable def arrows_tree_grundy {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] : ℕ
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…
  • ArrowsEmptyPosThe empty starting position in ArrowsPos V whose boolean relation is everywhere false.
  • 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…
Used by 2
  • 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…
  • arrows_realizable_grundy_valuesThe set of natural numbers g such that there exists a finite tree G (a simple graph G on a finite type V satisfying G.IsTree) with…

Read back from the Lean

arrows_tree_grundy defines a function that takes: - a type V with decidable equality ([DecidableEq V]) and a finite instance ([Fintype V]), and - a simple graph G : SimpleGraph V with decidable adjacency ([DecidableRel G.Adj]), and returns the natural number computed by arrows_pos_grundy G (|V| * |V|) (ArrowsEmptyPos V). That is, it computes the Sprague-Grundy value of the "Arrows" game played on G starting from the empty position (no directed edges), using |V| * |V| as the recursion fuel.

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 the empty position of the Game of Arrows on a finite graph G. -/
noncomputable def arrows_tree_grundy {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] : ℕ := arrows_pos_grundy G (Fintype.card V * Fintype.card V) (ArrowsEmptyPos V)
See it in the graphDiscuss this resultChallenge it