The Reed–Solomon code
DefinitionTwoFoldOPI_Supplement_rsCodecoding-theoryoptimal-polynomial-intersectionp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithmsregev-reductionschur-product-codes
For a finite field , an element and ,
With a generator of this is the code of Definition 11.1 and of Definition 12.1.
Formalization Note Coordinate is the evaluation at . Statements require to have order .
Definition code
import Mathlib
namespace TwoFoldOPI
namespace Supplement
/-- **The Reed–Solomon code `RS_{F_q,γ,k}`.**
Ragavan, Shutty, *Quantum Algorithms for OPI Variants Beyond Locality and Classical
Decodability*, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §5.1, Definition 5.3, p.21: "Let F_q be a field, k ∈ [1, q − 1] an integer, γ a generator
of F_q^*, and v ∈ F_q^{q−1} some vector of nonzero elements. Then the generalized Reed–Solomon
code GRS_{F_q,γ,k,v} is defined as: {(v_1 f(γ), v_2 f(γ^2), …, v_{q−1} f(γ^{q−1})) : f ∈ F_q[X],
deg f ≤ k − 1}. … When v is the all 1's vector, we simply refer to this as the Reed–Solomon code
RS_{F_q,γ,k}."
`rsCode γ k = {(f(γ^1), f(γ^2), …, f(γ^{q−1})) : deg f ≤ k − 1} ⊆ K^{q−1}`, `q = |K|`; coordinate
`j ∈ {0, …, q−2}` is the evaluation at `γ^{j+1}`.
**Formalization Note.** `deg f ≤ k − 1` is `f ∈ K[X]_{<k}` (`Polynomial.degreeLT K k`). The code is
the image of that space under the evaluation map, so it is `K`-linear. Statements supply `γ` with
`orderOf γ = q − 1` (a generator of `K^*`). -/
noncomputable def rsCode {K : Type*} [Field K] [Fintype K] (γ : K) (k : ℕ) :
Submodule K (Fin (Fintype.card K - 1) → K) :=
(Polynomial.degreeLT K k).map
(LinearMap.pi fun j : Fin (Fintype.card K - 1) => Polynomial.leval (γ ^ (j.val + 1)))
end Supplement
end TwoFoldOPI
Source
Ragavan, Shutty, Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §5.1, Definition 5.3, p. 21