Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.4 — CLtC_{L_t}CLt​​, CRtC_{R_t}CRt​​ are fixed functions of CLt−1C_{L_{t-1}}CLt−1​​, CRt−1C_{R_{t-1}}CRt−1​​ and dpdpdpBBB-bit messages

Proved
DistVerif.Simulation.lemma_3_4

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

communication-complexitydistributed-computinglower-boundsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let A\mathcal AA be a deterministic B-model algorithm on the network G(Γ,d,p)G(\Gamma,d,p)G(Γ,d,p) of §3.1, with inputs xxx at s=u0ps=u^p_0s=u0p​ and yyy at r=udp−1pr=u^p_{d^p-1}r=udp−1p​, and write CLt=CA(Lt,t,x,y)C_{L_t}=C_{\mathcal A}(L_t,t,x,y)CLt​​=CA​(Lt​,t,x,y) and CRt=CA(Rt,t,x,y)C_{R_t}=C_{\mathcal A}(R_t,t,x,y)CRt​​=CA​(Rt​,t,x,y) for the configurations of the ttt-left and ttt-right sets at the end of round ttt. Let 0<t<(dp−1)/20<t<(d^p-1)/20<t<(dp−1)/2. Then:

  1. (3.2) There are dpdpdp slots, each either empty or an edge (w,u)(w,u)(w,u) of G(Γ,d,p)G(\Gamma,d,p)G(Γ,d,p) with w∈Lt−1w\in L_{t-1}w∈Lt−1​, and a function gRg_RgR​, such that for all inputs x,yx,yx,y
CRt=gR(CRt−1,M1Lt−1,…,MdpLt−1),C_{R_t}=g_R\big(C_{R_{t-1}},M^{L_{t-1}}_1,\dots,M^{L_{t-1}}_{dp}\big),CRt​​=gR​(CRt−1​​,M1Lt−1​​,…,MdpLt−1​​),

where MiLt−1M^{L_{t-1}}_iMiLt−1​​ is the BBB-bit message sent in round ttt along the edge of slot iii (and a fixed dummy message if slot iii is empty). 2. (3.1) Symmetrically, there are dpdpdp slots, each empty or an edge (w,u)(w,u)(w,u) with w∈Rt−1w\in R_{t-1}w∈Rt−1​, and a function gLg_LgL​, such that for all inputs x,yx,yx,y

CLt=gL(CLt−1,M1Rt−1,…,MdpRt−1).C_{L_t}=g_L\big(C_{L_{t-1}},M^{R_{t-1}}_1,\dots,M^{R_{t-1}}_{dp}\big).CLt​​=gL​(CLt−1​​,M1Rt−1​​,…,MdpRt−1​​).

This is the step of the Simulation Theorem: Bob, who knows CRt−1C_{R_{t-1}}CRt−1​​, can compute CRtC_{R_t}CRt​​ once Alice sends him dpdpdp messages of BBB bits, which she can compute from CLt−1C_{L_{t-1}}CLt−1​​, and vice versa.

Formalization Note The functions gL,gRg_L,g_RgL​,gR​ and the slot edges are chosen once, before the inputs, and depend only on A\mathcal AA, ttt and the network. The paper's wording ("Fix any deterministic algorithm A\mathcal AA and input strings xxx and yyy … there exist functions") read literally would let gRg_RgR​ depend on (x,y)(x,y)(x,y), which makes the lemma trivial; its proof constructs input-independent functions and edges, and the proof of Theorem 3.1 needs that, since Bob evaluates gRg_RgR​ without knowing xxx. Empty slots are the paper's padding ("if there are less than dpdpdp such messages, then we add some empty messages"). The node indices s,rs,rs,r need dp≥1d^p\ge1dp≥1, which is a hypothesis.

Preamble
import Mathlib
import Definitions.Def_DistVerif_Simulation_Network
import Definitions.Def_DistVerif_Simulation_Algorithm
Formal statement
namespace DistVerif.Simulation

/-- **Lemma 3.4** (p. 1249). Let `A` be a deterministic B-model algorithm on `G(Γ, d, p)`
(inputs at `s = u^p_0` and `r = u^p_{d^p-1}`) and `0 < t < (d^p - 1)/2`.
* (3.2) There are `d·p` slots `eR`, each either empty or an edge `(w, u)` of the graph with
  `w ∈ L_{t-1}`, and a function `gR`, both independent of the inputs, such that for all inputs
  `x, y` the configuration `C_{R_t}` equals `gR` applied to `C_{R_{t-1}}` and the `B`-bit
  messages sent along the slots' edges in round `t` (an all-`false` message for empty slots).
* (3.1) Symmetrically for `C_{L_t}`, with `d·p` edges leaving `R_{t-1}` and a function `gL`. -/
theorem lemma_3_4 (Γ d p B b : ℕ) (hdp : 0 < d ^ p) (A : DetAlg (Vtx Γ d p) B b)
    (t : ℕ) (ht0 : 0 < t) (ht : (t : ℝ) < ((d : ℝ) ^ p - 1) / 2) :
    (∃ eL : Fin (d * p) → Option (Vtx Γ d p × Vtx Γ d p),
      ∃ gL : (↥(L Γ d p (t - 1)) → A.State) → (Fin (d * p) → Msg B) → (↥(L Γ d p t) → A.State),
        (∀ i w u, eL i = some (w, u) → w ∈ R Γ d p (t - 1) ∧ (graph Γ d p).Adj w u) ∧
        ∀ x y : Fin b → Bool,
          (fun v : ↥(L Γ d p t) =>
              A.exec (graph Γ d p) (sNode Γ d p hdp) (rNode Γ d p hdp) x y t v) =
            gL (fun v : ↥(L Γ d p (t - 1)) =>
                  A.exec (graph Γ d p) (sNode Γ d p hdp) (rNode Γ d p hdp) x y (t - 1) v)
               (fun i => match eL i with
                 | some (w, u) => A.send w u
                     (A.exec (graph Γ d p) (sNode Γ d p hdp) (rNode Γ d p hdp) x y (t - 1) w)
                 | none => fun _ => false)) ∧
    (∃ eR : Fin (d * p) → Option (Vtx Γ d p × Vtx Γ d p),
      ∃ gR : (↥(R Γ d p (t - 1)) → A.State) → (Fin (d * p) → Msg B) → (↥(R Γ d p t) → A.State),
        (∀ i w u, eR i = some (w, u) → w ∈ L Γ d p (t - 1) ∧ (graph Γ d p).Adj w u) ∧
        ∀ x y : Fin b → Bool,
          (fun v : ↥(R Γ d p t) =>
              A.exec (graph Γ d p) (sNode Γ d p hdp) (rNode Γ d p hdp) x y t v) =
            gR (fun v : ↥(R Γ d p (t - 1)) =>
                  A.exec (graph Γ d p) (sNode Γ d p hdp) (rNode Γ d p hdp) x y (t - 1) v)
               (fun i => match eR i with
                 | some (w, u) => A.send w u
                     (A.exec (graph Γ d p) (sNode Γ d p hdp) (rNode Γ d p hdp) x y (t - 1) w)
                 | none => fun _ => false)) := by sorry

end DistVerif.Simulation
Source
Das Sarma, Holzer, Kor, Korman, Nanongkai, Pandurangan, Peleg, Wattenhofer, Distributed Verification and Hardness of Distributed Approximation, SIAM J. Comput. 41 (2012), p. 1249, Lemma 3.4, equations (3.1)–(3.2); proof on pp. 1249–1250
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me