AFTD Auto-Formalizing Theoretical Domains

linear_code_supports_rate_cut_bound

theoremverified

If 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 number of sessions crossing S is at most the total capacity leaving S.

Statement

theorem linear_code_supports_rate_cut_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) (S : Finset V) :
    r * (cutSeparation sess S : ℝ) ≤ cutCapacity net S
Source
step towards undirected_binary_linear_unicast_advantage
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10
  • 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…
  • 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…
  • code_transmissions_cross_cut_leIn a causal linear network code on net, the number of transmissions whose endpoints are separated by a vertex set S is at most T *…
  • causal_code_vals_zero_outsideLet a causal linear code on net have transmission values val satisfying the recurrence for a message msg, where msg vanishes on sessions…
  • causal_code_val_uniqueFor a fixed message msg, any two assignments of transmission values satisfying the linear recurrence val m = sum alpha*msg + sum beta*val…
  • 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,…
  • 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…
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Used by 2
  • linear_code_rate_le_cut_cone_boundIf 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…
  • one_slot_code_rate_le_cut_ratioA one-slot (T = 1) causal linear code over any field satisfies L * (number of sessions separated by S) ≤ (capacity leaving S) for every…

The proof, explained

To establish the cut-set bound, the proof constructs a linear map from messages on sessions crossing a cut S to the wire values on transmissions leaving S. By causality of the network code and locality of decoding at receivers outside S, wire values received outside S must vanish when all cut transmissions vanish, which implies that the cut map is injective. Comparing the vector space dimensions yields that the number of crossing sessions times the packet length L is at most the number of cut transmissions. Summing this bound for S and its complement Sᶜ, the total cut transmissions are bounded by the transmission capacity of the cut times the time horizon T, and dividing by T gives r times the cut separation is at most the cut capacity.

  1. The wire values assigned by the network code depend additively on the input messages: val(msg + msg') = val(msg) + val(msg').

    By the uniqueness of the solution to the causal wire recurrence relation (causal_code_val_unique), it suffices to check that the pointwise sum val(msg) + val(msg') satisfies the recurrence relation for the sum of messages msg + msg'. Substituting the recurrence for each message (linear_code_supports_rate_cut_bound_code_val_recurrence) and distributing multiplication over addition (mul_add, Finset.sum_add_distrib), the result follows by abelian group simplification (abel).

    lines 29–35

    uses causal_code_val_unique, linear_code_supports_rate_cut_bound_code_val_recurrence, Pi.add_apply, mul_add, Finset.sum_add_distrib

      apply causal_code_val_unique F net sess code (msg + msg')
      · exact linear_code_supports_rate_cut_bound_code_val_recurrence code (msg + msg')
      · intro m
        rw [Pi.add_apply, linear_code_supports_rate_cut_bound_code_val_recurrence code msg m,
          linear_code_supports_rate_cut_bound_code_val_recurrence code msg' m]
        simp only [Pi.add_apply, mul_add, Finset.sum_add_distrib]
        abel
  2. The wire values assigned by the network code depend homogeneously on the input messages: val(c • msg) = c • val(msg).

    Applying uniqueness of solutions to the causal recurrence (causal_code_val_unique), it suffices to verify that c • val(msg) satisfies the recurrence for c • msg. Expanding both sides using the recurrence (linear_code_supports_rate_cut_bound_code_val_recurrence) and distributing the scalar factor into the sums (Finset.mul_sum, smul_eq_mul), the equality reduces to ring arithmetic in the field F.

    lines 43–53

    uses causal_code_val_unique, linear_code_supports_rate_cut_bound_code_val_recurrence, Pi.smul_apply, smul_eq_mul, mul_add, Finset.mul_sum, Finset.sum_congr

      apply causal_code_val_unique F net sess code (c • msg)
      · exact linear_code_supports_rate_cut_bound_code_val_recurrence code (c • msg)
      · intro m
        rw [Pi.smul_apply, linear_code_supports_rate_cut_bound_code_val_recurrence code msg m]
        simp only [Pi.smul_apply, smul_eq_mul, mul_add, Finset.mul_sum]
        congr 1
        · apply Finset.sum_congr rfl; intro k _
          apply Finset.sum_congr rfl; intro j _
          ring
        · apply Finset.sum_congr rfl; intro m' _
          ring
  3. The cut transmission map preserves message addition: cut_map(f + g) = cut_map(f) + cut_map(g).

    Extending the sum of two messages on sessions crossing S with zeros outside S gives the sum of their individual zero-extensions. The additivity of code wire values (linear_code_supports_rate_cut_bound_code_val_add) then ensures that the resulting transmission values on the cut are additive.

    lines 75–82

    uses Pi.add_apply, linear_code_supports_rate_cut_bound_code_val_add

        ext m
        have h_ext : linear_code_supports_rate_cut_bound_extend_msg code.L S (f + g) =
          linear_code_supports_rate_cut_bound_extend_msg code.L S f + linear_code_supports_rate_cut_bound_extend_msg code.L S g := by
          ext k j
          simp only [linear_code_supports_rate_cut_bound_extend_msg, Pi.add_apply]
          split_ifs <;> simp
        rw [h_ext, linear_code_supports_rate_cut_bound_code_val_add]
        rfl
  4. The cut transmission map preserves scalar multiplication: cut_map(c • f) = c • cut_map(f).

    Extending a scaled message c • f by zeros outside the cut produces c times the zero-extended message of f. By scalar multiplicativity of code wire values (linear_code_supports_rate_cut_bound_code_val_smul), the transmission values on the cut scale by c, establishing linearity.

    lines 84–91

    uses Pi.smul_apply, linear_code_supports_rate_cut_bound_code_val_smul

        ext m
        have h_ext : linear_code_supports_rate_cut_bound_extend_msg code.L S (c • f) =
          c • linear_code_supports_rate_cut_bound_extend_msg code.L S f := by
          ext k j
          simp only [linear_code_supports_rate_cut_bound_extend_msg, Pi.smul_apply]
          split_ifs <;> simp
        rw [h_ext, linear_code_supports_rate_cut_bound_code_val_smul]
        rfl
  5. If a message f on crossing sessions produces all-zero cut transmissions, then all wire values received outside S are zero.

    To prove injectivity of the linear cut map, it suffices to show that any message f in its kernel is zero (injective_iff_map_eq_zero). When the cut transmissions are zero, every transmission originating in S and received outside S evaluates to zero (congr_fun). Since f is zero-extended outside S, no non-zero messages originate outside S. By causal_code_vals_zero_outside, all transmissions received outside S must carry value zero.

    lines 97–115

    uses injective_iff_map_eq_zero, congr_fun, causal_code_vals_zero_outside, linear_code_supports_rate_cut_bound_code_val_recurrence, False.elim

      rw [injective_iff_map_eq_zero]
      intro f hf
      have h_mzero : ∀ m : linear_code_supports_rate_cut_bound_mout code S,
          linear_code_supports_rate_cut_bound_code_val code (linear_code_supports_rate_cut_bound_extend_msg code.L S f) m.1 = 0 := by
        intro m
        exact congr_fun hf m
      have h_outside := causal_code_vals_zero_outside F net sess code S
        (linear_code_supports_rate_cut_bound_extend_msg code.L S f)
        (linear_code_supports_rate_cut_bound_code_val code (linear_code_supports_rate_cut_bound_extend_msg code.L S f))
        (linear_code_supports_rate_cut_bound_code_val_recurrence code (linear_code_supports_rate_cut_bound_extend_msg code.L S f))
        (by
          intro k j hk
          dsimp [linear_code_supports_rate_cut_bound_extend_msg]
          split_ifs with h
          · exact False.elim (hk h.1)
          · rfl)
        (by
          intro m hsnd hrcv
          exact h_mzero ⟨m, hsnd, hrcv⟩)
  6. Any message in the kernel of the cut map is zero, so the cut map is injective.

    For each session k crossing from S to Sᶜ, its destination tgt(k) is outside S. By the decoding relation (linear_code_supports_rate_cut_bound_code_val_decode), the decoded symbol is a linear combination of received wire values. Decoding locality ensures that non-zero decoding coefficients γ only attach to wires received at tgt(k), which are outside S and therefore evaluate to zero. Hence each term vanishes (zero_mul, mul_zero), so the decoded message f(k) is zero (Finset.sum_eq_zero), proving injectivity.

    lines 116–132

    uses linear_code_supports_rate_cut_bound_code_val_decode, Finset.sum_eq_zero, zero_mul, mul_zero

      ext ⟨k, hk⟩ j
      have h_dec := linear_code_supports_rate_cut_bound_code_val_decode code
        (linear_code_supports_rate_cut_bound_extend_msg code.L S f) k j
      dsimp [linear_code_supports_rate_cut_bound_extend_msg] at h_dec
      split_ifs at h_dec
      rw [h_dec]
      apply Finset.sum_eq_zero
      intro m _
      by_cases hγ : code.γ k j m = 0
      · rw [hγ, zero_mul]
      · have h_tgt := code.dec_local k j m hγ
        have h_rcv_not : code.rcv m ∉ S := by
          rw [h_tgt]
          exact hk.2
        have h_val_zero := h_outside m h_rcv_not
        rw [h_val_zero, mul_zero]
    
  7. The number of sessions crossing from S to Sᶜ times L is at most the number of transmissions crossing from S to Sᶜ: |K_out(S)| * L ≤ |M_out(S)|.

    Because the cut map is an injective linear map between finite-dimensional F-vector spaces (LinearMap.finrank_le_finrank_of_injective), the dimension of the domain is at most the dimension of the codomain. Uncurrying identifies the domain with functions from K_out(S) × Fin L to F (LinearEquiv.curry, LinearEquiv.finrank_eq), whose dimension is |K_out(S)| * L (Module.finrank_fintype_fun_eq_card, Fintype.card_prod, Fintype.card_fin), while the codomain has dimension |M_out(S)|.

    lines 138–147

    uses linear_code_supports_rate_cut_bound_cut_map_injective, LinearMap.finrank_le_finrank_of_injective, LinearEquiv.curry, LinearEquiv.finrank_eq, Module.finrank_fintype_fun_eq_card, Fintype.card_prod, Fintype.card_fin

      have hinj := linear_code_supports_rate_cut_bound_cut_map_injective code S
      have hrank := LinearMap.finrank_le_finrank_of_injective hinj
      have e : (linear_code_supports_rate_cut_bound_kout sess S → Fin code.L → F) ≃ₗ[F]
          (linear_code_supports_rate_cut_bound_kout sess S × Fin code.L → F) :=
        (LinearEquiv.curry F F (linear_code_supports_rate_cut_bound_kout sess S) (Fin code.L)).symm
      rw [LinearEquiv.finrank_eq e] at hrank
      rw [Module.finrank_fintype_fun_eq_card] at hrank
      rw [Module.finrank_fintype_fun_eq_card] at hrank
      rw [Fintype.card_prod, Fintype.card_fin] at hrank
      exact hrank
  8. Summing the cut inequalities for S and Sᶜ bounds crossing sessions in both directions: (|K_out(S)| + |K_out(Sᶜ)|) * L ≤ |M_out(S)| + |M_out(Sᶜ)|.

    From the hypothesis that the code supports rate r, we extract the code and the condition r ≤ L/T. Applying the dimension bound (linear_code_supports_rate_cut_bound_cut_card_le) to S and its complement Sᶜ, and adding the resulting inequalities (add_le_add), yields the combined inequality after factoring out L.

    lines 155–165

    uses linear_code_supports_rate_cut_bound_cut_card_le, add_le_add

      rcases h with ⟨code, hr⟩
      have h_le_S := linear_code_supports_rate_cut_bound_cut_card_le code S
      have h_le_Sc := linear_code_supports_rate_cut_bound_cut_card_le code Sᶜ
      have h_sum_le : (Fintype.card (linear_code_supports_rate_cut_bound_kout sess S) +
          Fintype.card (linear_code_supports_rate_cut_bound_kout sess Sᶜ)) * code.L ≤
        Fintype.card (linear_code_supports_rate_cut_bound_mout code S) +
          Fintype.card (linear_code_supports_rate_cut_bound_mout code Sᶜ) := by
        calc
          _ = Fintype.card (linear_code_supports_rate_cut_bound_kout sess S) * code.L +
              Fintype.card (linear_code_supports_rate_cut_bound_kout sess Sᶜ) * code.L := by ring
          _ ≤ _ := add_le_add h_le_S h_le_Sc
  9. Cut separation partitions into crossing sessions in both directions, and similarly cut transmissions partition by direction: (cutSeparation sess S) * L ≤ |M_cut|.

    A session crosses cut S if and only if its source and target are on opposite sides of S, which decomposes into the disjoint union of sessions going from S to Sᶜ and those going from Sᶜ to S (Finset.disjoint_filter). Thus cutSeparation sess S equals |K_out(S)| + |K_out(Sᶜ)| (Finset.card_union_of_disjoint, Fintype.card_subtype). The same disjoint union argument shows the total number of cut-crossing transmissions equals |M_out(S)| + |M_out(Sᶜ)|. Substituting these into the summed inequality rewrites the bound as (cutSeparation sess S) * L ≤ |M_cut|.

    lines 166–198

    uses Fintype.card_subtype, true_and, Finset.card_union_of_disjoint, Finset.disjoint_filter, Finset.mem_filter, Finset.mem_univ, Finset.mem_union, Finset.mem_compl

      have h_k_eq : cutSeparation sess S =
          Fintype.card (linear_code_supports_rate_cut_bound_kout sess S) +
          Fintype.card (linear_code_supports_rate_cut_bound_kout sess Sᶜ) := by
        dsimp [cutSeparation]
        rw [Fintype.card_subtype, Fintype.card_subtype]
        have h_eq : (Finset.univ.filter (fun k => (sess.src k ∈ S) ≠ (sess.tgt k ∈ S))) =
          (Finset.univ.filter (fun k => sess.src k ∈ S ∧ sess.tgt k ∉ S)) ∪
          (Finset.univ.filter (fun k => sess.src k ∈ Sᶜ ∧ sess.tgt k ∉ Sᶜ)) := by
          ext k
          simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union, Finset.mem_compl]
          tauto
        rw [h_eq, Finset.card_union_of_disjoint]
        rw [Finset.disjoint_filter]
        intro k _ h1 h2
        simp only [Finset.mem_compl] at h2
        exact h2.1 h1.1
      have h_m_eq : (Finset.univ.filter (fun m : Fin code.M => (code.snd m ∈ S) ≠ (code.rcv m ∈ S))).card =
          Fintype.card (linear_code_supports_rate_cut_bound_mout code S) +
          Fintype.card (linear_code_supports_rate_cut_bound_mout code Sᶜ) := by
        rw [Fintype.card_subtype, Fintype.card_subtype]
        have h_eq : (Finset.univ.filter (fun m : Fin code.M => (code.snd m ∈ S) ≠ (code.rcv m ∈ S))) =
          (Finset.univ.filter (fun m => code.snd m ∈ S ∧ code.rcv m ∉ S)) ∪
          (Finset.univ.filter (fun m => code.snd m ∈ Sᶜ ∧ code.rcv m ∉ Sᶜ)) := by
          ext m
          simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union, Finset.mem_compl]
          tauto
        rw [h_eq, Finset.card_union_of_disjoint]
        rw [Finset.disjoint_filter]
        intro m _ h1 h2
        simp only [Finset.mem_compl] at h2
        exact h2.1 h1.1
      rw [← h_k_eq] at h_sum_le
      rw [← h_m_eq] at h_sum_le
  10. r * cutSeparation sess S ≤ cutCapacity net S.

    By code_transmissions_cross_cut_le, the number of transmissions crossing cut S is bounded by T * cutCapacity net S, giving (cutSeparation sess S) * L ≤ T * cutCapacity net S by transitivity (le_trans). Dividing by T > 0 gives (cutSeparation sess S) * (L / T) ≤ cutCapacity net S (div_le_iff₀). Since the code supports rate r, r ≤ L / T. Multiplying by the non-negative cut separation (Nat.cast_nonneg, mul_le_mul_of_nonneg_right) and combining via linear arithmetic (linarith) proves the theorem.

    lines 199–214

    uses code_transmissions_cross_cut_le, le_trans, Nat.cast_nonneg, mul_le_mul_of_nonneg_right, div_le_iff₀

      have h_trans := code_transmissions_cross_cut_le F net sess code S
      have h_sep_L_le : (cutSeparation sess S : ℝ) * (code.L : ℝ) ≤ (code.T : ℝ) * cutCapacity net S := by
        have h_nat : (cutSeparation sess S : ℝ) * (code.L : ℝ) ≤
          ↑(Finset.univ.filter (fun m : Fin code.M => (code.snd m ∈ S) ≠ (code.rcv m ∈ S))).card := by
          exact_mod_cast h_sum_le
        exact le_trans h_nat h_trans
      have hT_pos : 0 < (code.T : ℝ) := Nat.cast_pos.mpr code.hT
      have hsep_nonneg : 0 ≤ (cutSeparation sess S : ℝ) := Nat.cast_nonneg (cutSeparation sess S)
      have h1 : r * (cutSeparation sess S : ℝ) ≤ ((code.L : ℝ) / (code.T : ℝ)) * (cutSeparation sess S : ℝ) :=
        mul_le_mul_of_nonneg_right hr hsep_nonneg
      have h2 : ((code.L : ℝ) / (code.T : ℝ)) * (cutSeparation sess S : ℝ) =
        ((cutSeparation sess S : ℝ) * (code.L : ℝ)) / (code.T : ℝ) := by ring
      rw [h2] at h1
      have h3 : ((cutSeparation sess S : ℝ) * (code.L : ℝ)) / (code.T : ℝ) ≤ cutCapacity net S := by
        exact (div_le_iff₀ hT_pos).mpr (by linarith)
      linarith
causal_code_val_unique
For a causal linear network code and message msg, the recurrence relation determining wire values has a unique solution.
linear_code_supports_rate_cut_bound_code_val_recurrence
The wire value on transmission m satisfies the linear recurrence in the source messages and earlier wire values.
Pi.add_apply
Pointwise addition of functions evaluates to the sum of their values: (f + g) x = f x + g x.
mul_add
Multiplication distributes over addition on the left: a * (b + c) = a * b + a * c.
Finset.sum_add_distrib
The sum of a sum over a finite set equals the sum of the individual sums: ∑ (f x + g x) = ∑ f x + ∑ g x.
linear_code_supports_rate_cut_bound_code_val_smul
Wire values depend homogeneously on the transmitted messages: val(c • msg) = c • val(msg).
Pi.smul_apply
Pointwise scalar multiplication evaluates to the scaled value: (c • f) x = c • f x.
smul_eq_mul
In a field, scalar multiplication by an element is standard field multiplication: c • x = c * x.
Finset.mul_sum
A scalar factor distributes over a finite sum: a * ∑ f x = ∑ a * f x.
Finset.sum_congr
Two finite sums over equal index sets with pointwise equal summands are equal.
linear_code_supports_rate_cut_bound_code_val_add
Wire values depend additively on the transmitted messages: val(msg + msg') = val(msg) + val(msg').
injective_iff_map_eq_zero
A linear map is injective if and only if its kernel is trivial (f a = 0 implies a = 0).
congr_fun
Equal functions take equal values on any argument: f = g implies f a = g a.
causal_code_vals_zero_outside
If no messages originate outside S and all transmissions leaving S carry value zero, then every wire value received outside S is zero.
False.elim
From a contradiction (False), any proposition follows.
linear_code_supports_rate_cut_bound_code_val_decode
The decoded message symbol of session k at index j equals the linear combination of wire values weighted by decoding coefficients γ.
Finset.sum_eq_zero
A sum over a finite set whose terms are all zero evaluates to zero.
zero_mul
Multiplication by zero on the left gives zero: 0 * b = 0.
mul_zero
Multiplication by zero on the right gives zero: a * 0 = 0.
linear_code_supports_rate_cut_bound_cut_map_injective
The cut transmission map from crossing session messages to cut transmissions is injective.
LinearMap.finrank_le_finrank_of_injective
An injective linear map between finite-dimensional spaces satisfies dim(domain) ≤ dim(codomain).
LinearEquiv.curry
The canonical linear equivalence between functions on a product space V × V₂ and curried functions V → V₂ → M.
LinearEquiv.finrank_eq
Linearly equivalent vector spaces have equal finite dimension.
Module.finrank_fintype_fun_eq_card
The dimension of the vector space of functions from a finite type η to the base field equals |η|.
Fintype.card_prod
The cardinality of a Cartesian product of two finite types is the product of their cardinalities: |α × β| = |α| * |β|.
Fintype.card_fin
The cardinality of Fin n is n.
linear_code_supports_rate_cut_bound_cut_card_le
The number of sessions crossing from S to Sᶜ times packet length L is at most the number of transmissions crossing from S to Sᶜ.
add_le_add
Addition preserves inequalities: a ≤ b and c ≤ d imply a + c ≤ b + d.
Fintype.card_subtype
The cardinality of a subtype {x // p x} equals the cardinality of the filtered set of elements satisfying p.
true_and
For any proposition p, True ∧ p is equivalent to p.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.disjoint_filter
Two filtered subsets of a finset are disjoint if and only if no element satisfies both conditions.
Finset.mem_filter
Membership in a filtered set: x ∈ filter p s ↔ x ∈ s ∧ p x.
Finset.mem_univ
Every element belongs to the universal finset: x ∈ Finset.univ.
Finset.mem_union
Membership in a union: x ∈ s ∪ t ↔ x ∈ s ∨ x ∈ t.
Finset.mem_compl
Membership in the complement: x ∈ sᶜ ↔ x ∉ s.
code_transmissions_cross_cut_le
The total number of transmissions crossing cut S in a network code is at most T times the cut capacity of S.
le_trans
Inequality is transitive: a ≤ b and b ≤ c imply a ≤ c.
Nat.cast_nonneg
The coercion of any natural number into an ordered semiring is non-negative: 0 ≤ (n : ℝ).
mul_le_mul_of_nonneg_right
Multiplying an inequality by a non-negative quantity on the right preserves the inequality: b ≤ c and 0 ≤ a imply b * a ≤ c * a.
div_le_iff₀
For c > 0, b / c ≤ a if and only if b ≤ a * c.

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

noncomputable def linear_code_supports_rate_cut_bound_code_val    {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) (msg : K → Fin code.L → F) :    Fin code.M → F :=  (code.correct msg).choosetheorem linear_code_supports_rate_cut_bound_code_val_recurrence    {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) (msg : K → Fin code.L → F) (m : Fin code.M) :    linear_code_supports_rate_cut_bound_code_val code msg m =      ∑ k, ∑ j, code.α m k j * msg k j + ∑ m', code.β m m' * linear_code_supports_rate_cut_bound_code_val code msg m' :=  (code.correct msg).choose_spec.1 mtheorem linear_code_supports_rate_cut_bound_code_val_decode    {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) (msg : K → Fin code.L → F) (k : K) (j : Fin code.L) :    msg k j = ∑ m, code.γ k j m * linear_code_supports_rate_cut_bound_code_val code msg m :=  (code.correct msg).choose_spec.2 k jtheorem linear_code_supports_rate_cut_bound_code_val_add    {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) (msg msg' : K → Fin code.L → F) :    linear_code_supports_rate_cut_bound_code_val code (msg + msg') =      linear_code_supports_rate_cut_bound_code_val code msg + linear_code_supports_rate_cut_bound_code_val code msg' := by  apply causal_code_val_unique F net sess code (msg + msg')  · exact linear_code_supports_rate_cut_bound_code_val_recurrence code (msg + msg')  · intro m    rw [Pi.add_apply, linear_code_supports_rate_cut_bound_code_val_recurrence code msg m,      linear_code_supports_rate_cut_bound_code_val_recurrence code msg' m]    simp only [Pi.add_apply, mul_add, Finset.sum_add_distrib]    abeltheorem linear_code_supports_rate_cut_bound_code_val_smul    {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) (c : F) (msg : K → Fin code.L → F) :    linear_code_supports_rate_cut_bound_code_val code (c • msg) =      c • linear_code_supports_rate_cut_bound_code_val code msg := by  apply causal_code_val_unique F net sess code (c • msg)  · exact linear_code_supports_rate_cut_bound_code_val_recurrence code (c • msg)  · intro m    rw [Pi.smul_apply, linear_code_supports_rate_cut_bound_code_val_recurrence code msg m]    simp only [Pi.smul_apply, smul_eq_mul, mul_add, Finset.mul_sum]    congr 1    · apply Finset.sum_congr rfl; intro k _      apply Finset.sum_congr rfl; intro j _      ring    · apply Finset.sum_congr rfl; intro m' _      ringabbrev linear_code_supports_rate_cut_bound_kout {V K : Type} (sess : UnicastSessions V K) (S : Finset V) :=  {k : K // sess.src k ∈ S ∧ sess.tgt k ∉ S}abbrev linear_code_supports_rate_cut_bound_mout {V K F : Type} [Fintype V] [DecidableEq V] [Fintype K] [DecidableEq K] [Field F]    {net : CapacitatedNetwork V} {sess : UnicastSessions V K}    (code : CausalLinearNetworkCode V K F net sess) (S : Finset V) :=  {m : Fin code.M // code.snd m ∈ S ∧ code.rcv m ∉ S}noncomputable def linear_code_supports_rate_cut_bound_extend_msg {V K F : Type} [Zero F] [DecidableEq V]    {sess : UnicastSessions V K} (L : ℕ) (S : Finset V)    (f : linear_code_supports_rate_cut_bound_kout sess S → Fin L → F) : K → Fin L → F :=  fun k j => if h : sess.src k ∈ S ∧ sess.tgt k ∉ S then f ⟨k, h⟩ j else 0noncomputable def linear_code_supports_rate_cut_bound_cut_map {V K F : Type} [Fintype V] [DecidableEq V] [Fintype K] [DecidableEq K] [Field F]    {net : CapacitatedNetwork V} {sess : UnicastSessions V K}    (code : CausalLinearNetworkCode V K F net sess) (S : Finset V) :    (linear_code_supports_rate_cut_bound_kout sess S → Fin code.L → F) →ₗ[F]      (linear_code_supports_rate_cut_bound_mout code S → F) where  toFun f m := linear_code_supports_rate_cut_bound_code_val code (linear_code_supports_rate_cut_bound_extend_msg code.L S f) m.1  map_add' f g := by    ext m    have h_ext : linear_code_supports_rate_cut_bound_extend_msg code.L S (f + g) =      linear_code_supports_rate_cut_bound_extend_msg code.L S f + linear_code_supports_rate_cut_bound_extend_msg code.L S g := by      ext k j      simp only [linear_code_supports_rate_cut_bound_extend_msg, Pi.add_apply]      split_ifs <;> simp    rw [h_ext, linear_code_supports_rate_cut_bound_code_val_add]    rfl  map_smul' c f := by    ext m    have h_ext : linear_code_supports_rate_cut_bound_extend_msg code.L S (c • f) =      c • linear_code_supports_rate_cut_bound_extend_msg code.L S f := by      ext k j      simp only [linear_code_supports_rate_cut_bound_extend_msg, Pi.smul_apply]      split_ifs <;> simp    rw [h_ext, linear_code_supports_rate_cut_bound_code_val_smul]    rfltheorem linear_code_supports_rate_cut_bound_cut_map_injective {V K F : Type} [Fintype V] [DecidableEq V] [Fintype K] [DecidableEq K] [Field F]    {net : CapacitatedNetwork V} {sess : UnicastSessions V K}    (code : CausalLinearNetworkCode V K F net sess) (S : Finset V) :    Function.Injective (linear_code_supports_rate_cut_bound_cut_map code S) := by  rw [injective_iff_map_eq_zero]  intro f hf  have h_mzero : ∀ m : linear_code_supports_rate_cut_bound_mout code S,      linear_code_supports_rate_cut_bound_code_val code (linear_code_supports_rate_cut_bound_extend_msg code.L S f) m.1 = 0 := by    intro m    exact congr_fun hf m  have h_outside := causal_code_vals_zero_outside F net sess code S    (linear_code_supports_rate_cut_bound_extend_msg code.L S f)    (linear_code_supports_rate_cut_bound_code_val code (linear_code_supports_rate_cut_bound_extend_msg code.L S f))    (linear_code_supports_rate_cut_bound_code_val_recurrence code (linear_code_supports_rate_cut_bound_extend_msg code.L S f))    (by      intro k j hk      dsimp [linear_code_supports_rate_cut_bound_extend_msg]      split_ifs with h      · exact False.elim (hk h.1)      · rfl)    (by      intro m hsnd hrcv      exact h_mzero ⟨m, hsnd, hrcv⟩)  ext ⟨k, hk⟩ j  have h_dec := linear_code_supports_rate_cut_bound_code_val_decode code    (linear_code_supports_rate_cut_bound_extend_msg code.L S f) k j  dsimp [linear_code_supports_rate_cut_bound_extend_msg] at h_dec  split_ifs at h_dec  rw [h_dec]  apply Finset.sum_eq_zero  intro m _  by_cases hγ : code.γ k j m = 0  · rw [hγ, zero_mul]  · have h_tgt := code.dec_local k j m hγ    have h_rcv_not : code.rcv m ∉ S := by      rw [h_tgt]      exact hk.2    have h_val_zero := h_outside m h_rcv_not    rw [h_val_zero, mul_zero]theorem linear_code_supports_rate_cut_bound_cut_card_le {V K F : Type} [Fintype V] [DecidableEq V] [Fintype K] [DecidableEq K] [Field F]    {net : CapacitatedNetwork V} {sess : UnicastSessions V K}    (code : CausalLinearNetworkCode V K F net sess) (S : Finset V) :    Fintype.card (linear_code_supports_rate_cut_bound_kout sess S) * code.L ≤      Fintype.card (linear_code_supports_rate_cut_bound_mout code S) := by  have hinj := linear_code_supports_rate_cut_bound_cut_map_injective code S  have hrank := LinearMap.finrank_le_finrank_of_injective hinj  have e : (linear_code_supports_rate_cut_bound_kout sess S → Fin code.L → F) ≃ₗ[F]      (linear_code_supports_rate_cut_bound_kout sess S × Fin code.L → F) :=    (LinearEquiv.curry F F (linear_code_supports_rate_cut_bound_kout sess S) (Fin code.L)).symm  rw [LinearEquiv.finrank_eq e] at hrank  rw [Module.finrank_fintype_fun_eq_card] at hrank  rw [Module.finrank_fintype_fun_eq_card] at hrank  rw [Fintype.card_prod, Fintype.card_fin] at hrank  exact hrank/-- Cut-set bound: the rate of a linear network code is at most capacity over crossing sessions on every cut. -/theorem linear_code_supports_rate_cut_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) (S : Finset V) :    r * (cutSeparation sess S : ℝ) ≤ cutCapacity net S := by  rcases h with ⟨code, hr⟩  have h_le_S := linear_code_supports_rate_cut_bound_cut_card_le code S  have h_le_Sc := linear_code_supports_rate_cut_bound_cut_card_le code Sᶜ  have h_sum_le : (Fintype.card (linear_code_supports_rate_cut_bound_kout sess S) +      Fintype.card (linear_code_supports_rate_cut_bound_kout sess Sᶜ)) * code.L ≤    Fintype.card (linear_code_supports_rate_cut_bound_mout code S) +      Fintype.card (linear_code_supports_rate_cut_bound_mout code Sᶜ) := by    calc      _ = Fintype.card (linear_code_supports_rate_cut_bound_kout sess S) * code.L +          Fintype.card (linear_code_supports_rate_cut_bound_kout sess Sᶜ) * code.L := by ring      _ ≤ _ := add_le_add h_le_S h_le_Sc  have h_k_eq : cutSeparation sess S =      Fintype.card (linear_code_supports_rate_cut_bound_kout sess S) +      Fintype.card (linear_code_supports_rate_cut_bound_kout sess Sᶜ) := by    dsimp [cutSeparation]    rw [Fintype.card_subtype, Fintype.card_subtype]    have h_eq : (Finset.univ.filter (fun k => (sess.src k ∈ S) ≠ (sess.tgt k ∈ S))) =      (Finset.univ.filter (fun k => sess.src k ∈ S ∧ sess.tgt k ∉ S)) ∪      (Finset.univ.filter (fun k => sess.src k ∈ Sᶜ ∧ sess.tgt k ∉ Sᶜ)) := by      ext k      simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union, Finset.mem_compl]      tauto    rw [h_eq, Finset.card_union_of_disjoint]    rw [Finset.disjoint_filter]    intro k _ h1 h2    simp only [Finset.mem_compl] at h2    exact h2.1 h1.1  have h_m_eq : (Finset.univ.filter (fun m : Fin code.M => (code.snd m ∈ S) ≠ (code.rcv m ∈ S))).card =      Fintype.card (linear_code_supports_rate_cut_bound_mout code S) +      Fintype.card (linear_code_supports_rate_cut_bound_mout code Sᶜ) := by    rw [Fintype.card_subtype, Fintype.card_subtype]    have h_eq : (Finset.univ.filter (fun m : Fin code.M => (code.snd m ∈ S) ≠ (code.rcv m ∈ S))) =      (Finset.univ.filter (fun m => code.snd m ∈ S ∧ code.rcv m ∉ S)) ∪      (Finset.univ.filter (fun m => code.snd m ∈ Sᶜ ∧ code.rcv m ∉ Sᶜ)) := by      ext m      simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union, Finset.mem_compl]      tauto    rw [h_eq, Finset.card_union_of_disjoint]    rw [Finset.disjoint_filter]    intro m _ h1 h2    simp only [Finset.mem_compl] at h2    exact h2.1 h1.1  rw [← h_k_eq] at h_sum_le  rw [← h_m_eq] at h_sum_le  have h_trans := code_transmissions_cross_cut_le F net sess code S  have h_sep_L_le : (cutSeparation sess S : ℝ) * (code.L : ℝ) ≤ (code.T : ℝ) * cutCapacity net S := by    have h_nat : (cutSeparation sess S : ℝ) * (code.L : ℝ) ≤      ↑(Finset.univ.filter (fun m : Fin code.M => (code.snd m ∈ S) ≠ (code.rcv m ∈ S))).card := by      exact_mod_cast h_sum_le    exact le_trans h_nat h_trans  have hT_pos : 0 < (code.T : ℝ) := Nat.cast_pos.mpr code.hT  have hsep_nonneg : 0 ≤ (cutSeparation sess S : ℝ) := Nat.cast_nonneg (cutSeparation sess S)  have h1 : r * (cutSeparation sess S : ℝ) ≤ ((code.L : ℝ) / (code.T : ℝ)) * (cutSeparation sess S : ℝ) :=    mul_le_mul_of_nonneg_right hr hsep_nonneg  have h2 : ((code.L : ℝ) / (code.T : ℝ)) * (cutSeparation sess S : ℝ) =    ((cutSeparation sess S : ℝ) * (code.L : ℝ)) / (code.T : ℝ) := by ring  rw [h2] at h1  have h3 : ((cutSeparation sess S : ℝ) * (code.L : ℝ)) / (code.T : ℝ) ≤ cutCapacity net S := by    exact (div_le_iff₀ hT_pos).mpr (by linarith)  linarith
See it in the graphDiscuss this resultChallenge it