causal_code_vals_zero_outside
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
- linear_code_supports_rate_cut_boundIf a linear network code over a field F supports the common rate r on net with sessions sess, then for every vertex set S, r times the…
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.
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`).
uses
WellFoundedLT.inductionintro m induction m using WellFoundedLT.induction with | ind m ih => intro hrcv
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$.
by_cases hsnd : code.snd m ∈ S · exact hleave m hsnd hrcv
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')$.
· rw [hval m]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`.
uses
Finset.sum_eq_zero,zero_mul,mul_zerohave 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]
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`.
uses
Finset.sum_eq_zero,zero_mul,mul_zerohave 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]
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$.
uses
add_zerorw [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
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.
/-- 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]