Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

YukonModule.ArkLib.Data.CodingTheory.InterleavedCode.part0

Definition
Yukon_57f2f4a582b59c53cdee835d

by yukon · Sep 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

better-codes

Source module ArkLib.Data.CodingTheory.InterleavedCode.

Definition code
/-
Copyright (c) 2024-2025 ArkLib Contributors. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Katerina Hristova, František Silváši, Chung Thai Nguyen
-/

import Definitions.Def_Yukon_940a9691b0192ef0397b04a2

import Definitions.Def_Yukon_2d0e6914e1f35ef62dbe39e4

import Definitions.Def_Yukon_06fd17bede7d9846a07acaa7

import Definitions.Def_Yukon_d283689b285597996aeda737

import Definitions.Def_Yukon_e9ee7c0e88307b8acac3260e

import Mathlib.Logic.Equiv.Fin.Basic
import Mathlib.Order.CompletePartialOrder
import Mathlib.Probability.Distributions.Uniform
import Mathlib.Data.Real.Basic
import Mathlib.Analysis.Real.Sqrt
import Definitions.Def_Yukon_30e807a5525bb5bfbcd8d7fe

import Definitions.Def_Yukon_dacf5252cb9737d29e49b4e4

import Mathlib.Algebra.Polynomial.Roots
import Mathlib.Analysis.InnerProductSpace.PiL2
import Mathlib.Data.ENat.Lattice
import Mathlib.InformationTheory.Hamming
import Mathlib.Tactic.Qify
import Mathlib.Topology.MetricSpace.Infsep
import Mathlib.Data.NNReal.Defs


import Mathlib.RingTheory.Henselian
import Mathlib.LinearAlgebra.AffineSpace.Combination
import Mathlib.LinearAlgebra.AffineSpace.Pointwise
import Mathlib.LinearAlgebra.Matrix.Rank
import Mathlib.Algebra.Lie.OfAssociative
import Init
import Mathlib.Tactic.DepRewrite
import Mathlib.Data.Fin.Basic
import Batteries.Data.Fin.Fold
import Mathlib.Tactic.FinCases
import Mathlib.Data.Fin.Tuple.Take
import Mathlib.Algebra.Polynomial.Eval.Defs
import Mathlib.Algebra.Order.Sub.Basic
import Mathlib.Algebra.Order.Ring.Nat
import Mathlib.Algebra.BigOperators.Fin
import Mathlib.Data.NNReal.Basic
import Mathlib.LinearAlgebra.Lagrange
import Mathlib.LinearAlgebra.StdBasis
import Mathlib.LinearAlgebra.FreeModule.StrongRankCondition
import Mathlib.LinearAlgebra.FiniteDimensional.Defs
import Mathlib.Algebra.Order.Star.Basic
import Mathlib.Algebra.BigOperators.Finsupp.Fin
import Mathlib.Data.Finsupp.Fin
import Mathlib.Algebra.MvPolynomial.Equiv
import Mathlib.RingTheory.MvPolynomial.Basic
import Mathlib.RingTheory.Polynomial.Basic
import Mathlib.Algebra.MvPolynomial.Eval
import Mathlib.Data.FinEnum
import Mathlib.Algebra.Group.Action.Pointwise.Finset
import Mathlib.Algebra.MvPolynomial.Degrees
import Mathlib.Algebra.MvPolynomial.SchwartzZippel
import Mathlib.Data.Nat.GCD.Basic
import Mathlib.Data.ENNReal.Inv
import Mathlib.Data.ENat.Basic
import Mathlib.Data.ENat.Defs
import Mathlib.Data.Nat.Cast.Order.Field
import Mathlib.Algebra.CharP.Defs
import Mathlib.Algebra.Order.BigOperators.Group.Finset
import Mathlib.Data.Finsupp.Basic
import Mathlib.Data.Nat.Digits.Defs
import Mathlib.Data.Nat.Bitwise
import Mathlib.Algebra.Order.Ring.Star
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Tactic.IntervalCases
import Mathlib.Order.Interval.Finset.Nat
import Mathlib.Data.Fintype.BigOperators
import Mathlib.Algebra.Ring.Regular
import Mathlib.RingTheory.SimpleRing.Principal
import Mathlib.RingTheory.RegularLocalRing.Defs
import Mathlib.RingTheory.PicardGroup
import Mathlib.LinearAlgebra.FreeModule.PID
import Mathlib.FieldTheory.Finiteness
import Mathlib.Algebra.Order.Chebyshev
import Mathlib.Data.Real.ENatENNReal
import Mathlib.Algebra.Order.Floor.Semifield
set_option backward.isDefEq.respectTransparency.types false
/-!
## Main definitions

Interleaved codes for generic codes over a semiring, with **unified global APIs**.

### Core Data Types
1. **Single vector data structure**: used for computation
  - **Word**: `(ι → A)` - a word
  - **Codeword**: `(C : Set (ι → A))` - a codeword in base code `C`
2. **Horizontal interleaved data structure**: used for computation, the underlying data structure is
  `Matrix κ ι A`
  - **WordStack**: `Matrix κ ι A` - each row is a word
  - **CodewordStack**: `codewordStackSet (κ := κ) (C := C)` - each row is a codeword in C
3. **Vertical interleaved data structure**: used for security (e.g. Δ₀, δᵣ, ...), the underlying
  data structure is `Matrix ι κ A`
  `(κ → A)`.
  - **InterleavedWord**: `Matrix ι κ A`
  - **InterleavedCodeword**: `interleavedCodeSet (κ := κ) (C := C)`

### Global Unified APIs (Type Classes)
- **`GetRow α RowIdx RowType`** - extract rows uniformly across structures
- **`GetSymbol α SymbolIdx SymbolType`** - extract symbols uniformly
- **`GetCell α RowIdx SymbolIdx CellTy`** - extract individual cells
- **`Interleavable α β`** - interleave structures (notation: `⋈|u`)
- **`Interleavable₂ α β`** - interleave two structures (notation: `u ⋈₂ v`)
- **`CodeInterleavable Code InterleavedCode`** - interleave codes (notation: `C^⋈κ`)
- **`Stackifiable α β`** - inverse of interleaving (notation: `⋈⁻¹|v`)

### Key Set
- **`interleavedCodeSet C`** - set of interleaved codewords for code `C`
- **`codewordStackSet C`** - set of codeword stacks for code `C`
- **`ModuleCode.moduleInterleavedCode`** - interleaved code as
  `ModuleCode ι F (InterleavedSymbol A κ)` (preserves submodule; used with `C^⋈κ`)
- **`ModuleCode.codewordStackSubmodule`** - codeword stack as
  `Submodule F (WordStack A κ ι)` (preserves submodule for horizontal interleaving)

### Structure of the interleaved module code
- **`moduleInterleavedCodeEquiv`** - the column-tuple linear equivalence
  `(κ → MC) ≃ₗ[F] (MC ^⋈ κ)`
- **`finrank_moduleInterleavedCode`** - `finrank F (MC ^⋈ κ) = Fintype.card κ * finrank F MC`

