The consecutive partition of of Definition 11.2
DefinitionTwoFoldOPI_Supplement_canonicalPartitioncoding-theoryoptimal-polynomial-intersectionp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithmsregev-reductionschur-product-codes
Given weights , the partition of of Definition 11.2 puts the first symbols in , the next in , and so on up to ; holds the remaining symbols. This definition returns the class of each symbol.
It is the partition of the oracle instances (Theorems 11.3, 11.9).
Formalization Note Symbols and classes are -based: class (the paper's ) is the interval with , and the last class takes the rest.
Definition code
import Mathlib
namespace TwoFoldOPI
namespace Supplement
/-- **The partition of `[n]` into consecutive classes `S_1, …, S_R` of Definition 11.2.**
Ragavan, Shutty, *Quantum Algorithms for OPI Variants Beyond Locality and Classical
Decodability*, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §11, Definition 11.2, p.57: "define S_1 to consist of the first ⌊α_1 n⌋ elements of [n],
S_2 the next ⌊α_2 n⌋ elements, and so on until S_{R−1}, and then let S_R consist of the remaining
elements of [n]."
`canonicalPartition α n a` is the class of the symbol `a ∈ [n] = {0, …, n−1}`: with
`c_r = ⌊α_0 n⌋ + ⋯ + ⌊α_r n⌋`, symbol `a` is in class `#{r < R − 1 : c_r ≤ a}` (0-based), so class
`r < R − 1` is `[c_{r−1}, c_r)` and class `R − 1` holds the rest.
**Formalization Note.** Classes are 0-based (`Fin R`: the paper's `S_{r+1}` is class `r`); `R ≥ 1`
(`NeZero R`). The `min` with `R − 1` only makes the value a `Fin R` and never binds. -/
noncomputable def canonicalPartition {R : ℕ} [NeZero R] (α : Fin R → ℝ) (n : ℕ) (a : Fin n) :
Fin R :=
⟨min (Finset.univ.filter fun r : Fin R =>
r.val + 1 < R ∧ ∑ r' ∈ Finset.univ.filter (fun r' : Fin R => r' ≤ r), ⌊α r' * n⌋₊ ≤ a.val).card
(R - 1), by have := NeZero.pos R; omega⟩
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), §11, Definition 11.2, p. 57