linear_code_supports_rate_cut_bound
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.
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).
uses
causal_code_val_unique,linear_code_supports_rate_cut_bound_code_val_recurrence,Pi.add_apply,mul_add,Finset.sum_add_distribapply 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
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.
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_congrapply 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
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.
uses
Pi.add_apply,linear_code_supports_rate_cut_bound_code_val_addext 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
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.
uses
Pi.smul_apply,linear_code_supports_rate_cut_bound_code_val_smulext 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
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.
uses
injective_iff_map_eq_zero,congr_fun,causal_code_vals_zero_outside,linear_code_supports_rate_cut_bound_code_val_recurrence,False.elimrw [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⟩)
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.
uses
linear_code_supports_rate_cut_bound_code_val_decode,Finset.sum_eq_zero,zero_mul,mul_zeroext ⟨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]
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)|.
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_finhave 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
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.
uses
linear_code_supports_rate_cut_bound_cut_card_le,add_le_addrcases 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
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|.
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_complhave 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
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.
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
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.
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