AFTD Auto-Formalizing Theoretical Domains

CausalLinearNetworkCode

structure

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)
See it in the graphDiscuss this resultChallenge it