/- Released under Apache-2.0; see adjacent LICENSE. Finite first-order factorial logarithm bounds by positive log increments. No Stirling/calculus import, asymptotic hypothesis, prime supply or PNT. -/ import SmoothBudget namespace FactorialLogBounds noncomputable section open scoped BigOperators def f (t : ℝ) : ℝ := t * Real.log t - t theorem increment_bounds (n : ℕ) (hn : 1 ≤ n) : Real.log (n : ℝ) ≤ f ((n + 1 : ℕ) : ℝ) - f (n : ℝ) ∧ f ((n + 1 : ℕ) : ℝ) - f (n : ℝ) ≤ Real.log ((n + 1 : ℕ) : ℝ) := by have hn0 : (0 : ℝ) < n := by exact_mod_cast (show 0 < n by omega) have hn1 : (0 : ℝ) < (n : ℝ) + 1 := by linarith let q : ℝ := ((n : ℝ) + 1) / n have hq : 0 < q := by dsimp [q]; positivity have hlog : Real.log q = Real.log ((n : ℝ) + 1) - Real.log (n : ℝ) := by dsimp [q] rw [Real.log_div hn1.ne' hn0.ne'] have hlo := mul_le_mul_of_nonneg_left (Real.one_sub_inv_le_log_of_pos hq) hn1.le have hhi := mul_le_mul_of_nonneg_left (Real.log_le_sub_one_of_pos hq) hn0.le have helo : ((n : ℝ) + 1) * (1 - q⁻¹) = 1 := by dsimp [q] field_simp [hn0.ne', hn1.ne'] <;> ring have hehi : (n : ℝ) * (q - 1) = 1 := by dsimp [q] field_simp [hn0.ne'] <;> ring rw [helo, hlog] at hlo rw [hehi, hlog] at hhi simp only [f, Nat.cast_add, Nat.cast_one] constructor <;> nlinarith theorem log_factorial_zero : Real.log ((Nat.factorial 0 : ℕ) : ℝ) = 0 := by simp theorem log_factorial_succ (n : ℕ) : Real.log ((Nat.factorial (n + 1) : ℕ) : ℝ) = Real.log ((n + 1 : ℕ) : ℝ) + Real.log ((Nat.factorial n : ℕ) : ℝ) := by rw [Nat.factorial_succ, Nat.cast_mul, Real.log_mul] · positivity · exact_mod_cast (Nat.factorial_pos n).ne' /-- Exact finite factorial-log identity, without the cold Log.Sum module. -/ theorem log_factorial_eq_sum (N : ℕ) : Real.log ((Nat.factorial N : ℕ) : ℝ) = ∑ k ∈ Finset.range N, Real.log ((k + 1 : ℕ) : ℝ) := by induction N with | zero => simp | succ N ih => rw [log_factorial_succ, Finset.sum_range_succ, ih]; ring theorem log_factorial_bounds_succ (n : ℕ) : f ((n + 1 : ℕ) : ℝ) + 1 ≤ Real.log ((Nat.factorial (n + 1) : ℕ) : ℝ) ∧ Real.log ((Nat.factorial (n + 1) : ℕ) : ℝ) ≤ f ((n + 1 : ℕ) : ℝ) + 1 + Real.log ((n + 1 : ℕ) : ℝ) := by induction n with | zero => norm_num [f] | succ n ih => have hi := increment_bounds (n + 1) (by omega) rw [log_factorial_succ] constructor <;> linarith [ih.1, ih.2, hi.1, hi.2] /-- Genuine finite first-order two-sided logarithmic factorial bounds, N>=1. -/ theorem log_factorial_bounds (N : ℕ) (hN : 1 ≤ N) : (N : ℝ) * Real.log (N : ℝ) - N + 1 ≤ Real.log ((Nat.factorial N : ℕ) : ℝ) ∧ Real.log ((Nat.factorial N : ℕ) : ℝ) ≤ (N : ℝ) * Real.log (N : ℝ) - N + 1 + Real.log (N : ℝ) := by cases N with | zero => omega | succ n => exact log_factorial_bounds_succ n end end FactorialLogBounds #print axioms FactorialLogBounds.f #print axioms FactorialLogBounds.increment_bounds #print axioms FactorialLogBounds.log_factorial_zero #print axioms FactorialLogBounds.log_factorial_succ #print axioms FactorialLogBounds.log_factorial_eq_sum #print axioms FactorialLogBounds.log_factorial_bounds_succ #print axioms FactorialLogBounds.log_factorial_bounds