### Joint Proximity & Agreement (Consequent of Proximity Gap)
- **`jointProximity u δ`** - interleaved `u` within relative distance `δ` of `C^⋈κ`
- **`jointProximityNat u e`** - interleaved `u` within concrete distance `e` of `C^⋈κ`
- **`jointProximity₂ u₀ u₁ δ`** - interleaved pair within relative distance `δ` of `C^⋈(Fin 2)`
- **`jointProximityNat₂ u₀ u₁ e`** - interleaved pair within concrete distance `e` of `C^⋈(Fin 2)`
- **`pairJointProximity u v e`** - two interleaved stacks within distance `e` of each other
- **`pairJointProximity₂ u₀ u₁ v₀ v₁ e`** - two interleaved pairs within distance `e` of each other
- **`jointAgreement C δ W`** - words collectively agree on large set with `C`
  (equivalent to `jointProximity`)

## References

* [Ben-Sasson, E., Carmon, D., Ishai, Y., Kopparty, S., and Saraf, S., *Proximity Gaps
    for Reed-Solomon Codes*][BCIKS20]
    * NB we use version 20210703:203025

* [Ames, S., Hazay, C., Ishai, Y., and Venkitasubramaniam, M., *Ligero: Lightweight sublinear
    arguments without a trusted setup*][AHIV22]

* [Diamond, B. E. and Gruen, A., *Proximity Gaps in Interleaved Codes*, In: IACR
  Communications in Cryptology 1.4 (Jan. 13, 2025). issn: 3006-5496. doi: 10.62056/a0ljbkrz.][DG25]
-/

section InterleavedCodeDefinitions
variable (F : Type*) [Semiring F]
variable (A : Type*) [AddCommMonoid A] [Module F A]
variable (κ ι : Type*) [Fintype κ] [Fintype ι]
variable (MC : ModuleCode ι F A)
variable (C : Set (ι → A))

open NNReal
namespace Code

/-- A word is a vector (ι → A) -/
@[simp]
abbrev Word := ι → A

/-- A codeword is a vector (ι → A) that belongs to the base module code MC -/
@[simp]
abbrev Codeword := MC

@[simp]
abbrev InterleavedSymbol := κ → A

/-- A word stack is a (row-wise) matrix (κ → ι → A) where each ROW is a word -/
@[simp]
abbrev WordStack := Matrix κ ι A

@[simp]
def WordStack.getRowWord {A : Type*} {κ : Type*} {ι : Type*} (u : WordStack A κ ι)
    (k : κ) : Word A ι := u k

@[simp]
def WordStack.getSymbol {A : Type*} {κ : Type*} {ι : Type*} (u : WordStack A κ ι)
    (i : ι) : InterleavedSymbol A κ := u.transpose i

/-- An interleaved word is a (column-wise) matrix (ι → (κ → A)) where each ROW is a word, each
  column i is a symbol (κ → A) for the interleaved code MC^⋈ κ. -/
@[simp]
abbrev InterleavedWord := Matrix ι κ A

@[simp]
def InterleavedWord.getRowWord {A : Type*} {κ : Type*} {ι : Type*}
    (v : InterleavedWord A κ ι) (k : κ) : Word A ι := v.transpose k

@[simp]
def InterleavedWord.getSymbol {A : Type*} {κ : Type*} {ι : Type*}
    (v : InterleavedWord A κ ι) (i : ι) : InterleavedSymbol A κ := v i

/-- The set of interleaved words where each row belongs to a code C.
    This is a generic version that works for any code represented as a Set. -/
@[simp]
def interleavedCodeSet {A : Type*} {κ ι : Type*}
    (C : Set (ι → A)) : Set (Matrix ι κ A) :=
  { V : Matrix ι κ A | ∀ k : κ, V.transpose k ∈ C }

/-- If C is finite and membership is decidable, then interleavedCodeSet C is finite. -/
@[simp]
noncomputable instance interleavedCodeSet_fintype {A : Type*} {κ ι : Type*}
    [Fintype κ] [Fintype ι] [Fintype A] [DecidableEq A]
    (C : Set (ι → A)) :
    Fintype (interleavedCodeSet (κ := κ) (ι := ι) C) := by
  exact Fintype.ofFinite (interleavedCodeSet C)

/-- Interleaved code submodule of any `ModuleCode`, where each row belongs to the code. -/
@[simp]
def ModuleCode.moduleInterleavedCode : ModuleCode ι F (InterleavedSymbol A κ) := {
  -- Simple condition wrapping over Matrix
  carrier := interleavedCodeSet (C := (MC : Set (ι → A)))
  add_mem' hU hV i := MC.add_mem (hU i) (hV i)
  zero_mem' _ := MC.zero_mem
  smul_mem' a _ hV i := MC.smul_mem a (hV i)
}

-- TODO: lift these to CodeInterleavable
omit [Fintype κ] [Fintype ι] [AddCommMonoid A] in
@[simp]
lemma mem_interleavedCode_iff (v : InterleavedWord A κ ι) : -- column-wise matrix
    v ∈ interleavedCodeSet (C := C) ↔ ∀ k, InterleavedWord.getRowWord v k ∈ C := by rfl

omit [Fintype κ] [Fintype ι] in
lemma mem_moduleInterleavedCode_iff (v : InterleavedWord A κ ι) :
    v ∈ ModuleCode.moduleInterleavedCode (F := F) (A := A) (κ := κ) (ι := ι) (MC := MC)
    ↔ ∀ k, InterleavedWord.getRowWord v k ∈ MC := by exact Eq.to_iff rfl

omit [Fintype κ] [Fintype ι] in
/-- **Projection commutes with interleaving.** An interleaved word projects into the interleaved
code on `T` iff each of its rows projects into the base code on `T`.

Forward direction: extract rows of the interleaved witness. Backward direction: assemble the
chosen row witnesses into an interleaved codeword. This is the bridge that lets mutual correlated
agreement be applied to interleaved codes: the proof of Lemma 4.4 [BCGM25] applies MCA of the
inner generator to the `ℓ`-fold interleaving `C^ℓ`, and this lemma converts its projected
membership clauses row-wise. -/
lemma projectedCodeSubmod_moduleInterleavedCode_iff (v : InterleavedWord A κ ι) (T : Finset ι) :
    LinearCode.projectedWord v T ∈
      LinearCode.projectedCodeSubmod (ModuleCode.moduleInterleavedCode F A κ ι MC) T ↔
    ∀ k, LinearCode.projectedWord (InterleavedWord.getRowWord v k) T ∈
      LinearCode.projectedCodeSubmod MC T := by
  constructor
  · intro h k
    obtain ⟨c, hc, hw⟩ := (LinearCode.mem_projectedCodeSubmod_iff _ T _).mp h
    exact (LinearCode.mem_projectedCodeSubmod_iff _ T _).mpr
      ⟨InterleavedWord.getRowWord c k, (mem_moduleInterleavedCode_iff F A κ ι MC c).mp hc k,
        funext fun i => congr_fun (congr_fun hw i) k⟩
  · intro h
    choose c hc hw using fun k => (LinearCode.mem_projectedCodeSubmod_iff _ T _).mp (h k)
    exact (LinearCode.mem_projectedCodeSubmod_iff _ T _).mpr
      ⟨fun i k => c k i, (mem_moduleInterleavedCode_iff F A κ ι MC _).mpr fun k => hc k,
        funext fun i => funext fun k => congr_fun (hw k) i⟩

@[simp]
def codewordStackSet {A : Type*} {κ ι : Type*} (C : Set (ι → A)) : Set (WordStack A κ ι) :=
  { V : WordStack A κ ι | ∀ k, V.getRowWord k ∈ C }

