AFTD Auto-Formalizing Theoretical Domains

op_902_tail_bound_implies_poly_bound

theoremverified

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.

  1. 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.

    lines 7–11

      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
  2. (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.

    lines 12–21

    uses Real.log_le_log, Real.log_two_gt_d9, lt_of_lt_of_le

      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
  3. 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).

    lines 22–31

    uses Real.rpow_natCast, Real.rpow_mul, Real.rpow_lt_rpow

      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
  4. 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.

    lines 32–41

    uses Nat.le_ceil, lt_of_lt_of_le, le_of_lt

      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
  5. 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.

    lines 42–62

    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
  6. 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.

    lines 63–74

    uses Real.exp_le_exp.mpr, Real.rpow_def_of_pos, mul_le_mul_of_nonneg_left

        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
  7. 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.

    lines 75–100

    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_trans

        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
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

/-- 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
See it in the graphDiscuss this resultChallenge it