prioritized_borel_fork_decode_expand
Expanding equally long visible and hidden block histories and decoding the result recovers the hidden history.
Statement
theorem prioritized_borel_fork_decode_expand (u h : List Bool) (hlen : u.length = h.length) :
prioritized_borel_fork_hidden_decode (prioritized_borel_fork_expand u h) = h- Source
- arXiv:2611.10136, Section 5.3.2; the three-state fork subarena
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- prioritized_borel_fork_expandExpand equally indexed visible bits and hidden stay-or-excursion choices into three-edge blocks.
- prioritized_borel_fork_hidden_decodeRecover the hidden stay-or-excursion choices from the first edge of each three-edge block.
- prioritized_borel_fork_three_step_blockA three-edge stay or excursion with common output directions false, false, then the supplied bit.
- PrioritizedBorelForkEdgeOne edge of the three-state fork arena, recording source, direction, target, and priority.
- Used by 2
- prioritized_borel_fork_strategy_fixed_branchFor any history-dependent strategy and finite-memory assignment in the three-state fork arena, there are one infinite visible block…
- prioritized_borel_fork_unbounded_same_memoryFor any history-dependent excursion choice and finite-memory assignment, arbitrarily many distinct legal runs from q to q share their…
The proof, explained
The proof proceeds by induction on the visible history u, generalizing over the hidden history h. In the base case, the length equality forces h to be empty, and expanding followed by decoding trivially yields the empty list. In the inductive step where u = b :: u', the length equality ensures h is non-empty (c :: h') with |u'| = |h'|; case analysis on the boolean c reveals that the three-step block encodes c in the destination of its first edge, which the decoder recovers before inductively decoding the remaining edges into h'.
The theorem holds when the visible history u is empty.
We proceed by induction on u, generalizing over h. When u is empty, we perform case analysis on h. If h is also empty, expanding both empty lists produces an empty edge list, which decodes to the empty list. If h were non-empty, its length would be at least 1, contradicting the hypothesis that u and h have equal lengths (0 = h.length).
uses
prioritized_borel_fork_expand,prioritized_borel_fork_hidden_decodeinduction u generalizing h with | nil => cases h <;> simp_all [prioritized_borel_fork_expand, prioritized_borel_fork_hidden_decode]
In the inductive step for u = b :: u', the hidden history h cannot be empty.
Assuming the induction hypothesis for u', we inspect h. If h were empty, the equality of lengths hlen would assert that |u'| + 1 = 0, an arithmetic impossibility that is ruled out by simplification.
| cons b u ih => cases h with | nil => simp at hlenWhen h = c :: h', decoding the expansion of b :: u' and c :: h' recovers c :: h', completing the induction.
Simplifying the length equality |b :: u'| = |c :: h'| removes 1 from both sides to establish |u'| = |h'|, allowing the use of the induction hypothesis on the tail lists. We then case split on the boolean c. Expanding the definitions shows that the first edge in the three-step block has destination 1 when c is true and 0 when c is false; the decoder tests this destination against 1, successfully extracting the boolean c. The decoder then continues on the remainder of the edge list, which by the induction hypothesis decodes to h'.
uses
prioritized_borel_fork_expand,prioritized_borel_fork_three_step_block,prioritized_borel_fork_hidden_decode| cons c h => have hh : u.length = h.length := by simpa using hlen cases c <;> simp [prioritized_borel_fork_expand, prioritized_borel_fork_three_step_block, prioritized_borel_fork_hidden_decode, ih h hh]
prioritized_borel_fork_expand- Expands two boolean lists into a list of prioritized Borel fork edges by concatenating three-step blocks for each corresponding pair of bits.
prioritized_borel_fork_hidden_decode- Decodes a list of edges into a boolean list by checking whether the destination node of the first edge in each three-step block is 1.
prioritized_borel_fork_three_step_block- Constructs a three-step block of edges from a visible bit and an exit bit, setting the destination of the first edge to 1 if the exit bit is true and to 0 if false.
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 prioritized_borel_fork_decode_expand (u h : List Bool) (hlen : u.length = h.length) : prioritized_borel_fork_hidden_decode (prioritized_borel_fork_expand u h) = h := by induction u generalizing h with | nil => cases h <;> simp_all [prioritized_borel_fork_expand, prioritized_borel_fork_hidden_decode] | cons b u ih => cases h with | nil => simp at hlen | cons c h => have hh : u.length = h.length := by simpa using hlen cases c <;> simp [prioritized_borel_fork_expand, prioritized_borel_fork_three_step_block, prioritized_borel_fork_hidden_decode, ih h hh]