AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_run

theoremverifiedimported Lean

Evaluation of the complete Alice-query tree. Fix a depth $d \in \bbn$, a family of binary query functions $\mathrm{query}_i : X \to \mathrm{Bool}$ for $i \in \mathrm{Fin}\,d$, and a family of deterministic protocols $Q(b)$ indexed by bit patterns $b : \mathrm{Fin}\,d \to \mathrm{Bool}$. Then for every pair of inputs $x : X$ and $y : Y$, the protocol that first has Alice read the $d$ query bits in sequence and then runs $Q$ on the collected pattern evaluates on $(x,y)$ to the same value as the single protocol $Q\bigl(i \mapsto \mathrm{query}_i(x)\bigr)$ evaluated on $(x,y)$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
theorem CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_run (d : ℕ) (query : Fin d → X → Bool)
    (Q : (Fin d → Bool) → Deterministic.Protocol X Y α) (x : X) (y : Y) :
    (completeTreeAlice d query Q).run x y = (Q (fun i => query i x)).run x y
Source
TCSlib, `CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_run`
Lean proof
By Lucy Horowitz, Timothe Kasriel, Mihir Singhal, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Lucy Horowitz, Timothe Kasriel, and Mihir Singhal. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
What was changed in CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_run
--- TCSlib/CommunicationComplexity/DeterministicCC/FiniteMessage.lean:121 (CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_run)
+++ as compiled here
@@ -1,4 +1,5 @@
-/-- Running the complete tree of depth `d` on `(x, y)` is the same as running the
-continuation `Q` at the bit vector `i ↦ query i x` on `(x, y)`. -/
-private theorem completeTreeAlice_run (d : ℕ) (query : Fin d → X → Bool)
+set_option relaxedAutoImplicit false in
+set_option autoImplicit false in
+variable {X Y α : Type*} in
+theorem CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_run (d : ℕ) (query : Fin d → X → Bool)
     (Q : (Fin d → Bool) → Deterministic.Protocol X Y α) (x : X) (y : Y) :
@@ -17,3 +18,3 @@
         fun i => query i x := by
-      simpa [Function.comp] using (Fin.cons_self_tail (fun i => query i x))
+      exact Fin.cons_self_tail (fun i => query i x)
     rw [this]
Verified
07 Oct 2026
Axioms
Quot.soundpropext
Built on 4
Used by 1

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false invariable {X Y α : Type*} in/-- Running the complete tree of depth `d` on `(x, y)` is the same as running the continuation `Q` at the bit vector `i ↦ query i x` on `(x, y)`. -/theorem CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_run (d : ℕ) (query : Fin d → X → Bool)    (Q : (Fin d → Bool) → Deterministic.Protocol X Y α) (x : X) (y : Y) :    (completeTreeAlice d query Q).run x y = (Q (fun i => query i x)).run x y := by  induction d with  | zero =>    simp only [completeTreeAlice]    congr; ext i; exact i.elim0  | succ d ih =>    simp only [completeTreeAlice, Deterministic.Protocol.run]    rw [ih]    -- Goal: (Q (Fin.cons (query 0 x) ...)).run x y = (Q (fun i => query i x)).run x y    -- Suffices to show the arguments to Q are equal    have :        Fin.cons (query 0 x) (fun i => (query ∘ Fin.succ) i x) =        fun i => query i x := by      exact Fin.cons_self_tail (fun i => query i x)    rw [this]
See it in the graphDiscuss this resultChallenge it