Theorem 2.3 — General two-precision laws
OpenRankingQueryCost.Joint.Supplement.theorem_2_3Fix . For every admissible and positive rational precisions , with , the optimal fixed-support hard budgets satisfy
With online support, actual accuracy, baseline safety, same-precision dual certification, and dual certification at every admissible all have rate
Each comparison is two-sided against a finite operational optimum. The constants are uniform over all admissible , including , with no large- threshold. Every upper bound includes a finite implementing program; dual upper bounds include a public verifier with polynomial computation in and input bit length. Lower bounds allow arbitrary measurable policies with real outputs throughout . Setting in the universally quantified dual clause gives the same-precision clause. These are companion laws beyond the goal's linear-density regime.
Differences from the source:
- encoding: n labelled objects and ranks 0 through n−1 → Fin n labels and Rank n permutations; reason: a bijective encoding preserving every instance and the full continuous output space Q
- encoding: Oδ or Θδ query rates and polynomial computation → positive constants and finite word-RAM programs quantified before n, s and the precisions; reason: makes exactly the stated uniform dependence explicit and charges computation with the published Implements contracts
- encoding: positive rational ε and τ and fixed real δ → the implementing program receives both rational precisions and a rational internal margin; reason: both input bit lengths are charged; δstar in [δ/2,δ] preserves the full real-margin claim
import Definitions.Def_RankingQueryCost_Joint_PublicGate set_option autoImplicit false
namespace RankingQueryCost.Joint.Supplement
/-- Theorem 2.3, printed p. 5 / PDF 6. All comparison constants and finite
programs precede n,s,epsilon,tau. Lower bounds use the unrestricted real-output
policy class. Setting tau=epsilon recovers same-precision dual certification.
The algorithm input includes both requested rational precisions. -/
theorem theorem_2_3 (δ : ℝ) (hδ : 0 < δ ∧ δ ≤ 1) :
∃ (c C : ℝ) (Ctime degree : ℕ)
(pFA pFS pFD pOA pOS pOD vF vO : ComparisonProgram) (δstar : ℚ),
0 < c ∧ 0 < C ∧ 0 < Ctime ∧ 0 < δstar ∧
δ / 2 ≤ (δstar : ℝ) ∧ (δstar : ℝ) ≤ δ ∧
∀ (n s : ℕ) (ε : ℚ), Admissible n s → 0 < ε →
threshold n s δ ≤ (ε : ℝ) → (ε : ℝ) ≤ precisionCeiling →
let Ract := resolutionCost n ε
let Rsafe := min (pairCount n : ℝ) (Ract + s)
let Ronline := sparseRate n s ε
FiniteOptimumBound (actualBudgets n s 0 ε) c C Ract ∧
FiniteOptimumBound (safeBudgets n s 0 ε) c C Rsafe ∧
FiniteOptimumBound (actualBudgets n 0 s ε) c C Ronline ∧
FiniteOptimumBound (safeBudgets n 0 s ε) c C Ronline ∧
(∃ (B : ℕ) (A : QueryPolicy n), HardBudget s 0 B A ∧ Actual s 0 ε A ∧
(B : ℝ) ≤ C * Ract ∧
Implements s 0 Ctime degree pFA (dualInput n s 0 δstar ε) A) ∧
(∃ (B : ℕ) (A : QueryPolicy n), HardBudget s 0 B A ∧ Safe s 0 ε A ∧
(B : ℝ) ≤ C * Rsafe ∧
Implements s 0 Ctime degree pFS (dualInput n s 0 δstar ε) A) ∧
(∃ (B : ℕ) (A : QueryPolicy n), HardBudget 0 s B A ∧ Actual 0 s ε A ∧
(B : ℝ) ≤ C * Ronline ∧
Implements 0 s Ctime degree pOA (dualInput n 0 s δstar ε) A) ∧
(∃ (B : ℕ) (A : QueryPolicy n), HardBudget 0 s B A ∧ Safe 0 s ε A ∧
(B : ℝ) ≤ C * Ronline ∧
Implements 0 s Ctime degree pOS (dualInput n 0 s δstar ε) A) ∧
∀ τ : ℚ, ε ≤ τ → (τ : ℝ) ≤ precisionCeiling →
let Rdual := min (pairCount n : ℝ)
(Ract + min ((n : ℝ) * s) ((s : ℝ) / τ))
FiniteOptimumBound (dualBudgets n s 0 ε τ) c C Rdual ∧
FiniteOptimumBound (dualBudgets n 0 s ε τ) c C Ronline ∧
(∃ (B : ℕ) (A : QueryPolicy n) (V : PublicVerifier n),
HardBudget s 0 B A ∧ Dual s 0 ε τ A V ∧ (B : ℝ) ≤ C * Rdual ∧
Implements s 0 Ctime degree pFD (dualInput n s 0 δstar ε ++ encodeRational τ) A ∧
ImplementsVerifier s Ctime degree vF τ V) ∧
∃ (B : ℕ) (A : QueryPolicy n) (V : PublicVerifier n),
HardBudget 0 s B A ∧ Dual 0 s ε τ A V ∧ (B : ℝ) ≤ C * Ronline ∧
Implements 0 s Ctime degree pOD (dualInput n 0 s δstar ε ++ encodeRational τ) A ∧
ImplementsVerifier s Ctime degree vO τ V := by sorry
end RankingQueryCost.Joint.Supplement