Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

YukonModule.ArkLib.Data.CodingTheory.ReedSolomon.part0

Definition
Yukon_e9ee7c0e88307b8acac3260e

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

better-codes

Source module ArkLib.Data.CodingTheory.ReedSolomon. Reviewed historical port from Lean 4.32.2 to 4.33.1: compatible proof bodies, equivalent notation expansion, and omission of unused tooling/declarations. Retained statements and mathematical definitions preserve the original meaning. Original source: https://github.com/Verified-zkEVM/ArkLib/blob/e65197892890b8fd9b0dc05b8980273cf1d595cc/ArkLib/Data/CodingTheory/ReedSolomon.lean

Definition code
/-
Copyright (c) 2024 ArkLib Contributors. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Quang Dao, Katerina Hristova, František Silváši, Julian Sutherland, Ilia Vlasov,
Mirco Richter, Chung Thai Nguyen, Aristotle (Harmonic)
-/

import Definitions.Def_Yukon_73b6d213572a257be84d4060

import Definitions.Def_Yukon_2acb8bd3d300b885b84da30c

import Definitions.Def_Yukon_a07d5a446bf8be9c414fdc73

import Definitions.Def_Yukon_56681f993ecf0dddcae4ca01

import Definitions.Def_Yukon_ed298d692f02efadb0468be6

import Mathlib.LinearAlgebra.Lagrange
import Mathlib.RingTheory.Henselian
import Mathlib.Data.NNReal.Defs
import Mathlib.Data.NNReal.Basic -- for instFloorSemiring of ℝ≥0


import Mathlib.LinearAlgebra.StdBasis
import Mathlib.Order.CompletePartialOrder
import Mathlib.LinearAlgebra.FreeModule.StrongRankCondition
import Mathlib.LinearAlgebra.FiniteDimensional.Defs
import Mathlib.Algebra.Order.Star.Basic
import Mathlib.Algebra.Lie.OfAssociative
import Mathlib.Algebra.BigOperators.Finsupp.Fin
import Mathlib.Data.Finsupp.Fin
import Init
import Mathlib.Algebra.MvPolynomial.Equiv
import Mathlib.RingTheory.MvPolynomial.Basic
import Mathlib.RingTheory.Polynomial.Basic
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.Algebra.MvPolynomial.Eval
import Mathlib.Data.FinEnum
import Mathlib.Algebra.Group.Action.Pointwise.Finset
import Mathlib.Algebra.Polynomial.Roots
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.Topology.MetricSpace.Infsep
import Mathlib.Tactic.Qify
import Mathlib.InformationTheory.Hamming
import Mathlib.Data.ENat.Lattice
import Mathlib.Analysis.InnerProductSpace.PiL2
import Mathlib.Algebra.Order.Floor.Semifield
import Mathlib.LinearAlgebra.AffineSpace.Combination
import Mathlib.LinearAlgebra.AffineSpace.Pointwise
import Mathlib.LinearAlgebra.Matrix.Rank
import Definitions.Def_Yukon_2d0e6914e1f35ef62dbe39e4
import Definitions.Def_Yukon_06fd17bede7d9846a07acaa7
set_option backward.isDefEq.respectTransparency.types false
/-!
# Reed-Solomon Codes

- The lemmas with suffix `'` (e.g. dim_eq_deg_of_le', minDist', ...) are generalizations of
  their corresponding non-suffixed versions from `Fin m` index to arbitrary finite index type `ι`.

## References

* [Arnon, G., Chiesa, A., Fenzi, G., and Yogev, E., *WHIR: Reed–Solomon Proximity Testing
    with Super-Fast Verification*][ACFY24]
* [Guruswami, V., Rudra, A., Sudan M., *Essential Coding Theory*, online copy][GRS25]
-/

namespace ReedSolomon

open Polynomial NNReal

variable {F : Type*} {ι : Type*} (domain : ι ↪ F)

/-- The evaluation of a polynomial at a set of points specified by `domain : ι ↪ F`, as a linear
map. -/
def evalOnPoints [Semiring F] : F[X] →ₗ[F] (ι → F) where
  toFun p x := p.eval (domain x)
  map_add'  := by aesop
  map_smul' := by aesop

/-- Proves that `evalOnPoints` preserves multiplication as well. -/
def evalOnPointsRingHom [CommSemiring F] : F[X] →+* (ι → F) where
  toFun p x := p.eval (domain x)
  map_zero' := by aesop
  map_one'  := by aesop
  map_add'  := by aesop
  map_mul'  := by aesop

lemma evalOnPointsRingHom_eq_evalOnPoints [CommSemiring F] {p : F[X]} {domain : ι ↪ F} :
  evalOnPointsRingHom domain p = evalOnPoints domain p := rfl

@[simp]
lemma evalOnPoints_mul [CommSemiring F] {domain : ι ↪ F} {p q : F[X]} :
  evalOnPoints domain (p * q) = evalOnPoints domain p * evalOnPoints domain q := by
  exact (evalOnPointsRingHom domain).map_mul p q

/-- The Reed-Solomon code for polynomials of degree less than `deg` and evaluation points `domain`.
-/
noncomputable def code (deg : ℕ) [Semiring F] : Submodule F (ι → F) :=
  (Polynomial.degreeLT F deg).map (evalOnPoints domain)

/-- If a linear encoder `enc : F[X] →ₗ[F] (ι → Fin 1 → F)` agrees with plain evaluation at
its single index, `enc p x 0 = p.eval (domain x)`, then the code it cuts out of
`Polynomial.degreeLT F k` is `code domain k`, up to erasing the trivial `Fin 1` index.

This is the shared content of the degenerate-parameter collapse for the Reed-Solomon
variants over the alphabet `Fin s → F`. -/
lemma mem_map_degreeLT_one_iff_mem_code [CommSemiring F] (k : ℕ)
    (enc : F[X] →ₗ[F] (ι → Fin 1 → F))
    (henc : ∀ (p : F[X]) (x : ι), enc p x 0 = p.eval (domain x))
    (f : ι → Fin 1 → F) :
    f ∈ (Polynomial.degreeLT F k).map enc ↔ (fun x ↦ f x 0) ∈ code domain k := by
  simp only [Submodule.mem_map, code, evalOnPoints, LinearMap.coe_mk, AddHom.coe_mk]
  constructor
  · rintro ⟨p, hp, rfl⟩
    exact ⟨p, hp, funext fun x ↦ (henc p x).symm⟩
  · rintro ⟨p, hp, hp_eval⟩
    refine ⟨p, hp, ?_⟩
    funext x j
    have hj : j = 0 := Subsingleton.elim _ _
    subst hj
    rw [henc p x]
    exact congrFun hp_eval x

