CommunicationComplexity.Deterministic.FiniteMessage.Protocol.encode_alice
Binary encoding of a finite-alphabet message from Alice. Let $X$, $Y$, and $\alpha$ be types, let $\beta$ be a finite nonempty type, let $f : X \to \beta$ be a function, and let $Q : \beta \to \mathrm{Protocol}\,X\,Y\,\alpha$ assign to each value $b \in \beta$ a deterministic two-party communication protocol. Then there exists a deterministic protocol $R$ over the same input types such that, on every pair of inputs $x : X$ and $y : Y$, running $R$ yields the same output as running the protocol $Q(f(x))$, and the communication complexity of $R$ equals \[ \lceil \log_2 \abs{\beta} \rceil \;+\; \max_{b \in \beta} \operatorname{complexity}(Q(b)), \] where $\abs{\beta}$ denotes the cardinality of $\beta$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in theorem CommunicationComplexity.Deterministic.FiniteMessage.Protocol.encode_alice {X Y α β : Type*} [Fintype β] [Nonempty β] (f : X → β) (Q : β → Deterministic.Protocol X Y α) : ∃ R : Deterministic.Protocol X Y α, (∀ x y, R.run x y = (Q (f x)).run x y) ∧ R.complexity = Nat.clog 2 (Fintype.card β) + Finset.univ.sup (fun b => (Q b).complexity)
- Source
- TCSlib, `CommunicationComplexity.Deterministic.FiniteMessage.Protocol.encode_alice`
- 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.CommunicationComplexity.Deterministic.FiniteMessage.Protocol.encode_alice← CommunicationComplexity.Deterministic.FiniteMessage.Protocol.encode_alice (TCSlib/CommunicationComplexity/DeterministicCC/FiniteMessage.lean:200): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- CommunicationComplexity.Deterministic.Protocol.complexityThe communication complexity of a protocol $p$ is the worst-case total number of bits exchanged: an output node costs $0$, while an alice…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_complexityComplexity of the complete Alice-query tree. Fix a natural number $d$, together with binary query functions…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAliceAn auxiliary construction: given $d$ binary query functions $\mathrm{query}_i : X \to \mathrm{Bool}$ and a family of binary protocols…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_runEvaluation of the complete Alice-query tree. Fix a depth $d \in \bbn$, a family of binary query functions…
- CommunicationComplexity.Deterministic.ProtocolA deterministic two-party communication protocol over input types $X$ (Alice) and $Y$ (Bob) producing a value of type $\alpha$ is an…
- CommunicationComplexity.Deterministic.Protocol.runGiven a protocol $p$,
runevaluates $p$ on inputs $x : X$ and $y : Y$ by recursively following the bit-branching structure until…
- Used by 1
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toProtocol_existsBinary simulation of a finite-message protocol. Let $X$, $Y$, and $\alpha$ be types, and let $p$ be a finite-message two-party protocol…
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.
set_option relaxedAutoImplicit false inset_option autoImplicit false invariable {X Y α : Type*} in/-- Given a function `f : X → β` and binary protocols `Q b` for each `b : β`, there is a single binary protocol `R` that behaves like `Q (f x)` on every input and whose complexity is exactly `⌈log₂ |β|⌉` plus the maximum complexity of the `Q b`: Alice sends `f x` encoded in `⌈log₂ |β|⌉` bits via a complete binary tree, then the parties continue with `Q (f x)`. **Proof sketch.** Let `d = ⌈log₂ |β|⌉`. (1) Encode `β` injectively into `Fin d → Bool` by composing `Fintype.equivFin` with the binary digits: injectivity holds because `|β| ≤ 2 ^ d`, so bits at positions `≥ d` are all zero. (2) Let Alice's `i`-th query on input `x` be the `i`-th bit of `encode (f x)`. (3) Define the continuation at a bit vector: if the vector encodes some (necessarily unique) `b`, continue with `Q b`, otherwise with `Q b₀` for a fixed `b₀`. Take `R` to be the complete Alice tree of depth `d` with these queries and continuations. (4) Outcome: by `completeTreeAlice_run` the tree reaches the continuation at `encode (f x)`, which is `Q (f x)` by injectivity. (5) Complexity: by `completeTreeAlice_complexity` it is `d + sup` over bit vectors of the continuation's complexity, and that supremum equals `sup_b (Q b).complexity` because every continuation is some `Q b` and every `Q b` occurs (at `encode b`). -/theorem CommunicationComplexity.Deterministic.FiniteMessage.Protocol.encode_alice {X Y α β : Type*} [Fintype β] [Nonempty β] (f : X → β) (Q : β → Deterministic.Protocol X Y α) : ∃ R : Deterministic.Protocol X Y α, (∀ x y, R.run x y = (Q (f x)).run x y) ∧ R.complexity = Nat.clog 2 (Fintype.card β) + Finset.univ.sup (fun b => (Q b).complexity) := by have hcard : 0 < Fintype.card β := Fintype.card_pos let b₀ : β := (Fintype.equivFin β).symm ⟨0, hcard⟩ let d := Nat.clog 2 (Fintype.card β) -- Step 1: binary encoding `β → (Fin d → Bool)` via `Fintype.equivFin` then `testBit`, -- injective because `|β| ≤ 2 ^ d` let encode : β → (Fin d → Bool) := fun b => fun i => (Fintype.equivFin β b).val.testBit i.val have hencode_inj : Function.Injective encode := by intro a b hab apply (Fintype.equivFin β).injective; apply Fin.ext apply Nat.eq_of_testBit_eq; intro i by_cases hi : i < d · exact congr_fun hab ⟨i, hi⟩ · have hd : Fintype.card β ≤ 2 ^ d := Nat.le_pow_clog (by norm_num) _ have hle := hd.trans (Nat.pow_le_pow_right (by norm_num) (not_lt.mp hi)) rw [Nat.testBit_eq_false_of_lt (lt_of_lt_of_le (Fintype.equivFin β a).isLt hle), Nat.testBit_eq_false_of_lt (lt_of_lt_of_le (Fintype.equivFin β b).isLt hle)] -- Upgrade ∃ to ∃! using injectivity, for use with Fintype.choose have hencode_unique : ∀ bits, (∃ b, encode b = bits) → ∃! b, encode b = bits := by intro bits ⟨b, hb⟩; exact ⟨b, hb, fun c hc => hencode_inj (hc.trans hb.symm)⟩ -- Step 2: Alice's queries are the bits of `encode (f x)` let query : Fin d → X → Bool := fun i x => encode (f x) i -- Step 3: the continuation at each bit pattern, decoding via `Fintype.choose` when possible let leafQ : (Fin d → Bool) → Deterministic.Protocol X Y α := fun bits => if h : ∃ b, encode b = bits then Q (Fintype.choose (fun b => encode b = bits) (hencode_unique bits h)) else Q b₀ refine ⟨completeTreeAlice d query leafQ, ?_, ?_⟩ · -- Step 4: outcome — the tree reaches the continuation at `encode (f x)`, i.e. `Q (f x)` intro x y rw [completeTreeAlice_run] have hquery : (fun i => query i x) = encode (f x) := rfl rw [hquery] have hexists : ∃ b, encode b = encode (f x) := ⟨f x, rfl⟩ simp only [leafQ, hexists, dite_true] -- Fintype.choose picks the unique b with encode b = encode (f x); by injectivity it's f x have hch := Fintype.choose_spec (fun b => encode b = encode (f x)) (hencode_unique _ hexists) rw [hencode_inj hch] · -- Step 5: complexity — the supremum over bit patterns equals the supremum over `β` rw [completeTreeAlice_complexity] congr 1 apply le_antisymm · apply Finset.sup_le; intro bits _ by_cases h : ∃ b, encode b = bits · simp only [leafQ, h, dite_true] exact Finset.le_sup (f := fun b => (Q b).complexity) (Finset.mem_univ _) · simp only [leafQ, h, dite_false] exact Finset.le_sup (f := fun b => (Q b).complexity) (Finset.mem_univ _) · apply Finset.sup_le; intro b _ have hleafQ : leafQ (encode b) = Q b := by have hexb : ∃ b', encode b' = encode b := ⟨b, rfl⟩ simp only [leafQ, hexb, dite_true] congr 1 have hch := Fintype.choose_spec (fun b' => encode b' = encode b) (hencode_unique _ hexb) exact hencode_inj hch calc (Q b).complexity = (leafQ (encode b)).complexity := by rw [hleafQ] _ ≤ Finset.univ.sup (fun bits => (leafQ bits).complexity) := Finset.le_sup (f := fun bits => (leafQ bits).complexity) (Finset.mem_univ _)