Theorem 3.2 — common-tree safety representation
OpenCausalFailureRank.Supplement.theorem_3_2Consider the current-window tool game with known stage order and a laminar compatibility family. If , augment the distinct nonempty compatibility sets by and every singleton to obtain one inclusion tree with nodes. For every suffix and budget , the safety family is either VOID or for a normalized integer capacity vector on this same tree, and
The table recovers for every . At every nonterminal stage with , it returns an actual compatible tool attaining
Uniform constants bound preprocessing by elementary integer operations, storage by bits, and either query by operations. Capacities and counts lie in ; for these become and . Constructing the tree and checking laminarity from incidence input uses set-membership operations. If , no tree is needed: the rank is while a stage remains and at termination.
This is a compact exact representation of the adaptive causal allocation game, not offline matchability.
Differences from the source:
- encoding: stages , budgets , nonnegative integer capacities, and the separate symbol
VOID→ 0-basedFin (N+1)/Fin (q+2), natural-valued capacities, andOption.none; reason: these are bijective Lean encodings, andnoneremains distinct from the zero capacity vector - encoding: a capacity vector indexed only by nodes → a total function on finite tool sets whose values are constrained and read only on ; reason: coordinates outside the finite node set are ignored, so this represents exactly the same node-indexed data
- encoding: asymptotic operation/storage bounds written with → positive universal constants quantified before all game parameters and explicit inequalities; reason: this is the literal uniform meaning of the displayed complexity bounds
import Mathlib import Definitions.Def_CausalFailureRank_Supplement_safetyTable set_option autoImplicit false
namespace CausalFailureRank
namespace Supplement
/-- **Theorem 3.2 (Common-tree safety representation).** Zang, Li, Jin, Xu, *Causal
Failure Rank Determines Statistical Depth*, preprint (STOC 2027 submission, version of
2026-11-03, sha256 721c8b0d…), Theorem 3.2, p.8 (PDF p.9).
For every known-order laminar current-window tool game with at least one tool, one augmented
inclusion tree represents every suffix safety family and every budget `0,…,q+1`. Membership is
exactly the causal allocation game, the table recovers every rank and an actual compatible
maximizing tool, and its capacities, storage, preprocessing, query, and incidence-input tree
construction satisfy the printed bounds. The zero-tool boundary is included.
**Formalization Note.** Stages are 0-based. `none` is `VOID`, whereas `some 0` represents a family
containing the empty used set. The four constants precede every game parameter, so all `O(·)`
bounds are uniform. Operation counts are the elementary integer and set-membership work units of
the paper. The rank is the published adaptive causal game rank (`∃` one causal allocator, `∀`
future patterns), not offline matchability. -/
theorem theorem_3_2 :
∃ Cpre Cstore Cquery Ctree : ℕ,
0 < Cpre ∧ 0 < Cstore ∧ 0 < Cquery ∧ 0 < Ctree ∧
∀ (N q : ℕ) (S : Fin N → Finset (Fin q)), IsLaminar S →
(0 < q → ∃ T : SafetyTable S,
T.Correct ∧
T.tree.card ≤ N + q + 1 ∧
T.preprocessOps ≤ Cpre * (N + 1) * (q + 1) * T.tree.card ∧
T.storageBits ≤
Cstore * (N + 1) * (q + 1) * T.tree.card * Nat.log2 (q + 2) ∧
(∀ i R, T.rankQueryOps i R ≤ Cquery * (q + 1) * T.tree.card) ∧
(∀ i R, T.toolQueryOps i R ≤ Cquery * (q + 1) * T.tree.card) ∧
T.treeConstructionOps ≤ Ctree * (N + q + 1) ^ 2 * q ∧
(0 < N →
T.preprocessOps ≤ 4 * Cpre * N * q * T.tree.card ∧
(∀ i R, T.rankQueryOps i R ≤ 2 * Cquery * q * T.tree.card) ∧
∀ i R, T.toolQueryOps i R ≤ 2 * Cquery * q * T.tree.card)) ∧
(q = 0 →
(∀ i R, i < N → gameRank S i R = 1) ∧
∀ i R, N ≤ i → gameRank S i R = ⊤) := by sorry
end Supplement
end CausalFailureRank