Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1 — for odd composite M, every optimal plan of the explicit aperiodic instance has q₂ = M and 1 < gcd(q₁, M) < M

Proved
JRPHard.Aperiodic.lemma_1

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

integer-factorizationjoint-replenishmentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reduction

Let MMM be an odd composite number. Consider the two-item aperiodic joint replenishment problem

min⁡{JRP(q1,q2)=K1q1+H1q1+K2q2+H2q2−K0lcm(q1,q2) : q1,q2∈Z+}\min\left\{\mathrm{JRP}(q_1,q_2) = \frac{K_1}{q_1} + H_1 q_1 + \frac{K_2}{q_2} + H_2 q_2 - \frac{K_0}{\mathrm{lcm}(q_1,q_2)} \ :\ q_1, q_2 \in \mathbb Z^+\right\}min{JRP(q1​,q2​)=q1​K1​​+H1​q1​+q2​K2​​+H2​q2​−lcm(q1​,q2​)K0​​ : q1​,q2​∈Z+}

with the coefficients

K1=K0=M(M−1),H1=4,K2=M3(M2−1),H2=M(M2−1).K_1 = K_0 = M(M-1), \qquad H_1 = 4, \qquad K_2 = M^3(M^2-1), \qquad H_2 = M(M^2-1).K1​=K0​=M(M−1),H1​=4,K2​=M3(M2−1),H2​=M(M2−1).

Then:

  1. the instance is a valid aperiodic JRP instance, K0≤K1K_0 \le K_1K0​≤K1​ and K0≤K2K_0 \le K_2K0​≤K2​, and every coefficient is at most M5M^5M5 (so its binary size is at most 5log⁡M5\log M5logM);
  2. the problem has an optimal solution;
  3. every optimal solution (q1,q2)(q_1, q_2)(q1​,q2​) satisfies
q2=Mand1<gcd⁡(q1,M)<M.q_2 = M \qquad\text{and}\qquad 1 < \gcd(q_1, M) < M .q2​=Mand1<gcd(q1​,M)<M.

Thus an exact algorithm for the two-item aperiodic JRP yields a non-trivial divisor gcd⁡(q1,M)\gcd(q_1,M)gcd(q1​,M) of MMM; this is the mathematical core of the paper's Theorem 1(a), the reduction from integer factorization.

Formalization Note The paper states the lemma as "there is a two-item instance … whose optimal solutions satisfy …"; here the instance is the explicit one constructed in the proof (p. 9), which is what the reduction uses and which rules out choosing an instance that does not depend on MMM in the intended way. The existence of an optimal solution is stated explicitly, so that the claim about every optimal solution is not vacuous; it holds because the objective tends to infinity. "Size at most 5log⁡M5\log M5logM" is rendered as "every coefficient is at most M5M^5M5", equivalent in any logarithm base. Odd composite is encoded as Odd M, 1 < M, ¬ M.Prime. Periods range over positive integers only. The polynomial running time of the reduction is not formalized.

Preamble
import Mathlib
import Definitions.Def_JRPHard_Aperiodic_Setting
Formal statement
namespace JRPHard.Aperiodic

theorem lemma_1 (M : ℕ) (hodd : Odd M) (h1 : 1 < M) (hcomp : ¬ M.Prime) :
    (coefK0 M ≤ coefK1 M ∧ coefK0 M ≤ coefK2 M ∧
      coefK0 M ≤ M ^ 5 ∧ coefK1 M ≤ M ^ 5 ∧ coefK2 M ≤ M ^ 5 ∧ coefH1 ≤ M ^ 5 ∧
      coefH2 M ≤ M ^ 5) ∧
    (∃ q₁ q₂ : ℕ, IsOptimal (lemma1Cost M) q₁ q₂) ∧
    ∀ q₁ q₂ : ℕ, IsOptimal (lemma1Cost M) q₁ q₂ →
      q₂ = M ∧ 1 < Nat.gcd q₁ M ∧ Nat.gcd q₁ M < M := by sorry

end JRPHard.Aperiodic
Source
Schulz and Telha, Integer factorization and Riemann's hypothesis: Why two-item joint replenishment is hard, arXiv:2007.09045v1, p. 8, Lemma 1 (instance from the proof, p. 9)
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