@[simp]
def ModuleCode.codewordStackSubmodule : Submodule F (WordStack A κ ι) := {
  -- Simple condition wrapping over Matrix
  carrier := codewordStackSet (C := (MC : Set (ι → A)))
  add_mem' hU hV i := MC.add_mem (hU i) (hV i)
  zero_mem' _ := MC.zero_mem
  smul_mem' a _ hV i := MC.smul_mem a (hV i)
}

omit [Fintype κ] [Fintype ι] in
lemma codewordStackSubmodule_eq_codewordStackSet (MC : ModuleCode ι F A) :
    ((ModuleCode.codewordStackSubmodule (MC := MC) F A κ ι) : Set (WordStack A κ ι))
      = codewordStackSet (MC : Set (ι → A)) := rfl

instance instMembershipWordStackCodewordStackSet : Membership (α := WordStack A κ ι)
  (γ := codewordStackSet (κ := κ) (C := C)) where
  mem u := by exact fun a ↦ PEmpty.{0}

instance instMembershipInterleavedWordInterleavedCodeSet :
  Membership (InterleavedWord A κ ι) (interleavedCodeSet (κ := κ) (C := C)) where
  mem u := by exact fun a ↦ PEmpty.{0}

omit [Fintype κ] [Fintype ι] [AddCommMonoid A] in
@[simp]
lemma mem_codewordStack_iff (u : WordStack A κ ι) : -- row-wise matrix
    u ∈ codewordStackSet (κ := κ) (C := C) ↔ ∀ k, u.getRowWord k ∈ C := by rfl

omit [Fintype κ] [Fintype ι] in
@[simp]
lemma mem_moduleCodewordStack_iff (u : WordStack A κ ι) : -- might rename this
    u ∈ ModuleCode.codewordStackSubmodule (F := F) (A := A) (κ := κ) (ι := ι) (MC := MC)
    ↔ ∀ k, u.getRowWord k ∈ MC := by exact Eq.to_iff rfl

/-- An interleaved codeword is a (column-wise) matrix (ι → (κ → A)) where each ROW is a codeword
  of the base module code MC. -/
@[simp]
abbrev InterleavedCodeword := interleavedCodeSet (κ := κ) (C := C)

/-- A codeword stack is a (row-wise) matrix (κ → ι → A) where each ROW is a codeword of MC. -/
@[simp]
abbrev CodewordStack := codewordStackSet (κ := κ) (C := C)

-- TODO: mem of Module interleaved code, Module codeword stack

@[simp]
def interleaveWordStack {A : Type*} {κ ι : Type*} (u : WordStack A κ ι) : InterleavedWord A κ ι
    := u.transpose

/-- Interleave a codeword stack into an interleaved codeword. -/
@[simp]
def interleaveCodewordStack (u : CodewordStack A κ ι C) : InterleavedCodeword A κ ι C :=
  ⟨interleaveWordStack u.val, by
    rw [mem_interleavedCode_iff]
    let h_u_mem := u.property
    rw [mem_codewordStack_iff] at h_u_mem
    intro k
    exact h_u_mem k
  ⟩

@[simp]
def finMapTwoWords {A : Type*} {ι : Type*} (u₀ u₁ : Word A ι)
    : WordStack A (κ := Fin 2) (ι := ι)
    := fun rowIdx =>
  match rowIdx with
  | ⟨0, _⟩ => u₀
  | ⟨1, _⟩ => u₁

@[simp]
def finMapTwoCodewords (u₀ u₁ : C) :
    CodewordStack A (κ := Fin 2) (ι := ι) C :=
  ⟨finMapTwoWords u₀ u₁, by
    simp only [WordStack, CodewordStack, codewordStackSet, Word, WordStack.getRowWord,
      Set.mem_setOf_eq, finMapTwoWords]
    intro k
    match k with
    | 0 => simp only [Subtype.coe_prop]
    | 1 => simp only [Subtype.coe_prop]
  ⟩

/-- Interleave two codewords u₀ and u₁ into a single interleaved codeword -/
@[simp]
def interleaveTwoWords (u₀ u₁ : Word A ι) : InterleavedWord A (Fin 2) ι :=
  interleaveWordStack (κ := Fin 2) (ι := ι) (u := finMapTwoWords u₀ u₁)

@[simp]
def interleaveTwoCodewords (u₀ u₁ : C) : InterleavedCodeword A (κ := Fin 2) ι C :=
  interleaveCodewordStack A (κ := Fin 2) (ι := ι) (u := finMapTwoCodewords A ι C u₀ u₁)

/-- Combine two codeword stacks with different κ types by stacking vertically -/
@[simp]
def finMapCodewordStacksAppend {κ₁ κ₂ : Type*}
    (u : CodewordStack A κ₁ ι C) (v : CodewordStack A κ₂ ι C) :
    CodewordStack A (Sum κ₁ κ₂) ι C :=
  ⟨fun s =>
    match s with
    | Sum.inl k₁ => u.val k₁
    | Sum.inr k₂ => v.val k₂, by
    simp only [WordStack, CodewordStack, mem_codewordStack_iff]
    intro s
    match s with
    | Sum.inl k₁ =>
      have h_u := u.property
      rw [mem_codewordStack_iff] at h_u
      simp only [WordStack.getRowWord]
      exact h_u k₁
    | Sum.inr k₂ =>
      have h_v := v.property
      rw [mem_codewordStack_iff] at h_v
      simp only [WordStack.getRowWord]
      exact h_v k₂
  ⟩

/-- Type class for overloading the interleave notation.
Interleaving a word stack -> interleaved word
Interleaving a codeword stack -> interleaved codeword -/
class Interleavable (α : Type*) (β : outParam Type*) where
  interleave : α → β
notation:65 "⋈|" u => Interleavable.interleave u

class Interleavable₂ (α : Type*) (β : outParam Type*) where
  interleave₂ : α → α → β
notation:65 u "⋈₂" v => Interleavable₂.interleave₂ u v

/-- Typeclass for interleaving codes (preserving their structure).
    For Set → Set, for ModuleCode → ModuleCode, etc. -/
class CodeInterleavable.{u, v} (Code : Type*) (InterleavedCode : outParam (Type u → Type v)) where
  interleaveCode : Code → (κ : Type u) → InterleavedCode κ

notation:20 C "^⋈" κ => @CodeInterleavable.interleaveCode _ _ _ C κ

@[simp]
instance  _root_.Code.instInterleavableWordStackInterleavedWord : Interleavable (α := WordStack A κ ι) (β := InterleavedWord A κ ι) where
  interleave := interleaveWordStack

@[simp]
instance  _root_.Code.instInterleavableElemWordStackCodewordStackMatrixInterleavedCodeword : Interleavable (α := CodewordStack A κ ι C) (β := InterleavedCodeword A κ ι C) where
  interleave u := ⟨interleaveWordStack u.val, by
    rw [mem_interleavedCode_iff]
    let h_u_mem := u.property
    rw [mem_codewordStack_iff] at h_u_mem
    intro k
    exact h_u_mem k
  ⟩

