Fact 1 — (log m)^t ≤ m · t!
ProvedCapacitatedKMedianFPT.Main.fact_1approximation-algorithmscapacitated-k-medianp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1parameterized-complexity
For every integer and every ,
where is the natural logarithm.
This bound turns enumeration counts such as with depending on only into FPT bounds .
Differences from the source:
- generalization: m ≥ 1 (applied to integers) → every real m ≥ 1; reason: the statement does not restrict m to integers; integers m ≥ 1 are a special case
- reading: log → natural logarithm Real.log; reason: the proof expands m = e^{log m}
Preamble
import Mathlib set_option autoImplicit false
Formal statement
namespace CapacitatedKMedianFPT.Main
/-- **Fact 1** (p. 6, proof p. 22–23). `(log m)^t ≤ m · t!` for all integers `t ≥ 0` and all real
`m ≥ 1` (natural logarithm). -/
theorem fact_1 (t : ℕ) (m : ℝ) (hm : 1 ≤ m) :
Real.log m ^ t ≤ m * (t.factorial : ℝ) := by sorry
end CapacitatedKMedianFPT.Main
Source
Aditya Anand, Yichen Huang, Ragesh Jaiswal, Amit Kumar, Euiwoong Lee, Jatin Yadav, A Tight FPT Approximation for Capacitated k-Median, STOC 2027 submission #1646 (October 2026), p. 6, Fact 1; proof p. 22–23
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.