AFTD Auto-Formalizing Theoretical Domains

one_slot_code_of_scaled_capacities

theoremverified

A deterministic causal linear code with T transmission slots on a capacitated network can be read as a one-slot (T = 1) code with the same message dimension L on the network whose capacities are all multiplied by T: the capacity condition of the one-slot code on T * cap is literally the T-slot capacity condition on cap, and every other field (transmission list, encoding, decoding, causality, locality, correctness) is copied unchanged.

Statement

theorem one_slot_code_of_scaled_capacities
    {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) :
    ∃ (net' : CapacitatedNetwork V) (code' : CausalLinearNetworkCode V K F net' sess),
      (∀ e : Sym2 V, net'.cap e = (code.T : ℝ) * net.cap e) ∧ code'.T = 1 ∧ code'.L = code.L
Source
step towards single_slot_binary_linear_coding_advantage
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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…
  • 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 convert a T-slot causal linear network code into a 1-slot code, we define a new capacitated network net' whose capacities are scaled by T. We then construct a 1-slot code code' on net' with the same message dimension L by setting T = 1 and copying all transmission functions, coding matrices, and correctness proofs from the original code. The 1-slot capacity constraint on the scaled network is algebraically identical to the original T-slot capacity constraint, so the code remains valid without any modifications to its operations.

  1. The number of time slots T is strictly positive when cast to the real numbers.

    The original code satisfies T > 0 in ℕ by definition (code.hT). Casting this inequality to ℝ yields 0 < (code.T : ℝ).

    line 8

      have hT : (0 : ℝ) < (code.T : ℝ) := by exact_mod_cast code.hT
  2. The scaled network net' is well-defined with edge capacities T * net.cap e.

    We retain the underlying graph G and set net'.cap e = T * net.cap e. For each graph edge e, the capacity is strictly positive because it is the product of positive reals (mul_pos). For non-edges e ∉ G.edgeSet, net.cap e = 0, so the scaled capacity is also zero (mul_zero).

    lines 9–12

    uses mul_pos, mul_zero

      let net' : CapacitatedNetwork V :=
        { G := net.G, decAdj := net.decAdj, cap := fun e => (code.T : ℝ) * net.cap e,
          cap_pos := fun e he => mul_pos hT (net.cap_pos e he),
          cap_zero := fun e he => by rw [net.cap_zero e he, mul_zero] }
  3. The original code induces a valid 1-slot causal linear code code' on net' with message dimension L.

    We define code' by setting T = 1 (verified positive by norm_num since 0 < 1) while keeping M and L unchanged. The transmission schedule (snd, rcv), coding matrices (α, β, γ), and all structural properties (causality, locality, decodability) are copied directly from the original code. For the capacity condition on any undirected edge e, the required bound |{m | s(snd m, rcv m) = e}| ≤ 1 * net'.cap e simplifies, by definition of net', to the original capacity condition |{m | s(snd m, rcv m) = e}| ≤ T * net.cap e, which code already satisfies.

    lines 13–23

      let code' : CausalLinearNetworkCode V K F net' sess :=
        { M := code.M, T := 1, L := code.L, hT := by norm_num, hL := code.hL,
          snd := code.snd, rcv := code.rcv, snd_ne_rcv := code.snd_ne_rcv,
          cap_le := fun e => by
            have h := code.cap_le e
            simp only [net']
            simpa using h,
          α := code.α, β := code.β, γ := code.γ,
          causal := code.causal, snd_local := code.snd_local,
          rcv_local := code.rcv_local, dec_local := code.dec_local,
          correct := code.correct }
  4. The pair (net', code') satisfies all existential requirements of the theorem.

    We provide net' and code' as existential witnesses. The capacity scaling equality net'.cap e = T * net.cap e, the one-slot condition code'.T = 1, and the dimension preservation code'.L = code.L all hold definitionally by reflexivity.

    line 24

      exact ⟨net', code', fun e => rfl, rfl, rfl⟩
mul_pos
The product of two strictly positive real numbers is strictly positive.
mul_zero
Multiplying any element by zero yields zero.

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

/-- Normalisation: a T-slot code on capacities cap becomes a one-slot code with the same message dimension on capacities T * cap. -/theorem one_slot_code_of_scaled_capacities    {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) :    ∃ (net' : CapacitatedNetwork V) (code' : CausalLinearNetworkCode V K F net' sess),      (∀ e : Sym2 V, net'.cap e = (code.T : ℝ) * net.cap e) ∧ code'.T = 1 ∧ code'.L = code.L := by  have hT : (0 : ℝ) < (code.T : ℝ) := by exact_mod_cast code.hT  let net' : CapacitatedNetwork V :=    { G := net.G, decAdj := net.decAdj, cap := fun e => (code.T : ℝ) * net.cap e,      cap_pos := fun e he => mul_pos hT (net.cap_pos e he),      cap_zero := fun e he => by rw [net.cap_zero e he, mul_zero] }  let code' : CausalLinearNetworkCode V K F net' sess :=    { M := code.M, T := 1, L := code.L, hT := by norm_num, hL := code.hL,      snd := code.snd, rcv := code.rcv, snd_ne_rcv := code.snd_ne_rcv,      cap_le := fun e => by        have h := code.cap_le e        simp only [net']        simpa using h,      α := code.α, β := code.β, γ := code.γ,      causal := code.causal, snd_local := code.snd_local,      rcv_local := code.rcv_local, dec_local := code.dec_local,      correct := code.correct }  exact ⟨net', code', fun e => rfl, rfl, rfl⟩
See it in the graphDiscuss this resultChallenge it