AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_fork_decode_expand

theoremverified

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
Used by 2

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'.

  1. 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).

    lines 3–4

    uses prioritized_borel_fork_expand, prioritized_borel_fork_hidden_decode

      induction u generalizing h with
      | nil => cases h <;> simp_all [prioritized_borel_fork_expand, prioritized_borel_fork_hidden_decode]
  2. 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.

    lines 5–7

      | cons b u ih =>
          cases h with
          | nil => simp at hlen
  3. When 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'.

    lines 8–10

    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

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]
See it in the graphDiscuss this resultChallenge it