AFTD Auto-Formalizing Theoretical Domains

linear_code_supports_rate_mono

theoremverified

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.

  1. 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).

    lines 6–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

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