AFTD Auto-Formalizing Theoretical Domains

causal_code_vals_zero_outside

theoremverified

Let a causal linear code on net have transmission values val satisfying the recurrence for a message msg, where msg vanishes on sessions whose source is outside S and val vanishes on transmissions that leave S. Then val vanishes on every transmission whose receiver is outside S.

Statement

theorem causal_code_vals_zero_outside
    {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K]
    (F : Type) [Field F] (net : CapacitatedNetwork V) (sess : UnicastSessions V K)
    (code : CausalLinearNetworkCode V K F net sess) (S : Finset V) (msg : K → Fin code.L → F)
    (val : Fin code.M → F)
    (hval : ∀ m, val m = ∑ k, ∑ j, code.α m k j * msg k j + ∑ m', code.β m m' * val m')
    (hmsg : ∀ (k : K) (j : Fin code.L), sess.src k ∉ S → msg k j = 0)
    (hleave : ∀ m : Fin code.M, code.snd m ∈ S → code.rcv m ∉ S → val m = 0) :
    ∀ m : Fin code.M, code.rcv m ∉ S → val m = 0
Source
step towards undirected_binary_linear_unicast_advantage
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • CausalLinearNetworkCodeA structure CausalLinearNetworkCode parameterized by a finite vertex type V with decidable equality, a finite session type K with…
  • UnicastSessionsA collection of unicast communication sessions indexed by a type K on an arbitrary vertex type V, consisting of a source map src : K → V,…
  • CapacitatedNetworkAn undirected capacitated network on a finite vertex set V given by a simple graph G where each edge in G has strictly positive capacity…
Used by 1

The proof, explained

The theorem is proved by well-founded induction on the transmission index $m$, corresponding to the causal order of transmissions. For any transmission $m$ received outside $S$, we case-split on whether its sender is in $S$: if it is, the transmission crosses the cut leaving $S$, so its value is zero by the cut condition. If the sender is outside $S$, we expand the value using the recurrence; the direct message terms vanish because their sources lie outside $S$, and the forwarded transmission terms vanish because causality and locality ensure they are earlier transmissions received outside $S$, where the inductive hypothesis applies.

  1. It suffices to show that any transmission $m$ received outside $S$ has value zero, assuming by induction that the property holds for all transmissions prior to $m$.

    We introduce an arbitrary transmission $m$ and proceed by well-founded induction on $m$ (`WellFoundedLT.induction`), ordering transmissions by causal transmission index. We then introduce the assumption that the receiver of $m$ lies outside $S$ (`hrcv`).

    lines 11–14

    uses WellFoundedLT.induction

      intro m
      induction m using WellFoundedLT.induction with
      | ind m ih =>
        intro hrcv
  2. If the sender of $m$ is in $S$, then $\text{val}(m) = 0$.

    We case-split on whether the sender of $m$ is in $S$. If it is, then $m$ is a transmission with sender in $S$ and receiver outside $S$. By the cut condition `hleave`, any transmission leaving $S$ carries value zero, directly giving $\text{val}(m) = 0$.

    lines 15–16

        by_cases hsnd : code.snd m ∈ S
        · exact hleave m hsnd hrcv
  3. When the sender of $m$ is outside $S$, expanding $\text{val}(m)$ reduces the goal to showing that the sum of direct message inputs and forwarded transmissions vanishes.

    In the case where the sender of $m$ is not in $S$, we rewrite $\text{val}(m)$ using the recurrence relation `hval`, expressing it as the sum of session messages $\sum_{k, j} \alpha_{m, k, j} \text{msg}(k, j)$ and forwarded transmission values $\sum_{m'} \beta_{m, m'} \text{val}(m')$.

    line 17

        · rw [hval m]
  4. The message contribution $\sum_{k, j} \alpha_{m, k, j} \text{msg}(k, j)$ is zero.

    Using `Finset.sum_eq_zero`, we show each term $\alpha_{m, k, j} \text{msg}(k, j)$ vanishes. If $\alpha_{m, k, j} = 0$, the term is zero by `zero_mul`. If $\alpha_{m, k, j} \ne 0$, encoding locality (`code.snd_local`) implies the source of session $k$ is the sender of $m$, which is outside $S$. By hypothesis `hmsg`, the message $\text{msg}(k, j)$ must be zero, so the product vanishes by `mul_zero`.

    lines 18–29

    uses Finset.sum_eq_zero, zero_mul, mul_zero

          have h1 : (∑ k, ∑ j, code.α m k j * msg k j) = (0 : F) := by
            apply Finset.sum_eq_zero
            intro k _
            apply Finset.sum_eq_zero
            intro j _
            by_cases hα : code.α m k j = 0
            · rw [hα, zero_mul]
            · have hsrc := code.snd_local m k j hα
              have hk : sess.src k ∉ S := by
                rw [hsrc]
                exact hsnd
              rw [hmsg k j hk, mul_zero]
  5. The forwarded transmission contribution $\sum_{m'} \beta_{m, m'} \text{val}(m')$ is zero.

    Again using `Finset.sum_eq_zero`, we show each term $\beta_{m, m'} \text{val}(m')$ vanishes. If $\beta_{m, m'} = 0$, the term is zero by `zero_mul`. If $\beta_{m, m'} \ne 0$, causality (`code.causal`) gives $m' < m$, and receiver locality (`code.rcv_local`) shows that the receiver of $m'$ is the sender of $m$, which is outside $S$. Applying the induction hypothesis to $m' < m$ shows $\text{val}(m') = 0$, so the term is zero by `mul_zero`.

    lines 30–41

    uses Finset.sum_eq_zero, zero_mul, mul_zero

          have h2 : (∑ m', code.β m m' * val m') = (0 : F) := by
            apply Finset.sum_eq_zero
            intro m' _
            by_cases hβ : code.β m m' = 0
            · rw [hβ, zero_mul]
            · have hlt : m' < m := code.causal m m' hβ
              have hrcv' : code.rcv m' = code.snd m := code.rcv_local m m' hβ
              have hrcv_not : code.rcv m' ∉ S := by
                rw [hrcv']
                exact hsnd
              have hval' : val m' = 0 := ih m' hlt hrcv_not
              rw [hval', mul_zero]
  6. The transmission value $\text{val}(m)$ is zero, completing the inductive step.

    Substituting the two zero sums into the recurrence for $\text{val}(m)$ yields $0 + 0 = 0$ via `add_zero`, establishing $\text{val}(m) = 0$.

    line 42

    uses add_zero

          rw [h1, h2, add_zero]
WellFoundedLT.induction
The principle of well-founded induction: to prove a statement holds for all elements of a well-founded partially ordered type, it suffices to prove it for an arbitrary element assuming it holds for all strictly smaller elements.
Finset.sum_eq_zero
A finite sum is zero if every term in the sum is zero.
zero_mul
Zero multiplied by any element on the left equals zero: $0 \\cdot a = 0$.
mul_zero
Any element multiplied by zero on the right equals zero: $a \\cdot 0 = 0$.
add_zero
Adding zero to an element on the right leaves it unchanged: $a + 0 = a$.

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

/-- Values on a cut that carry no traffic vanish on the far side of the cut. -/theorem causal_code_vals_zero_outside    {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K]    (F : Type) [Field F] (net : CapacitatedNetwork V) (sess : UnicastSessions V K)    (code : CausalLinearNetworkCode V K F net sess) (S : Finset V) (msg : K → Fin code.L → F)    (val : Fin code.M → F)    (hval : ∀ m, val m = ∑ k, ∑ j, code.α m k j * msg k j + ∑ m', code.β m m' * val m')    (hmsg : ∀ (k : K) (j : Fin code.L), sess.src k ∉ S → msg k j = 0)    (hleave : ∀ m : Fin code.M, code.snd m ∈ S → code.rcv m ∉ S → val m = 0) :    ∀ m : Fin code.M, code.rcv m ∉ S → val m = 0 := by  intro m  induction m using WellFoundedLT.induction with  | ind m ih =>    intro hrcv    by_cases hsnd : code.snd m ∈ S    · exact hleave m hsnd hrcv    · rw [hval m]      have h1 : (∑ k, ∑ j, code.α m k j * msg k j) = (0 : F) := by        apply Finset.sum_eq_zero        intro k _        apply Finset.sum_eq_zero        intro j _        by_cases hα : code.α m k j = 0        · rw [hα, zero_mul]        · have hsrc := code.snd_local m k j hα          have hk : sess.src k ∉ S := by            rw [hsrc]            exact hsnd          rw [hmsg k j hk, mul_zero]      have h2 : (∑ m', code.β m m' * val m') = (0 : F) := by        apply Finset.sum_eq_zero        intro m' _        by_cases hβ : code.β m m' = 0        · rw [hβ, zero_mul]        · have hlt : m' < m := code.causal m m' hβ          have hrcv' : code.rcv m' = code.snd m := code.rcv_local m m' hβ          have hrcv_not : code.rcv m' ∉ S := by            rw [hrcv']            exact hsnd          have hval' : val m' = 0 := ih m' hlt hrcv_not          rw [hval', mul_zero]      rw [h1, h2, add_zero]
See it in the graphDiscuss this resultChallenge it