Lemma 1 — for odd composite M, every optimal plan of the explicit aperiodic instance has q₂ = M and 1 < gcd(q₁, M) < M
ProvedJRPHard.Aperiodic.lemma_1Let be an odd composite number. Consider the two-item aperiodic joint replenishment problem
with the coefficients
Then:
- the instance is a valid aperiodic JRP instance, and , and every coefficient is at most (so its binary size is at most );
- the problem has an optimal solution;
- every optimal solution satisfies
Thus an exact algorithm for the two-item aperiodic JRP yields a non-trivial divisor of ; 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 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 " is rendered as "every coefficient is at most ", 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.
import Mathlib import Definitions.Def_JRPHard_Aperiodic_Setting
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.