linear_code_supports_rate_mono
If LinearCodeSupportsRate F net sess r holds on net with sessions sess over field F, then for any r' ≤ r, LinearCodeSupportsRate F net sess r' also holds.
Statement
theorem linear_code_supports_rate_mono {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K] (F : Type) [Field F] (net : CapacitatedNetwork V) (sess : UnicastSessions V K) {r r' : ℝ} (h_supp : LinearCodeSupportsRate F net sess r) (h_le : r' ≤ r) : LinearCodeSupportsRate F net sess r'
- Source
- folklore
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
Read back from the Lean
Let $V$ and $K$ be finite types with decidable equality, let $F$ be a field, let $net$ be a capacitated network on $V$, and let $sess$ be unicast sessions on $V$ indexed by $K$. Let $r, r' \in \mathbb{R}$. If $net$ and $sess$ support rate $r$ with a causal linear network code over $F$, and $r' \le r$, then $net$ and $sess$ also support rate $r'$ with a causal linear network code over $F$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The property that a network supports a linear network coding rate is defined existentially by the existence of a causal linear network code achieving rate $L/T \ge r$. To show that any lower rate $r' \le r$ is also supported, we reuse the exact same code: by transitivity of inequality on the real numbers, $r' \le r \le L/T$, so the code witnesses that $r'$ is supported as well.
The network code supporting rate $r$ also witnesses that rate $r'$ is supported.
From the hypothesis `h_supp` that rate $r$ is supported, unpacking the definition of `LinearCodeSupportsRate` provides a causal linear network code `code` whose message length $L$ and time horizon $T$ satisfy $r \le L/T$ (line 6). Since $r' \le r$ by hypothesis `h_le`, transitivity of $\le$ on $\mathbb{R}$ gives $r' \le L/T$. Providing `code` alongside this inequality (`h_le.trans hcode`) proves that rate $r'$ is supported (line 7).
obtain ⟨code, hcode⟩ := h_supp exact ⟨code, h_le.trans hcode⟩
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.
/-- Achievable linear network coding rates are downward-closed. -/theorem linear_code_supports_rate_mono {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K] (F : Type) [Field F] (net : CapacitatedNetwork V) (sess : UnicastSessions V K) {r r' : ℝ} (h_supp : LinearCodeSupportsRate F net sess r) (h_le : r' ≤ r) : LinearCodeSupportsRate F net sess r' := by obtain ⟨code, hcode⟩ := h_supp exact ⟨code, h_le.trans hcode⟩