/-- The generator matrix of the Reed-Solomon code of degree `deg` and evaluation points `domain`. -/
def genMatrix (deg : ℕ) [Semiring F] : Matrix (Fin deg) ι F :=
  .of fun i j => domain j ^ (i : ℕ)

/-- The (parity)-check matrix of the Reed-Solomon code, assuming `ι` is finite. -/
noncomputable def checkMatrix (deg : ℕ) [Fintype ι] [Field F] :
  Matrix (Fin (Fintype.card ι - deg)) ι F :=
  let P := Finset.univ.prod fun j => (X - C (domain j))
  .of fun i j => domain j ^ (i : ℕ) * (P.derivative.eval (domain j))⁻¹

open Polynomial Matrix Code LinearCode

variable {F ι ι' : Type*}
         {C : Set (ι → F)}

section

open Finset Function

open scoped BigOperators

variable {ι : Type*} [Fintype ι] [Nonempty ι]
         {F : Type*} [Field F] [Fintype F]

abbrev RScodeSet (domain : ι ↪ F) (deg : ℕ) : Set (ι → F) := ReedSolomon.code domain deg

open Classical in
noncomputable def toFinset (domain : ι ↪ F) (deg : ℕ) : Finset (ι → F) :=
  (RScodeSet domain deg).toFinset

end

section

variable {deg m n : ℕ} {α : Fin m → F}

section

variable [Semiring F] {p : F[X]}

@[simp]
lemma evalOnPoints_C {domain : ι ↪ F} {a : F} :
  evalOnPoints domain (Polynomial.C a) = fun _ ↦ a := by simp [evalOnPoints]

@[simp]
lemma evalOnPoints_X {domain : ι ↪ F} :
  evalOnPoints domain Polynomial.X = domain := by simp [evalOnPoints]

lemma natDegree_lt_of_mem_degreeLT [NeZero deg] (h : p ∈ degreeLT F deg) : p.natDegree < deg := by
  by_cases p = 0
  · cases deg <;> aesop
  · aesop (add simp [natDegree_lt_iff_degree_lt, mem_degreeLT])

def encode [DecidableEq F] (msg : Fin deg → F) (domain : Fin m ↪ F) : Fin m → F :=
  (polynomialOfCoeffs msg).eval ∘ ⇑domain

lemma encode_mem_ReedSolomon_code [DecidableEq F] [NeZero deg]
    {msg : Fin deg → F} {domain : Fin m ↪ F} :
  encode msg domain ∈ ReedSolomon.code domain deg :=
  ⟨polynomialOfCoeffs msg, ⟨by simp, by ext i; simp [encode, ReedSolomon.evalOnPoints]⟩⟩

end

def makeZero (ι : ℕ) (F : Type*) [Zero F] : Fin ι → F := fun _ ↦ 0

@[simp]
lemma codewordIsZero_makeZero {ι : ℕ} {F : Type*} [Zero F] :
    makeZero ι F = 0 := by unfold makeZero; ext; rfl

open LinearCode

/-- The Vandermonde matrix is the generator matrix for an RS code of length `ι` and dimension `deg`.
-/
lemma genMatIsVandermonde [Fintype ι] [Field F] [inst : NeZero m] {α : ι ↪ F} :
    fromColGenMat (Vandermonde.nonsquare (ι' := m) α) = ReedSolomon.code α m := by
  classical
  unfold fromColGenMat ReedSolomon.code
  ext x; rw [LinearMap.mem_range, Submodule.mem_map]
  refine ⟨
    fun ⟨coeffs, h⟩ ↦ ⟨polynomialOfCoeffs coeffs, h.symm ▸ ?p₁⟩,
    fun ⟨p, h⟩ ↦ ⟨Fin.liftF' p.coeff, ?p₂⟩
  ⟩
  · rw [
      ←coeff_polynomialOfCoeffs_eq_coeffs (coeffs := coeffs),
      Vandermonde.mulVecLin_coeff_vandermondens_eq_eval_matrixOfPolynomials (by simp)
    ]
    simp [ReedSolomon.evalOnPoints]
  · exact h.2 ▸ Vandermonde.mulVecLin_coeff_vandermondens_eq_eval_matrixOfPolynomials
                  (natDegree_lt_of_mem_degreeLT h.1)

section

variable [Semiring F]

lemma mem_code_of_polynomial_of_degree_lt_of_eval {n : ℕ} {α : ι ↪ F} {f : ι → F}
  (p : Polynomial F)
  (hdeg : p.degree < n) (heval : ∀ i, f i = p.eval (α i)) :
  f ∈ code α n := by
  aesop
    (add simp [code, evalOnPoints,
               Polynomial.degreeLT,
               Polynomial.degree_lt_iff_coeff_zero])

lemma mem_code_of_polynomial_of_natDegree_lt_of_eval {n : ℕ} {α : ι ↪ F} {f : ι → F}
  (p : Polynomial F)
  (hdeg : p.natDegree < n) (heval : ∀ i, f i = p.eval (α i)) :
  f ∈ code α n := by
  by_cases h0 : p = 0
  · have hf : f = 0 := by aesop
    simp [hf]
  · rw [Polynomial.natDegree_lt_iff_degree_lt h0] at hdeg
    exact mem_code_of_polynomial_of_degree_lt_of_eval _ hdeg heval

lemma mem_code_iff_exists_polynomial {n : ℕ} {α : ι ↪ F} {f : ι → F} :
  f ∈ code α n ↔ ∃ p : Polynomial F, p.degree < n ∧ f = evalOnPoints α p := by
  constructor <;>
    intro h <;>
    obtain ⟨p, h₁, h₂⟩ := h <;>
    exists p <;>
    aesop (add simp
            [Polynomial.degreeLT,
             Polynomial.degree_lt_iff_coeff_zero])

theorem mem_code_iff_eval {n : ℕ} {α : ι ↪ F} {f : ι → F} :
  f ∈ ReedSolomon.code α n ↔
    ∃ p : F[X], p.degree < n ∧ ∀ x, p.eval (α x) = f x := by
  aesop (add simp [evalOnPoints, mem_code_iff_exists_polynomial])

lemma mem_code_iff_exists_polynomial_of_ne_zero {n : ℕ} [ne : NeZero n] {α : ι ↪ F} {f : ι → F} :
  f ∈ code α n ↔ ∃ p : Polynomial F, p.natDegree < n ∧ f = evalOnPoints α p := by
  rw [mem_code_iff_exists_polynomial]
  have hne := ne.out
  constructor <;>
  intro h <;>
  obtain ⟨p, h₁, h₂⟩ := h <;>
  exists p <;>
  by_cases hy : p = 0 <;>
  aesop
    (add simp [Polynomial.natDegree_lt_iff_degree_lt])
    (add safe (by omega))

theorem mem_code_iff_eval_of_ne_zero {n : ℕ} [NeZero n] {α : ι ↪ F} {f : ι → F} :
  f ∈ ReedSolomon.code α n ↔
    ∃ p : F[X], p.natDegree < n ∧ ∀ x, p.eval (α x) = f x := by
  aesop (add simp [evalOnPoints, mem_code_iff_exists_polynomial_of_ne_zero])

/-- `evalOnPoints α p` belongs to an RS-code of degree `n`,
  if `p.degree < n`. -/
lemma evalOnPoints_mem_code_of_degree_lt {α : ι ↪ F} {p : F[X]} (h_deg : p.degree < n) :
  evalOnPoints α p ∈ code α n :=
  mem_code_of_polynomial_of_degree_lt_of_eval p h_deg (by simp [evalOnPoints])

/-- `evalOnPoints α p` belongs to an RS-code of degree `n`,
  if `p.natDegree < n`. -/
lemma evalOnPoints_mem_code_of_natDegree_lt {α : ι ↪ F} {p : F[X]} (h_deg : p.natDegree < n) :
  evalOnPoints α p ∈ code α n :=
  mem_code_of_polynomial_of_natDegree_lt_of_eval p h_deg (by simp [evalOnPoints])

/-- **Monotonicity of `code` in the degree bound.** If `n ≤ m`, the degree-`n` Reed-Solomon code
is contained in the degree-`m` code over the same domain. -/
@[mono]
lemma code_mono {n m : ℕ} (h : n ≤ m) (α : ι ↪ F) :
    code α n ≤ code α m :=
  Submodule.map_mono (Polynomial.degreeLT_mono h)

/-- **The degree-zero Reed-Solomon code is trivial.** Only the zero word is a codeword of
`code α 0`. A direct corollary of `Polynomial.degreeLT_zero` (general polynomial fact) +
`Submodule.map_bot` (general linear-algebra fact). -/
@[simp]
lemma code_zero (α : ι ↪ F) : code α 0 = ⊥ := by
  rw [code, Polynomial.degreeLT_zero, Submodule.map_bot]

end

section

open NNReal

variable [Field F]

/-- Dimension formula for RS code with arbitrary finite index type `ι`. -/
lemma dim_eq_deg_of_le [Fintype ι]
  {α : ι ↪ F} (h : n ≤ Fintype.card ι) :
  LinearCode.dim (ReedSolomon.code α n) = n := by
  by_cases hcard : Fintype.card ι = 0
  · aesop (add simp [
      Module.finrank_eq_zero_of_subsingleton,
      Fintype.card_eq_zero_iff,
      ReedSolomon.code,
      dim])
  · rw [LinearCode.dim]
    let f := ReedSolomon.evalOnPoints (F := F) α
    let S := Polynomial.degreeLT F n
    have h_code : ReedSolomon.code α n = S.map f := rfl
    rw [h_code]
    have h_range : S.map f = LinearMap.range (f.domRestrict S) := by
      ext
      simp [Submodule.mem_map]
    rw [h_range, LinearMap.finrank_range_of_inj]
    · rw [Polynomial.finrank_degreeLT_n]
    · -- Injectivity proof
      rw [←LinearMap.ker_eq_bot]
      ext p
      simp only [LinearMap.mem_ker, LinearMap.domRestrict_apply, Submodule.mem_bot]
      constructor
      · intro hfp
        apply Subtype.ext
        apply Polynomial.eq_zero_of_natDegree_lt_card_of_eval_eq_zero' p.val (Finset.univ.map α)
        · intro x hx
          simp only [Finset.mem_map, Finset.mem_univ, true_and] at hx
          rcases hx with ⟨i, rfl⟩
          exact congr_fun hfp i
        · simp only [Finset.card_map]
          by_cases hn : n = 0
          · subst hn
            have h : ∀ i, p.val.coeff i = 0 := by
              intro i
              rcases p with ⟨p, hp⟩
              simp [S, Polynomial.degreeLT] at hp
              simp [hp i]
            have h : p.val.natDegree = 0 := by
              rw [Polynomial.natDegree_eq_zero_iff_degree_le_zero]
              rw [Polynomial.degree_le_zero_iff]
              ext n
              rw [h n]
              rcases n with _ | n <;> simp [h 0]
            rw [h]
            simp
            omega
          · calc p.val.natDegree < n
              := @natDegree_lt_of_mem_degreeLT _ _ _ _ (⟨hn⟩) p.2
                _ ≤ Fintype.card ι := h
      · intro hfp
        simp [hfp]

/-- The dimension of an RS-code equals the cardinality
  of the evaluation points if the original degree exceeds the cardinality. -/
lemma dim_eq_card_of_lt [Fintype ι] {α : ι ↪ F} (h : Fintype.card ι < n) :
  LinearCode.dim (ReedSolomon.code α n) = Fintype.card ι := by
  rw [LinearCode.dim]
  let f := ReedSolomon.evalOnPoints (F := F) α
  let S := Polynomial.degreeLT F n
  have h_code : ReedSolomon.code α n = S.map f := rfl
  rw [h_code]
  have h_range : S.map f = LinearMap.range (f.domRestrict S) := by
    ext
    simp [Submodule.mem_map]
  simp only [ModuleCode]
  apply le_antisymm
  · apply le_trans
    · apply Submodule.finrank_le
    · simp
  · have h_sub : ReedSolomon.code α (Fintype.card ι) ≤ ReedSolomon.code α n :=
      code_mono (le_of_lt h) α
    have h_sub := Submodule.finrank_mono h_sub
    have dim_eq := dim_eq_deg_of_le
      (n := Fintype.card ι)
      (α := α)
      (by simp)
    simp only [dim] at dim_eq
    rw [dim_eq] at h_sub
    exact h_sub

/-- Assumption-less expression for the dimension of an RS-code.
  The dimension equals the minimum of the degree and the cardinality
  of the evaluation set. -/
theorem dim_eq_min_deg_card {ι : Type*} [Fintype ι] {F : Type*} [Field F]
    {n : ℕ} {α : ι ↪ F} :
  LinearCode.dim (ReedSolomon.code α n) = min n (Fintype.card ι) := by
  by_cases hle : n ≤ Fintype.card ι <;>
    aesop
      (add simp [dim_eq_deg_of_le, dim_eq_card_of_lt])
      (add safe (by omega))

@[simp]
lemma length_eq_domain_card [Fintype ι] {deg : ℕ} {α : ι ↪ F} :
  length (ReedSolomon.code α deg) = Fintype.card ι := rfl

/- The usual formula for the rate of an RS-code: the degree divided by
  the cardinality of the evaluation set. -/
lemma rateOfLinearCode_eq_div [Fintype ι] {α : ι ↪ F} (h : n ≤ Fintype.card ι) :
  rate (ReedSolomon.code α n) = n / Fintype.card ι := by
  rw [rate, dim_eq_deg_of_le h, length_eq_domain_card]

/- Assumption-less formula for the rate of an RS-code: the minimun of degree
  and the cardinality of the evaluation set divided by the cardinality. -/
lemma rateOfLinearCode_eq_min_div [Fintype ι] {α : ι ↪ F} :
  rate (ReedSolomon.code α n) = (min n (Fintype.card ι)) / Fintype.card ι := by
  rw [rate, dim_eq_min_deg_card, length_eq_domain_card]

@[simp]
lemma dist_le_length [DecidableEq F] (inj : Function.Injective α) :
  minDist ((ReedSolomon.code ⟨α, inj⟩ n) : Set (Fin m → F)) ≤ m := by
  convert dist_UB
  simp

noncomputable abbrev sqrtRate [Fintype ι] (deg : ℕ) (domain : ι ↪ F) : ℝ≥0 :=
  (LinearCode.rate (ReedSolomon.code domain deg) : ℝ≥0).sqrt

@[simp]
lemma sqrtRate_nonneg [Fintype ι] (m : ℕ) (domain : ι ↪ F) :
  0 ≤ (sqrtRate m domain : ℝ) := (sqrtRate m domain).coe_nonneg

lemma sqrtRate_sq [Fintype ι] (m : ℕ) (domain : ι ↪ F) :
  (sqrtRate m domain : ℝ) ^ 2 =
    (min m (Fintype.card ι) : ℝ) / (Fintype.card ι : ℝ) := by
  rw [sqrtRate, ←NNReal.coe_pow, NNReal.sq_sqrt,
    ReedSolomon.rateOfLinearCode_eq_min_div]
  push_cast
  ring

lemma sqrtRate_pos [Fintype ι] [Nonempty ι] {m : ℕ}
  (hm : 0 < m) {domain : ι ↪ F} :
  0 < (sqrtRate m domain : ℝ) := by
  have hcard : 0 < Fintype.card ι := Fintype.card_pos
  have hsq : 0 < (sqrtRate m domain : ℝ) ^ 2 := by
    rw [sqrtRate_sq]
    have : 0 < min m (Fintype.card ι) := lt_min hm hcard
    positivity
  rcases (sqrtRate_nonneg m domain).lt_or_eq with h | h
  · exact h
  · rw [←h] at hsq
    simp at hsq

@[simp]
lemma sqrtRate_sq_le_one [Fintype ι] (m : ℕ) (domain : ι ↪ F) :
  (sqrtRate m domain : ℝ) ^ 2 ≤ 1 := by
  rw [sqrtRate_sq]
  rcases Nat.eq_zero_or_pos (Fintype.card ι) with h | h
  · simp [h]
  · rw [div_le_one (by exact_mod_cast h)]
    exact_mod_cast min_le_right _ _

@[simp high]
lemma sqrtRate_le_one [Fintype ι] (m : ℕ) (domain : ι ↪ F) :
  ReedSolomon.sqrtRate m domain ≤ 1 :=
  pow_le_one_iff_of_nonneg (sqrtRate_nonneg m domain) two_ne_zero |>.mp
    (sqrtRate_sq_le_one m domain)

@[simp high]
lemma sqrtRate_le_one' [Fintype ι] (m : ℕ) (domain : ι ↪ F) :
  (ReedSolomon.sqrtRate m domain : ℝ) ≤ 1 := by
  norm_cast
  simp

end

lemma card_le_card_of_count_inj {α β : Type*} [DecidableEq α] [DecidableEq β]
    {s : Multiset α} {s' : Multiset β}
  {f : α → β} (inj : Function.Injective f) (h : ∀ a : α, s.count a ≤ s'.count (f a)) :
  s.card ≤ s'.card := by
    classical
    simp only [←Multiset.toFinset_sum_count_eq]
    apply le_trans (b := ∑ x ∈ s.toFinset, s'.count (f x)) (Finset.sum_le_sum (by aesop))
    rw [←Finset.sum_image (f := s'.count) (by aesop (add simp [Set.InjOn]))]
    have : s.toFinset.image f ⊆ s'.toFinset :=
      suffices ∀ x ∈ s, f x ∈ s' by simpa [Finset.image_subset_iff]
      by simp_rw [←Multiset.count_pos]
         exact fun x h' ↦ lt_of_lt_of_le h' (h x)
    exact Finset.sum_le_sum_of_subset_of_nonneg this (by aesop)

section

def constantCode {α : Type*} (x : α) (ι' : Type*) [Fintype ι'] : ι' → α := fun _ ↦ x

variable [Semiring F] {x : F} [Fintype ι] {α : ι ↪ F}

@[simp]
lemma weight_constantCode [DecidableEq F] :
    wt (constantCode x ι) = 0 ↔ IsEmpty ι ∨ x = 0 := by
  by_cases eq : IsEmpty ι <;> aesop (add simp [constantCode, wt_eq_zero_iff])

@[simp]
lemma constantCode_mem_code [NeZero n] :
  constantCode x ι ∈ ReedSolomon.code α n :=
  ⟨C x, by aesop (add simp [ReedSolomon.evalOnPoints, coeff_C, degreeLT])⟩

@[simp]
lemma constantCode_eq_ofNat_zero_iff [Nonempty ι] :
  constantCode x ι = 0 ↔ x = 0 := by
  unfold constantCode
  exact ⟨fun x ↦ Eq.mp (by simp) (congrFun x), (· ▸ rfl)⟩

@[simp]
lemma wt_constantCode [DecidableEq F] [NeZero x] :
  wt (constantCode x ι) = Fintype.card ι := by aesop (add simp [constantCode, wt])

end

theorem minDist_of_le [Fintype ι] [Field F] [DecidableEq F]
  {α : ι ↪ F} [nz : NeZero n] (h : n ≤ Fintype.card ι) :
  Code.minDist (ReedSolomon.code α n : Set (ι → F)) = Fintype.card ι - n + 1 := by
  classical
  have := nz.out
  have : 0 < Fintype.card ι := by omega
  haveI : Nonempty ι := by aesop (add safe (by rw [←Fintype.card_pos_iff]))
  apply le_antisymm
  · have distUB := singletonBound (LC := ReedSolomon.code α n)
    have h_le_len : Code.minDist ((ReedSolomon.code α n) : Set (ι → F)) ≤ Fintype.card ι := dist_UB
    aesop
      (add safe (by grind))
      (add simp [LinearCode.length, dim_eq_deg_of_le])
  · rw [dist_eq_minWtCodewords]
    apply le_csInf (by use Fintype.card ι, constantCode 1 ι; simp)
    intro b ⟨msg, ⟨p, p_deg, p_eval_on_α_eq_msg⟩, msg_neq_0, wt_c_eq_b⟩
    let zeroes : Finset _ := {i | msg i = 0}
    have eq₁ : zeroes.val.Nodup := by
      simp only [Finset.filter_val, zeroes]
      refine Multiset.Nodup.filter (fun i ↦ msg i = 0) ?_
      exact Finset.univ.nodup
    have msg_zeros_lt_deg : zeroes.card < n := by
      apply lt_of_le_of_lt (b := p.roots.card)
                           (hbc := lt_of_le_of_lt (Polynomial.card_roots' _)
                                                  (natDegree_lt_of_mem_degreeLT p_deg))
      exact card_le_card_of_count_inj α.injective fun i ↦
        if h : msg i = 0
        then suffices 0 < Multiset.count (α i) p.roots by
                rwa [@Multiset.count_eq_one_of_mem (d := eq₁) (h := by simpa [zeroes])]
              by aesop
        else by simp [zeroes, h]
    have : zeroes.card + wt msg = Fintype.card ι := by
      aesop (add simp [wt, Finset.card_filter_add_card_filter_not])
    omega

@[simp]
theorem code_Nontrivial [Field F] [nz : NeZero n] [Inhabited ι] {α : ι ↪ F} :
  (ReedSolomon.code α n : Set (ι → F)).Nontrivial := by
  have hn : n ≠ 0 := nz.out
  have hn : 1 ≤ n := by omega
  simp only [Set.Nontrivial, SetLike.mem_coe, ne_eq]
  have h1 : evalOnPoints α 1 ∈ code α n :=
    evalOnPoints_mem_code_of_natDegree_lt (by aesop)
  exists (evalOnPoints α 0)
  simp only [map_zero, zero_mem, true_and]
  exists (evalOnPoints α 1)
  simp only [h1, true_and]
  intro contra
  have := congrFun contra default
  simp [evalOnPoints] at this

@[simp]
theorem minDist_n_0 [Fintype ι] [Field F] [DecidableEq F] {α : ι ↪ F} :
  minDist (ReedSolomon.code α 0 : Set (ι → F)) = 0 := by simp [minDist]

theorem minDist_eq_card_sub_min_add_1 [Fintype ι] [Inhabited ι] [Field F] [DecidableEq F]
  {α : ι ↪ F} [nz : NeZero n] :
  minDist (ReedSolomon.code α n : Set (ι → F)) = Fintype.card ι - min n (Fintype.card ι) + 1 := by
  classical
  by_cases hle : n ≤ Fintype.card ι
  · simp [hle, minDist_of_le hle]
  · simp only [not_le] at hle
    rw [min_eq_right (by grind)]
    simp
    have hmin : 0 < minDist (ReedSolomon.code α n : Set (ι → F)) := by
      have := dist_pos_of_Nontrivial (ReedSolomon.code α n : Set (ι → F)) (by simp)
      rw [dist_eq_minDist] at this
      exact this
    have hle : minDist (ReedSolomon.code α n : Set (ι → F)) ≤ 1 := by
      simp [minDist]
      exact csInf_le (by simp) <| by
        simp only [Set.mem_setOf_eq]
        let u : ι → F := fun i ↦ if i = default then 1 else 0
        exists u
        constructor
        · rw [mem_code_iff_exists_polynomial]
          exists (Lagrange.interpolate Finset.univ α u)
          constructor
          · exact lt_trans (Lagrange.degree_interpolate_lt _ (by cases α; aesop)) (by simp [hle])
          · cases α
            aesop
              (erase simp Lagrange.interpolate_apply)
              (add simp [evalOnPoints, Lagrange.eval_interpolate_at_node])
        · exists 0
          simp only [zero_mem, hammingDist_zero_right, hammingNorm, ne_eq, ite_eq_right_iff,
            one_ne_zero, imp_false, Decidable.not_not, true_and, u]
          constructor
          · intro contra
            have := congrFun contra default
            simp at this
          · rw [show 1 = Finset.card ({default} : Finset ι) by simp]
            congr
            ext a
            aesop
    omega

/-- Two distinct Reed–Solomon codewords of degree `< m` agree in fewer than `m` positions. -/
lemma agree_lt_of_mem_code {F : Type*} [Fintype ι] [Field F] [DecidableEq F]
  {α : ι ↪ F} {n : ℕ} {c c' : ι → F}
  (hc : c ∈ ReedSolomon.code α n) (hc' : c' ∈ ReedSolomon.code α n) (hne : c ≠ c') :
  Code.agree c c' < n := by
  by_cases hn : n = 0
  · aesop
  · by_cases hcard : Fintype.card ι = 0
    · exfalso
      exact hne <| funext <| fun i ↦ by
        rw [Fintype.card_eq_zero_iff, isEmpty_iff] at hcard
        simpa using hcard i
    · have : NeZero n := ⟨hn⟩
      have : Inhabited ι := ⟨Classical.choice <| by
        aesop (add safe [(by rw [←Fintype.card_pos_iff]), (by omega)])⟩
      have := minDist_eq_card_sub_min_add_1 (n := n) (α := α)
      have := minDist_le_dist hc hc' hne
      have := Code.agree_add_hammingDist (u := c) (v := c')
      by_cases! hn : n ≤ Fintype.card ι <;> grind

/-- Reed-Solomon codes are maximum distance separable (MDS). -/
lemma isMDS_code {ι : Type*} [Fintype ι] [Inhabited ι] [Field F] [DecidableEq F]
  {α : ι ↪ F} [NeZero n] : LinearCode.IsMDS (ReedSolomon.code α n) := by
  simp only [IsMDS, Submodule.carrier_eq_coe, length_eq_domain_card]
  rw [dist_eq_minDist, minDist_eq_card_sub_min_add_1, dim_eq_min_deg_card]

/-- Distance equality for RS code with arbitrary finite index type `ι`. -/
theorem dist_eq_of_le [Fintype ι] {α : ι ↪ F}
    [Field F] [DecidableEq F] [NeZero n] (h : n ≤ Fintype.card ι) :
  dist ((ReedSolomon.code α n) : Set (ι → F)) = Fintype.card ι - n + 1 := by
  aesop (add simp [dist_eq_minDist, ReedSolomon.minDist_of_le])

/-- Distance equality for RS code with arbitrary finite index type `ι`. -/
theorem dist_eq [Fintype ι] [Inhabited ι] {α : ι ↪ F}
    [Field F] [DecidableEq F] [NeZero n] :
  dist ((ReedSolomon.code α n) : Set (ι → F)) = Fintype.card ι - min n (Fintype.card ι) + 1 := by
  aesop (add simp [dist_eq_minDist, ReedSolomon.minDist_eq_card_sub_min_add_1])

/-- Unique decoding radius for RS code with arbitrary finite index type `ι`. -/
theorem uniqueDecodingRadius_RS_eq [Fintype ι]
  {α : ι ↪ F} [Field F] [DecidableEq F] [NeZero n]
  (h : n ≤ Fintype.card ι) :
  Code.uniqueDecodingRadius (ι := ι) (F := F) (C := ReedSolomon.code α n) =
    (Fintype.card ι - n) / 2 := by
  simp_all only [uniqueDecodingRadius, dist_eq_minDist, minDist_of_le, add_tsub_cancel_right]

open NNReal in
/-- Relative unique decoding radius for RS code with arbitrary finite index type `ι`. -/
theorem relativeUniqueDecodingRadius_RS_eq [Fintype ι]
  {α : ι ↪ F} [Field F] [DecidableEq F] [NeZero n]
  (h : n ≤ Fintype.card ι) :
  Code.relativeUniqueDecodingRadius (ι := ι) (F := F) (C := ReedSolomon.code α n) =
    ((1 : ℝ≥0) - n / Fintype.card ι) / 2 := by
  have h_card_ne_zero: Fintype.card ι ≠ 0 := by
    by_contra h_card_eq_zero
    have h_n_eq_0 : n = 0 := by omega
    have h_n_ne_0 : n ≠ 0 := by exact Ne.symm (NeZero.ne' n)
    exact h_n_ne_0 h_n_eq_0
  rw [Code.relativeUniqueDecodingRadius, ReedSolomon.dist_eq_of_le h]
  simp only [Nat.cast_add, Nat.cast_tsub, Nat.cast_one, add_tsub_cancel_right]
  conv_lhs =>
    rw [NNReal.sub_div, NNReal.sub_div, div_div, mul_comm, ←div_div]
    rw [div_self (Nat.cast_ne_zero.mpr h_card_ne_zero)]
  conv_rhs => rw [NNReal.sub_div, div_div, mul_comm, ←div_div]

end

noncomputable scoped instance  _root_.ReedSolomon.instFintypeElemOfFinite_arkLib {α : Type} (s : Set α) [inst : Finite s] : Fintype s
    := Fintype.ofFinite _

open NNReal Finset Function Finset in
noncomputable def finCarrier {ι : Type} [Fintype ι]
               {F : Type} [Field F] [Fintype F]
               (domain : ι ↪ F) (deg : ℕ) : Finset (ι → F) :=
  (ReedSolomon.code domain deg).carrier.toFinset

section

open LinearMap Finset Polynomial

variable {F : Type*} [Field F]
         {ι : Type*} [Fintype ι] [DecidableEq ι]
         {domain : ι ↪ F}
         {deg : ℕ}

/-- The linear map that maps a codeword `f : ι → F` to a degree < |ι| polynomial p,
such that `p(x) = f(x)` for all `x ∈ ι`. -/
public noncomputable def interpolate : (ι → F) →ₗ[F] F[X] :=
  Lagrange.interpolate univ domain

/-- The linear map that maps a Reed-Solomon codeword to its associated polynomial. -/
noncomputable def toPolynomial : (ReedSolomon.code domain deg) →ₗ[F] F[X] :=
  domRestrict
    (interpolate (domain := domain))
    (ReedSolomon.code domain deg)

lemma toPolynomial_def {f : ReedSolomon.code domain deg} :
  toPolynomial f = Lagrange.interpolate univ domain f := rfl

/-- The polynomials corresponding to Reed-Solomon codewords are of degree smaller than `deg`. -/
lemma toPolynomial_mem_lt_deg (c : ReedSolomon.code domain deg) :
  toPolynomial c ∈ (degreeLT F deg : Submodule F F[X]) := by
  -- Unpack the witness polynomial for this codeword
  rcases c.property with ⟨p, hp_deg, hp_eval⟩
  -- Two cases depending on comparison between `deg` and `|ι|`
  by_cases hle : deg ≤ Fintype.card ι
  · -- In this case, `p` has degree < |ι|,
    -- hence uniqueness of interpolation gives `toPolynomial c = p`.
    have hp_lt_card : p.degree < (Fintype.card ι : WithBot ℕ) :=
      lt_of_lt_of_le (Polynomial.mem_degreeLT.mp hp_deg) (by exact_mod_cast hle)
    -- Interpolants of equal data are equal
    have hinterp_eq_vals :
      (interpolate (domain := domain)) c =
      Lagrange.interpolate (Finset.univ : Finset ι) domain (fun i => p.eval (domain i)) := by
      refine (Lagrange.interpolate_eq_of_values_eq_on (s := Finset.univ)
                (v := domain) (r := (c : ι → F))
                (r' := fun i => p.eval (domain i))) ?_
      intro i _
      -- From codeword property: evaluations agree on all points
      exact congrArg (fun f => f i) hp_eval.symm
    -- A polynomial of degree < |ι| equals its Lagrange interpolant on `univ`
    have hp_eq_interp :
      p = Lagrange.interpolate (Finset.univ : Finset ι) domain (fun i => p.eval (domain i)) :=
        Lagrange.eq_interpolate (s := Finset.univ) (v := domain) (f := p)
          (by intro x _ y _ hxy; exact domain.injective hxy) hp_lt_card
    -- Chain equalities to get `toPolynomial c = p`
    have htoPolynomial_eq : toPolynomial c = p := by
      -- `hinterp_eq_vals` gives: interpolate _ c = interpolate _ (eval p ∘ domain)
      -- `hp_eq_interp` gives: p = interpolate _ (eval p ∘ domain)
      -- Hence, toPolynomial c = p
      have : (interpolate (domain := domain)) c = p :=
        hinterp_eq_vals.trans hp_eq_interp.symm
      simpa [toPolynomial, interpolate] using this
    -- Conclude degree bound from membership of `p` in `degreeLT F deg`.
    simpa [htoPolynomial_eq, Polynomial.mem_degreeLT] using hp_deg
  · -- Otherwise, `deg > |ι|`, and interpolation has degree < |ι| ≤ deg
    have hdeg_lt_card : (toPolynomial c).degree < (Fintype.card ι : WithBot ℕ) := by
      -- Degree bound for Lagrange interpolation over `univ`
      have := Lagrange.degree_interpolate_lt (s := Finset.univ) (v := domain)
        (r := (c : ι → F)) (by intro x _ y _ hxy; exact domain.injective hxy)
      simpa [toPolynomial, interpolate] using this
    have hcard_le_deg : (Fintype.card ι : WithBot ℕ) ≤ deg := by
      have hlt : Fintype.card ι < deg := Nat.lt_of_not_ge hle
      exact le_of_lt (by exact_mod_cast hlt)
    have : (toPolynomial c).degree < deg := lt_of_lt_of_le hdeg_lt_card hcard_le_deg
    simpa [Polynomial.mem_degreeLT] using this

@[simp]
lemma toPolynomial_lt_deg (c : ReedSolomon.code domain deg) :
  (toPolynomial c).degree < deg := by
  have := toPolynomial_mem_lt_deg c
  aesop
    (add simp [degreeLT, Polynomial.degree_lt_iff_coeff_zero])

@[simp]
lemma toPolynomial_lt_min_deg_card (c : ReedSolomon.code domain deg) :
  (toPolynomial c).degree < min deg (Fintype.card ι) := by
  by_cases h0 : toPolynomial c = 0
  · simp [h0]
  · rw [←Polynomial.natDegree_lt_iff_degree_lt h0, lt_min_iff]
    constructor
    · aesop (add simp [Polynomial.natDegree_lt_iff_degree_lt])
    · rw [Polynomial.natDegree_lt_iff_degree_lt h0, toPolynomial_def]
      exact lt_of_lt_of_le (Lagrange.degree_interpolate_lt _
        (by aesop (add safe cases Function.Embedding))) (by simp)

lemma toPolynomial_evalWord_of_degree_lt
  {p : F[X]} (hp_deg : p.degree < deg) (hdeg : deg ≤ Fintype.card ι)
  {hcode : evalOnPoints domain p ∈ ReedSolomon.code domain deg} :
  toPolynomial ⟨evalOnPoints domain p, hcode⟩ = p := by
  classical
  rcases domain with ⟨domain, hdomain_inj⟩
  apply Polynomial.eq_of_degrees_lt_of_eval_index_eq (v := domain) (s := univ)
  · simp_all
  · exact Lagrange.degree_interpolate_lt _ (by simp_all)
  · exact lt_of_lt_of_le hp_deg (by simp [hdeg])
  · aesop
      (add safe cases Function.Embedding)
      (erase simp Lagrange.interpolate_apply)
      (add simp [Lagrange.eval_interpolate_at_node, toPolynomial_def])

lemma toPolynomial_eval_at_domain
  {c : ReedSolomon.code domain deg} {i : ι} :
  (toPolynomial c).eval (domain i) = c.1 i := by
  aesop
    (erase simp Lagrange.interpolate_apply)
    (add simp [toPolynomial_def, Lagrange.eval_interpolate_at_node])
    (add safe cases Function.Embedding)

set_option linter.unusedDecidableInType false in -- false alarm
lemma mem_code_iff_exists_polynomial' {n : ℕ} {α : ι ↪ F} {f : ι → F} :
  f ∈ code α n ↔
    ∃ p : Polynomial F, p.degree < min n (Fintype.card ι) ∧
      f = evalOnPoints α p := by
  constructor
  · intro h
    by_cases hd : n ≤ Fintype.card ι
    · aesop
        (add simp [mem_code_iff_exists_polynomial])
    · exists (toPolynomial ⟨f, h⟩)
      aesop (add simp [evalOnPoints, toPolynomial_eval_at_domain])
  · by_cases hd : n ≤ Fintype.card ι
    · aesop
        (add simp [mem_code_iff_exists_polynomial])
    · rintro ⟨p, hp₁, hp₂⟩
      rw [mem_code_iff_exists_polynomial]
      have : p.degree < n := lt_trans hp₁ (by simpa using hd)
      aesop

/-- The linear map that maps a Reed-Solomon codeword to its associated polynomial of degree less
than `deg`. -/
noncomputable def toPolynomialLT :
  (ReedSolomon.code domain deg) →ₗ[F] (Polynomial.degreeLT F deg) :=
  codRestrict
    (Polynomial.degreeLT F deg)
    toPolynomial
    toPolynomial_mem_lt_deg

open LinearMvExtension

variable {F : Type*} [Semiring F] [DecidableEq F]
         {ι : Type*} [Fintype ι]

/-- A domain `ι ↪ F` is `smooth`, if `ι ⊆ F`, `|ι| = 2^k` for some `k` and there exists a subgroup
 `H` in the group of units `Rˣ` and an invertible element `a ∈ R` such that `ι = a • H` -/
class Smooth
  (domain : ι ↪ F) where
    H : Subgroup (Units F)
    a           : Units F
    h_coset     : Finset.image domain Finset.univ
                  = (fun h : Units F => (a : F) * (h : F)) '' (H : Set (Units F))
    h_card_pow2 : ∃ k : ℕ, Fintype.card ι = 2 ^ k

variable {F : Type*} [Field F] [DecidableEq F]
        {ι : Type*} [Fintype ι] [DecidableEq ι]
        {domain : ι ↪ F} [Smooth domain]
        {m : ℕ}

/-- Definition 4.2, WHIR[ACFY24]
Smooth Reed-Solomon codes are Reed-Solomon codes defined over smooth domains, such that their
decoded univariate polynomials are of degree less than `2ᵐ` for some `m ∈ ℕ`. -/
noncomputable def smoothCode
    (domain : ι ↪ F) [Smooth domain]
  (m : ℕ) : Submodule F (ι → F) := ReedSolomon.code domain (2^m)

/-- The linear map that maps smooth Reed-Solomon Code words to their corresponding degreewise linear
`m`-variate polynomial. -/
noncomputable def mVdecode :
  (smoothCode domain m) →ₗ[F] MvPolynomial (Fin m) F :=
    linearMvExtensionLMap.comp toPolynomialLT

/-- Auxiliary function to assign values to the weight polynomial variables: index `0` ↦ `p.eval b`,
index `j+1` ↦ `b j`. -/
private noncomputable def toWeightAssignment
  (p : MvPolynomial (Fin m) F)
  (b : Fin m → Fin 2) : Fin (m+1) → F :=
    let b' : Fin m → F := fun i => ↑(b i : ℕ)
    Fin.cases (MvPolynomial.eval b' p)
              (fun i => ↑(b i : ℕ))

/-- Constraint is true, if `∑ {b ∈ {0,1}^m} w(f(b),b) = σ` for given `m`-variate polynomial `f` and
`(m+1)`-variate polynomial `w`. -/
def weightConstraint
    (f : MvPolynomial (Fin m) F)
  (w : MvPolynomial (Fin (m + 1)) F) (σ : F) : Prop :=
    ∑ b : Fin m → Fin 2 , w.eval (toWeightAssignment f b) = σ

/-- Definition 4.5, WHIR[ACFY24]
Constrained Reed-Solomon codes are smooth codes whose decoded `m`-variate polynomial satisfies the
weight constraint for given `w` and `σ`.
-/
def constrainedCode
    (domain : ι ↪ F) [Smooth domain] (m : ℕ)
  (w : MvPolynomial (Fin (m + 1)) F) (σ : F) : Set (ι → F) :=
    { f | ∃ (h : f ∈ smoothCode domain m),
      weightConstraint (mVdecode (⟨f, h⟩ : smoothCode domain m)) w σ }

/-- Definition 4.6, WHIR[ACFY24]
Multi-constrained Reed-Solomon codes are smooth codes whose decoded `m`-variate polynomial satisfies
the `t` weight constraints for given `w₀,..., wₜ₋₁` and `σ₀,..., σₜ₋₁`. -/
def multiConstrainedCode
    (domain : ι ↪ F) [Smooth domain] (m t : ℕ)
  (w : Fin t → MvPolynomial (Fin (m + 1)) F)
  (σ : Fin t → F) : Set (ι → F) :=
    { f |
      ∃ (h : f ∈ smoothCode domain m),
        ∀ i : Fin t, weightConstraint (mVdecode (⟨f, h⟩ : smoothCode domain m)) (w i) (σ i)}

end
end ReedSolomon


Source
https://github.com/Verified-zkEVM/ArkLib/blob/e65197892890b8fd9b0dc05b8980273cf1d595cc/ArkLib/Data/CodingTheory/ReedSolomon.lean yukon-proof-operation:05c47e57106ce3b1ae31e5b953056d7886891f0c13a36f49c11a24189d019736 [yukon-proof-receipt:eyJ2IjoxLCJtYXJrZXIiOiJ5dWtvbi1wcm9vZi1vcGVyYXRpb246MDVjNDdlNTcxMDZjZTNiMWFlMzFlNWI5NTMwNTZkNzg4Njg5MWYwYzEzYTM2ZjQ5YzExYTI0MTg5ZDAxOTczNiIsImhhc2giOiJmYmJmMGNmYzYzNGNjNmE1MzhkOTQ5ZDAyNDE2ZjhiNDQ3ZTdlZWMyYjRiZWNhOGVkYjdkNmQ5MzQ4YjdlOWExIiwia2luZCI6ImRlZmluaXRpb24iLCJ0YXJnZXQiOiJZdWtvbl9lOWVlN2MwZTg4MzA3YjhhY2FjMzI2MGUiLCJlbnZpcm9ubWVudCI6eyJtYXRobGliUmV2IjoiMGRmNDQ0YTM2MGVhYTYwYWI4YzExZGNhNTFhODZhZjY5Mjk1NTQ3NCIsInRvb2xjaGFpbiI6ImxlYW5wcm92ZXIvbGVhbjQ6djQuMzMuMSJ9LCJ0YWciOiJiZXR0ZXItY29kZXMifQ]

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