The Schur product code
DefinitionTwoFoldOPI_Supplement_schurTriplecoding-theoryoptimal-polynomial-intersectionp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithmsregev-reductionschur-product-codes
For codes , is the linear span of all coordinate-wise products with and .
Orthogonality of to this code is an input condition of Algorithm 8.1.
Formalization Note By bilinearity, the span of triple products equals of Definition 5.23.
Definition code
import Mathlib
namespace TwoFoldOPI
namespace Supplement
/-- **The Schur product code `V ∗ E^{∗2}`.**
Ragavan, Shutty, *Quantum Algorithms for OPI Variants Beyond Locality and Classical
Decodability*, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §5.1, Definition 5.23, p.26: "For codes C_1, …, C_k ⊆ F_q^M, let C_1 ∗ ⋯ ∗ C_k ⊆ F_q^M denote
the linear subspace spanned by the coordinate-wise products c_1 ⊙ ⋯ ⊙ c_k with c_j ∈ C_j for every
j. When C_1 = ⋯ = C_k = C, we write C^{∗k}"; Algorithm 8.1, p.45 ("h ⊥ V ∗ E^{∗2}").
`schurTriple V E` is the span of all coordinate-wise products `u ⊙ e ⊙ e'` with `u ∈ V`,
`e, e' ∈ E`, i.e. `V ∗ E ∗ E = V ∗ E^{∗2}`.
**Formalization Note.** `V ∗ E^{∗2}` is the span of `u ⊙ x` with `x` in the span of products
`e ⊙ e'`; by bilinearity it equals the span of the triple products used here. -/
def schurTriple {K : Type*} [Field K] {m : ℕ} (V E : Submodule K (Fin m → K)) :
Submodule K (Fin m → K) :=
Submodule.span K {x | ∃ u ∈ V, ∃ e ∈ E, ∃ e' ∈ E, x = u * e * e'}
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.23, p. 26; §8.1, Algorithm 8.1, p. 45