linear_code_supports_rate_of_transfer_matrix
Given M transmissions with endpoints snd, rcv on a capacitated network, a time horizon T > 0, a message dimension L > 0, capacity-respecting edge usage, encoding and decoding tables alpha, beta, gamma obeying causality and sender/receiver/decoder locality, and a transfer table W satisfying W m k j = alpha m k j + sum_{m'} beta m m' * W m' k j together with the decoding identity sum_m gamma k j m * W m k' j' = 1 if (k,j)=(k',j') and 0 otherwise, the resulting causal binary (or any-field) linear network code supports rate L/T.
Statement
theorem linear_code_supports_rate_of_transfer_matrix {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K] (F : Type) [Field F] (net : CapacitatedNetwork V) (sess : UnicastSessions V K) {M T L : ℕ} (hT : 0 < T) (hL : 0 < L) (snd rcv : Fin M → V) (hne : ∀ m, snd m ≠ rcv m) (hcap : ∀ e : Sym2 V, ((Finset.univ.filter (fun m : Fin M => s(snd m, rcv m) = e)).card : ℝ) ≤ (T : ℝ) * net.cap e) (α : Fin M → K → Fin L → F) (β : Fin M → Fin M → F) (γ : K → Fin L → Fin M → F) (W : Fin M → K → Fin L → F) (hcausal : ∀ m m', β m m' ≠ 0 → m' < m) (hsnd : ∀ (m : Fin M) (k : K) (j : Fin L), α m k j ≠ 0 → sess.src k = snd m) (hrcv : ∀ (m m' : Fin M), β m m' ≠ 0 → rcv m' = snd m) (hdec : ∀ (k : K) (j : Fin L) (m : Fin M), γ k j m ≠ 0 → rcv m = sess.tgt k) (hW : ∀ (m : Fin M) (k : K) (j : Fin L), W m k j = α m k j + ∑ m', β m m' * W m' k j) (hD : ∀ (k : K) (j : Fin L) (k' : K) (j' : Fin L), (∑ m, γ k j m * W m k' j') = if k = k' ∧ j = j' then 1 else 0) : LinearCodeSupportsRate F net sess ((L : ℝ) / (T : ℝ))
- Source
- step towards undirected_binary_linear_unicast_advantage
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- CausalLinearNetworkCodeA structure CausalLinearNetworkCode parameterized by a finite vertex type V with decidable equality, a finite session type K with…
- LinearCodeSupportsRateA common rate r is achievable by deterministic causal linear network coding over a field F on net with sessions sess if there exists a…
- 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…
- 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,…
- Used by 1
- causal_linear_network_code_of_transfer_matrixThe construction half of the transfer-matrix criterion, returned as the code itself: explicit transmission endpoints, horizon T, message…
The proof, explained
To prove that the capacitated network supports transmission rate L/T, we explicitly construct a causal linear network code from the encoding, forwarding, and decoding matrices α, β, and γ. For each message msg, the transmission values are witnessed by val m = ∑ k, ∑ j, W m k j * msg k j using the transfer matrix certificate W. Algebraic reindexing of finite sums establishes that the transfer recurrence W = α + β W ensures node transmission recurrence, while the decoding identity γ W = I guarantees message recovery at the destinations.
In any triple sum over finite types, the order of summation can be permuted from (i, k, l) to (l, i, k).
We repeatedly swap adjacent summation indices using commutativity of finite sums (`linear_code_supports_rate_of_transfer_matrix_sum_comm_univ`) and congruence (`Finset.sum_congr`): first swapping the outer indices i and k, then swapping inner indices i and l, then outer indices k and l, and finally inner indices k and i.
uses
linear_code_supports_rate_of_transfer_matrix_sum_comm_univ,Finset.sum_congrcalc (∑ i, ∑ k, ∑ l, f i k l) = ∑ k, ∑ i, ∑ l, f i k l := linear_code_supports_rate_of_transfer_matrix_sum_comm_univ _ _ = ∑ k, ∑ l, ∑ i, f i k l := by apply Finset.sum_congr rfl; intro k _ exact linear_code_supports_rate_of_transfer_matrix_sum_comm_univ (fun i l => f i k l) _ = ∑ l, ∑ k, ∑ i, f i k l := linear_code_supports_rate_of_transfer_matrix_sum_comm_univ _ _ = ∑ l, ∑ i, ∑ k, f i k l := by apply Finset.sum_congr rfl; intro l _ exact linear_code_supports_rate_of_transfer_matrix_sum_comm_univ (fun k i => f i k l)
In any triple sum over finite types, the order of summation can be rotated from (i, k, l) to (k, l, i).
We swap the outer two sums over i and k using `linear_code_supports_rate_of_transfer_matrix_sum_comm_univ`, and then swap the inner two sums over i and l using `Finset.sum_congr` with `linear_code_supports_rate_of_transfer_matrix_sum_comm_univ`.
uses
linear_code_supports_rate_of_transfer_matrix_sum_comm_univ,Finset.sum_congrcalc (∑ i, ∑ k, ∑ l, f i k l) = ∑ k, ∑ i, ∑ l, f i k l := linear_code_supports_rate_of_transfer_matrix_sum_comm_univ _ _ = ∑ k, ∑ l, ∑ i, f i k l := by apply Finset.sum_congr rfl; intro k _ exact linear_code_supports_rate_of_transfer_matrix_sum_comm_univ (fun i l => f i k l)
The candidate transmission values ∑ k, ∑ j, W m k j * msg k j satisfy the network coding recurrence relation.
We substitute W m k j by its recursive definition a m k j + ∑ m', b m m' * W m' k j using hW and `Finset.sum_congr`. Next, we distribute multiplication by msg k j over the addition and split the sum into source encoding and transmission terms using `add_mul` and `Finset.sum_add_distrib`. We then push msg k j inside the sum over m' using `Finset.sum_mul`, swap the triple summation order via `linear_code_supports_rate_of_transfer_matrix_triple_sum_swap`, and factor out b m m' using `mul_assoc` and `Finset.mul_sum`.
uses
Finset.sum_congr,add_mul,Finset.sum_add_distrib,Finset.sum_mul,linear_code_supports_rate_of_transfer_matrix_triple_sum_swap,mul_assoc,Finset.mul_sumcalc (∑ k, ∑ j, W m k j * msg k j) = ∑ k, ∑ j, (a m k j + ∑ m', b m m' * W m' k j) * msg k j := by apply Finset.sum_congr rfl; intro k _ apply Finset.sum_congr rfl; intro j _ rw [hW] _ = (∑ k, ∑ j, a m k j * msg k j) + ∑ k, ∑ j, (∑ m', b m m' * W m' k j) * msg k j := by simp only [add_mul, Finset.sum_add_distrib] _ = (∑ k, ∑ j, a m k j * msg k j) + ∑ k, ∑ j, ∑ m', (b m m' * W m' k j) * msg k j := by congr 1 simp only [Finset.sum_mul] _ = (∑ k, ∑ j, a m k j * msg k j) + ∑ m', ∑ k, ∑ j, (b m m' * W m' k j) * msg k j := by congr 1 exact linear_code_supports_rate_of_transfer_matrix_triple_sum_swap (fun k j m' => (b m m' * W m' k j) * msg k j) _ = (∑ k, ∑ j, a m k j * msg k j) + ∑ m', b m m' * (∑ k, ∑ j, W m' k j * msg k j) := by congr 1 apply Finset.sum_congr rfl; intro m' _ simp only [mul_assoc, Finset.mul_sum]
The double sum over k' and j' of (if k = k' ∧ j = j' then 1 else 0) * msg k' j' collapses to msg k j.
Using `Finset.sum_eq_single`, we isolate the term k' = k in the outer sum, simplifying the summand to (if j = j' then msg k j' else 0) via `true_and`, `ite_mul`, `one_mul`, and `zero_mul`. A second application of `Finset.sum_eq_single` isolates j' = j, yielding msg k j. For both sums, all off-diagonal terms vanish because k' ≠ k or j' ≠ j (by `Ne.symm`), and the indices are members of the universe by `Finset.mem_univ`.
uses
Finset.sum_eq_single,true_and,ite_mul,one_mul,zero_mul,Ne.symm,Finset.mem_univrw [Finset.sum_eq_single (a := k)] · simp only [true_and, ite_mul, one_mul, zero_mul] rw [Finset.sum_eq_single (a := j)] · simp · intro j' _ hj' simp [Ne.symm hj'] · intro h; exact absurd (Finset.mem_univ j) h · intro k' _ hk' simp [Ne.symm hk'] · intro h; exact absurd (Finset.mem_univ k) h
Applying the decoding coefficients γ to the candidate transmission values reconstructs the original message msg k j.
We flip the equality symmetrically (`symm`), push γ k j m inside the inner double sum via `Finset.mul_sum`, and rotate the triple sum using `linear_code_supports_rate_of_transfer_matrix_triple_sum_rot` so the sum over m becomes innermost. We then factor out msg k' j' using `mul_assoc` and `Finset.sum_mul`, apply the decoding condition hD to replace the inner sum with the Kronecker delta indicator, and collapse the resulting sum to msg k j using `linear_code_supports_rate_of_transfer_matrix_ite_collapse`.
uses
Finset.mul_sum,linear_code_supports_rate_of_transfer_matrix_triple_sum_rot,Finset.sum_congr,mul_assoc,Finset.sum_mul,linear_code_supports_rate_of_transfer_matrix_ite_collapsesymm calc (∑ m, γ k j m * (∑ k', ∑ j', W m k' j' * msg k' j')) = ∑ m, ∑ k', ∑ j', γ k j m * (W m k' j' * msg k' j') := by simp only [Finset.mul_sum] _ = ∑ k', ∑ j', ∑ m, γ k j m * (W m k' j' * msg k' j') := linear_code_supports_rate_of_transfer_matrix_triple_sum_rot _ _ = ∑ k', ∑ j', (∑ m, γ k j m * W m k' j') * msg k' j' := by apply Finset.sum_congr rfl; intro k' _ apply Finset.sum_congr rfl; intro j' _ simp only [← mul_assoc, Finset.sum_mul] _ = ∑ k', ∑ j', (if k = k' ∧ j = j' then (1:F) else 0) * msg k' j' := by apply Finset.sum_congr rfl; intro k' _ apply Finset.sum_congr rfl; intro j' _ rw [hD k j k' j'] _ = msg k j := linear_code_supports_rate_of_transfer_matrix_ite_collapse msg k j
A causal linear network code candidate is constructed from the network and code parameters, satisfying the required rate bound L/T.
We instantiate the `CausalLinearNetworkCode` record with the provided parameters (transmission count M, horizon T, message size L, node endpoints, capacities, coding tables α, β, γ, causality, and locality conditions). The rate bound L/T ≤ code.L / code.T holds by reflexivity (`le_refl`), leaving only the correctness condition on arbitrary messages.
uses
le_reflrefine ⟨{ M := M, T := T, L := L, hT := hT, hL := hL, snd := snd, rcv := rcv, snd_ne_rcv := hne, cap_le := hcap, α := α, β := β, γ := γ, causal := hcausal, snd_local := hsnd, rcv_local := hrcv, dec_local := hdec, correct := ?_ }, le_refl _⟩For every message, the candidate transmission values satisfy the transmission recurrence and decoding conditions.
Given any message `msg`, we choose the transmission values val m = ∑ k, ∑ j, W m k j * msg k j. Node transmission correctness holds by `linear_code_supports_rate_of_transfer_matrix_rec`, and receiver decoding correctness holds by `linear_code_supports_rate_of_transfer_matrix_dec`.
uses
linear_code_supports_rate_of_transfer_matrix_rec,linear_code_supports_rate_of_transfer_matrix_decintro msg exact ⟨fun m => ∑ k, ∑ j, W m k j * msg k j, fun m => linear_code_supports_rate_of_transfer_matrix_rec α β W msg m hW, fun k j => linear_code_supports_rate_of_transfer_matrix_dec W γ msg k j hD⟩
linear_code_supports_rate_of_transfer_matrix_sum_comm_univ- Sums over all elements of two finite types can be swapped: ∑ i, ∑ k, f i k = ∑ k, ∑ i, f i k.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree at every element.
linear_code_supports_rate_of_transfer_matrix_triple_sum_swap- In a triple sum over finite types, the summation order can be permuted from (i, k, l) to (l, i, k).
linear_code_supports_rate_of_transfer_matrix_triple_sum_rot- In a triple sum over finite types, the summation order can be rotated from (i, k, l) to (k, l, i).
add_mul- Multiplication distributes from the right over addition: (a + b) * c = a * c + b * c.
Finset.sum_add_distrib- A sum of a sum of functions splits into the sum of each function: ∑ x ∈ s, (f x + g x) = ∑ x ∈ s, f x + ∑ x ∈ s, g x.
Finset.sum_mul- Multiplying a finite sum by a scalar from the right distributes into each summand: (∑ i ∈ s, f i) * a = ∑ i ∈ s, f i * a.
mul_assoc- Multiplication is associative: (a * b) * c = a * (b * c).
Finset.mul_sum- Multiplying a finite sum by a scalar from the left distributes into each summand: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.sum_eq_single- If a summand f b is zero for all b ≠ a in a finite set s, then the sum over s evaluates to f a.
true_and- A conjunction True ∧ p simplifies to p.
ite_mul- Multiplication distributes into both branches of an if-then-else: (if P then a else b) * c = if P then a * c else b * c.
one_mul- Multiplying by 1 on the left is the identity: 1 * a = a.
zero_mul- Multiplying by 0 on the left yields 0: 0 * a = 0.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set univ.
linear_code_supports_rate_of_transfer_matrix_ite_collapse- Summing the product of a double Kronecker delta indicator and a message matrix collapses to the single message entry msg k j.
le_refl- The order relation ≤ is reflexive: a ≤ a.
linear_code_supports_rate_of_transfer_matrix_rec- If the transfer matrix W satisfies the linear network recurrence, the candidate transmission values satisfy the node transmission recurrence equation.
linear_code_supports_rate_of_transfer_matrix_dec- If the transfer matrix W and decoding matrix γ satisfy the decoding identity, applying γ to the candidate transmission values reconstructs the original message msg k j.
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.
lemma linear_code_supports_rate_of_transfer_matrix_sum_comm_univ {ι κ R : Type} [Fintype ι] [Fintype κ] [AddCommMonoid R] (f : ι → κ → R) : (∑ i, ∑ k, f i k) = ∑ k, ∑ i, f i k := Finset.sum_commlemma linear_code_supports_rate_of_transfer_matrix_triple_sum_swap {ι κ μ R : Type} [Fintype ι] [Fintype κ] [Fintype μ] [AddCommMonoid R] (f : ι → κ → μ → R) : (∑ i, ∑ k, ∑ l, f i k l) = ∑ l, ∑ i, ∑ k, f i k l := by calc (∑ i, ∑ k, ∑ l, f i k l) = ∑ k, ∑ i, ∑ l, f i k l := linear_code_supports_rate_of_transfer_matrix_sum_comm_univ _ _ = ∑ k, ∑ l, ∑ i, f i k l := by apply Finset.sum_congr rfl; intro k _ exact linear_code_supports_rate_of_transfer_matrix_sum_comm_univ (fun i l => f i k l) _ = ∑ l, ∑ k, ∑ i, f i k l := linear_code_supports_rate_of_transfer_matrix_sum_comm_univ _ _ = ∑ l, ∑ i, ∑ k, f i k l := by apply Finset.sum_congr rfl; intro l _ exact linear_code_supports_rate_of_transfer_matrix_sum_comm_univ (fun k i => f i k l)lemma linear_code_supports_rate_of_transfer_matrix_triple_sum_rot {ι κ μ R : Type} [Fintype ι] [Fintype κ] [Fintype μ] [AddCommMonoid R] (f : ι → κ → μ → R) : (∑ i, ∑ k, ∑ l, f i k l) = ∑ k, ∑ l, ∑ i, f i k l := by calc (∑ i, ∑ k, ∑ l, f i k l) = ∑ k, ∑ i, ∑ l, f i k l := linear_code_supports_rate_of_transfer_matrix_sum_comm_univ _ _ = ∑ k, ∑ l, ∑ i, f i k l := by apply Finset.sum_congr rfl; intro k _ exact linear_code_supports_rate_of_transfer_matrix_sum_comm_univ (fun i l => f i k l)lemma linear_code_supports_rate_of_transfer_matrix_rec {F : Type} [Field F] {MM K L : Type} [Fintype MM] [Fintype K] [Fintype L] (a : MM → K → L → F) (b : MM → MM → F) (W : MM → K → L → F) (msg : K → L → F) (m : MM) (hW : ∀ (m : MM) (k : K) (j : L), W m k j = a m k j + ∑ m', b m m' * W m' k j) : (∑ k, ∑ j, W m k j * msg k j) = (∑ k, ∑ j, a m k j * msg k j) + ∑ m', b m m' * (∑ k, ∑ j, W m' k j * msg k j) := by calc (∑ k, ∑ j, W m k j * msg k j) = ∑ k, ∑ j, (a m k j + ∑ m', b m m' * W m' k j) * msg k j := by apply Finset.sum_congr rfl; intro k _ apply Finset.sum_congr rfl; intro j _ rw [hW] _ = (∑ k, ∑ j, a m k j * msg k j) + ∑ k, ∑ j, (∑ m', b m m' * W m' k j) * msg k j := by simp only [add_mul, Finset.sum_add_distrib] _ = (∑ k, ∑ j, a m k j * msg k j) + ∑ k, ∑ j, ∑ m', (b m m' * W m' k j) * msg k j := by congr 1 simp only [Finset.sum_mul] _ = (∑ k, ∑ j, a m k j * msg k j) + ∑ m', ∑ k, ∑ j, (b m m' * W m' k j) * msg k j := by congr 1 exact linear_code_supports_rate_of_transfer_matrix_triple_sum_swap (fun k j m' => (b m m' * W m' k j) * msg k j) _ = (∑ k, ∑ j, a m k j * msg k j) + ∑ m', b m m' * (∑ k, ∑ j, W m' k j * msg k j) := by congr 1 apply Finset.sum_congr rfl; intro m' _ simp only [mul_assoc, Finset.mul_sum]lemma linear_code_supports_rate_of_transfer_matrix_ite_collapse {F : Type} [Field F] {K L : Type} [Fintype K] [Fintype L] [DecidableEq K] [DecidableEq L] (msg : K → L → F) (k : K) (j : L) : (∑ k', ∑ j', (if k = k' ∧ j = j' then (1:F) else 0) * msg k' j') = msg k j := by rw [Finset.sum_eq_single (a := k)] · simp only [true_and, ite_mul, one_mul, zero_mul] rw [Finset.sum_eq_single (a := j)] · simp · intro j' _ hj' simp [Ne.symm hj'] · intro h; exact absurd (Finset.mem_univ j) h · intro k' _ hk' simp [Ne.symm hk'] · intro h; exact absurd (Finset.mem_univ k) hlemma linear_code_supports_rate_of_transfer_matrix_dec {F : Type} [Field F] {MM K L : Type} [Fintype MM] [Fintype K] [Fintype L] [DecidableEq K] [DecidableEq L] (W : MM → K → L → F) (γ : K → L → MM → F) (msg : K → L → F) (k : K) (j : L) (hD : ∀ (k : K) (j : L) (k' : K) (j' : L), (∑ m, γ k j m * W m k' j') = if k = k' ∧ j = j' then 1 else 0) : msg k j = ∑ m, γ k j m * (∑ k', ∑ j', W m k' j' * msg k' j') := by symm calc (∑ m, γ k j m * (∑ k', ∑ j', W m k' j' * msg k' j')) = ∑ m, ∑ k', ∑ j', γ k j m * (W m k' j' * msg k' j') := by simp only [Finset.mul_sum] _ = ∑ k', ∑ j', ∑ m, γ k j m * (W m k' j' * msg k' j') := linear_code_supports_rate_of_transfer_matrix_triple_sum_rot _ _ = ∑ k', ∑ j', (∑ m, γ k j m * W m k' j') * msg k' j' := by apply Finset.sum_congr rfl; intro k' _ apply Finset.sum_congr rfl; intro j' _ simp only [← mul_assoc, Finset.sum_mul] _ = ∑ k', ∑ j', (if k = k' ∧ j = j' then (1:F) else 0) * msg k' j' := by apply Finset.sum_congr rfl; intro k' _ apply Finset.sum_congr rfl; intro j' _ rw [hD k j k' j'] _ = msg k j := linear_code_supports_rate_of_transfer_matrix_ite_collapse msg k j/-- A finite transfer-matrix certificate turns the code half of a witness into decidable table equations. -/theorem linear_code_supports_rate_of_transfer_matrix {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K] (F : Type) [Field F] (net : CapacitatedNetwork V) (sess : UnicastSessions V K) {M T L : ℕ} (hT : 0 < T) (hL : 0 < L) (snd rcv : Fin M → V) (hne : ∀ m, snd m ≠ rcv m) (hcap : ∀ e : Sym2 V, ((Finset.univ.filter (fun m : Fin M => s(snd m, rcv m) = e)).card : ℝ) ≤ (T : ℝ) * net.cap e) (α : Fin M → K → Fin L → F) (β : Fin M → Fin M → F) (γ : K → Fin L → Fin M → F) (W : Fin M → K → Fin L → F) (hcausal : ∀ m m', β m m' ≠ 0 → m' < m) (hsnd : ∀ (m : Fin M) (k : K) (j : Fin L), α m k j ≠ 0 → sess.src k = snd m) (hrcv : ∀ (m m' : Fin M), β m m' ≠ 0 → rcv m' = snd m) (hdec : ∀ (k : K) (j : Fin L) (m : Fin M), γ k j m ≠ 0 → rcv m = sess.tgt k) (hW : ∀ (m : Fin M) (k : K) (j : Fin L), W m k j = α m k j + ∑ m', β m m' * W m' k j) (hD : ∀ (k : K) (j : Fin L) (k' : K) (j' : Fin L), (∑ m, γ k j m * W m k' j') = if k = k' ∧ j = j' then 1 else 0) : LinearCodeSupportsRate F net sess ((L : ℝ) / (T : ℝ)) := by refine ⟨{ M := M, T := T, L := L, hT := hT, hL := hL, snd := snd, rcv := rcv, snd_ne_rcv := hne, cap_le := hcap, α := α, β := β, γ := γ, causal := hcausal, snd_local := hsnd, rcv_local := hrcv, dec_local := hdec, correct := ?_ }, le_refl _⟩ intro msg exact ⟨fun m => ∑ k, ∑ j, W m k j * msg k j, fun m => linear_code_supports_rate_of_transfer_matrix_rec α β W msg m hW, fun k j => linear_code_supports_rate_of_transfer_matrix_dec W γ msg k j hD⟩