CausalLinearNetworkCode
A structure CausalLinearNetworkCode parameterized by a finite vertex type V with decidable equality, a finite session type K with decidable equality, a field F, a capacitated network net on V, and unicast sessions sess on V indexed by K. It packages: positive integers T (time horizon) and L (message dimension) with 0 < T and 0 < L; total transmissions M : ℕ; sender and receiver maps snd, rcv : Fin M → V with snd m ≠ rcv m for all m; edge capacity condition that for every e : Sym2 V, the number of transmissions m along e is at most (T : ℝ) * net.cap e; encoding matrices α : Fin M → K → Fin L → F and β : Fin M → Fin M → F; decoding matrix γ : K → Fin L → Fin M → F; index-based causality stating that β m m' ≠ 0 implies m' < m; sender locality stating α m k j ≠ 0 implies sess.src k = snd m; receiver locality stating β m m' ≠ 0 implies rcv m' = snd m; decoding locality stating γ k j m ≠ 0 implies rcv m = sess.tgt k; and correctness asserting that for every message msg : K → Fin L → F there exists a transmission valuation val : Fin M → F satisfying the local encoding equations val m = (∑ k, ∑ j, α m k j * msg k j) + (∑ m', β m m' * val m') for all m, and decoding equations msg k j = ∑ m, γ k j m * val m for all k and j.
Statement
structure CausalLinearNetworkCode (V : Type) [Fintype V] [DecidableEq V] (K : Type) [Fintype K] [DecidableEq K] (F : Type) [Field F] (net : CapacitatedNetwork V) (sess : UnicastSessions V K)
- Defined in
- arXiv:2610.10108, Sec. 2
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Built on 2
- 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 12
- 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…
- linear_code_supports_rate_monoIf LinearCodeSupportsRate F net sess r holds on net with sessions sess over field F, then for any r' ≤ r, LinearCodeSupportsRate F net…
- causal_code_vals_zero_outsideLet a causal linear code on net have transmission values val satisfying the recurrence for a message msg, where msg vanishes on sessions…
- code_transmissions_cross_cut_leIn a causal linear network code on net, the number of transmissions whose endpoints are separated by a vertex set S is at most T *…
- single_slot_advantage_of_multislot_advantageAny multi-slot coding advantage yields a one-slot coding advantage: if on some instance the code rate strictly exceeds every supported…
- 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…
- causal_code_val_uniqueFor a fixed message msg, any two assignments of transmission values satisfying the linear recurrence val m = sum alpha*msg + sum beta*val…
- 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…
- one_slot_code_rate_le_cut_ratioA one-slot (T = 1) causal linear code over any field satisfies L * (number of sessions separated by S) ≤ (capacity leaving S) for every…
- one_slot_code_of_scaled_capacitiesA deterministic causal linear code with T transmission slots on a capacitated network can be read as a one-slot (T = 1) code with the same…
- linear_code_supports_rate_unit_edgeNon-vacuity of LinearCodeSupportsRate: on the two-vertex graph with a single unit-capacity edge, with the single session 0 -> 1, a…
- 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,…
Read back from the Lean
A structure CausalLinearNetworkCode parametrized by:
- a finite type of vertices V with decidable equality,
- a finite type of session identifiers K with decidable equality,
- a field F,
- a capacitated network net : CapacitatedNetwork V,
- a set of unicast sessions sess : UnicastSessions V K,
consisting of the following data and conditions:
1. M : ℕ: the total number of transmissions.
2. T : ℕ: the time horizon (number of time steps).
3. L : ℕ: the message packet length per session.
4. hT : 0 < T: the time horizon T is strictly positive.
5. hL : 0 < L: the message packet length L is strictly positive.
6. snd : Fin M → V: the sending node for each transmission m : Fin M.
7. rcv : Fin M → V: the receiving node for each transmission m : Fin M.
8. snd_ne_rcv: for all m : Fin M, snd m ≠ rcv m (no self-transmissions).
9. cap_le: for every undirected edge e : Sym2 V, the number of transmissions m : Fin M whose endpoints {snd m, rcv m} equal e is at most (T : ℝ) * net.cap e.
10. α : Fin M → K → Fin L → F: encoding coefficients combining source messages into transmissions.
11. β : Fin M → Fin M → F: network coding coefficients combining earlier transmissions into subsequent transmissions.
12. γ : K → Fin L → Fin M → F: decoding coefficients reconstructing session messages from received transmissions.
13. causal: for all m, m' : Fin M, if β m m' ≠ 0, then m' < m (transmissions depend strictly on earlier transmissions).
14. snd_local: for all m : Fin M, k : K, and j : Fin L, if α m k j ≠ 0, then the sender snd m must be the source sess.src k.
15. rcv_local: for all m, m' : Fin M, if β m m' ≠ 0, then the sender snd m must be the receiver rcv m'.
16. dec_local: for all k : K, j : Fin L, and m : Fin M, if γ k j m ≠ 0, then the receiver rcv m must be the destination sess.tgt k.
17. correct: for every message assignment msg : K → Fin L → F, there exists a transmission valuation val : Fin M → F such that:
- for every transmission m : Fin M, val m = (∑ k : K, ∑ j : Fin L, α m k j * msg k j) + (∑ m' : Fin M, β m m' * val m'), and
- for every session k : K and index j : Fin L, msg k j = ∑ m : Fin M, γ k j m * val m.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A deterministic causal linear network code over a field F on a capacitated network. -/ structure CausalLinearNetworkCode (V : Type) [Fintype V] [DecidableEq V] (K : Type) [Fintype K] [DecidableEq K] (F : Type) [Field F] (net : CapacitatedNetwork V) (sess : UnicastSessions V K) where M : ℕ T : ℕ L : ℕ hT : 0 < T hL : 0 < L snd : Fin M → V rcv : Fin M → V snd_ne_rcv : ∀ m, snd m ≠ rcv m cap_le : ∀ e : Sym2 V, ((Finset.univ.filter (fun 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 causal : ∀ m m', β m m' ≠ 0 → m' < m snd_local : ∀ m k j, α m k j ≠ 0 → sess.src k = snd m rcv_local : ∀ m m', β m m' ≠ 0 → rcv m' = snd m dec_local : ∀ k j m, γ k j m ≠ 0 → rcv m = sess.tgt k correct : ∀ msg : K → Fin L → F, ∃ val : Fin M → F, (∀ m, val m = (∑ k, ∑ j, α m k j * msg k j) + (∑ m', β m m' * val m')) ∧ (∀ k j, msg k j = ∑ m, γ k j m * val m)