one_slot_code_rate_le_cut_ratio
A one-slot (T = 1) causal linear code over any field satisfies L * (number of sessions separated by S) ≤ (capacity leaving S) for every vertex set S: with one transmission slot the common rate of the code is exactly its message dimension L, so the general cut bound applies with r = L.
Statement
theorem one_slot_code_rate_le_cut_ratio {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) (hT : code.T = 1) (S : Finset V) : (code.L : ℝ) * (cutSeparation sess S : ℝ) ≤ cutCapacity net S
- Source
- step towards single_slot_binary_linear_coding_advantage
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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…
- 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…
- 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…
- cutCapacityThe total capacity of the edges of the network leaving a vertex set S: the sum over u ∈ S and all v of cap({u,v}), with the terms where v…
- cutSeparationThe number of sessions (out of the unicast session set sess) with exactly one endpoint in the vertex set S, i.e. the number of sessions…
The proof, explained
The theorem establishes that for a one-slot (T = 1) causal linear network code, the message dimension L satisfies the cut bound L * cutSeparation(S) ≤ cutCapacity(S) for any vertex set S. The proof applies the general cut bound linear_code_supports_rate_cut_bound with rate r = L, reducing the claim to showing that the network supports rate L. This is verified by using the code itself as the witness, since with T = 1 its achieved rate L / T is exactly L.
It suffices to show that the network supports rate code.L.
By linear_code_supports_rate_cut_bound, any rate r supported by a causal linear code satisfies r * cutSeparation(S) ≤ cutCapacity(S) for all cuts S. Applying this lemma with rate r = code.L reduces the goal to showing that code.L is supported by the network (LinearCodeSupportsRate F net sess code.L).
uses
linear_code_supports_rate_cut_boundapply linear_code_supports_rate_cut_bound F net sess (r := (code.L : ℝ)) (S := S)The network supports rate code.L, concluding the proof.
Unfolding the definition of LinearCodeSupportsRate, we must exhibit a causal linear code whose rate L' / T' is at least code.L. Using code itself as the witness, its rate is code.L / code.T. Since hT states code.T = 1, this simplifies to code.L / 1 = code.L, which trivially satisfies code.L ≤ code.L.
unfold LinearCodeSupportsRate exact ⟨code, by rw [hT]; simp⟩
linear_code_supports_rate_cut_bound- For any capacitated network and unicast sessions, if a transmission rate r is supported by a causal linear network code, then for every vertex cut S, the product of r and the number of sessions separated by S is at most the cut capacity of S.
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.
/-- A one-slot code's message dimension is bounded by every cut ratio cap(δS)/sep(S). -/theorem one_slot_code_rate_le_cut_ratio {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) (hT : code.T = 1) (S : Finset V) : (code.L : ℝ) * (cutSeparation sess S : ℝ) ≤ cutCapacity net S := by apply linear_code_supports_rate_cut_bound F net sess (r := (code.L : ℝ)) (S := S) unfold LinearCodeSupportsRate exact ⟨code, by rw [hT]; simp⟩