AFTD Auto-Formalizing Theoretical Domains

linear_code_rate_le_cut_cone_bound

theoremverified

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.

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

    lines 9–10

    uses le_div_iff₀, Finset.mul_sum, Finset.sum_le_sum

      rw [le_div_iff₀ hpos, Finset.mul_sum]
      apply Finset.sum_le_sum
  2. 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.

    lines 11–14

    uses linear_code_supports_rate_cut_bound

      intro 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

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