causal_linear_network_code_of_transfer_matrix
The construction half of the transfer-matrix criterion, returned as the code itself: explicit transmission endpoints, horizon T, message dimension L and encoding/decoding tables over any field that respect the capacities and locality, together with a transfer table W solving the local encoding equations and inverting the decoding identity, are the data of an actual deterministic causal linear network code with $\mathtt{code}.T = T$ and $\mathtt{code}.L = L$.
Statement
theorem causal_linear_network_code_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) : ∃ code : CausalLinearNetworkCode V K F net sess, code.T = T ∧ code.L = L
- Source
- step towards single_slot_binary_linear_coding_advantage
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- linear_code_supports_rate_of_transfer_matrixGiven M transmissions with endpoints snd, rcv on a capacitated network, a time horizon T > 0, a message dimension L > 0,…
- CausalLinearNetworkCodeA structure CausalLinearNetworkCode parameterized by a finite vertex type V with decidable equality, a finite session type K with…
- 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,…
The proof, explained
The theorem directly constructs a `CausalLinearNetworkCode` by packaging the given parameters and hypotheses into its structural fields. The operational correctness requirement—that for any input message there exist edge signals satisfying the causal encoding equations and decoding back to the original message—is witnessed by evaluating the transfer matrix W on the message. The local encoding recurrence and the decoding correctness then follow from the algebraic identities assumed for W.
The candidate network code is instantiated with the given tables and parameters, satisfying all structural, capacity, causality, and locality axioms directly by hypothesis and leaving only operational correctness.
A term of `CausalLinearNetworkCode` is constructed from the provided parameters (horizon T, message dimension L, M transmissions, endpoints snd and rcv, and coefficients α, β, γ). Hypotheses hne, hcap, hcausal, hsnd, hrcv, and hdec supply the proofs of non-self transmissions, edge capacity bounds, causality of the transmission schedule, and source/receiver/decoding node locality. The equalities on T and L are verified by reflexivity.
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 := ?_ }, rfl, rfl⟩
For an arbitrary session message, the transmitted edge values are defined via the transfer matrix W as val(m) = ∑ k, ∑ j, W(m, k, j) * msg(k, j).
To satisfy the correctness field, we introduce an arbitrary message tuple msg and witness the transmitted signals val by modulating msg by the transfer table W. This leaves two proof obligations: showing that val satisfies the local linear combination recurrence, and showing that decoding reconstructs msg.
intro msg refine ⟨fun m => ∑ k, ∑ j, W m k j * msg k j, ?_, ?_⟩
The transmitted values val(m) satisfy the local network encoding equations at every transmission m.
For each transmission index m, substituting the recurrence equation hW for W into val(m) and distributing the summation over messages verifies that val(m) is the sum of local source injections and incoming transmissions, as established by `linear_code_supports_rate_of_transfer_matrix_rec`.
uses
linear_code_supports_rate_of_transfer_matrix_rec· intro m exact linear_code_supports_rate_of_transfer_matrix_rec α β W msg m hW
The destination nodes reconstruct the exact sent message symbols from the transmissions.
For each session k and message symbol index j, applying the decoding weights γ(k, j, ·) to val and applying the decoding identity hD contracts the double sum over all session messages to the single target symbol msg(k, j), via `linear_code_supports_rate_of_transfer_matrix_dec`.
uses
linear_code_supports_rate_of_transfer_matrix_dec· intro k j exact linear_code_supports_rate_of_transfer_matrix_dec W γ msg k j hD
linear_code_supports_rate_of_transfer_matrix_rec- If a transfer matrix W satisfies W(m, k, j) = α(m, k, j) + ∑ m', β(m, m') * W(m', k, j), then the message-modulated values val(m) = ∑ k, ∑ j, W(m, k, j) * msg(k, j) satisfy the network encoding recurrence val(m) = ∑ k, ∑ j, α(m, k, j) * msg(k, j) + ∑ m', β(m, m') * val(m').
linear_code_supports_rate_of_transfer_matrix_dec- If a transfer matrix W and decoding table γ satisfy the inversion identity ∑ m, γ(k, j, m) * W(m, k', j') = 1 if (k, j) = (k', j') else 0, then decoding the values val(m) = ∑ k', ∑ j', W(m, k', j') * msg(k', j') recovers the original message symbol 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.
/-- Table-level data satisfying the transfer-matrix hypotheses determine an actual causal linear code with the same T and L. -/theorem causal_linear_network_code_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) : ∃ code : CausalLinearNetworkCode V K F net sess, code.T = T ∧ code.L = L := 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 := ?_ }, rfl, rfl⟩ intro msg refine ⟨fun m => ∑ k, ∑ j, W m k j * msg k j, ?_, ?_⟩ · intro m exact linear_code_supports_rate_of_transfer_matrix_rec α β W msg m hW · intro k j exact linear_code_supports_rate_of_transfer_matrix_dec W γ msg k j hD