AFTD Auto-Formalizing Theoretical Domains

zero_mem_full_reed_solomon_code

theoremverified

For any commutative ring $F$ and natural number $k$, the constant zero function is a codeword in the full-length Reed-Solomon code of dimension $k$ over $F$.

Statement

theorem zero_mem_full_reed_solomon_code (F : Type*) [CommRing F] (k : ℕ) :
    (fun _ : F => (0 : F)) ∈ full_reed_solomon_code F k
Source
arXiv:2611.07607
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • full_reed_solomon_codeThe full-length Reed-Solomon code of dimension $k$ over a commutative ring $F$ is the set of functions from $F$ to $F$ obtained by…

Read back from the Lean

For any commutative ring $F$ and any natural number $k$, the constant zero function $(F \to F)$ mapping every element to $0$ is an element of full_reed_solomon_code F k.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The full-length Reed-Solomon code consists of all evaluation vectors of polynomials of degree strictly less than $k$. The all-zero word is shown to belong to the code by taking the zero polynomial as witness: its degree is $-\infty$ (the bottom element $\bot$), which is strictly less than $k$, and it evaluates to zero at every point of the field.

  1. To show that the all-zero word is in the code, it suffices to find a polynomial $P$ of degree strictly less than $k$ that evaluates to $0$ everywhere.

    We unfold the definition of `full_reed_solomon_code`, which reduces the goal to proving that there exists a polynomial $P$ such that $\deg P < k$ and the evaluation map $x \mapsto P(x)$ is identically zero.

    line 4

      dsimp [full_reed_solomon_code]
  2. The zero polynomial $0$ is of degree less than $k$ and evaluates to zero at every point.

    We choose the zero polynomial $P = 0$. By `Polynomial.degree_zero`, its degree is $\bot$, which is strictly less than $k$ by `WithBot.bot_lt_coe`. Finally, evaluating the zero polynomial at any field element gives $0$, which simplifies the remaining goal.

    line 5

    uses Polynomial.degree_zero, WithBot.bot_lt_coe

      exact ⟨0, by rw [Polynomial.degree_zero]; exact WithBot.bot_lt_coe k, by simp⟩
Polynomial.degree_zero
The degree of the zero polynomial is $\bot$ (representing $-\infty$).
WithBot.bot_lt_coe
The bottom element $\bot$ in an adjoined-bottom type is strictly less than any coerced element from the underlying type (in particular, $\bot < \uparrow k$ for any natural number $k$).

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 all-zero word is in the full-length Reed-Solomon code of any dimension. -/theorem zero_mem_full_reed_solomon_code (F : Type*) [CommRing F] (k : ℕ) :    (fun _ : F => (0 : F)) ∈ full_reed_solomon_code F k := by  dsimp [full_reed_solomon_code]  exact ⟨0, by rw [Polynomial.degree_zero]; exact WithBot.bot_lt_coe k, by simp⟩
See it in the graphDiscuss this resultChallenge it