@[simp]
instance  _root_.Code.instInterleavableSubtypeWordStackMemSubmoduleCodewordStackSubmoduleForallInterleavedSymbolModuleCodeModuleInterleavedCode : Interleavable (α := ModuleCode.codewordStackSubmodule F A κ ι (MC := MC))
    (β := ModuleCode.moduleInterleavedCode F A κ ι (MC := MC)) where
  interleave u := interleaveCodewordStack (κ := κ) (ι := ι) (u := u)

@[simp]
instance  _root_.Code.instInterleavable₂WordInterleavedWordFinOfNatNat : Interleavable₂ (α := Word A ι) (β := InterleavedWord A (Fin 2) ι) where
  interleave₂ u₀ u₁ := interleaveTwoWords A ι u₀ u₁

@[simp]
instance  _root_.Code.instInterleavable₂ElemForallMatrixFinOfNatNatInterleavedCodeword : Interleavable₂ (α := C) (β := InterleavedCodeword A (κ := (Fin 2)) ι C) where
  interleave₂ u₀ u₁ := interleaveTwoCodewords A ι C u₀ u₁

/-- Interleave a Set-based code into an interleaved code set. -/
@[simp]
instance  _root_.Code.instCodeInterleavableSetForallMatrix : CodeInterleavable (Code := Set (ι → A))
    (InterleavedCode := fun κ => Set (Matrix ι κ A)) where
  interleaveCode C := fun κ => interleavedCodeSet (κ := κ) C

/-- Interleave a ModuleCode into an interleaved ModuleCode (preserving submodule structure). -/
@[simp]
instance  _root_.Code.instCodeInterleavableModuleCodeInterleavedSymbol : CodeInterleavable (Code := ModuleCode ι F A)
    (InterleavedCode := fun κ => ModuleCode ι F (InterleavedSymbol A κ)) where
  interleaveCode MC := fun κ => ModuleCode.moduleInterleavedCode
    (F := F) (A := A) (κ := κ) (ι := ι) (MC := MC)

omit [AddCommMonoid A] [Fintype κ] [Fintype ι] in
@[simp]
lemma interleave_wordStack_eq (u : WordStack A κ ι) : (⋈|u) = u.transpose := rfl

omit [AddCommMonoid A] [Fintype κ] [Fintype ι] in
@[simp]
lemma interleave_codewordStack_val_eq (u : CodewordStack A κ ι C) :
    (⋈| u).val = u.val.transpose := rfl

@[simp]
noncomputable instance instFintypeInterleavedModuleCode [Fintype A] : Fintype (MC ^⋈ κ) := by
  exact Fintype.ofFinite ((MC ^⋈ κ) : Set (ι → (κ → A)))

@[simp]
lemma interleavedCode_eq_interleavedCodeSet {A : Type*} {ι : Type*} {κ : Type*} {C : Set (ι → A)} :
    (C ^⋈ κ) = interleavedCodeSet (κ := κ) C:= by rfl

@[simp]
lemma interleavedCode_eq_interleavedCodeSet_of_moduleCode {F A : Type*} {κ ι : Type*} [Semiring F]
    [AddCommMonoid A] [Module F A] {MC : ModuleCode ι F A} :
    ((MC ^⋈ κ) : Set (ι → (κ → A))) = interleavedCodeSet (κ := κ) (C := (MC : Set (ι → A)))
    := by rfl

/-- Interleaving over a nonempty row index preserves minimum block distance:
`minDist (interleavedCodeSet C) = minDist C`.

For `≥`, two distinct interleaved words differ in some row, whose Hamming distance is bounded
by their block distance. For `≤`, place a minimum-distance base pair in one row and repeat
one endpoint in every other row. The subsingleton case is handled separately, both sides
being zero there. -/
theorem minDist_interleavedCodeSet
    {κ ι A : Type*} [Fintype κ] [Nonempty κ] [Fintype ι] [DecidableEq A]
    (C : Set (ι → A)) :
    minDist (interleavedCodeSet (κ := κ) C) = minDist C := by
  classical
  let IC : Set (ι → κ → A) := {V | ∀ k, (fun i ↦ V i k) ∈ C}
  change minDist IC = minDist C
  by_cases hC : Set.Nontrivial C
  · obtain ⟨u, hu, v, hv, huv⟩ := hC
    let k0 : κ := Classical.choice ‹Nonempty κ›
    let U : ι → κ → A := fun i _ ↦ u i
    let V : ι → κ → A := fun i k ↦ if k = k0 then v i else u i
    have hU : U ∈ IC := by
      intro k
      change (fun i ↦ u i) ∈ C
      exact hu
    have hV : V ∈ IC := by
      intro k
      by_cases hk : k = k0
      · subst k
        change (fun i ↦ if k0 = k0 then v i else u i) ∈ C
        simpa using hv
      · change (fun i ↦ if k = k0 then v i else u i) ∈ C
        simp [hk, hu]
    have hUV : U ≠ V := by
      intro h
      apply huv
      funext i
      have := congrFun (congrFun h i) k0
      simpa [U, V] using this
    have hupper : minDist IC ≤ minDist C := by
      have hS : {d | ∃ x ∈ C, ∃ y ∈ C, x ≠ y ∧ hammingDist x y = d}.Nonempty :=
        ⟨hammingDist u v, u, hu, v, hv, huv, rfl⟩
      have hmem : ∃ x ∈ C, ∃ y ∈ C, x ≠ y ∧ hammingDist x y = minDist C := by
        exact Nat.sInf_mem hS
      obtain ⟨x, hx, y, hy, hxy, hdist⟩ := hmem
      let X : ι → κ → A := fun i _ ↦ x i
      let Y : ι → κ → A := fun i k ↦ if k = k0 then y i else x i
      have hX : X ∈ IC := by
        intro k
        change (fun i ↦ x i) ∈ C
        exact hx
      have hY : Y ∈ IC := by
        intro k
        by_cases hk : k = k0
        · subst k
          change (fun i ↦ if k0 = k0 then y i else x i) ∈ C
          simpa using hy
        · change (fun i ↦ if k = k0 then y i else x i) ∈ C
          simp [hk, hx]
      have hXY : X ≠ Y := by
        intro h
        apply hxy
        funext i
        have := congrFun (congrFun h i) k0
        simpa [X, Y] using this
      apply Nat.sInf_le
      refine ⟨X, hX, Y, hY, hXY, ?_⟩
      rw [← hdist]
      unfold hammingDist
      congr 1
      ext i
      simp only [Finset.mem_filter, Finset.mem_univ, true_and]
      constructor
      · intro hne hxy_i
        apply hne
        funext k
        simp [X, Y, hxy_i]
      · intro hxy_i hEq
        apply hxy_i
        have := congrFun hEq k0
        simpa [X, Y] using this
    have hSIC : {d | ∃ x ∈ IC, ∃ y ∈ IC, x ≠ y ∧ hammingDist x y = d}.Nonempty :=
      ⟨hammingDist U V, U, hU, V, hV, hUV, rfl⟩
    have hmemIC : ∃ X ∈ IC, ∃ Y ∈ IC, X ≠ Y ∧ hammingDist X Y = minDist IC := by
      exact Nat.sInf_mem hSIC
    obtain ⟨X, hX, Y, hY, hXY, hdist⟩ := hmemIC
    have hex : ∃ i k, X i k ≠ Y i k := by
      obtain ⟨i, hi⟩ := Function.ne_iff.mp hXY
      obtain ⟨k, hk⟩ := Function.ne_iff.mp hi
      exact ⟨i, k, hk⟩
    obtain ⟨i0, k, hik⟩ := hex
    have hrow : (fun i ↦ X i k) ≠ fun i ↦ Y i k := by
      intro h
      exact hik (congrFun h i0)
    have hlower : minDist C ≤ minDist IC := by
      calc
        minDist C ≤ hammingDist (fun i ↦ X i k) (fun i ↦ Y i k) := by
          apply Nat.sInf_le
          exact ⟨_, hX k, _, hY k, hrow, rfl⟩
        _ ≤ hammingDist X Y := by
          unfold hammingDist
          apply Finset.card_le_card
          intro i hi
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hi ⊢
          intro h
          exact hi (congrFun h k)
        _ = minDist IC := hdist
    exact le_antisymm hupper hlower
  · have hCsub : Set.Subsingleton C := Set.not_nontrivial_iff.mp hC
    have hICsub : Set.Subsingleton IC := by
      intro U hU V hV
      funext i k
      have h := hCsub (hU k) (hV k)
      exact congrFun h i
    have hbase : minDist C = 0 := by
      unfold minDist
      have hempty : {d | ∃ x ∈ C, ∃ y ∈ C, x ≠ y ∧ hammingDist x y = d} = ∅ := by
        rw [Set.eq_empty_iff_forall_notMem]
        rintro d ⟨x, hx, y, hy, hxy, -⟩
        exact hxy (hCsub hx hy)
      rw [hempty, Nat.sInf_empty]
    have hinter : minDist IC = 0 := by
      unfold minDist
      have hempty : {d | ∃ x ∈ IC, ∃ y ∈ IC, x ≠ y ∧ hammingDist x y = d} = ∅ := by
        rw [Set.eq_empty_iff_forall_notMem]
        rintro d ⟨x, hx, y, hy, hxy, -⟩
        exact hxy (hICsub hx hy)
      rw [hempty, Nat.sInf_empty]
    rw [hbase, hinter]

