AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_record_replay

theoremverified

A compatible finite history can be reconstructed from its length and the sequence of choices at opponent-controlled branching positions.

Statement

theorem prioritized_borel_record_replay {A : Type} (own branch : List A → Bool)
    (policy forced : List A → A) (hist xs : List A)
    (h : op1385Compatible own branch policy forced hist xs) :
    op1385Replay own branch policy forced hist (op1385Record own branch hist xs) xs.length =
      some (hist ++ xs, [])
Source
Strategy reconstruction for arXiv:2611.10136, Conjecture 19.
Verified
13 Nov 2026
Axioms
propext
Used by 2

The proof, explained

The theorem is proved by structural induction on the move sequence xs, generalizing over the initial history hist. The base case xs = [] holds directly by unfolding the definitions of recording and replaying. For the inductive step xs = a :: rest, a four-way case analysis on whether the position is player-controlled (own hist) and whether it is branching (branch hist) shows that replay executes the exact action determined by compatibility, allowing the induction hypothesis on the extended history hist ++ [a] to complete each case via list concatenation associativity.

  1. For the empty sequence `xs = []`, replaying 0 steps with the empty record yields `some (hist, [])`.

    We argue by induction on `xs`, generalizing over `hist`. In the base case `xs = []`, the record `op1385Record own branch hist []` is `[]` and the length is 0. By definition, `op1385Replay` for 0 steps immediately returns `some (hist, [])`, which matches `some (hist ++ [], [])` since `hist ++ [] = hist`.

    lines 32–33

    uses op1385Record, op1385Replay

      induction xs generalizing hist with
      | nil => simp [op1385Record, op1385Replay]
  2. For `xs = a :: rest`, we unpack the compatibility condition for action `a` and split into four cases based on `own hist` and `branch hist`.

    In the inductive step, the induction hypothesis `ih` applies to any history. Unfolding the definition of `op1385Compatible` at `a :: rest` separates the compatibility requirement on the first action `a` (conjunct `h.1`) from the compatibility of `rest` starting from `hist ++ [a]` (conjunct `h.2`). We then perform a four-way case analysis on the boolean values of `own hist` and `branch hist`.

    lines 34–36

    uses op1385Compatible

      | cons a xs ih =>
        simp only [op1385Compatible] at h
        cases ho : own hist <;> cases hb : branch hist
  3. When the position is opponent-controlled and non-branching (`own hist = false`, `branch hist = false`), replay correctly reconstructs `forced hist :: rest`.

    Since `own hist = false` and `branch hist = false`, compatibility (`h.1`) forces `a = forced hist`. Substituting this into the goal, the action is not recorded by `op1385Record`, and one step of `op1385Replay` executes `forced hist`. Applying the induction hypothesis `ih` to the extended history `hist ++ [forced hist]` with `h.2`, together with associativity of list concatenation `(hist ++ [forced hist]) ++ rest = hist ++ (forced hist :: rest)`, closes this case.

    lines 37–39

    uses op1385Record, op1385Replay, List.append_assoc

        · have ha : a = forced hist := by simpa [ho, hb] using h.1
          subst a
          simpa [op1385Record, op1385Replay, ho, hb, List.append_assoc] using ih (hist ++ [forced hist]) h.2
  4. When the position is opponent-controlled and branching (`own hist = false`, `branch hist = true`), replay consumes `a` from the record and reconstructs `a :: rest`.

    With `own hist = false` and `branch hist = true`, `op1385Record` places `a` at the head of the log. One step of `op1385Replay` inspects the non-empty log, extracts `a`, and advances the history to `hist ++ [a]`. Applying the induction hypothesis to `hist ++ [a]` with tail compatibility `h.2` and reassociating list concatenation completes this branch.

    line 40

    uses op1385Record, op1385Replay, List.append_assoc

        · simpa [op1385Record, op1385Replay, ho, hb, List.append_assoc] using ih (hist ++ [a]) h.2
  5. When the position is player-controlled and non-branching (`own hist = true`, `branch hist = false`), replay executes `policy hist` and reconstructs `policy hist :: rest`.

    Because `own hist = true`, compatibility (`h.1`) dictates `a = policy hist`. Substituting `policy hist` for `a`, the move is not added to the opponent record, and `op1385Replay` executes `policy hist`. Applying the induction hypothesis to `hist ++ [policy hist]` using `h.2` and list associativity finishes this case.

    lines 41–43

    uses op1385Record, op1385Replay, List.append_assoc

        · have ha : a = policy hist := by simpa [ho, hb] using h.1
          subst a
          simpa [op1385Record, op1385Replay, ho, hb, List.append_assoc] using ih (hist ++ [policy hist]) h.2
  6. When the position is player-controlled and branching (`own hist = true`, `branch hist = true`), replay executes `policy hist` and reconstructs `policy hist :: rest`.

    Even though `branch hist = true`, player ownership (`own hist = true`) takes priority: compatibility requires `a = policy hist`, and the move is omitted from the opponent record. Replay executes `policy hist`, and the induction hypothesis combined with list associativity completes the final case.

    lines 44–46

    uses op1385Record, op1385Replay, List.append_assoc

        · have ha : a = policy hist := by simpa [ho, hb] using h.1
          subst a
          simpa [op1385Record, op1385Replay, ho, hb, List.append_assoc] using ih (hist ++ [policy hist]) h.2
