AFTD Auto-Formalizing Theoretical Domains

code_transmissions_cross_cut_le

theoremverified

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

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.

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

    lines 8–11

      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)
  2. 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.

    lines 12–25

    uses Finset.mem_coe, Finset.mem_product, Finset.mem_univ, Finset.mem_filter

      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]
  3. 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.

    lines 26–29

    uses Finset.card_eq_sum_card_fiberwise, Finset.sum_product

      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]
  4. 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).

    lines 30–68

    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_trans

      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))
  5. 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.

    lines 69–80

    uses le_trans, Finset.mul_sum, le_of_eq, Finset.sum_congr

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

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

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