section Finrank

/-! ### Structure and dimension of an interleaved module code -/

/-- A `κ`-tuple of codewords of a module code `MC` is the same data as a codeword of the
interleave `MC ^⋈ κ`: the tuple `g` corresponds to the interleaved word whose `k`-th row is
`g k`. No finiteness of `κ` or `ι` is required. -/
def moduleInterleavedCodeEquiv {F : Type*} [Semiring F] {A : Type*} [AddCommMonoid A]
    [Module F A] {ι : Type*} (MC : ModuleCode ι F A) (κ : Type*) :
    (κ → MC) ≃ₗ[F] (MC ^⋈ κ) where
  toFun g := ⟨fun i k => (g k : ι → A) i, fun k => (g k).2⟩
  invFun V := fun k => ⟨fun i => V.val i k, V.2 k⟩
  left_inv g := by funext k; exact Subtype.ext rfl
  right_inv V := by apply Subtype.ext; funext i k; rfl
  map_add' g g' := by apply Subtype.ext; funext i k; rfl
  map_smul' a g := by apply Subtype.ext; funext i k; rfl

/-- Interleaving multiplies the dimension by the interleaving factor:
`finrank F (MC ^⋈ κ) = Fintype.card κ * finrank F MC`.

Immediate from `moduleInterleavedCodeEquiv` and `Module.finrank_pi_fintype`, whose `Free` and
`Finite` hypotheses are inherited; both hold automatically when `F` is a field and the ambient
`ι → A` is finite-dimensional. -/
lemma finrank_moduleInterleavedCode {F : Type*} [Semiring F] [StrongRankCondition F]
    {A : Type*} [AddCommMonoid A] [Module F A] {ι : Type*} (MC : ModuleCode ι F A)
    [Module.Free F MC] [Module.Finite F MC] (κ : Type*) [Fintype κ] :
    Module.finrank F (MC ^⋈ κ) = Fintype.card κ * Module.finrank F MC := by
  rw [← (moduleInterleavedCodeEquiv MC κ).finrank_eq, Module.finrank_pi_fintype,
    Finset.sum_const, Finset.card_univ, smul_eq_mul]

end Finrank

@[simp]
instance  _root_.Code.instHAppendWordStackSum {κ₁ κ₂ : Type*} :
    HAppend (WordStack A κ₁ ι) (WordStack A κ₂ ι) (WordStack A (Sum κ₁ κ₂) ι) where
  hAppend u v := fun s =>
    match s with
    | Sum.inl k₁ => u k₁
    | Sum.inr k₂ => v k₂

@[simp]
instance  _root_.Code.instHAppendElemWordStackCodewordStackSum {κ₁ κ₂ : Type*} :
    HAppend (CodewordStack A κ₁ ι C) (CodewordStack A κ₂ ι C)
      (CodewordStack A (Sum κ₁ κ₂) ι C) where
  hAppend u v := finMapCodewordStacksAppend A ι C (κ₁ := κ₁) (κ₂ := κ₂) u v


namespace InterleavedCode

/-!
  ## Interleaved Code Structure
  Implementation of the 7-step blueprint for Interleaved Codes.
-/

variable (RowIdx SymbolIdx : Type*)
variable (RowType SymbolType CellTy : Type*)

/-! ### 1, 2, 3. Accessors -/

/-- 1. GetRow -/
class GetRow (α : Type*) (RowIdx RowType : outParam Type*) where
  getRow : (u : α) → (rowIdx : RowIdx) → RowType

/-- 2. GetSymbol -/
class GetSymbol (α : Type*) (SymbolIdx SymbolType : outParam Type*) where
  getSymbol : (u : α) → (symbolIdx : SymbolIdx) → SymbolType

/-- 3. GetCell -/
class GetCell (α : Type*) (RowIdx SymbolIdx : Type*) (CellTy : outParam Type*) where
  getCell : (u : α) → (rowIdx : RowIdx) → (symbolIdx : SymbolIdx) → CellTy

export GetRow (getRow)
export GetSymbol (getSymbol)
export GetCell (getCell)

/-- 6. InterleavedStructure: Extends accessors and defines equality via rows/symbols/cells.
    Applied to the InterleavedElementType. -/
class InterleavedStructure (α : Type*) (RowIdx SymbolIdx : outParam Type*)
    (RowType SymbolType CellTy : outParam Type*)
    extends GetRow α RowIdx RowType,
            GetSymbol α SymbolIdx SymbolType,
            GetCell α RowIdx SymbolIdx CellTy where
  eq_iff_all_rows_eq {u v : α} : u = v ↔ ∀ i, getRow u i = getRow v i
  eq_iff_all_symbols_eq {u v : α} : u = v ↔ ∀ k, getSymbol u k = getSymbol v k
  eq_iff_all_cells_eq {u v : α} : u = v ↔ ∀ i k, getCell u i k = getCell v i k

export InterleavedStructure (eq_iff_all_rows_eq eq_iff_all_symbols_eq eq_iff_all_cells_eq)