op1385Compatible
A predicate defining when a sequence of moves from a given history is compatible with the game policy: moves must match `policy` on player turns and `forced` on opponent non-branching turns, while opponent branching moves are unconstrained.
op1385Record
A function that extracts from a sequence of moves only those choices made at opponent-controlled branching positions (where `own hist` is false and `branch hist` is true).
op1385Replay
A simulation function that reconstructs `n` moves from an initial history and a recorded list of opponent choices: on player turns it plays `policy`, on opponent branching turns it consumes the next recorded move, and on opponent non-branching turns it plays `forced`.
List.append_assoc
Associativity of list concatenation: `(as ++ bs) ++ cs = as ++ (bs ++ cs)`.

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

def op1385Compatible {A : Type} (own branch : List A → Bool)    (policy forced : List A → A) : List A → List A → Prop  | _, [] => True  | hist, a :: rest =>    (if own hist then a = policy hist else if branch hist then True else a = forced hist) ∧      op1385Compatible own branch policy forced (hist ++ [a]) restdef op1385Record {A : Type} (own branch : List A → Bool) : List A → List A → List A  | _, [] => []  | hist, a :: rest =>    if !own hist && branch hist then      a :: op1385Record own branch (hist ++ [a]) rest    else op1385Record own branch (hist ++ [a]) restdef op1385Replay {A : Type} (own branch : List A → Bool)    (policy forced : List A → A) : List A → List A → ℕ → Option (List A × List A)  | hist, record, 0 => some (hist, record)  | hist, record, n + 1 =>    if own hist then      op1385Replay own branch policy forced (hist ++ [policy hist]) record n    else if branch hist then      match record with      | [] => none      | a :: tail => op1385Replay own branch policy forced (hist ++ [a]) tail n    else op1385Replay own branch policy forced (hist ++ [forced hist]) record ntheorem prioritized_borel_record_replay {A : Type} (own branch : List A → Bool)    (policy forced : List A → A) (hist xs : List A)    (h : op1385Compatible own branch policy forced hist xs) :    op1385Replay own branch policy forced hist (op1385Record own branch hist xs) xs.length =      some (hist ++ xs, []) := by  induction xs generalizing hist with  | nil => simp [op1385Record, op1385Replay]  | cons a xs ih =>    simp only [op1385Compatible] at h    cases ho : own hist <;> cases hb : branch hist    · have ha : a = forced hist := by simpa [ho, hb] using h.1      subst a      simpa [op1385Record, op1385Replay, ho, hb, List.append_assoc] using ih (hist ++ [forced hist]) h.2    · simpa [op1385Record, op1385Replay, ho, hb, List.append_assoc] using ih (hist ++ [a]) h.2    · have ha : a = policy hist := by simpa [ho, hb] using h.1      subst a      simpa [op1385Record, op1385Replay, ho, hb, List.append_assoc] using ih (hist ++ [policy hist]) h.2    · have ha : a = policy hist := by simpa [ho, hb] using h.1      subst a      simpa [op1385Record, op1385Replay, ho, hb, List.append_assoc] using ih (hist ++ [policy hist]) h.2
See it in the graphDiscuss this resultChallenge it