The reduced-monomial count
DefinitionTwoFoldOPI_Supplement_rmCountcoding-theoryoptimal-polynomial-intersectionp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithmsregev-reductionschur-product-codes
For integers , and ,
It is the dimension of the Reed–Muller code and the number of rows of the matrix in .
Formalization Note The threshold is a natural number; the paper's real threshold enters only as .
Definition code
import Mathlib
namespace TwoFoldOPI
namespace Supplement
/-- **The reduced-monomial count `Count_q(v, r)`.**
Ragavan, Shutty, *Quantum Algorithms for OPI Variants Beyond Locality and Classical
Decodability*, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §5.1, Definition 5.10, p.22: "For integers q ≥ 2, v ≥ 1, and a real threshold r ≥ 0,
define Count_q(v, r) := #{α ∈ {0, …, q − 1}^v : ‖α‖_1 ≤ r}. Thus Count_q(v, r) = Count_q(v, ⌊r⌋)."
`rmCount q v r` is the number of exponent vectors `α ∈ {0, …, q−1}^v` with `α_1 + ⋯ + α_v ≤ r`.
**Formalization Note.** The threshold is a natural number; the paper's real threshold enters only
through `Count_q(v, ⌊ρv⌋)` (Definition 6.1), which statements write with `⌊ρv⌋₊`. -/
def rmCount (q v r : ℕ) : ℕ :=
(Finset.univ.filter fun α : Fin v → Fin q => ∑ i, (α i : ℕ) ≤ r).card
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.10, p. 22