-- WordStack
@[simp] instance (priority := 500) instInterleavedStructureWordStack :
    InterleavedStructure (α := WordStack A κ ι) (RowIdx := κ) (SymbolIdx := ι)
      (RowType := Word A ι) (SymbolType := InterleavedSymbol A κ) (CellTy := A) where
  getRow u k := WordStack.getRowWord u k
  getSymbol u i := WordStack.getSymbol u i
  getCell u k i := (WordStack.getRowWord u k) i
  eq_iff_all_rows_eq := by
    intro u v; constructor
    · intro h; exact fun i ↦ congrFun h i
    · intro h; ext i k; exact congrFun (h i) k
  eq_iff_all_symbols_eq := by
    intro u v; constructor
    · intro h; exact fun k ↦ congrFun (congrArg Matrix.transpose h) k
    · intro h; ext i k; exact congrFun (h k) i
  eq_iff_all_cells_eq := by
    intro u v; constructor
    · intro h; exact fun i k ↦ congrFun (congrFun h i) k
    · intro h; ext i k; exact h i k

-- CodewordStack
@[simp] instance instInterleavedStructureCodewordStack :
    InterleavedStructure (α := CodewordStack A κ ι C) (RowIdx := κ)
  (SymbolIdx := ι) (RowType := C) (SymbolType := InterleavedSymbol A κ) (CellTy := A) where
  getRow u k := ⟨u.val k, by -- No separate functions because CodewordStack is a subtype
    have h_u_mem := u.property
    rw [mem_codewordStack_iff] at h_u_mem
    exact h_u_mem k
  ⟩
  getSymbol u i := u.val.transpose i
  getCell u k i := u.val k i
  eq_iff_all_rows_eq := by
    intro u v; constructor
    · intro h; rw [h]; exact fun i ↦ rfl
    · intro h; ext i k
      exact congrFun (congrArg Subtype.val (h i)) k
  eq_iff_all_symbols_eq := by
    intro u v; constructor
    · intro h; rw [h]; exact fun k ↦ rfl
    · intro h; ext i k
      exact congrFun (h k) i
  eq_iff_all_cells_eq := by
    intro u v; constructor
    · intro h; rw [h]; exact fun i k ↦ rfl
    · intro h; ext i k
      exact h i k

-- InterleavedWord
@[simp] instance instInterleavedStructureInterleavedWord :
    InterleavedStructure (α := InterleavedWord A κ ι) (RowIdx := κ)
  (SymbolIdx := ι) (RowType := Word A ι) (SymbolType := InterleavedSymbol A κ) (CellTy := A) where
  getRow u i := InterleavedWord.getRowWord u i
  getSymbol u k := InterleavedWord.getSymbol u k
  getCell u i k := (InterleavedWord.getRowWord u i) k
  eq_iff_all_rows_eq := by
    intro u v; constructor
    · intro h; exact fun k ↦ congrFun (congrArg Matrix.transpose h) k
    · intro h; ext i k; exact congrFun (h k) i
  eq_iff_all_symbols_eq := by
    intro u v; constructor
    · intro h; exact fun k ↦ congrFun h k
    · intro h; ext i k; exact congrFun (h i) k
  eq_iff_all_cells_eq := by
    intro u v; constructor
    · intro h; exact fun i k ↦ congrFun (congrFun h k) i
    · intro h; ext k i; exact h i k

-- InterleavedCodeword
@[simp] instance instInterleavedStructureInterleavedCodeword :
    InterleavedStructure (α := InterleavedCodeword A κ ι C) (RowIdx := κ)
  (SymbolIdx := ι) (RowType := C) (SymbolType := InterleavedSymbol A κ) (CellTy := A) where
  -- No separate functions cuz InterleavedCodeword is a subtype
  getRow u k := ⟨(Matrix.transpose u) k, by
    have h_u_mem := u.property
    rw [mem_interleavedCode_iff] at h_u_mem
    exact h_u_mem k
  ⟩
  getSymbol u colIdx := u.val colIdx
  getCell u k i := Matrix.transpose u k i
  eq_iff_all_rows_eq := by
    intro u v; constructor
    · intro h; rw [h]; exact fun i ↦ rfl
    · intro h; ext i k;
      let res := h k; simp only [Subtype.mk.injEq] at res; exact congrFun res i
  eq_iff_all_symbols_eq := by
    intro u v; constructor
    · intro h; rw [h]; exact fun k ↦ rfl
    · intro h; ext i k;
      exact congrFun (h i) k
  eq_iff_all_cells_eq := by
    intro u v; constructor
    · intro h; rw [h]; exact fun i k ↦ rfl
    · intro h; ext i k; exact h k i

class Stackifiable (α : Type*) (β : outParam Type*) where
  stackify : α → β

notation:65 "⋈⁻¹|" u => Stackifiable.stackify u

@[simp]
instance  _root_.Code.InterleavedCode.instStackifiableInterleavedWordWordStack : Stackifiable (α := InterleavedWord A κ ι) (β := WordStack A κ ι) where
  stackify u := u.transpose

@[simp]
instance  _root_.Code.InterleavedCode.instStackifiableElemMatrixInterleavedCodewordWordStackCodewordStack : Stackifiable (α := InterleavedCodeword A κ ι C) (β := CodewordStack A κ ι C) where
  stackify u := ⟨u.val.transpose, by
    rw [mem_codewordStack_iff]
    let h_u_mem := u.property
    rw [mem_interleavedCode_iff] at h_u_mem
    intro k
    exact h_u_mem k
  ⟩

omit [AddCommMonoid A] [Fintype κ] [Fintype ι] in
/-- Used to getRow at u.val instead of getRow u -/
@[simp]
lemma getRowOfInterleavedCodeword_mem_code (C : Set (ι → A))
    (u : CodeInterleavable.interleaveCode (C) κ) (rowIdx : κ) :
    getRow (u.val) rowIdx ∈ C := by
  let getRowAsIC := getRow (show InterleavedCodeword A κ ι C from u) rowIdx
  exact getRowAsIC.property

omit [AddCommMonoid A] [Fintype κ] [Fintype ι] in
/-- Used to getRow at u.val instead of getRow u -/
@[simp]
lemma getRowOfCodewordStack_mem_code (C : Set (ι → A))
    (u : CodewordStack A κ ι C) (rowIdx : κ) :
    u.val rowIdx ∈ C := by
  have := u.property
  rw [mem_codewordStack_iff] at this
  exact this rowIdx

/-- Notation for stacking one stack on top of another -/
infixl:65 " ++ₕ " => HAppend.hAppend

@[simp]
instance instNonemptyInterleavedCode [Nonempty C] :
    Nonempty (C ^⋈ κ) := by
  let c : C := Classical.arbitrary C
  use fun i k => c.val i
  intro k
  exact c.property

example (C : Set (ι → A)) : ((C ^⋈ (Fin 2))) = interleavedCodeSet (κ := Fin 2) C
    := by rfl
example (MC : ModuleCode ι F A) : (MC ^⋈ (Fin 2))
    = ModuleCode.moduleInterleavedCode (F := F) (A := A) (κ := Fin 2) (ι := ι) (MC := MC)
    := by rfl
example (u : CodewordStack A κ ι C) :
  let iuCodewords: InterleavedCodeword A κ ι C := ⋈|u
  let iuWords: InterleavedWord A κ ι := ⋈|u.val
  iuCodewords.val = iuWords := by rfl
example (v₀ v₁ : C) :
  let iv_codeword : InterleavedWord A (Fin 2) ι := v₀.val ⋈₂ v₁.val
  let iv_word : InterleavedCodeword A (Fin 2) ι C := v₀ ⋈₂ v₁
  iv_codeword = iv_word := by rfl

