causal_code_val_unique
For a fixed message msg, any two assignments of transmission values satisfying the linear recurrence val m = sum alpha*msg + sum beta*val agree.
Statement
theorem causal_code_val_unique {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) (msg : K → Fin code.L → F) (val val' : Fin code.M → F) (hval : ∀ m, val m = ∑ k, ∑ j, code.α m k j * msg k j + ∑ m', code.β m m' * val m') (hval' : ∀ m, val' m = ∑ k, ∑ j, code.α m k j * msg k j + ∑ m', code.β m m' * val' m') : val = val'
- 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 uniqueness of the transmission values is proved by function extensionality followed by well-founded (strong) induction on the transmission index m with respect to the strict order < on Fin code.M. Expanding both assignments via their recurrence relations, the direct message terms cancel immediately. For the remaining dependence on other transmission values, the causality of the code guarantees that any nonzero coefficient code.β m m' requires m' < m, allowing the induction hypothesis to equate val m' with val' m'.
It suffices to prove by strong induction on m that val m = val' m for every transmission index m.
By function extensionality (`ext m`), two value functions are identical if they agree at each index `m`. We prove this equality by well-founded induction (`WellFoundedLT.induction`) on the index type `Fin code.M` ordered by `<`, obtaining an induction hypothesis `ih` that `val y = val' y` for all earlier transmissions `y < m`.
uses
WellFoundedLT.inductionext m induction m using WellFoundedLT.induction with | ind m ih =>
To show val m = val' m, it suffices to show code.β m m' * val m' = code.β m m' * val' m' for each m'.
We expand both `val m` and `val' m` using the recurrence relations `hval m` and `hval' m`. The message-dependent linear combinations are identical on both sides and cancel (`congr 1`). By congruence of finite sums (`Finset.sum_congr`), it is enough to show that the individual terms in the sums over `m'` agree pointwise.
uses
Finset.sum_congrrw [hval m, hval' m] congr 1 apply Finset.sum_congr rfl intro m' _
The equality code.β m m' * val m' = code.β m m' * val' m' holds when code.β m m' = 0.
A case split on whether `code.β m m' = 0` yields that if the coefficient is zero, both sides evaluate to zero by multiplying by zero (`zero_mul`), establishing the equality.
uses
zero_mulby_cases hβ : code.β m m' = 0 · rw [hβ, zero_mul, zero_mul]
The equality code.β m m' * val m' = code.β m m' * val' m' holds when code.β m m' ≠ 0.
When `code.β m m' ≠ 0`, causality (`code.causal`) implies that `m' < m`. The induction hypothesis `ih` therefore applies to `m'`, giving `val m' = val' m'`, which equates the two products.
uses
code.causal· have hlt : m' < m := code.causal m m' hβ rw [ih m' hlt]
WellFoundedLT.induction- Well-founded induction on a type equipped with a well-founded `<` relation: to prove a property for all elements, it suffices to prove it for an arbitrary element assuming it holds for all strictly smaller elements.
Finset.sum_congr- Two finite sums over the same finite set are equal if their summands agree at every element.
zero_mul- Multiplication by zero on the left yields zero: `0 * a = 0`.
code.causal- In a causal linear network code, if the dependency coefficient β m m' is nonzero, then transmission index m' strictly precedes m (m' < m).
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.
/-- The transmission values of a causal linear code are uniquely determined by the message. -/theorem causal_code_val_unique {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) (msg : K → Fin code.L → F) (val val' : Fin code.M → F) (hval : ∀ m, val m = ∑ k, ∑ j, code.α m k j * msg k j + ∑ m', code.β m m' * val m') (hval' : ∀ m, val' m = ∑ k, ∑ j, code.α m k j * msg k j + ∑ m', code.β m m' * val' m') : val = val' := by ext m induction m using WellFoundedLT.induction with | ind m ih => rw [hval m, hval' m] congr 1 apply Finset.sum_congr rfl intro m' _ by_cases hβ : code.β m m' = 0 · rw [hβ, zero_mul, zero_mul] · have hlt : m' < m := code.causal m m' hβ rw [ih m' hlt]