AFTD Auto-Formalizing Theoretical Domains

causal_code_val_unique

theoremverified

For a fixed message msg, any two assignments of transmission values satisfying the linear recurrence val m = sum alpha*msg + sum beta*val agree.

Statement

theorem causal_code_val_unique
    {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)
    (val val' : Fin code.M → F)
    (hval : ∀ m, val m = ∑ k, ∑ j, code.α m k j * msg k j + ∑ m', code.β m m' * val m')
    (hval' : ∀ m, val' m = ∑ k, ∑ j, code.α m k j * msg k j + ∑ m', code.β m m' * val' m') :
    val = val'
Source
step towards undirected_binary_linear_unicast_advantage
Verified
20 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…
  • 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

The uniqueness of the transmission values is proved by function extensionality followed by well-founded (strong) induction on the transmission index m with respect to the strict order < on Fin code.M. Expanding both assignments via their recurrence relations, the direct message terms cancel immediately. For the remaining dependence on other transmission values, the causality of the code guarantees that any nonzero coefficient code.β m m' requires m' < m, allowing the induction hypothesis to equate val m' with val' m'.

  1. It suffices to prove by strong induction on m that val m = val' m for every transmission index m.

    By function extensionality (`ext m`), two value functions are identical if they agree at each index `m`. We prove this equality by well-founded induction (`WellFoundedLT.induction`) on the index type `Fin code.M` ordered by `<`, obtaining an induction hypothesis `ih` that `val y = val' y` for all earlier transmissions `y < m`.

    lines 10–12

    uses WellFoundedLT.induction

      ext m
      induction m using WellFoundedLT.induction with
      | ind m ih =>
  2. To show val m = val' m, it suffices to show code.β m m' * val m' = code.β m m' * val' m' for each m'.

    We expand both `val m` and `val' m` using the recurrence relations `hval m` and `hval' m`. The message-dependent linear combinations are identical on both sides and cancel (`congr 1`). By congruence of finite sums (`Finset.sum_congr`), it is enough to show that the individual terms in the sums over `m'` agree pointwise.

    lines 13–16

    uses Finset.sum_congr

        rw [hval m, hval' m]
        congr 1
        apply Finset.sum_congr rfl
        intro m' _
  3. The equality code.β m m' * val m' = code.β m m' * val' m' holds when code.β m m' = 0.

    A case split on whether `code.β m m' = 0` yields that if the coefficient is zero, both sides evaluate to zero by multiplying by zero (`zero_mul`), establishing the equality.

    lines 17–18

    uses zero_mul

        by_cases hβ : code.β m m' = 0
        · rw [hβ, zero_mul, zero_mul]
  4. The equality code.β m m' * val m' = code.β m m' * val' m' holds when code.β m m' ≠ 0.

    When `code.β m m' ≠ 0`, causality (`code.causal`) implies that `m' < m`. The induction hypothesis `ih` therefore applies to `m'`, giving `val m' = val' m'`, which equates the two products.

    lines 19–20

    uses code.causal

        · have hlt : m' < m := code.causal m m' hβ
          rw [ih m' hlt]
WellFoundedLT.induction
Well-founded induction on a type equipped with a well-founded `<` relation: to prove a property for all elements, it suffices to prove it for an arbitrary element assuming it holds for all strictly smaller elements.
Finset.sum_congr
Two finite sums over the same finite set are equal if their summands agree at every element.
zero_mul
Multiplication by zero on the left yields zero: `0 * a = 0`.
code.causal
In a causal linear network code, if the dependency coefficient β m m' is nonzero, then transmission index m' strictly precedes m (m' < m).

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 transmission values of a causal linear code are uniquely determined by the message. -/theorem causal_code_val_unique    {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)    (val val' : Fin code.M → F)    (hval : ∀ m, val m = ∑ k, ∑ j, code.α m k j * msg k j + ∑ m', code.β m m' * val m')    (hval' : ∀ m, val' m = ∑ k, ∑ j, code.α m k j * msg k j + ∑ m', code.β m m' * val' m') :    val = val' := by  ext m  induction m using WellFoundedLT.induction with  | ind m ih =>    rw [hval m, hval' m]    congr 1    apply Finset.sum_congr rfl    intro m' _    by_cases hβ : code.β m m' = 0    · rw [hβ, zero_mul, zero_mul]    · have hlt : m' < m := code.causal m m' hβ      rw [ih m' hlt]
See it in the graphDiscuss this resultChallenge it