Proof of Lemma 1, pp. 9–10 — the interval [(M − 1)/2 − (p − 1)/2, (M − 1)/2 + (p − 1)/2] contains a multiple q of p with JRP^red(q) < 4(M − 1)
ProvedJRPHard.Aperiodic.exists_good_multipleinteger-factorizationjoint-replenishmentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pigeonhole
Let be an odd composite number and let be a divisor of with (so is odd). Then there is a positive integer that is a multiple of , lies in the integer interval
and satisfies
Combined with the coprime lower bound, this shows that every minimizer of problem (2) satisfies .
Formalization Note Because and are odd, both endpoints are integers; they are written with natural-number division and subtraction, (M - 1) / 2 - (p - 1) / 2 and (M - 1) / 2 + (p - 1) / 2, which are exact here (and the lower endpoint is positive since ).
Preamble
import Mathlib import Definitions.Def_JRPHard_Aperiodic_Setting
Formal statement
namespace JRPHard.Aperiodic
theorem exists_good_multiple (M : ℕ) (hodd : Odd M) (h1 : 1 < M) (hcomp : ¬ M.Prime)
(p : ℕ) (hpM : p ∣ M) (hp3 : 3 ≤ p) (hplt : p < M) :
∃ q : ℕ, 0 < q ∧ p ∣ q ∧
(M - 1) / 2 - (p - 1) / 2 ≤ q ∧ q ≤ (M - 1) / 2 + (p - 1) / 2 ∧
jrpRed M q < 4 * ((M : ℝ) - 1) := 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, pp. 9–10, proof of Lemma 1, "This upper bound, as a continuous function of q, is strictly convex …"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.