/- Released under Apache-2.0; see adjacent LICENSE. Signed finite factorial wheel and explicit factorial-combination error. No VonMangoldt/Chebyshev import, prime supply or PNT hypothesis. -/ import FactorialLogBounds namespace FactorialWheel noncomputable section open FactorialLogBounds def wheel (n : ℕ) : ℤ := (n : ℤ) - (n / 2 : ℕ) - (n / 3 : ℕ) - (n / 5 : ℕ) + (n / 30 : ℕ) theorem wheel_period (n : ℕ) : wheel (n + 30) = wheel n := by unfold wheel; omega theorem wheel_mod (n : ℕ) : wheel n = wheel (n % 30) := by unfold wheel; omega theorem wheel_zero_or_one (n : ℕ) : wheel n = 0 ∨ wheel n = 1 := by rw [wheel_mod] have hh : n % 30 < 30 := Nat.mod_lt _ (by norm_num) interval_cases n % 30 <;> norm_num [wheel] theorem wheel_one (n : ℕ) (hn : 1 ≤ n) (hn6 : n < 6) : wheel n = 1 := by interval_cases n <;> norm_num [wheel] def a : ℝ := (7 / 15) * Real.log 2 + (3 / 10) * Real.log 3 + (1 / 6) * Real.log 5 theorem power_log_lower (r b : ℝ) (k : ℕ) (hr : 0 < r) (hpow : r ^ k ≤ b) : (k : ℝ) * (1 - r⁻¹) ≤ Real.log b := by calc _ ≤ (k : ℝ) * Real.log r := mul_le_mul_of_nonneg_left (Real.one_sub_inv_le_log_of_pos hr) (Nat.cast_nonneg k) _ = Real.log (r ^ k) := (Real.log_pow r k).symm _ ≤ _ := Real.log_le_log (pow_pos hr k) hpow theorem log_two_lower : (2 / 3 : ℝ) ≤ Real.log 2 := by have hh := power_log_lower (24 / 23) 2 16 (by norm_num) (by norm_num) norm_num at hh exact hh theorem log_three_lower : (1 : ℝ) ≤ Real.log 3 := by have hh := power_log_lower (12 / 11) 3 12 (by norm_num) (by norm_num) norm_num at hh exact hh theorem log_five_lower : (3 / 2 : ℝ) ≤ Real.log 5 := by have hh := power_log_lower (8 / 7) 5 12 (by norm_num) (by norm_num) norm_num at hh exact hh theorem a_lower : (31 / 36 : ℝ) ≤ a := by have h2 := log_two_lower have h3 := log_three_lower have h5 := log_five_lower unfold a linarith theorem a_margin : (5 / 6 : ℝ) < a ∧ (1 / 3 + 1 / 90 : ℝ) ≤ 2 * a / 5 := by have hh := a_lower constructor <;> linarith def F (x : ℝ) : ℝ := Real.log ((Nat.factorial ⌊x⌋₊ : ℕ) : ℝ) def T (x : ℝ) : ℝ := F x - F (x / 2) - F (x / 3) - F (x / 5) + F (x / 30) theorem f_difference_bounds (x t : ℝ) (hx : 0 < x) (ht : 0 < t) : (x - t) * Real.log t ≤ f x - f t ∧ f x - f t ≤ (x - t) * Real.log x := by have hq : 0 < x / t := div_pos hx ht have hlo := mul_le_mul_of_nonneg_left (Real.one_sub_inv_le_log_of_pos hq) hx.le have hhi := mul_le_mul_of_nonneg_left (Real.log_le_sub_one_of_pos hq) ht.le have helo : x * (1 - (x / t)⁻¹) = x - t := by field_simp [hx.ne', ht.ne'] have hehi : t * (x / t - 1) = x - t := by field_simp [ht.ne'] rw [helo, Real.log_div hx.ne' ht.ne'] at hlo rw [hehi, Real.log_div hx.ne' ht.ne'] at hhi unfold f constructor <;> nlinarith /-- Uniform all-nonnegative-real floor-factorial error, including 0<=x<1. -/ theorem F_error (x : ℝ) (hx : 0 ≤ x) : |F x - f x| ≤ 1 + Real.log (x + 1) := by have hlog1 : 0 ≤ Real.log (x + 1) := Real.log_nonneg (by linarith) by_cases hx1 : 1 ≤ x · let n := ⌊x⌋₊ have hn : 1 ≤ n := (Nat.le_floor_iff hx).mpr (by simpa using hx1) have hn0 : (0 : ℝ) < n := by exact_mod_cast (show 0 < n by omega) have hn1 : (1 : ℝ) ≤ n := by exact_mod_cast hn have hnx : (n : ℝ) ≤ x := Nat.floor_le hx have hxn : x < (n : ℝ) + 1 := Nat.lt_floor_add_one x have hx0 : 0 < x := by linarith have hln : 0 ≤ Real.log (n : ℝ) := Real.log_nonneg hn1 have hlx : 0 ≤ Real.log x := Real.log_nonneg hx1 have hd := f_difference_bounds x n hx0 hn0 have hd0 : 0 ≤ f x - f n := by have hm := mul_nonneg (show 0 ≤ x - n by linarith) hln linarith [hd.1] have hd1 : f x - f n ≤ Real.log x := by have hm := mul_le_mul_of_nonneg_right (show x - n ≤ 1 by linarith) hlx linarith [hd.2] have hfac := log_factorial_bounds n hn change f (n : ℝ) + 1 ≤ F x ∧ F x ≤ f (n : ℝ) + 1 + Real.log (n : ℝ) at hfac have hlogn := Real.log_le_log hn0 (show (n : ℝ) ≤ x + 1 by linarith) have hlogx := Real.log_le_log hx0 (show x ≤ x + 1 by linarith) apply abs_le.mpr constructor <;> linarith [hfac.1, hfac.2] · have hsmall : x < 1 := by linarith have hn0 : ⌊x⌋₊ = 0 := Nat.floor_eq_zero.mpr hsmall have hF : F x = 0 := by simp [F, hn0] rw [hF] by_cases hx0 : x = 0 · subst x; simp [f] · have hxpos : 0 < x := lt_of_le_of_ne hx (Ne.symm hx0) have hlx : Real.log x ≤ 0 := by simpa using Real.log_le_log hxpos (show x ≤ 1 by linarith) have hlow := mul_le_mul_of_nonneg_left (Real.one_sub_inv_le_log_of_pos hxpos) hx have hid : x * (1 - x⁻¹) = x - 1 := by field_simp [hx0] rw [hid] at hlow have hneg := mul_nonpos_of_nonneg_of_nonpos hx hlx unfold f apply abs_le.mpr constructor <;> nlinarith theorem f_linear_identity (x : ℝ) (hx : 0 ≤ x) : f x - f (x / 2) - f (x / 3) - f (x / 5) + f (x / 30) = a * x := by by_cases hx0 : x = 0 · subst x; simp [f] · have hxpos : 0 < x := lt_of_le_of_ne hx (Ne.symm hx0) have h30 : Real.log (30 : ℝ) = Real.log 2 + Real.log 3 + Real.log 5 := by calc _ = Real.log ((2 : ℝ) * 3 * 5) := by norm_num _ = _ := by rw [Real.log_mul (by norm_num) (by norm_num), Real.log_mul (by norm_num) (by norm_num)] simp only [f, Real.log_div hxpos.ne' (by norm_num : (2 : ℝ) ≠ 0), Real.log_div hxpos.ne' (by norm_num : (3 : ℝ) ≠ 0), Real.log_div hxpos.ne' (by norm_num : (5 : ℝ) ≠ 0), Real.log_div hxpos.ne' (by norm_num : (30 : ℝ) ≠ 0), h30, a] ring /-- Explicit uniform linear/error estimate for the actual factorial combination. -/ theorem T_error (x : ℝ) (hx : 0 ≤ x) : |T x - a * x| ≤ 5 * (1 + Real.log (x + 1)) := by have hscale (d : ℝ) (hd : 1 ≤ d) : |F (x / d) - f (x / d)| ≤ 1 + Real.log (x + 1) := by have hd0 : 0 < d := by linarith have hy0 : 0 ≤ x / d := div_nonneg hx hd0.le have hyx : x / d ≤ x := by apply (div_le_iff₀ hd0).mpr nlinarith have hlog : Real.log (x / d + 1) ≤ Real.log (x + 1) := Real.log_le_log (by linarith : 0 < x / d + 1) (by linarith) exact (F_error (x / d) hy0).trans (add_le_add le_rfl hlog) have h0 := F_error x hx have h2 := hscale 2 (by norm_num) have h3 := hscale 3 (by norm_num) have h5 := hscale 5 (by norm_num) have h30 := hscale 30 (by norm_num) have hid : T x - a * x = (F x - f x) - (F (x / 2) - f (x / 2)) - (F (x / 3) - f (x / 3)) - (F (x / 5) - f (x / 5)) + (F (x / 30) - f (x / 30)) := by rw [← f_linear_identity x hx] unfold T ring rw [hid] have ht1 := abs_sub (F x - f x) (F (x / 2) - f (x / 2)) have ht2 := abs_sub ((F x - f x) - (F (x / 2) - f (x / 2))) (F (x / 3) - f (x / 3)) have ht3 := abs_sub ((F x - f x) - (F (x / 2) - f (x / 2)) - (F (x / 3) - f (x / 3))) (F (x / 5) - f (x / 5)) have ht4 := abs_add_le ((F x - f x) - (F (x / 2) - f (x / 2)) - (F (x / 3) - f (x / 3)) - (F (x / 5) - f (x / 5))) (F (x / 30) - f (x / 30)) linarith end end FactorialWheel #print axioms FactorialWheel.wheel #print axioms FactorialWheel.wheel_period #print axioms FactorialWheel.wheel_mod #print axioms FactorialWheel.wheel_zero_or_one #print axioms FactorialWheel.wheel_one #print axioms FactorialWheel.a #print axioms FactorialWheel.power_log_lower #print axioms FactorialWheel.log_two_lower #print axioms FactorialWheel.log_three_lower #print axioms FactorialWheel.log_five_lower #print axioms FactorialWheel.a_lower #print axioms FactorialWheel.a_margin #print axioms FactorialWheel.F #print axioms FactorialWheel.T #print axioms FactorialWheel.f_difference_bounds #print axioms FactorialWheel.F_error #print axioms FactorialWheel.f_linear_identity #print axioms FactorialWheel.T_error