spider_gamma
The function spider_gamma computes a natural number from a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider legs L : List (ℕ × SpiderLegEnd). It is defined by recursion on fuel: if fuel = 0, it returns 0. If fuel = fuel' + 1: if s = CentreStatus.free, it returns the bitwise XOR sum starting from 0 of spider_rho_star h phi for each (h, phi) in L. Otherwise, if L is empty, it returns 0; if L is a singleton [(h, phi)], it returns spider_rho h SpiderLegEnd.outward phi if s = CentreStatus.incoming, spider_rho h SpiderLegEnd.inward phi if s = CentreStatus.outgoing, and 0 if s = CentreStatus.none; if L has at least two elements, it returns nat_mex_list of options collected over each leg (h, phi) at index idx in L, with rest = L.eraseIdx idx, each integer j from 1 to h, and each direction delta in {SpiderLegEnd.inward, SpiderLegEnd.outward}: skipping when j = h, phi ≠ SpiderLegEnd.free, and delta ≠ phi; otherwise letting d = spider_rho (h - j) delta phi and taking d ^^^ spider_gamma fuel' s ((j - 1, delta) :: rest) if j ≥ 2, and d ^^^ spider_gamma fuel' (spider_update_centre s delta) rest if j = 1.
Statement
def spider_gamma (fuel : ℕ) (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)) : ℕ- Defined in
- scout/2610-15145-nim-heaps-in-the-game-of-cycles-the-parity-conjecture-fails.md, Proposition 6.1
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Built on 6
- spider_rhoThe function spider_rho takes h : ℕ and delta, phi : SpiderLegEnd, returning h if phi = free; if phi = inward, it returns h % 2 when delta…
- spider_rho_starThe function spider_rho_star takes h : ℕ and phi : SpiderLegEnd, returning h % 2 if phi = free, and h otherwise.
- spider_update_centreThe function spider_update_centre updates centre status s given leg transition delta: if delta is inward, none maps to incoming, incoming…
- nat_mex_listThe minimum excluded value (mex) of a finite list of natural numbers is the least non-negative integer not in the list.
- CentreStatusThe status of the central vertex in a spider state: none (no marked arcs incident), incoming (at least one incoming arc), outgoing (at…
- SpiderLegEndThe end condition of an attached leg in a spider state is either free (no arc on the leg), inward (pointing towards the centre), or…
- Used by 41
- spider_blocked_two_three_level_fourAt level t = 4, the inward blocked family for the configuration (none; {2^*, 3^*}) at canonical fuel 10 is at most 7.
- spider_gamma_rotate_three_short_legsFor any leg p, centre status and fuel, the value of (s;{p,1^in,1^out}) equals the value of (s;{1^in,1^out,p}): the leg p may be moved from…
- spider_blocked_incoming_one_outwardFor the configuration κ₂ = (in;{(1,outward)}), the blocked family V^φ_κ₂(r) equals r xor 1 for every r ≥ 1 and both φ.
- spider_blocked_two_three_reversalFor any fuel and leg length t, the spider gamma value with centre none and legs (t, outward), (2, free), (3, free) equals the gamma value…
- spider_blocked_incoming_one_outward_options_eqFor r ≥ 2, the raw options list generated by [(1, outward), (r, φ)] at fuel r + 2 with centre status incoming unfolds to the explicit list…
- spider_gamma_root_optionsThe option list of the root state S(1,2,z) at fuel N+1 (with z = m+1 and N ≥ 3) is the mex of 8 explicit "head" options together with the…
- spider_blocked_two_three_level_fiveAt level t = 5, the inward blocked family for the configuration (none; {2^*, 3^*}) at canonical fuel 11 is at most 7.
- spider_blocked_raw_opts_splitThe raw option list of (in;{(r,β),(1,free)}) decomposes as spider_blocked_leg0_opts r β ++ spider_blocked_free_leg_opts r β: the zipIdx…
- spider_blocked_none_one_inward_one_outward_opts_eqFor r ≥ 2, φ ≠ free, and assuming the closed form for all smaller levels, the mex of the raw option list equals the mex of the explicit…
- spider_two_leg_short_short_zeroAt any fuel at least 3, the two-leg state with centre incoming and legs (1,inward),(1,outward) has value 0, and likewise with centre…
- spider_blocked_leg0_optsThe contribution of the blocked leg (r,β) alone to the raw option list of (in;{(r,β),(1,free)}): for each cut j₀ = 0,…,r-1 of that leg,…
- spider_blocked_free_leg_optsThe contribution of the free leg (1,free) alone to the raw option list of (in;{(r,β),(1,free)}): the unique cut j = 1 with direction δ…
- spider_blocked_two_three_level_five_sub_long_leg_j34With free centre, the state obtained from (none;{(5,inward),2^*,3^*}) by cutting the (5,inward) leg at j = 4 leaves a leg of length 2 with…
- spider_eventual_parity_two_three_centre_constThe paper's constant W_in(κ0) = Γ(in;{2^*,3^*}) and W_out(κ0) = Γ(out;{2^*,3^*}) for the configuration κ0 = (n;{2^*,3^*}) both equal 3.
- spider_blocked_two_three_level_five_sub_sum_nineFour sub-states at fuel 10: the states (incoming;{(5,inward),(3,free)}) and (outgoing;{(5,inward),(3,free)}) have value 4 and 6, and the…
- spider_blocked_two_three_level_five_sub_long_leg_j34_outwardWith free centre, the state whose legs are a length-2 leg with far end outward, the (5,inward) leg, and the free leg 2 has Grundy value 1…
- spider_mex_two_leg_one_freeGiven an explicit options list where every element has parity k % 2, the minimum excluded value is 1 - k % 2 (which is 1 when k is even,…
- spider_blocked_incoming_one_outward_oneFor the configuration κ₂ = (in;{(1,outward)}), the blocked family V^φ_κ₂(1) equals 1 ^^^ 1 for both φ ≠ free.
- spider_gamma_swap_twoThe Grundy value of a two-legged spider state is invariant under swapping the two legs in the list.
- spider_blocked_none_one_inward_one_outwardFor the configuration κ₁ = (none;{(1,inward),(1,outward)}), the blocked family V^φ_κ₁(r) equals r for every r ≥ 1 and both φ.
- spider_gamma_fuel_independentFor every fuel at least the total number of markable edges in L plus one, the value of spider_gamma does not depend on the fuel: it equals…
- spider_blocked_raw_optsThe raw option list of the state (in;{(r,β),(1,free)}) after exactly one unfolding step of spider_gamma at fuel r+2, with the *sub-state…
- spider_blocked_none_one_inward_one_outward_raw_opts_eqFor r ≥ 2 and φ ≠ free, the value of (none;{(1,inward),(1,outward),(r,φ)}) at fuel r+3 is the mex of the raw option list…
- spider_blocked_none_one_inward_one_outward_baseThe base case r = 1 of the κ₁ blocked family: for both far ends φ ≠ free, (none;{1^in,1^out,(1,φ)}) at canonical fuel 4 has value 1.
- spider_blocked_two_three_level_five_sub_long_leg_j34_inwardWith free centre, the state whose legs are a length-2 leg with far end inward, the (5,inward) leg, and the free leg 2 has Grundy value 0…
- spider_two_leg_blocked_incoming_baseThe closed form holds at r = 0 and r = 1: spider_gamma 2 incoming [(0,inward),(1,free)] = 1, spider_gamma 2 incoming…
- spider_blocked_two_three_level_five_sub_sum_sevenThe two sub-states with free centre where a leg of length 2 with far end inward (resp. outward) is added to the free legs 2 and 3 have…
- spider_none_one_inward_one_outward_raw_optsThe raw option list of the state (none;{(1,inward),(1,outward),(r,φ)}) after one unfolding step, in the exact order the recursion…
- spider_blocked_two_three_level_five_sub_long_leg_j4_inwardWith free centre, the state whose legs are the (4,inward) leg together with the free legs 2 and 3 has Grundy value 5 at fuel 10.
- spider_blocked_two_three_level_five_sub_incoming_two_threeWith centre incoming (resp. outgoing) and free legs of length 2 and 3, the value at fuel 10 is 3 (both).
- spider_blocked_two_three_level_five_sub_long_leg_j4Cutting the (5,inward) leg at j = 5 leaves, besides the free legs 2 and 3, a leg of length 4; at fuel 10 the value is 5 both when that…
- spider_grundy_valThe Grundy value spider_grundy_val of the 3-legged spider tree with leg parameters x, y, z : ℕ is defined as spider_gamma (x + y + z + 1)…
- spider_blocked_two_three_level_five_sub_sum_eightFour sub-states at fuel 10: the two states obtained by cutting the long leg at j = 4, which add a leg of length 3 with far end inward…
- spider_eventual_parity_two_three_blocked_smallFor the configuration κ0 = (none;{2^*,3^*}), the blocked family at level t is 2 for t = 1 and 6 for t = 2, for both far ends, and it is at…
- spider_blocked_incoming_one_inward_options_nonemptyThe options list generated by [(1, inward), (r, φ)] at incoming centre is non-empty.
- spider_blocked_two_three_level_five_sub_sum_sixThe two sub-states with free centre, a short leg of length 1 whose far end is inward (resp. outward), and the free legs 2 and 3, have…
- spider_two_leg_one_free_options_eqThe raw zipIdx.flatMap options list of [(1, free), (k, free)] at fuel k + 2 with incoming centre status unfolds to the explicit list [k, k…
- spider_blocked_two_three_level_five_optionsOne unfolding step of the recursion for the level-5 root state (none;{(5,inward),2^*,3^*}) at fuel n+1: the value is the mex of the list…
- spider_blocked_two_three_level_five_sub_short_legsWith centre incoming (resp. outgoing) and the legs (5,inward) and the free leg 2, the value at fuel 10 is 0 (resp. 1).
- spider_blocked_outgoing_one_inwardFor the mirror configuration (out;{(1,inward)}), the blocked family at level r equals r xor 1 for every r ≥ 1 and both far ends φ.
- spider_gamma_reversalFor every fuel, centre status s and leg list L, the value of the spider state (s;L) equals the value of the state obtained by exchanging…
Read back from the Lean
The definition spider_gamma computes a natural number recursively using a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider legs L : List (ℕ × SpiderLegEnd).
The computation proceeds by matching on fuel:
1. If fuel = 0, it returns 0.
2. If fuel = fuel' + 1:
- If s = .free, it returns the bitwise XOR sum (nim-sum) over all pairs (h, phi) ∈ L of spider_rho_star h phi, initialized at 0.
- If s ≠ .free (i.e., s is none, incoming, or outgoing):
- If L is empty ([]), it returns 0.
- If L is a singleton [(h, phi)]:
- If s = .incoming, it returns spider_rho h .outward phi.
- If s = .outgoing, it returns spider_rho h .inward phi.
- If s = .none, it returns 0.
- If L contains at least two elements:
It constructs a list options : List ℕ by iterating over each leg (h, phi) in L at 0-based index idx:
- Let rest be L with the element at idx removed.
- For each integer j from 1 to h (inclusive):
- For each direction delta ∈ [.inward, .outward]:
- If j = h, phi ≠ .free, and delta ≠ phi, this transition is omitted (none).
- Otherwise, let d = spider_rho (h - j) delta phi:
- If j ≥ 2, it appends d ^^^ spider_gamma fuel' s ((j - 1, delta) :: rest) to the options.
- If j < 2 (i.e., j = 1), it appends d ^^^ spider_gamma fuel' (spider_update_centre s delta) rest to the options.
Finally, it returns nat_mex_list options, the minimal excludant (mex) of options.
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
/-- Grundy value Γ(s; L) of a spider state with centre status s and attached legs L. -/ def spider_gamma (fuel : ℕ) (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)) : ℕ := match fuel with | 0 => 0 | fuel + 1 => match s with | .free => L.foldl (fun acc p => acc ^^^ spider_rho_star p.1 p.2) 0 | _ => match L with | [] => 0 | [(h, phi)] => match s with | .incoming => spider_rho h .outward phi | .outgoing => spider_rho h .inward phi | _ => 0 | _ => let options : List ℕ := L.zipIdx.flatMap (fun ⟨⟨h, phi⟩, idx⟩ => let rest := L.eraseIdx idx (List.range h).flatMap (fun j_zero => let j := j_zero + 1 [SpiderLegEnd.inward, SpiderLegEnd.outward].filterMap (fun delta => if j == h ∧ phi ≠ .free ∧ delta ≠ phi then none else let d := spider_rho (h - j) delta phi if j ≥ 2 then let new_L := (j - 1, delta) :: rest some (d ^^^ spider_gamma fuel s new_L) else let new_s := spider_update_centre s delta some (d ^^^ spider_gamma fuel new_s rest) ) ) ) nat_mex_list options