Tail thresholds and the weighted tail threshold
DefinitionTwoFoldOPI_Supplement_tailThresholdcoding-theoryoptimal-polynomial-intersectionp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithmsregev-reductionschur-product-codes
For a set the tail threshold is
with if no such exists. For load data with weights the weighted tail threshold is .
The weighted tail threshold bounds the rates for which classical provers fail (Theorems 11.9, 11.10).
Formalization Note and ; one infinite with makes .
Definition code
import Mathlib
namespace TwoFoldOPI
namespace Supplement
open Classical in
/-- **Tail thresholds `τ_r` and the weighted tail threshold `τ`.**
Ragavan, Shutty, *Quantum Algorithms for OPI Variants Beyond Locality and Classical
Decodability*, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §11.2, Definition 11.5, p.59: "For load data B_1, …, B_R and α_1, …, α_R, the tail
threshold of B_r is τ_r := min{t ∈ Z_{≥0} : {t, t + 1, …} ⊆ B_r}, with τ_r = ∞ if the set on the
right is empty. The weighted tail threshold is τ = Σ_{r∈[R]} α_r τ_r ∈ [0, ∞]."
`tailThreshold B` is the least `t` with `{t, t+1, …} ⊆ B`, or `⊤ = ∞` if there is none.
**Formalization Note.** `τ_r ∈ ℕ∞`; the weighted threshold `weightedTail` is computed in
`[0, ∞] = ℝ≥0∞` with weights `α_r` (positive in every use), so one infinite `τ_r` makes `τ = ∞`. -/
noncomputable def tailThreshold (B : Set ℕ) : ℕ∞ :=
if h : ∃ t : ℕ, ∀ k : ℕ, t ≤ k → k ∈ B then (Nat.find h : ℕ∞) else ⊤
/-- The weighted tail threshold `τ = Σ_r α_r τ_r ∈ [0, ∞]` (Definition 11.5, p.59). -/
noncomputable def weightedTail {R : ℕ} (B : Fin R → Set ℕ) (α : Fin R → ℝ) : ENNReal :=
∑ r, ENNReal.ofReal (α r) * ((tailThreshold (B r) : ℕ∞) : ENNReal)
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.2, Definition 11.5, p. 59