Proof of Lemma 3, p. 15 — rounded endpoints
ProvedJRPHard.Shor.roundingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1range-divisorrounding
Let be a natural number and be real. Suppose and . Then
and meets every RangeDivisor instance condition. This states the numerical validity of using integer endpoints. The stated ordering of rounded endpoints is needed for the second conclusion.
Preamble
import Mathlib import Definitions.Def_JRPHard_Shor_DecisionProblems
Formal statement
namespace JRPHard.Shor
/-- Proof of Lemma 3, p. 15: rounding the two endpoints preserves the divisor
question and, under the interval side conditions, gives a RangeDivisor instance. -/
theorem rounding (M : ℕ) (L U : ℝ) (hL : 0 < L) (hLU : L ≤ U)
(hceil : ⌈L⌉₊ ≤ ⌊U⌋₊) (hbound : ⌊U⌋₊ ≤ M)
(hrange : L + U < 2 * Real.sqrt (2 * L * U)) :
(JRPHard.RangeDiv.HasDivisorIn M ⌈L⌉₊ ⌊U⌋₊ ↔
∃ d : ℕ, d ∣ M ∧ L ≤ (d : ℝ) ∧ (d : ℝ) ≤ U) ∧
JRPHard.RangeDiv.IsRangeDivisorInstance M ⌈L⌉₊ ⌊U⌋₊ := by sorry
end JRPHard.Shor
Source
Schulz and Telha, Integer factorization and Riemann's hypothesis: Why two-item joint replenishment is hard, arXiv:2007.09045v1, p. 15, proof of Lemma 3, rounding sentence
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.