Lemma 3 — M has a divisor in [L, U] iff the explicit periodic instance JRP_{M,U,L} has a plan of cost at most L + U + 2M²(M + 1)
ProvedJRPHard.RangeDiv.lemma_3Let be integers with (an instance of RangeDivisor). Consider the two-item periodic JRP instance ,
that is, objective (3) with , , , , . Then:
- every coefficient is a natural number at most (and , ), so each has bit length polynomial in ;
- has a divisor with if and only if there are positive integers with
This is the mathematical content of the reduction from RangeDivisor to the two-item periodic JRP, which, combined with Shor's NP-completeness of RangeDivisor under randomized reductions, gives Theorem 2 of the paper.
Formalization Note The printed lemma compares "the optimal value of " with . The two-item objective also contains item 2's cost at , so the printed comparison is never met. The statement uses the threshold that §3.1 announces. "Optimal value " is stated in the decision form of p. 13, "is there a solution of cost at most "; the two agree because the minimum is attained. are Lemma 2's values, where the page says "sufficiently large". "Polynomial time" is not formalized; the explicit coefficients and the bound are what remain of it. The bound is rather than because is an instance, with .
import Mathlib import Definitions.Def_JRPHard_RangeDiv_Setting
namespace JRPHard.RangeDiv
theorem lemma_3 (M L U : ℕ) (hI : IsRangeDivisorInstance M L U) :
(coefK0 L U ≤ 2 * M ^ 4 ∧ JRPHard.Periodic.coefK2 M ≤ 2 * M ^ 4 ∧ JRPHard.Periodic.coefH2 M ≤ 2 * M ^ 4) ∧
(HasDivisorIn M L U ↔
∃ q₁ q₂ : ℕ, 0 < q₁ ∧ 0 < q₂ ∧ rangeCost M L U q₁ q₂ ≤ threshold M L U) := by sorry
end JRPHard.RangeDiv
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.