AFTD Auto-Formalizing Theoretical Domains

linear_code_supports_rate_of_transfer_matrix

theoremverified

Given M transmissions with endpoints snd, rcv on a capacitated network, a time horizon T > 0, a message dimension L > 0, capacity-respecting edge usage, encoding and decoding tables alpha, beta, gamma obeying causality and sender/receiver/decoder locality, and a transfer table W satisfying W m k j = alpha m k j + sum_{m'} beta m m' * W m' k j together with the decoding identity sum_m gamma k j m * W m k' j' = 1 if (k,j)=(k',j') and 0 otherwise, the resulting causal binary (or any-field) linear network code supports rate L/T.

Statement

theorem linear_code_supports_rate_of_transfer_matrix
    {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K]
    (F : Type) [Field F] (net : CapacitatedNetwork V) (sess : UnicastSessions V K)
    {M T L : ℕ} (hT : 0 < T) (hL : 0 < L)
    (snd rcv : Fin M → V) (hne : ∀ m, snd m ≠ rcv m)
    (hcap : ∀ e : Sym2 V,
      ((Finset.univ.filter (fun m : Fin M => s(snd m, rcv m) = e)).card : ℝ) ≤ (T : ℝ) * net.cap e)
    (α : Fin M → K → Fin L → F) (β : Fin M → Fin M → F) (γ : K → Fin L → Fin M → F)
    (W : Fin M → K → Fin L → F)
    (hcausal : ∀ m m', β m m' ≠ 0 → m' < m)
    (hsnd : ∀ (m : Fin M) (k : K) (j : Fin L), α m k j ≠ 0 → sess.src k = snd m)
    (hrcv : ∀ (m m' : Fin M), β m m' ≠ 0 → rcv m' = snd m)
    (hdec : ∀ (k : K) (j : Fin L) (m : Fin M), γ k j m ≠ 0 → rcv m = sess.tgt k)
    (hW : ∀ (m : Fin M) (k : K) (j : Fin L), W m k j = α m k j + ∑ m', β m m' * W m' k j)
    (hD : ∀ (k : K) (j : Fin L) (k' : K) (j' : Fin L),
      (∑ m, γ k j m * W m k' j') = if k = k' ∧ j = j' then 1 else 0) :
    LinearCodeSupportsRate F net sess ((L : ℝ) / (T : ℝ))
Source
step towards undirected_binary_linear_unicast_advantage
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • CausalLinearNetworkCodeA structure CausalLinearNetworkCode parameterized by a finite vertex type V with decidable equality, a finite session type K with…
  • 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…
  • 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,…
Used by 1

The proof, explained

To prove that the capacitated network supports transmission rate L/T, we explicitly construct a causal linear network code from the encoding, forwarding, and decoding matrices α, β, and γ. For each message msg, the transmission values are witnessed by val m = ∑ k, ∑ j, W m k j * msg k j using the transfer matrix certificate W. Algebraic reindexing of finite sums establishes that the transfer recurrence W = α + β W ensures node transmission recurrence, while the decoding identity γ W = I guarantees message recovery at the destinations.

  1. In any triple sum over finite types, the order of summation can be permuted from (i, k, l) to (l, i, k).

    We repeatedly swap adjacent summation indices using commutativity of finite sums (`linear_code_supports_rate_of_transfer_matrix_sum_comm_univ`) and congruence (`Finset.sum_congr`): first swapping the outer indices i and k, then swapping inner indices i and l, then outer indices k and l, and finally inner indices k and i.

    lines 6–14

    uses linear_code_supports_rate_of_transfer_matrix_sum_comm_univ, Finset.sum_congr

      calc (∑ i, ∑ k, ∑ l, f i k l)
          = ∑ k, ∑ i, ∑ l, f i k l := linear_code_supports_rate_of_transfer_matrix_sum_comm_univ _
        _ = ∑ k, ∑ l, ∑ i, f i k l := by
              apply Finset.sum_congr rfl; intro k _
              exact linear_code_supports_rate_of_transfer_matrix_sum_comm_univ (fun i l => f i k l)
        _ = ∑ l, ∑ k, ∑ i, f i k l := linear_code_supports_rate_of_transfer_matrix_sum_comm_univ _
        _ = ∑ l, ∑ i, ∑ k, f i k l := by
              apply Finset.sum_congr rfl; intro l _
              exact linear_code_supports_rate_of_transfer_matrix_sum_comm_univ (fun k i => f i k l)
  2. In any triple sum over finite types, the order of summation can be rotated from (i, k, l) to (k, l, i).

    We swap the outer two sums over i and k using `linear_code_supports_rate_of_transfer_matrix_sum_comm_univ`, and then swap the inner two sums over i and l using `Finset.sum_congr` with `linear_code_supports_rate_of_transfer_matrix_sum_comm_univ`.

    lines 18–22

    uses linear_code_supports_rate_of_transfer_matrix_sum_comm_univ, Finset.sum_congr

      calc (∑ i, ∑ k, ∑ l, f i k l)
          = ∑ k, ∑ i, ∑ l, f i k l := linear_code_supports_rate_of_transfer_matrix_sum_comm_univ _
        _ = ∑ k, ∑ l, ∑ i, f i k l := by
              apply Finset.sum_congr rfl; intro k _
              exact linear_code_supports_rate_of_transfer_matrix_sum_comm_univ (fun i l => f i k l)
  3. The candidate transmission values ∑ k, ∑ j, W m k j * msg k j satisfy the network coding recurrence relation.

    We substitute W m k j by its recursive definition a m k j + ∑ m', b m m' * W m' k j using hW and `Finset.sum_congr`. Next, we distribute multiplication by msg k j over the addition and split the sum into source encoding and transmission terms using `add_mul` and `Finset.sum_add_distrib`. We then push msg k j inside the sum over m' using `Finset.sum_mul`, swap the triple summation order via `linear_code_supports_rate_of_transfer_matrix_triple_sum_swap`, and factor out b m m' using `mul_assoc` and `Finset.mul_sum`.

    lines 28–44

    uses Finset.sum_congr, add_mul, Finset.sum_add_distrib, Finset.sum_mul, linear_code_supports_rate_of_transfer_matrix_triple_sum_swap, mul_assoc, Finset.mul_sum

      calc (∑ k, ∑ j, W m k j * msg k j)
          = ∑ k, ∑ j, (a m k j + ∑ m', b m m' * W m' k j) * msg k j := by
              apply Finset.sum_congr rfl; intro k _
              apply Finset.sum_congr rfl; intro j _
              rw [hW]
        _ = (∑ k, ∑ j, a m k j * msg k j) + ∑ k, ∑ j, (∑ m', b m m' * W m' k j) * msg k j := by
              simp only [add_mul, Finset.sum_add_distrib]
        _ = (∑ k, ∑ j, a m k j * msg k j) + ∑ k, ∑ j, ∑ m', (b m m' * W m' k j) * msg k j := by
              congr 1
              simp only [Finset.sum_mul]
        _ = (∑ k, ∑ j, a m k j * msg k j) + ∑ m', ∑ k, ∑ j, (b m m' * W m' k j) * msg k j := by
              congr 1
              exact linear_code_supports_rate_of_transfer_matrix_triple_sum_swap (fun k j m' => (b m m' * W m' k j) * msg k j)
        _ = (∑ k, ∑ j, a m k j * msg k j) + ∑ m', b m m' * (∑ k, ∑ j, W m' k j * msg k j) := by
              congr 1
              apply Finset.sum_congr rfl; intro m' _
              simp only [mul_assoc, Finset.mul_sum]
  4. The double sum over k' and j' of (if k = k' ∧ j = j' then 1 else 0) * msg k' j' collapses to msg k j.

    Using `Finset.sum_eq_single`, we isolate the term k' = k in the outer sum, simplifying the summand to (if j = j' then msg k j' else 0) via `true_and`, `ite_mul`, `one_mul`, and `zero_mul`. A second application of `Finset.sum_eq_single` isolates j' = j, yielding msg k j. For both sums, all off-diagonal terms vanish because k' ≠ k or j' ≠ j (by `Ne.symm`), and the indices are members of the universe by `Finset.mem_univ`.

    lines 49–58

    uses Finset.sum_eq_single, true_and, ite_mul, one_mul, zero_mul, Ne.symm, Finset.mem_univ

      rw [Finset.sum_eq_single (a := k)]
      · simp only [true_and, ite_mul, one_mul, zero_mul]
        rw [Finset.sum_eq_single (a := j)]
        · simp
        · intro j' _ hj'
          simp [Ne.symm hj']
        · intro h; exact absurd (Finset.mem_univ j) h
      · intro k' _ hk'
        simp [Ne.symm hk']
      · intro h; exact absurd (Finset.mem_univ k) h
  5. Applying the decoding coefficients γ to the candidate transmission values reconstructs the original message msg k j.

    We flip the equality symmetrically (`symm`), push γ k j m inside the inner double sum via `Finset.mul_sum`, and rotate the triple sum using `linear_code_supports_rate_of_transfer_matrix_triple_sum_rot` so the sum over m becomes innermost. We then factor out msg k' j' using `mul_assoc` and `Finset.sum_mul`, apply the decoding condition hD to replace the inner sum with the Kronecker delta indicator, and collapse the resulting sum to msg k j using `linear_code_supports_rate_of_transfer_matrix_ite_collapse`.

    lines 65–78

    uses Finset.mul_sum, linear_code_supports_rate_of_transfer_matrix_triple_sum_rot, Finset.sum_congr, mul_assoc, Finset.sum_mul, linear_code_supports_rate_of_transfer_matrix_ite_collapse

      symm
      calc (∑ m, γ k j m * (∑ k', ∑ j', W m k' j' * msg k' j'))
          = ∑ m, ∑ k', ∑ j', γ k j m * (W m k' j' * msg k' j') := by
              simp only [Finset.mul_sum]
        _ = ∑ k', ∑ j', ∑ m, γ k j m * (W m k' j' * msg k' j') := linear_code_supports_rate_of_transfer_matrix_triple_sum_rot _
        _ = ∑ k', ∑ j', (∑ m, γ k j m * W m k' j') * msg k' j' := by
              apply Finset.sum_congr rfl; intro k' _
              apply Finset.sum_congr rfl; intro j' _
              simp only [← mul_assoc, Finset.sum_mul]
        _ = ∑ k', ∑ j', (if k = k' ∧ j = j' then (1:F) else 0) * msg k' j' := by
              apply Finset.sum_congr rfl; intro k' _
              apply Finset.sum_congr rfl; intro j' _
              rw [hD k j k' j']
        _ = msg k j := linear_code_supports_rate_of_transfer_matrix_ite_collapse msg k j
  6. A causal linear network code candidate is constructed from the network and code parameters, satisfying the required rate bound L/T.

    We instantiate the `CausalLinearNetworkCode` record with the provided parameters (transmission count M, horizon T, message size L, node endpoints, capacities, coding tables α, β, γ, causality, and locality conditions). The rate bound L/T ≤ code.L / code.T holds by reflexivity (`le_refl`), leaving only the correctness condition on arbitrary messages.

    lines 98–101

    uses le_refl

      refine ⟨{ M := M, T := T, L := L, hT := hT, hL := hL, snd := snd, rcv := rcv,
                snd_ne_rcv := hne, cap_le := hcap, α := α, β := β, γ := γ,
                causal := hcausal, snd_local := hsnd, rcv_local := hrcv, dec_local := hdec,
                correct := ?_ }, le_refl _⟩
  7. For every message, the candidate transmission values satisfy the transmission recurrence and decoding conditions.

    Given any message `msg`, we choose the transmission values val m = ∑ k, ∑ j, W m k j * msg k j. Node transmission correctness holds by `linear_code_supports_rate_of_transfer_matrix_rec`, and receiver decoding correctness holds by `linear_code_supports_rate_of_transfer_matrix_dec`.

    lines 102–105

    uses linear_code_supports_rate_of_transfer_matrix_rec, linear_code_supports_rate_of_transfer_matrix_dec

      intro msg
      exact ⟨fun m => ∑ k, ∑ j, W m k j * msg k j,
              fun m => linear_code_supports_rate_of_transfer_matrix_rec α β W msg m hW,
              fun k j => linear_code_supports_rate_of_transfer_matrix_dec W γ msg k j hD⟩
linear_code_supports_rate_of_transfer_matrix_sum_comm_univ
Sums over all elements of two finite types can be swapped: ∑ i, ∑ k, f i k = ∑ k, ∑ i, f i k.
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree at every element.
linear_code_supports_rate_of_transfer_matrix_triple_sum_swap
In a triple sum over finite types, the summation order can be permuted from (i, k, l) to (l, i, k).
linear_code_supports_rate_of_transfer_matrix_triple_sum_rot
In a triple sum over finite types, the summation order can be rotated from (i, k, l) to (k, l, i).
add_mul
Multiplication distributes from the right over addition: (a + b) * c = a * c + b * c.
Finset.sum_add_distrib
A sum of a sum of functions splits into the sum of each function: ∑ x ∈ s, (f x + g x) = ∑ x ∈ s, f x + ∑ x ∈ s, g x.
Finset.sum_mul
Multiplying a finite sum by a scalar from the right distributes into each summand: (∑ i ∈ s, f i) * a = ∑ i ∈ s, f i * a.
mul_assoc
Multiplication is associative: (a * b) * c = a * (b * c).
Finset.mul_sum
Multiplying a finite sum by a scalar from the left distributes into each summand: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.sum_eq_single
If a summand f b is zero for all b ≠ a in a finite set s, then the sum over s evaluates to f a.
true_and
A conjunction True ∧ p simplifies to p.
ite_mul
Multiplication distributes into both branches of an if-then-else: (if P then a else b) * c = if P then a * c else b * c.
one_mul
Multiplying by 1 on the left is the identity: 1 * a = a.
zero_mul
Multiplying by 0 on the left yields 0: 0 * a = 0.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Finset.mem_univ
Every element of a finite type belongs to the universal finite set univ.
linear_code_supports_rate_of_transfer_matrix_ite_collapse
Summing the product of a double Kronecker delta indicator and a message matrix collapses to the single message entry msg k j.
le_refl
The order relation ≤ is reflexive: a ≤ a.
linear_code_supports_rate_of_transfer_matrix_rec
If the transfer matrix W satisfies the linear network recurrence, the candidate transmission values satisfy the node transmission recurrence equation.
linear_code_supports_rate_of_transfer_matrix_dec
If the transfer matrix W and decoding matrix γ satisfy the decoding identity, applying γ to the candidate transmission values reconstructs the original message msg k j.

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

lemma linear_code_supports_rate_of_transfer_matrix_sum_comm_univ {ι κ R : Type} [Fintype ι] [Fintype κ] [AddCommMonoid R]    (f : ι → κ → R) : (∑ i, ∑ k, f i k) = ∑ k, ∑ i, f i k := Finset.sum_commlemma linear_code_supports_rate_of_transfer_matrix_triple_sum_swap {ι κ μ R : Type} [Fintype ι] [Fintype κ] [Fintype μ] [AddCommMonoid R]    (f : ι → κ → μ → R) : (∑ i, ∑ k, ∑ l, f i k l) = ∑ l, ∑ i, ∑ k, f i k l := by  calc (∑ i, ∑ k, ∑ l, f i k l)      = ∑ k, ∑ i, ∑ l, f i k l := linear_code_supports_rate_of_transfer_matrix_sum_comm_univ _    _ = ∑ k, ∑ l, ∑ i, f i k l := by          apply Finset.sum_congr rfl; intro k _          exact linear_code_supports_rate_of_transfer_matrix_sum_comm_univ (fun i l => f i k l)    _ = ∑ l, ∑ k, ∑ i, f i k l := linear_code_supports_rate_of_transfer_matrix_sum_comm_univ _    _ = ∑ l, ∑ i, ∑ k, f i k l := by          apply Finset.sum_congr rfl; intro l _          exact linear_code_supports_rate_of_transfer_matrix_sum_comm_univ (fun k i => f i k l)lemma linear_code_supports_rate_of_transfer_matrix_triple_sum_rot {ι κ μ R : Type} [Fintype ι] [Fintype κ] [Fintype μ] [AddCommMonoid R]    (f : ι → κ → μ → R) : (∑ i, ∑ k, ∑ l, f i k l) = ∑ k, ∑ l, ∑ i, f i k l := by  calc (∑ i, ∑ k, ∑ l, f i k l)      = ∑ k, ∑ i, ∑ l, f i k l := linear_code_supports_rate_of_transfer_matrix_sum_comm_univ _    _ = ∑ k, ∑ l, ∑ i, f i k l := by          apply Finset.sum_congr rfl; intro k _          exact linear_code_supports_rate_of_transfer_matrix_sum_comm_univ (fun i l => f i k l)lemma linear_code_supports_rate_of_transfer_matrix_rec {F : Type} [Field F] {MM K L : Type} [Fintype MM] [Fintype K] [Fintype L]    (a : MM → K → L → F) (b : MM → MM → F) (W : MM → K → L → F) (msg : K → L → F)    (m : MM) (hW : ∀ (m : MM) (k : K) (j : L), W m k j = a m k j + ∑ m', b m m' * W m' k j) :    (∑ k, ∑ j, W m k j * msg k j) = (∑ k, ∑ j, a m k j * msg k j) + ∑ m', b m m' * (∑ k, ∑ j, W m' k j * msg k j) := by  calc (∑ k, ∑ j, W m k j * msg k j)      = ∑ k, ∑ j, (a m k j + ∑ m', b m m' * W m' k j) * msg k j := by          apply Finset.sum_congr rfl; intro k _          apply Finset.sum_congr rfl; intro j _          rw [hW]    _ = (∑ k, ∑ j, a m k j * msg k j) + ∑ k, ∑ j, (∑ m', b m m' * W m' k j) * msg k j := by          simp only [add_mul, Finset.sum_add_distrib]    _ = (∑ k, ∑ j, a m k j * msg k j) + ∑ k, ∑ j, ∑ m', (b m m' * W m' k j) * msg k j := by          congr 1          simp only [Finset.sum_mul]    _ = (∑ k, ∑ j, a m k j * msg k j) + ∑ m', ∑ k, ∑ j, (b m m' * W m' k j) * msg k j := by          congr 1          exact linear_code_supports_rate_of_transfer_matrix_triple_sum_swap (fun k j m' => (b m m' * W m' k j) * msg k j)    _ = (∑ k, ∑ j, a m k j * msg k j) + ∑ m', b m m' * (∑ k, ∑ j, W m' k j * msg k j) := by          congr 1          apply Finset.sum_congr rfl; intro m' _          simp only [mul_assoc, Finset.mul_sum]lemma linear_code_supports_rate_of_transfer_matrix_ite_collapse {F : Type} [Field F] {K L : Type} [Fintype K] [Fintype L]    [DecidableEq K] [DecidableEq L] (msg : K → L → F) (k : K) (j : L) :    (∑ k', ∑ j', (if k = k' ∧ j = j' then (1:F) else 0) * msg k' j') = msg k j := by  rw [Finset.sum_eq_single (a := k)]  · simp only [true_and, ite_mul, one_mul, zero_mul]    rw [Finset.sum_eq_single (a := j)]    · simp    · intro j' _ hj'      simp [Ne.symm hj']    · intro h; exact absurd (Finset.mem_univ j) h  · intro k' _ hk'    simp [Ne.symm hk']  · intro h; exact absurd (Finset.mem_univ k) hlemma linear_code_supports_rate_of_transfer_matrix_dec {F : Type} [Field F] {MM K L : Type} [Fintype MM] [Fintype K] [Fintype L]    [DecidableEq K] [DecidableEq L]    (W : MM → K → L → F) (γ : K → L → MM → F) (msg : K → L → F) (k : K) (j : L)    (hD : ∀ (k : K) (j : L) (k' : K) (j' : L), (∑ m, γ k j m * W m k' j') = if k = k' ∧ j = j' then 1 else 0) :    msg k j = ∑ m, γ k j m * (∑ k', ∑ j', W m k' j' * msg k' j') := by  symm  calc (∑ m, γ k j m * (∑ k', ∑ j', W m k' j' * msg k' j'))      = ∑ m, ∑ k', ∑ j', γ k j m * (W m k' j' * msg k' j') := by          simp only [Finset.mul_sum]    _ = ∑ k', ∑ j', ∑ m, γ k j m * (W m k' j' * msg k' j') := linear_code_supports_rate_of_transfer_matrix_triple_sum_rot _    _ = ∑ k', ∑ j', (∑ m, γ k j m * W m k' j') * msg k' j' := by          apply Finset.sum_congr rfl; intro k' _          apply Finset.sum_congr rfl; intro j' _          simp only [← mul_assoc, Finset.sum_mul]    _ = ∑ k', ∑ j', (if k = k' ∧ j = j' then (1:F) else 0) * msg k' j' := by          apply Finset.sum_congr rfl; intro k' _          apply Finset.sum_congr rfl; intro j' _          rw [hD k j k' j']    _ = msg k j := linear_code_supports_rate_of_transfer_matrix_ite_collapse msg k j/-- A finite transfer-matrix certificate turns the code half of a witness into decidable table equations. -/theorem linear_code_supports_rate_of_transfer_matrix    {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K]    (F : Type) [Field F] (net : CapacitatedNetwork V) (sess : UnicastSessions V K)    {M T L : ℕ} (hT : 0 < T) (hL : 0 < L)    (snd rcv : Fin M → V) (hne : ∀ m, snd m ≠ rcv m)    (hcap : ∀ e : Sym2 V,      ((Finset.univ.filter (fun m : Fin M => s(snd m, rcv m) = e)).card : ℝ) ≤ (T : ℝ) * net.cap e)    (α : Fin M → K → Fin L → F) (β : Fin M → Fin M → F) (γ : K → Fin L → Fin M → F)    (W : Fin M → K → Fin L → F)    (hcausal : ∀ m m', β m m' ≠ 0 → m' < m)    (hsnd : ∀ (m : Fin M) (k : K) (j : Fin L), α m k j ≠ 0 → sess.src k = snd m)    (hrcv : ∀ (m m' : Fin M), β m m' ≠ 0 → rcv m' = snd m)    (hdec : ∀ (k : K) (j : Fin L) (m : Fin M), γ k j m ≠ 0 → rcv m = sess.tgt k)    (hW : ∀ (m : Fin M) (k : K) (j : Fin L), W m k j = α m k j + ∑ m', β m m' * W m' k j)    (hD : ∀ (k : K) (j : Fin L) (k' : K) (j' : Fin L),      (∑ m, γ k j m * W m k' j') = if k = k' ∧ j = j' then 1 else 0) :    LinearCodeSupportsRate F net sess ((L : ℝ) / (T : ℝ)) := by  refine ⟨{ M := M, T := T, L := L, hT := hT, hL := hL, snd := snd, rcv := rcv,            snd_ne_rcv := hne, cap_le := hcap, α := α, β := β, γ := γ,            causal := hcausal, snd_local := hsnd, rcv_local := hrcv, dec_local := hdec,            correct := ?_ }, le_refl _⟩  intro msg  exact ⟨fun m => ∑ k, ∑ j, W m k j * msg k j,          fun m => linear_code_supports_rate_of_transfer_matrix_rec α β W msg m hW,          fun k j => linear_code_supports_rate_of_transfer_matrix_dec W γ msg k j hD⟩
See it in the graphDiscuss this resultChallenge it