Proof of Lemma 1, p. 9 — for a multiple q of a divisor p of M, DC(q, M; K₀) ≥ p(M − 1)/q and JRP^red(q) ≤ (M − 1)(M − p)/q + 4q
ProvedJRPHard.Aperiodic.multiple_upper_boundinteger-factorizationjoint-replenishmentlcmp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be an odd composite number, let be a divisor of with , and let be a positive multiple of . Then the discount satisfies
and therefore
This upper bound on periods that share the factor with is the comparison function used to exhibit a period with .
Preamble
import Mathlib import Definitions.Def_JRPHard_Aperiodic_Setting
Formal statement
namespace JRPHard.Aperiodic
theorem multiple_upper_bound (M : ℕ) (hodd : Odd M) (h1 : 1 < M) (hcomp : ¬ M.Prime)
(p : ℕ) (hpM : p ∣ M) (hp3 : 3 ≤ p) (hplt : p < M) (q : ℕ) (hq : 0 < q) (hpq : p ∣ q) :
(p : ℝ) * ((M : ℝ) - 1) / (q : ℝ) ≤ (coefK0 M : ℝ) / (Nat.lcm q M : ℝ) ∧
jrpRed M q ≤ ((M : ℝ) - 1) * ((M : ℝ) - p) / (q : ℝ) + 4 * (q : ℝ) := 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. 9, proof of Lemma 1, "Let p be a non-trivial divisor of M such that 3 ≤ p < M"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.