code_transmissions_cross_cut_le
In a causal linear network code on net, the number of transmissions whose endpoints are separated by a vertex set S is at most T * cutCapacity net S.
Statement
theorem code_transmissions_cross_cut_le {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) (S : Finset V) : ((Finset.univ.filter (fun m : Fin code.M => (code.snd m ∈ S) ≠ (code.rcv m ∈ S))).card : ℝ) ≤ (code.T : ℝ) * cutCapacity net S
- Source
- step towards undirected_binary_linear_unicast_advantage
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- 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…
- Used by 1
- 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…
The proof, explained
To bound the number of cut-crossing transmissions, each transmission is mapped to an ordered pair (u, v) ∈ S × V such that u is the endpoint in S and v is the other endpoint. Partitioning the cut-crossing transmissions by the fibers of this map expresses their total count as a double sum over u ∈ S and v ∈ V. When v ∈ S the fiber is empty because cut-crossing transmissions cannot have both endpoints in S, and when v ∉ S the fiber consists of transmissions using the undirected edge {u, v}, which is bounded by T * net.cap {u, v} via the code's capacity constraint. Summing these bounds over all pairs yields exactly T times the cut capacity of S.
Let A be the set of cut-crossing transmissions, and define an orientation map g : Fin code.M → V × V sending each transmission to an ordered pair of its endpoints with the first endpoint in S whenever possible.
The set A collects all transmissions m whose sender and receiver are separated by the cut S (exactly one lies in S). The map g evaluates whether the sender code.snd m is in S: if so, it pairs (snd m, rcv m); otherwise, it pairs (rcv m, snd m).
let A := Finset.univ.filter (fun m : Fin code.M => (code.snd m ∈ S) ≠ (code.rcv m ∈ S)) let g : Fin code.M → V × V := fun m => (if code.snd m ∈ S then code.snd m else code.rcv m, if code.snd m ∈ S then code.rcv m else code.snd m)
The map g maps the set A of cut-crossing transmissions into S × V.
For any m ∈ A, the sender and receiver cannot both belong to S or both lie outside S. If code.snd m ∈ S, the first component of g(m) is code.snd m ∈ S. If code.snd m ∉ S, the cut-crossing condition forces code.rcv m ∈ S, so the first component is code.rcv m ∈ S. In either case the first component lies in S, and the second component trivially lies in the universal finset on V.
uses
Finset.mem_coe,Finset.mem_product,Finset.mem_univ,Finset.mem_filterhave hmaps : Set.MapsTo g (↑A) (↑(S ×ˢ (Finset.univ : Finset V))) := by intro m hm rw [Finset.mem_coe] at hm ⊢ rw [Finset.mem_product] refine ⟨?_, Finset.mem_univ _⟩ dsimp [A] at hm rw [Finset.mem_filter] at hm obtain ⟨_, hdiff⟩ := hm dsimp [g] split_ifs with hs · exact hs · by_contra hc apply hdiff simp [hs, hc]
The cardinality |A| equals the iterated double sum ∑_{u ∈ S} ∑_{v ∈ V} |{m ∈ A | g(m) = (u, v)}| of the fiber sizes of g.
Because g maps A into S × V, fiberwise summation partitions A into disjoint fibers over all pairs (u, v) ∈ S × V. Rewriting the sum over the product finset as an iterated sum over u ∈ S and v ∈ V gives the desired double sum.
uses
Finset.card_eq_sum_card_fiberwise,Finset.sum_producthave hsum : (A.card : ℝ) = ∑ p ∈ S ×ˢ (Finset.univ : Finset V), ((A.filter (fun m => g m = p)).card : ℝ) := by have h := Finset.card_eq_sum_card_fiberwise hmaps norm_cast rw [hsum, Finset.sum_product]
The double sum of fiber sizes is bounded by ∑_{u ∈ S} ∑_{v ∈ V} (if v ∈ S then 0 else T * net.cap s(u, v)).
We compare the summands term by term for each u ∈ S and v ∈ V. If v ∈ S, the fiber {m ∈ A | g(m) = (u, v)} must be empty: whichever endpoint was in S, having g(m) = (u, v) with v ∈ S would force both endpoints of m to lie in S, contradicting m ∈ A; hence the fiber size is 0. If v ∉ S, any transmission m in the fiber satisfies {snd m, rcv m} = {u, v}, so m is transmitted across the undirected edge s(u, v). By the code capacity condition code.cap_le, the total number of transmissions across edge s(u, v) is at most T * net.cap s(u, v). Since the fiber is a subset of these transmissions, its cardinality is bounded by T * net.cap s(u, v).
uses
Finset.sum_le_sum,Finset.filter_eq_empty_iff,Finset.mem_filter,Finset.card_empty,Nat.cast_zero,Finset.mem_univ,Sym2.eq_swap,Finset.card_le_card,le_transhave h_le : (∑ u ∈ S, ∑ v : V, ((A.filter (fun m => g m = (u, v))).card : ℝ)) ≤ ∑ u ∈ S, ∑ v : V, (if v ∈ S then 0 else (code.T : ℝ) * net.cap s(u, v)) := by apply Finset.sum_le_sum intro u _ apply Finset.sum_le_sum intro v _ split_ifs with hv · have hempty : A.filter (fun m => g m = (u, v)) = ∅ := by rw [Finset.filter_eq_empty_iff] intro m hm hgm dsimp [A] at hm rw [Finset.mem_filter] at hm obtain ⟨_, hdiff⟩ := hm dsimp [g] at hgm split_ifs at hgm with hs · injection hgm with _ h2 rw [← h2] at hv apply hdiff simp [hs, hv] · injection hgm with _ h2 rw [← h2] at hv exact hs hv rw [hempty, Finset.card_empty, Nat.cast_zero] · have hsub : A.filter (fun m => g m = (u, v)) ⊆ Finset.univ.filter (fun m => s(code.snd m, code.rcv m) = s(u, v)) := by intro m hm rw [Finset.mem_filter] at hm ⊢ refine ⟨Finset.mem_univ _, ?_⟩ obtain ⟨_, hgm⟩ := hm dsimp [g] at hgm split_ifs at hgm with hs · injection hgm with hu hv' rw [← hu, ← hv'] · injection hgm with hu hv' rw [← hu, ← hv', Sym2.eq_swap] have hcard : ((A.filter (fun m => g m = (u, v))).card : ℝ) ≤ ((Finset.univ.filter (fun m => s(code.snd m, code.rcv m) = s(u, v))).card : ℝ) := by exact_mod_cast Finset.card_le_card hsub exact le_trans hcard (code.cap_le s(u, v))
The number of cut-crossing transmissions is at most T * cutCapacity net S.
By definition, cutCapacity net S is ∑_{u ∈ S} ∑_{v ∈ V} (if v ∈ S then 0 else net.cap s(u, v)). Distributing the scalar factor T across both sums matches each term of the previous upper bound (since T * 0 = 0 and T * net.cap = T * net.cap). Transitivity of inequality concludes the proof.
uses
le_trans,Finset.mul_sum,le_of_eq,Finset.sum_congrrefine le_trans h_le ?_ dsimp [cutCapacity] rw [Finset.mul_sum] apply le_of_eq apply Finset.sum_congr rfl intro u _ rw [Finset.mul_sum] apply Finset.sum_congr rfl intro v _ split_ifs with hv · ring · ring
Finset.mem_coe- An element belongs to a finset coerced to a set if and only if it belongs to the finset.
Finset.mem_product- A pair (a, b) belongs to the Cartesian product s ×ˢ t if and only if a ∈ s and b ∈ t.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
Finset.mem_filter- An element belongs to Finset.filter p s if and only if it belongs to s and satisfies the predicate p.
Finset.card_eq_sum_card_fiberwise- If a function f maps a finset s into a finset t, the cardinality of s is the sum over b ∈ t of the cardinalities of the fibers of f over b.
Finset.sum_product- A sum over a Cartesian product s ×ˢ t can be rewritten as the iterated sum ∑ x ∈ s, ∑ y ∈ t, f (x, y).
Finset.sum_le_sum- If f(i) ≤ g(i) for all i in a finset s, then the sum of f over s is at most the sum of g over s.
Finset.filter_eq_empty_iff- A filtered finset is empty if and only if no element of the base finset satisfies the predicate.
Finset.card_empty- The cardinality of the empty finset is 0.
Nat.cast_zero- The natural number 0 cast into a ring or semiring equals 0.
Sym2.eq_swap- Swapping the two coordinates of an unordered pair yields the same unordered pair: s(a, b) = s(b, a).
Finset.card_le_card- If s ⊆ t as finsets, then the cardinality of s is at most the cardinality of t.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Finset.mul_sum- Multiplication by a scalar distributes over a finite sum: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
le_of_eq- An equality a = b implies the inequality a ≤ b.
Finset.sum_congr- Two sums over the same finset are equal if their summands agree at every element.
- The definition of cutCapacity net S sums over all pairs (u, v) ∈ S × V, setting the summand to 0 whenever v ∈ S; this matches the directed orientation g used to fiber the transmissions.
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.
/-- The number of transmissions of a code crossing a cut is at most T times the cut capacity. -/theorem code_transmissions_cross_cut_le {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) (S : Finset V) : ((Finset.univ.filter (fun m : Fin code.M => (code.snd m ∈ S) ≠ (code.rcv m ∈ S))).card : ℝ) ≤ (code.T : ℝ) * cutCapacity net S := by let A := Finset.univ.filter (fun m : Fin code.M => (code.snd m ∈ S) ≠ (code.rcv m ∈ S)) let g : Fin code.M → V × V := fun m => (if code.snd m ∈ S then code.snd m else code.rcv m, if code.snd m ∈ S then code.rcv m else code.snd m) have hmaps : Set.MapsTo g (↑A) (↑(S ×ˢ (Finset.univ : Finset V))) := by intro m hm rw [Finset.mem_coe] at hm ⊢ rw [Finset.mem_product] refine ⟨?_, Finset.mem_univ _⟩ dsimp [A] at hm rw [Finset.mem_filter] at hm obtain ⟨_, hdiff⟩ := hm dsimp [g] split_ifs with hs · exact hs · by_contra hc apply hdiff simp [hs, hc] have hsum : (A.card : ℝ) = ∑ p ∈ S ×ˢ (Finset.univ : Finset V), ((A.filter (fun m => g m = p)).card : ℝ) := by have h := Finset.card_eq_sum_card_fiberwise hmaps norm_cast rw [hsum, Finset.sum_product] have h_le : (∑ u ∈ S, ∑ v : V, ((A.filter (fun m => g m = (u, v))).card : ℝ)) ≤ ∑ u ∈ S, ∑ v : V, (if v ∈ S then 0 else (code.T : ℝ) * net.cap s(u, v)) := by apply Finset.sum_le_sum intro u _ apply Finset.sum_le_sum intro v _ split_ifs with hv · have hempty : A.filter (fun m => g m = (u, v)) = ∅ := by rw [Finset.filter_eq_empty_iff] intro m hm hgm dsimp [A] at hm rw [Finset.mem_filter] at hm obtain ⟨_, hdiff⟩ := hm dsimp [g] at hgm split_ifs at hgm with hs · injection hgm with _ h2 rw [← h2] at hv apply hdiff simp [hs, hv] · injection hgm with _ h2 rw [← h2] at hv exact hs hv rw [hempty, Finset.card_empty, Nat.cast_zero] · have hsub : A.filter (fun m => g m = (u, v)) ⊆ Finset.univ.filter (fun m => s(code.snd m, code.rcv m) = s(u, v)) := by intro m hm rw [Finset.mem_filter] at hm ⊢ refine ⟨Finset.mem_univ _, ?_⟩ obtain ⟨_, hgm⟩ := hm dsimp [g] at hgm split_ifs at hgm with hs · injection hgm with hu hv' rw [← hu, ← hv'] · injection hgm with hu hv' rw [← hu, ← hv', Sym2.eq_swap] have hcard : ((A.filter (fun m => g m = (u, v))).card : ℝ) ≤ ((Finset.univ.filter (fun m => s(code.snd m, code.rcv m) = s(u, v))).card : ℝ) := by exact_mod_cast Finset.card_le_card hsub exact le_trans hcard (code.cap_le s(u, v)) refine le_trans h_le ?_ dsimp [cutCapacity] rw [Finset.mul_sum] apply le_of_eq apply Finset.sum_congr rfl intro u _ rw [Finset.mul_sum] apply Finset.sum_congr rfl intro v _ split_ifs with hv · ring · ring