end InterleavedCode

/-! ### Distance Properties for Interleaved Codes
**Naming conventions**:
- by default, when we say "interleaved word", it means the interleaved word of a
  `WordStack` (i.e. using notation `⋈|`).
- if the definition has `₂` at the end of its name, it means the interleaved word is of two
  `Word`s (i.e. using notation `⋈₂`).
- prefix `joint` or `pairjoint` :
  + `joint`: involves distance **from an interleaved word to the interleaved code `C^⋈ κ`**
  + `pairJoint`: involves distance **between two interleaved words**
- suffix `Nat` : the proximity is represented in terms of concrete distance (`Δ₀`),
  without this suffix, relative distance (`δᵣ`) is used instead.
-/
section JointProximityDefinitions

-- variable [DecidableEq A] [DecidableEq ι]

variable {κ ι : Type*} [Fintype ι] [Fintype κ]
  {A : Type*} (C : Set (ι → A)) [DecidableEq A]

/-- `jointProximity u δ` means the interleaved word stack `u` is within relative distance `δ` of
the interleaved code `MC^⋈ κ`. -/
def jointProximity (u : WordStack A κ ι) (δ : NNReal) : Prop :=
  let u_interleaved : InterleavedWord A κ ι := ⋈|u
  δᵣ(u_interleaved, interleavedCodeSet C) ≤ δ

/-- `jointProximity₂ u₀ u₁ e` means the interleaved pair `(u₀, u₁)` is within distance
`e` of the interleaved code `MC^⋈ (Fin 2)`. -/
def jointProximity₂ (u₀ u₁ : Word A ι) (δ : NNReal) : Prop :=
  let u_stack : WordStack A (Fin 2) ι := finMapTwoWords u₀ u₁
  jointProximity C (u := u_stack) δ

/-- `jointProximityNat u e` means the interleaved word stack `u` is within distance `e` of
the interleaved code `MC^⋈ κ`. Can use `distFromCode_le_iff_relDistFromCode_le` and
`relDistFromCode_le_iff_distFromCode_le` to prove equivalence with `jointProximity`. -/
def jointProximityNat (u : WordStack A κ ι) (e : ℕ) : Prop :=
  let u_interleaved : InterleavedWord A κ ι := ⋈|u
  Δ₀(u_interleaved, (interleavedCodeSet C)) ≤ e

/-- `jointProximityNat₂ u₀ u₁ e` means the interleaved pair `(u₀, u₁)` is within distance
`e` of the interleaved code `MC^⋈ (Fin 2)`. -/
def jointProximityNat₂ (u₀ u₁ : Word A ι) (e : ℕ) : Prop :=
  let u_stack : WordStack A (Fin 2) ι := finMapTwoWords u₀ u₁
  jointProximityNat C (u := u_stack) e

/-- `pairJointProximity u v e` means the two interleaved word stacks `u` and `v`
are within distance `e` of each other. -/
def pairJointProximity (u v : WordStack A κ ι) (e : ℕ) : Prop :=
  let u_interleaved : InterleavedWord A κ ι := ⋈|u
  let v_interleaved : InterleavedWord A κ ι := ⋈|v
  Δ₀(u_interleaved, v_interleaved) ≤ e

/-- `pairJointProximity₂ u₀ u₁ v₀ v₁ e` means the interleaved pairs `(u₀, u₁)` and `(v₀, v₁)`
  are within distance `e` of each other. -/
def pairJointProximity₂ (u₀ u₁ v₀ v₁ : Word A ι) (e : ℕ) : Prop :=
  let u_interleaved : InterleavedWord A (Fin 2) ι := u₀ ⋈₂ u₁
  let v_interleaved : InterleavedWord A (Fin 2) ι := v₀ ⋈₂ v₁
  Δ₀(u_interleaved, v_interleaved) ≤ e

theorem jointProximityNat_iff_closeToInterleavedCodeword (u : WordStack A κ ι) (e : ℕ) :
    jointProximityNat C (u := u) e ↔ ∃ (v : InterleavedCodeword A κ ι C),
      let u_interleaved : InterleavedWord A κ ι := ⋈|u
      Δ₀(u_interleaved, v.val) ≤ e := by
  unfold jointProximityNat
  let u_interleaved : InterleavedWord A κ ι := ⋈|u
  have h := Code.closeToCode_iff_closeToCodeword_of_minDist
    (C := (interleavedCodeSet C)) (u := u_interleaved) (e := e)
  constructor
  · -- Direction 1: correlatedAgreement u e → ∃ v, Δ₀(⋈|u, v) ≤ e
    intro h_corr_agree
    have res := h.mp h_corr_agree
    rcases res with ⟨v, hv_Mem, hv_dist_le_e⟩
    use ⟨v, hv_Mem⟩
  · -- Direction 2: (∃ v, Δ₀(⋈|u, v) ≤ e) → correlatedAgreement u e
    intro h_exists_v
    rcases h_exists_v with ⟨v, hvClose⟩
    have res := h.mpr (by
      use v.val
      constructor
      · exact v.property
      · exact hvClose
    )
    exact res

/-- The consequent of correlated agreement: Words collectively agree on the same set of coordinates
`S` with the base code `C`.
Variants of this definition should follow the naming conventions of `jointProximity`
if possible, for consistency.
TOOD: this can generalize further to support the consequent of mutual correlated agreement. -/
def jointAgreement {F κ ι : Type*} [Fintype ι] [DecidableEq F]
    (C : Set (ι → F)) (δ : ℝ≥0) (W : κ → ι → F) : Prop :=
  ∃ S : Finset ι, S.card ≥ (1 - δ) * (Fintype.card ι) ∧
      ∃ v : κ → ι → F, ∀ i, v i ∈ C ∧ S ⊆ Finset.filter (fun j => v i j = W i j) Finset.univ

