linear_code_rate_le_cut_cone_bound
If a linear network code over a field F supports the common rate r, then for any finite family of vertex sets cuts and any nonnegative weights y on them with positive total weighted separation, r is at most (sum over cuts of y*cutCapacity)/(sum over cuts of y*cutSeparation).
Statement
theorem linear_code_rate_le_cut_cone_bound {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K] (F : Type) [Field F] (net : CapacitatedNetwork V) (sess : UnicastSessions V K) {r : ℝ} (h : LinearCodeSupportsRate F net sess r) (cuts : Finset (Finset V)) (y : Finset V → ℝ) (hy : ∀ S ∈ cuts, 0 ≤ y S) (hpos : 0 < ∑ S ∈ cuts, y S * (cutSeparation sess S : ℝ)) : r ≤ (∑ S ∈ cuts, y S * cutCapacity net S) / (∑ S ∈ cuts, y S * (cutSeparation sess S : ℝ))
- Source
- step towards undirected_binary_linear_unicast_advantage
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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…
- 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…
- 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…
- 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,…
- 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…
- 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…
The proof, explained
To show that the rate r is bounded by the weighted cut ratio, the proof first clears the positive denominator and distributes r across the sum, reducing the goal to a term-by-term comparison for each cut. For each cut S, the single-cut bound provides r * cutSeparation(S) ≤ cutCapacity(S). Scaling this inequality by the nonnegative weight y(S) and summing over all cuts yields the desired bound.
It suffices to prove the inequality termwise: for every cut S ∈ cuts, r * (y S * cutSeparation sess S) ≤ y S * cutCapacity net S.
Because the total weighted separation ∑ S ∈ cuts, y S * cutSeparation sess S is strictly positive by hypothesis hpos, clearing the denominator via le_div_iff₀ turns the goal r ≤ A / B into r * B ≤ A. Distributing r across the sum with Finset.mul_sum yields a comparison between two sums over cuts. By Finset.sum_le_sum, this comparison holds if the inequality holds term-by-term for each cut S ∈ cuts.
uses
le_div_iff₀,Finset.mul_sum,Finset.sum_le_sumrw [le_div_iff₀ hpos, Finset.mul_sum] apply Finset.sum_le_sum
For every cut S ∈ cuts, the weighted cut bound r * (y S * cutSeparation sess S) ≤ y S * cutCapacity net S holds.
Fixing an arbitrary cut S ∈ cuts, the single-cut bound linear_code_supports_rate_cut_bound gives r * cutSeparation sess S ≤ cutCapacity net S. By hypothesis hy, the weight y S is nonnegative (hyS : 0 ≤ y S). Multiplying the single-cut bound by y S preserves the inequality, which nonlinear arithmetic (nlinarith) verifies.
uses
linear_code_supports_rate_cut_boundintro S hS have hcut := linear_code_supports_rate_cut_bound F net sess h S have hyS := hy S hS nlinarith
le_div_iff₀- For a positive element c in a linearly ordered division structure (such as ℝ), a ≤ b / c is equivalent to a * c ≤ b.
Finset.mul_sum- Multiplication distributes over a finite sum: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.sum_le_sum- An inequality between two finite sums over the same index set holds if it holds term-by-term for every element.
linear_code_supports_rate_cut_bound- If a linear network code supports rate r, then for any cut S, r times the separation of S is at most the 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.
/-- Cut cone bound: a linear code's rate is at most the weighted cut ratio for any nonnegative weighting of cuts. -/theorem linear_code_rate_le_cut_cone_bound {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K] (F : Type) [Field F] (net : CapacitatedNetwork V) (sess : UnicastSessions V K) {r : ℝ} (h : LinearCodeSupportsRate F net sess r) (cuts : Finset (Finset V)) (y : Finset V → ℝ) (hy : ∀ S ∈ cuts, 0 ≤ y S) (hpos : 0 < ∑ S ∈ cuts, y S * (cutSeparation sess S : ℝ)) : r ≤ (∑ S ∈ cuts, y S * cutCapacity net S) / (∑ S ∈ cuts, y S * (cutSeparation sess S : ℝ)) := by rw [le_div_iff₀ hpos, Finset.mul_sum] apply Finset.sum_le_sum intro S hS have hcut := linear_code_supports_rate_cut_bound F net sess h S have hyS := hy S hS nlinarith