op_902_tail_bound_implies_poly_bound
There exist positive real constants C and c such that for every natural number T ≥ 2, the threshold D = ceil(C * (log T)^(1/3)) satisfies 300 ≤ D and the exponential tail bound 12 * T * exp(-(D/40)^3) is at most T^(-c).
Statement
theorem op_902_tail_bound_implies_poly_bound : ∃ (C c : ℝ), 0 < C ∧ 0 < c ∧ ∀ (T : ℕ) (hT : 2 ≤ T), let D := Nat.ceil (C * (Real.log (T : ℝ)) ^ ((1 : ℝ) / 3)) 300 ≤ D ∧ 12 * (T : ℝ) * Real.exp (-(((D : ℝ) / 40) ^ 3)) ≤ (T : ℝ) ^ (-c)
- Source
- step towards op_902_poly_time_carpooling_cube_root_log_discrepancy
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem is proved by choosing explicit constants C = 400 and c = 1. For any natural number T ≥ 2, since log T ≥ log 2 > 27/64 = (3/4)^3, the cube root (log T)^(1/3) strictly exceeds 3/4, which directly ensures D = ⌈400 * (log T)^(1/3)⌉ ≥ 300. For the tail bound, D / 40 ≥ 10 * (log T)^(1/3) implies (D / 40)^3 ≥ 1000 * log T, so the exponential factor is at most exp(-1000 * log T) = T^(-1000). Multiplying by 12 * T yields 12 * T^(-999), which is bounded above by T^(-1) because T^998 ≥ 2^998 ≥ 12.
We instantiate C = 400 and c = 1, reducing the theorem to checking the bounds for an arbitrary natural number T ≥ 2.
The existential quantifiers for C and c are witnessed by 400 and 1, which are verified to be strictly positive by computation. We then assume an arbitrary integer T ≥ 2 and cast T ≥ 2 and T > 0 into the real numbers.
refine ⟨400, 1, by norm_num, by norm_num, ?_⟩ intro T hT dsimp only have hTreal : (2:ℝ) ≤ (T:ℝ) := by exact_mod_cast hT have hTpos : (0:ℝ) < (T:ℝ) := by linarith
(3/4)^3 < log T.
Monotonicity of the logarithm (`Real.log_le_log`) ensures that log 2 ≤ log T since 2 ≤ T. Using the library numerical bound log 2 > 0.6931... (`Real.log_two_gt_d9`), we check that 27/64 < log 2. Transitivity (`lt_of_lt_of_le`) then gives (3/4)^3 = 27/64 < log T.
uses
Real.log_le_log,Real.log_two_gt_d9,lt_of_lt_of_lehave hlog2le : Real.log (2:ℝ) ≤ Real.log (T:ℝ) := Real.log_le_log (by norm_num) hTreal have hlog2gt : (27/64:ℝ) < Real.log (2:ℝ) := by have h := Real.log_two_gt_d9 norm_num at h ⊢ linarith have hcube : (3/4:ℝ)^3 < Real.log (T:ℝ) := by have h1 : (27/64:ℝ) < Real.log (T:ℝ) := lt_of_lt_of_le hlog2gt hlog2le norm_num at h1 ⊢ exact h1
3/4 < (log T)^(1/3).
Using exponent arithmetic (`Real.rpow_natCast`, `Real.rpow_mul`), we compute ((3/4)^3)^(1/3) = 3/4. Since x ↦ x^(1/3) is strictly increasing on non-negative reals (`Real.rpow_lt_rpow`), taking cube roots preserves the inequality (3/4)^3 < log T, yielding 3/4 < (log T)^(1/3).
uses
Real.rpow_natCast,Real.rpow_mul,Real.rpow_lt_rpowhave hleft : (((3/4:ℝ)^3) ^ ((1:ℝ)/3)) = 3/4 := by rw [← Real.rpow_natCast (3/4) 3] rw [← Real.rpow_mul (by norm_num : (0:ℝ) ≤ 3/4)] norm_num have hroot_gt : (3/4:ℝ) < (Real.log (T:ℝ)) ^ ((1:ℝ)/3) := by have hrpow : (((3/4:ℝ)^3) ^ ((1:ℝ)/3)) < (Real.log (T:ℝ)) ^ ((1:ℝ)/3) := Real.rpow_lt_rpow (by positivity) hcube (by norm_num) calc (3/4:ℝ) = (((3/4:ℝ)^3) ^ ((1:ℝ)/3)) := hleft.symm _ < (Real.log (T:ℝ)) ^ ((1:ℝ)/3) := hrpow
300 ≤ D, settling the first conjunct of the theorem.
Multiplying 3/4 < (log T)^(1/3) by 400 gives 300 < 400 * (log T)^(1/3). Since D = ⌈400 * (log T)^(1/3)⌉ ≥ 400 * (log T)^(1/3) by `Nat.le_ceil`, combining inequalities via `lt_of_lt_of_le` and `le_of_lt` yields 300 ≤ D. Splitting the goal with `constructor`, this discharges the first conjunct.
uses
Nat.le_ceil,lt_of_lt_of_le,le_of_ltlet D : ℕ := Nat.ceil (400 * (Real.log (T:ℝ)) ^ ((1:ℝ)/3)) have hx_gt : (300:ℝ) < 400 * (Real.log (T:ℝ)) ^ ((1:ℝ)/3) := by nlinarith [hroot_gt] have hx_le_D : 400 * (Real.log (T:ℝ)) ^ ((1:ℝ)/3) ≤ (D:ℝ) := Nat.le_ceil _ have hD_ge_300 : 300 ≤ D := by have h : (300:ℝ) ≤ (D:ℝ) := le_of_lt (lt_of_lt_of_le hx_gt hx_le_D) exact_mod_cast h change 300 ≤ D ∧ 12 * (T:ℝ) * Real.exp (-(((D:ℝ)/40)^3)) ≤ (T:ℝ)^(-1:ℝ) constructor · exact hD_ge_300
1000 * log T ≤ (D/40)^3.
Since log T ≥ log 2 > 0, the cube root (log T)^(1/3) is non-negative (`Real.rpow_nonneg`), and cubing it returns log T (`Real.rpow_inv_natCast_pow`). From D ≥ 400 * (log T)^(1/3), division by 40 yields D/40 ≥ 10 * (log T)^(1/3). Cubing both sides (`pow_le_pow_left₀`) gives (D/40)^3 ≥ (10 * (log T)^(1/3))^3 = 1000 * log T.
uses
Real.rpow_nonneg,Real.rpow_inv_natCast_pow,pow_le_pow_left₀· have hlogT_nonneg : 0 ≤ Real.log (T:ℝ) := by have hpos : (0:ℝ) < Real.log (2:ℝ) := by linarith [hlog2gt] linarith have hr_nonneg : 0 ≤ (Real.log (T:ℝ)) ^ ((1:ℝ)/3) := Real.rpow_nonneg hlogT_nonneg _ have hr_cube : ((Real.log (T:ℝ)) ^ ((1:ℝ)/3))^3 = Real.log (T:ℝ) := by rw [show ((1:ℝ)/3) = ((3:ℕ):ℝ)⁻¹ by norm_num] apply Real.rpow_inv_natCast_pow · exact hlogT_nonneg · norm_num have hD_div : (10:ℝ) * ((Real.log (T:ℝ)) ^ ((1:ℝ)/3)) ≤ (D:ℝ)/40 := by nlinarith have hcubeD : 1000 * Real.log (T:ℝ) ≤ ((D:ℝ)/40)^3 := by have hmono : (10 * ((Real.log (T:ℝ)) ^ ((1:ℝ)/3)))^3 ≤ ((D:ℝ)/40)^3 := by apply pow_le_pow_left₀ (by positivity) hD_div 3 calc 1000 * Real.log (T:ℝ) = (10 * ((Real.log (T:ℝ)) ^ ((1:ℝ)/3)))^3 := by rw [show (10 * ((Real.log (T:ℝ)) ^ ((1:ℝ)/3)))^3 = 1000 * (((Real.log (T:ℝ)) ^ ((1:ℝ)/3))^3) by ring] rw [hr_cube] _ ≤ ((D:ℝ)/40)^3 := hmono
12 * T * exp(-(D/40)^3) ≤ 12 * T * T^(-1000).
Negating the inequality yields -(D/40)^3 ≤ -1000 * log T. Applying the monotonic exponential function (`Real.exp_le_exp.mpr`) gives exp(-(D/40)^3) ≤ exp(-1000 * log T), which equals T^(-1000) by the definition of real powers (`Real.rpow_def_of_pos`). Multiplying both sides by the non-negative factor 12 * T (`mul_le_mul_of_nonneg_left`) yields the bound.
uses
Real.exp_le_exp.mpr,Real.rpow_def_of_pos,mul_le_mul_of_nonneg_lefthave hexp_le : Real.exp (-(((D:ℝ)/40)^3)) ≤ (T:ℝ)^(-1000:ℝ) := by have h1 : Real.exp (-(((D:ℝ)/40)^3)) ≤ Real.exp (-(1000 * Real.log (T:ℝ))) := by apply Real.exp_le_exp.mpr linarith have h2 : Real.exp (-(1000 * Real.log (T:ℝ))) = (T:ℝ)^(-1000:ℝ) := by rw [Real.rpow_def_of_pos hTpos] congr 1 ring exact h1.trans_eq h2 have htail1 : 12 * (T:ℝ) * Real.exp (-(((D:ℝ)/40)^3)) ≤ 12 * (T:ℝ) * (T:ℝ)^(-1000:ℝ) := by apply mul_le_mul_of_nonneg_left hexp_le positivity
12 * T * T^(-1000) ≤ T^(-1), completing the proof.
Power addition (`Real.rpow_one`, `Real.rpow_add`) simplifies T * T^(-1000) to T^(-999). Because T ≥ 2, we have T^998 ≥ 2^998 ≥ 2^4 = 16 ≥ 12 using power monotonicity (`pow_le_pow_left₀`, `pow_le_pow_right₀`, `le_trans`). Multiplying 12 ≤ T^998 by the non-negative quantity T^(-999) (`mul_le_mul_of_nonneg_right`, `Real.rpow_nonneg`) gives 12 * T^(-999) ≤ T^998 * T^(-999) = T^(-1). Combining this with the upper bound from the previous step via `le_trans` finishes the theorem.
uses
Real.rpow_one,Real.rpow_add,pow_le_pow_left₀,pow_le_pow_right₀,mul_le_mul_of_nonneg_right,Real.rpow_nonneg,le_transhave hT_mul : (T:ℝ) * (T:ℝ)^(-1000:ℝ) = (T:ℝ)^(-999:ℝ) := by calc (T:ℝ) * (T:ℝ)^(-1000:ℝ) = (T:ℝ)^(1:ℝ) * (T:ℝ)^(-1000:ℝ) := by rw [Real.rpow_one] _ = (T:ℝ)^((1:ℝ) + (-1000:ℝ)) := by rw [Real.rpow_add hTpos] _ = (T:ℝ)^(-999:ℝ) := by norm_num have h12le : (12:ℝ) ≤ (T:ℝ)^998 := by have hpow : (2:ℝ)^998 ≤ (T:ℝ)^998 := pow_le_pow_left₀ (by norm_num) hTreal 998 have h12_2pow : (12:ℝ) ≤ (2:ℝ)^998 := by calc (12:ℝ) ≤ (2:ℝ)^4 := by norm_num _ ≤ (2:ℝ)^998 := pow_le_pow_right₀ (by norm_num : (1:ℝ) ≤ 2) (by norm_num : 4 ≤ 998) exact le_trans h12_2pow hpow have hpow_mul : (T:ℝ)^998 * (T:ℝ)^(-999:ℝ) = (T:ℝ)^(-1:ℝ) := by calc (T:ℝ)^998 * (T:ℝ)^(-999:ℝ) = (T:ℝ)^(998:ℝ) * (T:ℝ)^(-999:ℝ) := by norm_num _ = (T:ℝ)^((998:ℝ) + (-999:ℝ)) := by rw [Real.rpow_add hTpos] _ = (T:ℝ)^(-1:ℝ) := by norm_num have htail2 : 12 * (T:ℝ) * (T:ℝ)^(-1000:ℝ) ≤ (T:ℝ)^(-1:ℝ) := by calc 12 * (T:ℝ) * (T:ℝ)^(-1000:ℝ) = 12 * ((T:ℝ) * (T:ℝ)^(-1000:ℝ)) := by ring _ = 12 * (T:ℝ)^(-999:ℝ) := by rw [hT_mul] _ ≤ (T:ℝ)^998 * (T:ℝ)^(-999:ℝ) := by apply mul_le_mul_of_nonneg_right h12le exact Real.rpow_nonneg (by positivity) _ _ = (T:ℝ)^(-1:ℝ) := hpow_mul exact le_trans htail1 htail2
Real.log_le_log- The real logarithm is monotonic: if 0 < x and x ≤ y, then log x ≤ log y.
Real.log_two_gt_d9- A numerical lower bound on the natural logarithm of 2: 0.6931471803 < log 2.
lt_of_lt_of_le- Transitivity of strict and non-strict inequality: if a < b and b ≤ c, then a < c.
Real.rpow_natCast- For any real x and natural number n, the real power x^(↑n) equals the natural power x^n.
Real.rpow_mul- For x ≥ 0 and real exponents y, z, (x^y)^z = x^(y * z).
Real.rpow_lt_rpow- For 0 ≤ x < y and z > 0, x^z < y^z.
Nat.le_ceil- Any real number a is bounded above by the real cast of its ceiling: a ≤ ⌈a⌉.
le_of_lt- A strict inequality implies a non-strict inequality: if a < b, then a ≤ b.
Real.rpow_nonneg- For x ≥ 0 and any real y, x^y ≥ 0.
Real.rpow_inv_natCast_pow- For x ≥ 0 and n ≠ 0 in ℕ, (x^(1/n))^n = x.
pow_le_pow_left₀- If 0 ≤ a ≤ b, then a^n ≤ b^n for every natural number n.
Real.exp_le_exp.mpr- The exponential function is monotonic: if x ≤ y, then exp(x) ≤ exp(y).
Real.rpow_def_of_pos- For x > 0 and any real y, x^y = exp(y * log x).
mul_le_mul_of_nonneg_left- If b ≤ c and 0 ≤ a, then a * b ≤ a * c.
Real.rpow_one- For any real x, x^1 = x.
Real.rpow_add- For x > 0 and reals y, z, x^(y + z) = x^y * x^z.
pow_le_pow_right₀- If 1 ≤ a and m ≤ n for natural numbers m, n, then a^m ≤ a^n.
le_trans- Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
mul_le_mul_of_nonneg_right- If b ≤ c and 0 ≤ a, then b * a ≤ c * a.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Real-analytic bound converting the continuous tail bound 12 * T * exp(-(D/40)^3) at threshold D = ceil(C * (log T)^(1/3)) to a polynomial probability bound T^(-c). -/theorem op_902_tail_bound_implies_poly_bound : ∃ (C c : ℝ), 0 < C ∧ 0 < c ∧ ∀ (T : ℕ) (hT : 2 ≤ T), let D := Nat.ceil (C * (Real.log (T : ℝ)) ^ ((1 : ℝ) / 3)) 300 ≤ D ∧ 12 * (T : ℝ) * Real.exp (-(((D : ℝ) / 40) ^ 3)) ≤ (T : ℝ) ^ (-c) := by refine ⟨400, 1, by norm_num, by norm_num, ?_⟩ intro T hT dsimp only have hTreal : (2:ℝ) ≤ (T:ℝ) := by exact_mod_cast hT have hTpos : (0:ℝ) < (T:ℝ) := by linarith have hlog2le : Real.log (2:ℝ) ≤ Real.log (T:ℝ) := Real.log_le_log (by norm_num) hTreal have hlog2gt : (27/64:ℝ) < Real.log (2:ℝ) := by have h := Real.log_two_gt_d9 norm_num at h ⊢ linarith have hcube : (3/4:ℝ)^3 < Real.log (T:ℝ) := by have h1 : (27/64:ℝ) < Real.log (T:ℝ) := lt_of_lt_of_le hlog2gt hlog2le norm_num at h1 ⊢ exact h1 have hleft : (((3/4:ℝ)^3) ^ ((1:ℝ)/3)) = 3/4 := by rw [← Real.rpow_natCast (3/4) 3] rw [← Real.rpow_mul (by norm_num : (0:ℝ) ≤ 3/4)] norm_num have hroot_gt : (3/4:ℝ) < (Real.log (T:ℝ)) ^ ((1:ℝ)/3) := by have hrpow : (((3/4:ℝ)^3) ^ ((1:ℝ)/3)) < (Real.log (T:ℝ)) ^ ((1:ℝ)/3) := Real.rpow_lt_rpow (by positivity) hcube (by norm_num) calc (3/4:ℝ) = (((3/4:ℝ)^3) ^ ((1:ℝ)/3)) := hleft.symm _ < (Real.log (T:ℝ)) ^ ((1:ℝ)/3) := hrpow let D : ℕ := Nat.ceil (400 * (Real.log (T:ℝ)) ^ ((1:ℝ)/3)) have hx_gt : (300:ℝ) < 400 * (Real.log (T:ℝ)) ^ ((1:ℝ)/3) := by nlinarith [hroot_gt] have hx_le_D : 400 * (Real.log (T:ℝ)) ^ ((1:ℝ)/3) ≤ (D:ℝ) := Nat.le_ceil _ have hD_ge_300 : 300 ≤ D := by have h : (300:ℝ) ≤ (D:ℝ) := le_of_lt (lt_of_lt_of_le hx_gt hx_le_D) exact_mod_cast h change 300 ≤ D ∧ 12 * (T:ℝ) * Real.exp (-(((D:ℝ)/40)^3)) ≤ (T:ℝ)^(-1:ℝ) constructor · exact hD_ge_300 · have hlogT_nonneg : 0 ≤ Real.log (T:ℝ) := by have hpos : (0:ℝ) < Real.log (2:ℝ) := by linarith [hlog2gt] linarith have hr_nonneg : 0 ≤ (Real.log (T:ℝ)) ^ ((1:ℝ)/3) := Real.rpow_nonneg hlogT_nonneg _ have hr_cube : ((Real.log (T:ℝ)) ^ ((1:ℝ)/3))^3 = Real.log (T:ℝ) := by rw [show ((1:ℝ)/3) = ((3:ℕ):ℝ)⁻¹ by norm_num] apply Real.rpow_inv_natCast_pow · exact hlogT_nonneg · norm_num have hD_div : (10:ℝ) * ((Real.log (T:ℝ)) ^ ((1:ℝ)/3)) ≤ (D:ℝ)/40 := by nlinarith have hcubeD : 1000 * Real.log (T:ℝ) ≤ ((D:ℝ)/40)^3 := by have hmono : (10 * ((Real.log (T:ℝ)) ^ ((1:ℝ)/3)))^3 ≤ ((D:ℝ)/40)^3 := by apply pow_le_pow_left₀ (by positivity) hD_div 3 calc 1000 * Real.log (T:ℝ) = (10 * ((Real.log (T:ℝ)) ^ ((1:ℝ)/3)))^3 := by rw [show (10 * ((Real.log (T:ℝ)) ^ ((1:ℝ)/3)))^3 = 1000 * (((Real.log (T:ℝ)) ^ ((1:ℝ)/3))^3) by ring] rw [hr_cube] _ ≤ ((D:ℝ)/40)^3 := hmono have hexp_le : Real.exp (-(((D:ℝ)/40)^3)) ≤ (T:ℝ)^(-1000:ℝ) := by have h1 : Real.exp (-(((D:ℝ)/40)^3)) ≤ Real.exp (-(1000 * Real.log (T:ℝ))) := by apply Real.exp_le_exp.mpr linarith have h2 : Real.exp (-(1000 * Real.log (T:ℝ))) = (T:ℝ)^(-1000:ℝ) := by rw [Real.rpow_def_of_pos hTpos] congr 1 ring exact h1.trans_eq h2 have htail1 : 12 * (T:ℝ) * Real.exp (-(((D:ℝ)/40)^3)) ≤ 12 * (T:ℝ) * (T:ℝ)^(-1000:ℝ) := by apply mul_le_mul_of_nonneg_left hexp_le positivity have hT_mul : (T:ℝ) * (T:ℝ)^(-1000:ℝ) = (T:ℝ)^(-999:ℝ) := by calc (T:ℝ) * (T:ℝ)^(-1000:ℝ) = (T:ℝ)^(1:ℝ) * (T:ℝ)^(-1000:ℝ) := by rw [Real.rpow_one] _ = (T:ℝ)^((1:ℝ) + (-1000:ℝ)) := by rw [Real.rpow_add hTpos] _ = (T:ℝ)^(-999:ℝ) := by norm_num have h12le : (12:ℝ) ≤ (T:ℝ)^998 := by have hpow : (2:ℝ)^998 ≤ (T:ℝ)^998 := pow_le_pow_left₀ (by norm_num) hTreal 998 have h12_2pow : (12:ℝ) ≤ (2:ℝ)^998 := by calc (12:ℝ) ≤ (2:ℝ)^4 := by norm_num _ ≤ (2:ℝ)^998 := pow_le_pow_right₀ (by norm_num : (1:ℝ) ≤ 2) (by norm_num : 4 ≤ 998) exact le_trans h12_2pow hpow have hpow_mul : (T:ℝ)^998 * (T:ℝ)^(-999:ℝ) = (T:ℝ)^(-1:ℝ) := by calc (T:ℝ)^998 * (T:ℝ)^(-999:ℝ) = (T:ℝ)^(998:ℝ) * (T:ℝ)^(-999:ℝ) := by norm_num _ = (T:ℝ)^((998:ℝ) + (-999:ℝ)) := by rw [Real.rpow_add hTpos] _ = (T:ℝ)^(-1:ℝ) := by norm_num have htail2 : 12 * (T:ℝ) * (T:ℝ)^(-1000:ℝ) ≤ (T:ℝ)^(-1:ℝ) := by calc 12 * (T:ℝ) * (T:ℝ)^(-1000:ℝ) = 12 * ((T:ℝ) * (T:ℝ)^(-1000:ℝ)) := by ring _ = 12 * (T:ℝ)^(-999:ℝ) := by rw [hT_mul] _ ≤ (T:ℝ)^998 * (T:ℝ)^(-999:ℝ) := by apply mul_le_mul_of_nonneg_right h12le exact Real.rpow_nonneg (by positivity) _ _ = (T:ℝ)^(-1:ℝ) := hpow_mul exact le_trans htail1 htail2