spider_blocked_two_three_level_five_options
One 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 of the 19 options the recursion generates, where each option is a coefficient d (written as a numeral) xor spider_gamma at fuel n of the corresponding reduced position, in the exact order in which the recursion enumerates the legs, the cuts j and the two directions.
Statement
theorem spider_blocked_two_three_level_five_options (n : ℕ) :
spider_gamma (n + 1) CentreStatus.none
[(5, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] =
nat_mex_list
[ 0 ^^^ spider_gamma n CentreStatus.incoming [(2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],
1 ^^^ spider_gamma n CentreStatus.outgoing [(2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],
1 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],
0 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],
0 ^^^ spider_gamma n CentreStatus.none [(2, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],
1 ^^^ spider_gamma n CentreStatus.none [(2, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],
1 ^^^ spider_gamma n CentreStatus.none [(3, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],
0 ^^^ spider_gamma n CentreStatus.none [(3, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],
0 ^^^ spider_gamma n CentreStatus.none [(4, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],
1 ^^^ spider_gamma n CentreStatus.incoming [(5, SpiderLegEnd.inward), (3, SpiderLegEnd.free)],
1 ^^^ spider_gamma n CentreStatus.outgoing [(5, SpiderLegEnd.inward), (3, SpiderLegEnd.free)],
0 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.inward), (5, SpiderLegEnd.inward), (3, SpiderLegEnd.free)],
0 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.outward), (5, SpiderLegEnd.inward), (3, SpiderLegEnd.free)],
2 ^^^ spider_gamma n CentreStatus.incoming [(5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)],
2 ^^^ spider_gamma n CentreStatus.outgoing [(5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)],
1 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.inward), (5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)],
1 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.outward), (5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)],
0 ^^^ spider_gamma n CentreStatus.none [(2, SpiderLegEnd.inward), (5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)],
0 ^^^ spider_gamma n CentreStatus.none [(2, SpiderLegEnd.outward), (5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)] ]- Source
- step towards spider_blocked_two_three_level_five
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- spider_gammaThe function spider_gamma computes a natural number from a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider…
- nat_mex_listThe minimum excluded value (mex) of a finite list of natural numbers is the least non-negative integer not in the list.
- 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…
- 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…
- 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…
- CentreStatusThe status of the central vertex in a spider state: none (no marked arcs incident), incoming (at least one incoming arc), outgoing (at…
- Used by 1
- 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.
The proof, explained
The theorem performs one unfolding step of the recursion for the level-5 root state with centre status `none` and legs of lengths 5 (inward), 2 (free), and 3 (free). After rewriting with the recursive definition of `spider_gamma` and removing the outer `nat_mex_list` via `congr_arg`, the goal reduces to showing that the generated list of options equals the specified 19-element list. The proof expands the iteration over the three legs and their explicit cut ranges `List.range 5`, `List.range 2`, and `List.range 3`, and then finishes by finite evaluation with `simp` using `spider_rho` and `spider_update_centre`.
Unfolding `spider_gamma` reduces the equality to showing that the generated list of move options matches the explicit 19-element list.
Rewriting with `spider_gamma.eq_def` and simplifying the pattern matching reduces the left-hand side to `nat_mex_list` applied to the options generated for fuel $n$, centre status `none`, and the given three legs. Applying `congr_arg` with `nat_mex_list` removes the outer mex operator, leaving the goal of proving equality between the generated options list and the target 19-element list.
uses
spider_gamma.eq_def,congr_argrw [spider_gamma.eq_def] dsimp only apply congr_arg nat_mex_list
The options list decomposes into the concatenation of the options generated by each of the three legs.
The definition indexes the three legs via `zipIdx`, producing `[((5, inward), 0), ((2, free), 1), ((3, free), 2)]`. Rewriting with `List.flatMap_cons` for each of the three elements and `List.flatMap_nil` for the empty tail expands the outer list flatMap into three concatenated lists, and `dsimp only` simplifies the pair projections and index-based removals (`eraseIdx`).
uses
List.flatMap_cons,List.flatMap_nilchange List.flatMap _ [((5, SpiderLegEnd.inward), 0), ((2, SpiderLegEnd.free), 1), ((3, SpiderLegEnd.free), 2)] = _ rw [List.flatMap_cons, List.flatMap_cons, List.flatMap_cons, List.flatMap_nil] dsimp only
The cut ranges `List.range h` for legs of lengths 5, 2, and 3 are replaced by their explicit lists of indices.
The cut loop iterates over `List.range h` for each leg. The proof establishes by reflexivity (`rfl`) that `List.range 5 = [0, 1, 2, 3, 4]`, `List.range 2 = [0, 1]`, and `List.range 3 = [0, 1, 2]`. Rewriting with these identities substitutes concrete index lists into each of the three sublists.
have hr5 : List.range 5 = [0, 1, 2, 3, 4] := rfl have hr2 : List.range 2 = [0, 1] := rfl have hr3 : List.range 3 = [0, 1, 2] := rfl rw [hr5, hr2, hr3]
Evaluating the cuts and leg orientations generates exactly the 19 target options, completing the proof.
The `simp` tactic unfolds the definitions of `spider_rho` and `spider_update_centre` and computes all finite loop cases. The length-5 inward leg generates 9 valid moves (2 directions for cut lengths 1 to 4, and 1 direction for cut length 5 because the opposite direction is filtered out); the length-2 free leg generates 4 moves (2 cut lengths $\times$ 2 directions); and the length-3 free leg generates 6 moves (3 cut lengths $\times$ 2 directions). Computing the XOR coefficients and the updated game states for all $9 + 4 + 6 = 19$ cases confirms that the resulting list matches the right-hand side exactly.
simp [spider_rho, spider_update_centre]
spider_gamma.eq_def- The defining equation of `spider_gamma`, which unwinds the recursive evaluation at fuel $n+1$ into `nat_mex_list` applied to the list of available game options.
congr_arg- Equality is preserved under function application: if $a_1 = a_2$, then $f(a_1) = f(a_2)$.
List.flatMap_cons- Mapping and flattening over a non-empty list `x :: xs` equals the list `f x` concatenated with the flat map over `xs`.
List.flatMap_nil- Mapping and flattening over the empty list `[]` produces the empty list `[]`.
- The final step evaluates all 19 transition cases (9 options from the length-5 inward leg, 4 from the length-2 free leg, and 6 from the length-3 free leg) simultaneously using `simp` rather than expanding each cut and direction case-by-case.
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.
/-- The 19-option list of the level-5 root state, at symbolic fuel n+1. -/theorem spider_blocked_two_three_level_five_options (n : ℕ) : spider_gamma (n + 1) CentreStatus.none [(5, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = nat_mex_list [ 0 ^^^ spider_gamma n CentreStatus.incoming [(2, SpiderLegEnd.free), (3, SpiderLegEnd.free)], 1 ^^^ spider_gamma n CentreStatus.outgoing [(2, SpiderLegEnd.free), (3, SpiderLegEnd.free)], 1 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)], 0 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)], 0 ^^^ spider_gamma n CentreStatus.none [(2, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)], 1 ^^^ spider_gamma n CentreStatus.none [(2, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)], 1 ^^^ spider_gamma n CentreStatus.none [(3, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)], 0 ^^^ spider_gamma n CentreStatus.none [(3, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)], 0 ^^^ spider_gamma n CentreStatus.none [(4, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)], 1 ^^^ spider_gamma n CentreStatus.incoming [(5, SpiderLegEnd.inward), (3, SpiderLegEnd.free)], 1 ^^^ spider_gamma n CentreStatus.outgoing [(5, SpiderLegEnd.inward), (3, SpiderLegEnd.free)], 0 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.inward), (5, SpiderLegEnd.inward), (3, SpiderLegEnd.free)], 0 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.outward), (5, SpiderLegEnd.inward), (3, SpiderLegEnd.free)], 2 ^^^ spider_gamma n CentreStatus.incoming [(5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)], 2 ^^^ spider_gamma n CentreStatus.outgoing [(5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)], 1 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.inward), (5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)], 1 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.outward), (5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)], 0 ^^^ spider_gamma n CentreStatus.none [(2, SpiderLegEnd.inward), (5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)], 0 ^^^ spider_gamma n CentreStatus.none [(2, SpiderLegEnd.outward), (5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)] ] := by rw [spider_gamma.eq_def] dsimp only apply congr_arg nat_mex_list change List.flatMap _ [((5, SpiderLegEnd.inward), 0), ((2, SpiderLegEnd.free), 1), ((3, SpiderLegEnd.free), 2)] = _ rw [List.flatMap_cons, List.flatMap_cons, List.flatMap_cons, List.flatMap_nil] dsimp only have hr5 : List.range 5 = [0, 1, 2, 3, 4] := rfl have hr2 : List.range 2 = [0, 1] := rfl have hr3 : List.range 3 = [0, 1, 2] := rfl rw [hr5, hr2, hr3] simp [spider_rho, spider_update_centre]