Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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)

Proved
JRPHard.RangeDiv.lemma_3

by mikedeng1 · Oct 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

integer-factorizationjoint-replenishmentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1range-divisorreduction

Let M≥U≥L>0M \ge U \ge L > 0M≥U≥L>0 be integers with L+U<22LUL + U < 2\sqrt{2LU}L+U<22LU​ (an instance of RangeDivisor). Consider the two-item periodic JRP instance JRPM,U,L\mathrm{JRP}_{M,U,L}JRPM,U,L​,

JRPM,U,L(q1,q2)=q1+M3(M+1)q2+M(M+1) q2+LUgcd⁡(q1,q2),\mathrm{JRP}_{M,U,L}(q_1,q_2) = q_1 + \frac{M^3(M+1)}{q_2} + M(M+1)\,q_2 + \frac{LU}{\gcd(q_1,q_2)},JRPM,U,L​(q1​,q2​)=q1​+q2​M3(M+1)​+M(M+1)q2​+gcd(q1​,q2​)LU​,

that is, objective (3) with K0=LUK_0 = LUK0​=LU, K1=0K_1 = 0K1​=0, H1=1H_1 = 1H1​=1, K2=M3(M+1)K_2 = M^3(M+1)K2​=M3(M+1), H2=M(M+1)H_2 = M(M+1)H2​=M(M+1). Then:

  1. every coefficient K0,K2,H2K_0, K_2, H_2K0​,K2​,H2​ is a natural number at most 2M42M^42M4 (and K1=0K_1 = 0K1​=0, H1=1H_1 = 1H1​=1), so each has bit length polynomial in log⁡M\log MlogM;
  2. MMM has a divisor qqq with L≤q≤UL \le q \le UL≤q≤U if and only if there are positive integers q1,q2q_1, q_2q1​,q2​ with
JRPM,U,L(q1,q2) ≤ L+U+2M2(M+1).\mathrm{JRP}_{M,U,L}(q_1, q_2) \ \le\ L + U + 2M^2(M+1).JRPM,U,L​(q1​,q2​) ≤ L+U+2M2(M+1).

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 JRPM,U,L\mathrm{JRP}_{M,U,L}JRPM,U,L​" with L+UL + UL+U. The two-item objective also contains item 2's cost EOQK2,H2(M)=2M2(M+1)\mathrm{EOQ}_{K_2,H_2}(M) = 2M^2(M+1)EOQK2​,H2​​(M)=2M2(M+1) at q2=Mq_2 = Mq2​=M, so the printed comparison is never met. The statement uses the threshold zM,L,U=L+U+2M2(M+1)z_{M,L,U} = L + U + 2M^2(M+1)zM,L,U​=L+U+2M2(M+1) that §3.1 announces. "Optimal value ≤z\le z≤z" is stated in the decision form of p. 13, "is there a solution of cost at most zzz"; the two agree because the minimum is attained. K2,H2K_2, H_2K2​,H2​ are Lemma 2's values, where the page says "sufficiently large". "Polynomial time" is not formalized; the explicit coefficients and the bound 2M42M^42M4 are what remain of it. The bound is 2M42M^42M4 rather than M4M^4M4 because M=L=U=1M = L = U = 1M=L=U=1 is an instance, with K2=2K_2 = 2K2​=2.

Preamble
import Mathlib
import Definitions.Def_JRPHard_RangeDiv_Setting
Formal statement
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
Source
Schulz and Telha, Integer factorization and Riemann's hypothesis: Why two-item joint replenishment is hard, arXiv:2007.09045v1, pp. 13–14, Lemma 3 (threshold z_{M,L,U} of §3.1, p. 13; decision version, p. 13)
Human review
  • Endorsed by Shuze Chen · Oct 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 15, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me