one_slot_code_of_scaled_capacities
A 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 message dimension L on the network whose capacities are all multiplied by T: the capacity condition of the one-slot code on T * cap is literally the T-slot capacity condition on cap, and every other field (transmission list, encoding, decoding, causality, locality, correctness) is copied unchanged.
Statement
theorem one_slot_code_of_scaled_capacities {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) : ∃ (net' : CapacitatedNetwork V) (code' : CausalLinearNetworkCode V K F net' sess), (∀ e : Sym2 V, net'.cap e = (code.T : ℝ) * net.cap e) ∧ code'.T = 1 ∧ code'.L = code.L
- Source
- step towards single_slot_binary_linear_coding_advantage
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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,…
- Used by 1
- 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…
The proof, explained
To convert a T-slot causal linear network code into a 1-slot code, we define a new capacitated network net' whose capacities are scaled by T. We then construct a 1-slot code code' on net' with the same message dimension L by setting T = 1 and copying all transmission functions, coding matrices, and correctness proofs from the original code. The 1-slot capacity constraint on the scaled network is algebraically identical to the original T-slot capacity constraint, so the code remains valid without any modifications to its operations.
The number of time slots T is strictly positive when cast to the real numbers.
The original code satisfies T > 0 in ℕ by definition (code.hT). Casting this inequality to ℝ yields 0 < (code.T : ℝ).
have hT : (0 : ℝ) < (code.T : ℝ) := by exact_mod_cast code.hT
The scaled network net' is well-defined with edge capacities T * net.cap e.
We retain the underlying graph G and set net'.cap e = T * net.cap e. For each graph edge e, the capacity is strictly positive because it is the product of positive reals (mul_pos). For non-edges e ∉ G.edgeSet, net.cap e = 0, so the scaled capacity is also zero (mul_zero).
uses
mul_pos,mul_zerolet net' : CapacitatedNetwork V := { G := net.G, decAdj := net.decAdj, cap := fun e => (code.T : ℝ) * net.cap e, cap_pos := fun e he => mul_pos hT (net.cap_pos e he), cap_zero := fun e he => by rw [net.cap_zero e he, mul_zero] }
The original code induces a valid 1-slot causal linear code code' on net' with message dimension L.
We define code' by setting T = 1 (verified positive by norm_num since 0 < 1) while keeping M and L unchanged. The transmission schedule (snd, rcv), coding matrices (α, β, γ), and all structural properties (causality, locality, decodability) are copied directly from the original code. For the capacity condition on any undirected edge e, the required bound |{m | s(snd m, rcv m) = e}| ≤ 1 * net'.cap e simplifies, by definition of net', to the original capacity condition |{m | s(snd m, rcv m) = e}| ≤ T * net.cap e, which code already satisfies.
let code' : CausalLinearNetworkCode V K F net' sess := { M := code.M, T := 1, L := code.L, hT := by norm_num, hL := code.hL, snd := code.snd, rcv := code.rcv, snd_ne_rcv := code.snd_ne_rcv, cap_le := fun e => by have h := code.cap_le e simp only [net'] simpa using h, α := code.α, β := code.β, γ := code.γ, causal := code.causal, snd_local := code.snd_local, rcv_local := code.rcv_local, dec_local := code.dec_local, correct := code.correct }
The pair (net', code') satisfies all existential requirements of the theorem.
We provide net' and code' as existential witnesses. The capacity scaling equality net'.cap e = T * net.cap e, the one-slot condition code'.T = 1, and the dimension preservation code'.L = code.L all hold definitionally by reflexivity.
exact ⟨net', code', fun e => rfl, rfl, rfl⟩
mul_pos- The product of two strictly positive real numbers is strictly positive.
mul_zero- Multiplying any element by zero yields zero.
- In Lean, the slot count code.T is a natural number (ℕ) and edge capacities take values in ℝ, so code.T is explicitly cast to ℝ whenever it interacts with capacity values.
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.
/-- Normalisation: a T-slot code on capacities cap becomes a one-slot code with the same message dimension on capacities T * cap. -/theorem one_slot_code_of_scaled_capacities {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) : ∃ (net' : CapacitatedNetwork V) (code' : CausalLinearNetworkCode V K F net' sess), (∀ e : Sym2 V, net'.cap e = (code.T : ℝ) * net.cap e) ∧ code'.T = 1 ∧ code'.L = code.L := by have hT : (0 : ℝ) < (code.T : ℝ) := by exact_mod_cast code.hT let net' : CapacitatedNetwork V := { G := net.G, decAdj := net.decAdj, cap := fun e => (code.T : ℝ) * net.cap e, cap_pos := fun e he => mul_pos hT (net.cap_pos e he), cap_zero := fun e he => by rw [net.cap_zero e he, mul_zero] } let code' : CausalLinearNetworkCode V K F net' sess := { M := code.M, T := 1, L := code.L, hT := by norm_num, hL := code.hL, snd := code.snd, rcv := code.rcv, snd_ne_rcv := code.snd_ne_rcv, cap_le := fun e => by have h := code.cap_le e simp only [net'] simpa using h, α := code.α, β := code.β, γ := code.γ, causal := code.causal, snd_local := code.snd_local, rcv_local := code.rcv_local, dec_local := code.dec_local, correct := code.correct } exact ⟨net', code', fun e => rfl, rfl, rfl⟩