open InterleavedCode in
/-- Equivalence between the agreement-based definition `jointAgreement` and
the distance/proximity-based definition `jointProximity` (the latter is represented in
upperbound of interleaved-code distance). -/
@[simp]
theorem jointAgreement_iff_jointProximity
    {F : Type*} {κ ι : Type*} [Fintype κ] [Fintype ι] [Nonempty ι] [DecidableEq F]
    (C : Set (ι → F)) (u : WordStack F κ ι) (δ : ℝ≥0) :
    jointAgreement (C := C) (δ := δ) (W := u)  ↔ jointProximity (C := C) (u := u) (δ := δ) := by
  classical
  let e : ℕ := Nat.floor (δ * Fintype.card ι)
  constructor
  · -- Forward direction: jointAgreement → jointProximity
    intro h_words
    rcases h_words with ⟨S, hS_card, v, hv⟩
    -- We have: |S| ≥ (1-δ)*|ι| and ∀ i, v i ∈ MC and S ⊆ {j | v i j = u i j}
    -- Need to show: δᵣ(u_interleaved, MC.interleavedCode) ≤ δ
    -- Define interleaved word from u
    let u_interleaved : InterleavedWord F κ ι := ⋈|u
    -- Construct interleaved codeword from v
    let v_interleaved : InterleavedWord F κ ι := interleaveWordStack v
    have hv_interleaved_mem : v_interleaved ∈ interleavedCodeSet C := by
      rw [mem_interleavedCode_iff]
      intro k
      exact (hv k).1
    -- Now show that u_interleaved and v_interleaved agree on S
    -- This gives us the distance bound
    have h_agree_on_S : ∀ j ∈ S, u_interleaved j = getSymbol v_interleaved j := by
      intro j hj
      ext k
      -- u_interleaved j k = u k j, v_interleaved j k = v k j; Need: u k j = v k j
      have h_agree := (hv k).2
      have hj_in_filter : j ∈ Finset.filter (fun j => v k j = u k j) Finset.univ := by
        rw [Finset.mem_filter]
        constructor
        · exact Finset.mem_univ j
        · -- v k j = u k j
          have h_subset := Finset.subset_iff.mp h_agree
          have hj_mem : j ∈ S := hj
          let res := h_subset (x := j) hj_mem
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at res
          exact res
      simp only [Finset.mem_filter] at hj_in_filter
      exact hj_in_filter.2.symm
    -- From agreement on S, we get distance bound
    have h_dist : δᵣ(u_interleaved, v_interleaved) ≤ δ := by
      rw [relCloseToWord_iff_exists_agreementCols]
      use S
      rw [relDist_floor_bound_iff_complement_bound]
      constructor
      · exact hS_card
      · intro j
        constructor
        · intro hj_in_S
          have h_agree := h_agree_on_S j hj_in_S
          exact h_agree
        · intro hj_not_in_S
          by_contra hj_in_S
          exact hj_not_in_S (h_agree_on_S j hj_in_S)
    rw [←ENNReal.coe_le_coe] at h_dist
    -- Since v_interleaved ∈ MC.interleavedCode, we have δᵣ(u_interleaved, MC.interleavedCode) ≤ δ
    unfold jointProximity
    have h_min_dist :
        δᵣ(u_interleaved, interleavedCodeSet C) ≤ δᵣ(u_interleaved, v_interleaved)
      := by
      apply relDistFromCode_le_relDist_to_mem (u := u_interleaved) (C := interleavedCodeSet C)
        (v := v_interleaved) (hv := hv_interleaved_mem)
    exact le_trans h_min_dist h_dist
  · -- Backward direction: jointProximity → jointAgreement
    intro h_joint
    unfold jointProximity at h_joint
    let u_interleaved : InterleavedWord F κ ι := ⋈|u
    -- h_joint says: δᵣ(u_interleaved, MC.interleavedCode) ≤ δ
    -- This means there exists v in the interleaved code with δᵣ(u_interleaved, v) ≤ δ
    have h_close := Code.closeToCode_iff_closeToCodeword_of_minDist
      (C := (interleavedCodeSet C)) (u := u_interleaved)
    -- Convert relative distance to natural distance
    -- Key: if δᵣ(u, C) ≤ δ, there exists a codeword v with δᵣ(u, v) ≤ δ
    have h_rel_to_nat : δᵣ(u_interleaved, interleavedCodeSet C) ≤ δ →
        ∃ v ∈ (interleavedCodeSet C), δᵣ(u_interleaved, v) ≤ δ := by
      intro h_rel
      rw [relCloseToCode_iff_relCloseToCodeword_of_minDist] at h_rel
      exact h_rel
    have h_exists_v := h_rel_to_nat h_joint
    rcases h_exists_v with ⟨v, hv_mem, hv_dist⟩
    -- Now convert relative distance to agreement set
    -- We need: δᵣ(u_interleaved, v) ≤ δ → ∃ S, |S| ≥ (1-δ)*|ι| and agreement
    -- Convert relative distance δ to natural distance e
    have h_nat_dist : Δ₀(u_interleaved, v) ≤ e := by
      rw [pairRelDist_le_iff_pairDist_le (δ := δ)] at hv_dist
      exact hv_dist
    have h_agree := Code.closeToWord_iff_exists_agreementCols
      (u := u_interleaved) (v := v) (e := e)
    have h_agree_nat := h_agree.mp h_nat_dist
    rcases h_agree_nat with ⟨S, hS_card, h_agree_S⟩
    -- Now extract rows from v to get v : κ → ι → F
    let v_rows : κ → ι → F := fun k => getRow v k
    use S
    constructor
    · -- Prove |S| ≥ (1-δ)*|ι|
      rw [ge_iff_le]
      rw [relDist_floor_bound_iff_complement_bound] at hS_card
      exact hS_card
    · -- Prove agreement
      use v_rows
      intro i
      constructor
      · -- v_rows i ∈ MC
        simp only [interleavedCodeSet, Set.mem_setOf_eq] at hv_mem
        exact hv_mem i
      · -- S ⊆ {j | v_rows i j = u i j}
        simp only [Finset.subset_iff]
        intro j hj_mem
        simp only [Finset.mem_filter, Finset.mem_univ, true_and] -- ⊢ v_rows i j = u i j
        have h_agree := h_agree_S (colIdx := j).1 hj_mem
        apply congrArg (fun x => x i) at h_agree
        exact id (Eq.symm h_agree)

/-- The list of `κ`-fold codeword stacks whose interleaved codeword forms are
(less-than)-`δ`-close to `⋈|u`. -/
def relHammingBallInterleavedCode (u : WordStack A κ ι) (δ : ℝ≥0) : Set (CodewordStack A κ ι C) :=
  {v : CodewordStack A κ ι (C := C) | δᵣ(⋈|u, (⋈|v).val) < δ}

/-- `Λᵢ(u, C, δ)` denotes the list of `κ`-fold codeword stacks whose interleaved codeword forms are
(less-than)-`δ`-close to `⋈|u`. -/
notation "Λᵢ(" u "," C "," δ ")" => relHammingBallInterleavedCode C u δ

end JointProximityDefinitions

end Code
end InterleavedCodeDefinitions


Source
https://github.com/Verified-zkEVM/ArkLib/blob/e65197892890b8fd9b0dc05b8980273cf1d595cc/ArkLib/Data/CodingTheory/InterleavedCode.lean yukon-proof-operation:27b1afcb807aceb70eeb3d8de776649b460d3d1f979c53bbdb50f83ce20eb9dc [yukon-proof-receipt:eyJ2IjoxLCJtYXJrZXIiOiJ5dWtvbi1wcm9vZi1vcGVyYXRpb246MjdiMWFmY2I4MDdhY2ViNzBlZWIzZDhkZTc3NjY0OWI0NjBkM2QxZjk3OWM1M2JiZGI1MGY4M2NlMjBlYjlkYyIsImhhc2giOiJiNjM0MGM3OWU5Y2I1OWMxMmVmNWJjN2UwN2ZhYjFkNDU0ZTZiYTc5MTFlZjI4NWIwYmNkMTc2YTY4MWVmNWY5Iiwia2luZCI6ImRlZmluaXRpb24iLCJ0YXJnZXQiOiJZdWtvbl81N2YyZjRhNTgyYjU5YzUzY2RlZTgzNWQiLCJlbnZpcm9ubWVudCI6eyJtYXRobGliUmV2IjoiMGRmNDQ0YTM2MGVhYTYwYWI4YzExZGNhNTFhODZhZjY5Mjk1NTQ3NCIsInRvb2xjaGFpbiI6ImxlYW5wcm92ZXIvbGVhbjQ6djQuMzMuMSJ9LCJ0YWciOiJiZXR0ZXItY29kZXMifQ]

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me