forest_carpool_envelope_exp
At every positive integer level, the Fibonacci tail envelope is at most exp(-(log 2 / 4) times 2 to the power of half the level).
Statement
theorem forest_carpool_envelope_exp (D : ℕ) (hD : 1 ≤ D) :
forest_carpool_tail_envelope D ≤
Real.exp (-(Real.log 2 / 4) * (2 : ℝ) ^ ((D : ℝ) / 2))- Source
- Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- forest_carpool_tail_envelopeThe proposed one-sided discrepancy tail envelope is 3/8 at level 2 and otherwise two to the negative Fibonacci number of the level.
- forest_carpool_fibonacci_growthFor every integer level D at least 2, its Fibonacci number is at least 2 to the power (D-2)/2.
- Used by 1
- op_1106_forest_carpooling_random_greedy_double_exponential_tailThere exist absolute positive real constants c, C, and a such that for every natural number n, every forest edge sequence of length T ≥ 2…
The proof, explained
The proof bounds the tail envelope forest_carpool_tail_envelope(D) from above by (1/2)^(F_D) and rewrites this base-1/2 power as exp(-ln(2) * F_D). A Fibonacci growth lower bound establishes that F_D ≥ 2^(D/2) / 4 for all D ≥ 1. Multiplying this inequality by -ln 2 reverses the inequality on the exponents, and applying the monotonicity of the exponential function completes the bound.
The natural logarithm of 2 is strictly positive: ln 2 > 0.
Since 1 < 2, the strict monotonicity of the logarithm (`Real.log_pos`) gives ln 2 > 0.
uses
Real.log_poshave hlog : 0 < Real.log 2 := Real.log_pos (by norm_num)
The tail envelope at D is bounded above by (1/2)^(F_D), where F_D is the D-th Fibonacci number.
Unfolding the definition of `forest_carpool_tail_envelope`, there are two cases: when D = 2, the envelope is 3/8 and F_2 = 1, so 3/8 ≤ (1/2)¹ = 1/2; when D ≠ 2, the envelope is (1/2)^(F_D) by definition, which equals itself reflexively.
uses
Nat.fibhave hU : forest_carpool_tail_envelope D ≤ (1 / 2 : ℝ) ^ Nat.fib D := by unfold forest_carpool_tail_envelope split_ifs with h · subst D norm_num [Nat.fib] · rfl
The power (1/2)^(F_D) can be rewritten as exp(-ln(2) * F_D).
By the definition of real powers, (1/2)^(F_D) = exp(ln(1/2) * F_D). Since 1/2 = 2⁻¹ and ln(2⁻¹) = -ln 2, this simplifies to exp(-ln(2) * F_D).
uses
Real.rpow_natCast,Real.rpow_def_of_pos,one_div,Real.log_invhave hpow : (1 / 2 : ℝ) ^ Nat.fib D = Real.exp (-Real.log 2 * (Nat.fib D : ℝ)) := by calc _ = (1 / 2 : ℝ) ^ ((Nat.fib D : ℕ) : ℝ) := (Real.rpow_natCast _ _).symm _ = Real.exp (Real.log (1 / 2 : ℝ) * (Nat.fib D : ℝ)) := Real.rpow_def_of_pos (by norm_num) _ _ = _ := by rw [show Real.log (1 / 2 : ℝ) = -Real.log 2 by rw [one_div, Real.log_inv]]
The quantity 2^(D/2) is non-negative: 0 ≤ 2^(D/2). automation
Powers of positive numbers are non-negative, which is verified automatically by the `positivity` tactic.
have hz : 0 ≤ (2 : ℝ) ^ ((D : ℝ) / 2) := by positivity
The D-th Fibonacci number satisfies 2^(D/2) / 4 ≤ F_D.
We split into cases on D ≥ 1. If D = 1, then F_1 = 1; since 1/2 ≤ 1, monotonicity of powers yields 2^(1/2) ≤ 2¹ = 2, and therefore 2^(1/2)/4 ≤ 2/4 ≤ 1. If D ≥ 2, we invoke `forest_carpool_fibonacci_growth` to get 2^((D - 2)/2) ≤ F_D. Rewriting the exponent as (D - 2)/2 = D/2 - 1, the power becomes 2^(D/2) / 2, which is at least 2^(D/2) / 4.
uses
Real.rpow_le_rpow_of_exponent_le,Nat.fib,Real.rpow_one,forest_carpool_fibonacci_growth,Real.rpow_subhave hfib : (2 : ℝ) ^ ((D : ℝ) / 2) / 4 ≤ (Nat.fib D : ℝ) := by by_cases h1 : D = 1 · subst D have hr := Real.rpow_le_rpow_of_exponent_le (show (1 : ℝ) ≤ 2 by norm_num) (show (1 : ℝ) / 2 ≤ 1 by norm_num) norm_num [Nat.fib, Real.rpow_one] at hr ⊢ <;> linarith · have h2 : 2 ≤ D := by omega have hg := forest_carpool_fibonacci_growth D h2 have he : (((D : ℝ) - 2) / 2) = (D : ℝ) / 2 - 1 := by ring rw [he, Real.rpow_sub (by norm_num : (0 : ℝ) < 2), Real.rpow_one] at hg linarith
The exponent satisfies -ln(2) * F_D ≤ -(ln(2) / 4) * 2^(D/2).
Multiplying 2^(D/2) / 4 ≤ F_D by the non-negative scalar ln 2 preserves the inequality, giving ln(2) * (2^(D/2) / 4) ≤ ln(2) * F_D. Negating both sides reverses the direction, yielding -ln(2) * F_D ≤ -(ln(2) / 4) * 2^(D/2), which is closed by nonlinear arithmetic.
uses
mul_le_mul_of_nonneg_left,le_of_lthave hmul := mul_le_mul_of_nonneg_left hfib (le_of_lt hlog) have hexp : -Real.log 2 * (Nat.fib D : ℝ) ≤ -(Real.log 2 / 4) * (2 : ℝ) ^ ((D : ℝ) / 2) := by nlinarith
The tail envelope satisfies forest_carpool_tail_envelope D ≤ exp(-(ln(2) / 4) * 2^(D/2)).
We chain the inequalities: the tail envelope is bounded by (1/2)^(F_D), which equals exp(-ln(2) * F_D). Since exp is monotonically increasing, applying it to -ln(2) * F_D ≤ -(ln(2) / 4) * 2^(D/2) yields the desired final bound.
uses
Real.exp_le_exp.mprcalc _ ≤ (1 / 2 : ℝ) ^ Nat.fib D := hU _ = Real.exp (-Real.log 2 * (Nat.fib D : ℝ)) := hpow _ ≤ _ := Real.exp_le_exp.mpr hexp
Real.log_pos- If x > 1, then ln(x) > 0.
Nat.fib- The n-th Fibonacci number.
Real.rpow_natCast- Real exponentiation by a natural number cast to the reals agrees with standard natural-power exponentiation.
Real.rpow_def_of_pos- For x > 0 and any real y, x^y = exp(ln(x) * y).
one_div- For any invertible element a, 1 / a = a⁻¹.
Real.log_inv- For any real x, ln(x⁻¹) = -ln(x).
Real.rpow_le_rpow_of_exponent_le- For base x ≥ 1, if y ≤ z then x^y ≤ x^z.
Real.rpow_one- Any real number raised to the power 1 equals itself.
forest_carpool_fibonacci_growth- For any integer D ≥ 2, the D-th Fibonacci number satisfies 2^((D - 2) / 2) ≤ F_D.
Real.rpow_sub- For x > 0 and real numbers y and z, x^(y - z) = x^y / x^z.
mul_le_mul_of_nonneg_left- If b ≤ c and a ≥ 0, then a * b ≤ a * c.
le_of_lt- A strict inequality a < b implies the non-strict inequality a ≤ b.
Real.exp_le_exp.mpr- The real exponential function is order-preserving: if x ≤ y, then exp(x) ≤ exp(y).
- Line 18 establishes non-negativity of 2^(D/2) via `positivity` as an auxiliary fact to assist the nonlinear arithmetic tactic `nlinarith` on line 32.
- The case D = 1 is treated separately in bounding the Fibonacci number because the induction lemma `forest_carpool_fibonacci_growth` requires 2 ≤ D.
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.
theorem forest_carpool_envelope_exp (D : ℕ) (hD : 1 ≤ D) : forest_carpool_tail_envelope D ≤ Real.exp (-(Real.log 2 / 4) * (2 : ℝ) ^ ((D : ℝ) / 2)) := by have hlog : 0 < Real.log 2 := Real.log_pos (by norm_num) have hU : forest_carpool_tail_envelope D ≤ (1 / 2 : ℝ) ^ Nat.fib D := by unfold forest_carpool_tail_envelope split_ifs with h · subst D norm_num [Nat.fib] · rfl have hpow : (1 / 2 : ℝ) ^ Nat.fib D = Real.exp (-Real.log 2 * (Nat.fib D : ℝ)) := by calc _ = (1 / 2 : ℝ) ^ ((Nat.fib D : ℕ) : ℝ) := (Real.rpow_natCast _ _).symm _ = Real.exp (Real.log (1 / 2 : ℝ) * (Nat.fib D : ℝ)) := Real.rpow_def_of_pos (by norm_num) _ _ = _ := by rw [show Real.log (1 / 2 : ℝ) = -Real.log 2 by rw [one_div, Real.log_inv]] have hz : 0 ≤ (2 : ℝ) ^ ((D : ℝ) / 2) := by positivity have hfib : (2 : ℝ) ^ ((D : ℝ) / 2) / 4 ≤ (Nat.fib D : ℝ) := by by_cases h1 : D = 1 · subst D have hr := Real.rpow_le_rpow_of_exponent_le (show (1 : ℝ) ≤ 2 by norm_num) (show (1 : ℝ) / 2 ≤ 1 by norm_num) norm_num [Nat.fib, Real.rpow_one] at hr ⊢ <;> linarith · have h2 : 2 ≤ D := by omega have hg := forest_carpool_fibonacci_growth D h2 have he : (((D : ℝ) - 2) / 2) = (D : ℝ) / 2 - 1 := by ring rw [he, Real.rpow_sub (by norm_num : (0 : ℝ) < 2), Real.rpow_one] at hg linarith have hmul := mul_le_mul_of_nonneg_left hfib (le_of_lt hlog) have hexp : -Real.log 2 * (Nat.fib D : ℝ) ≤ -(Real.log 2 / 4) * (2 : ℝ) ^ ((D : ℝ) / 2) := by nlinarith calc _ ≤ (1 / 2 : ℝ) ^ Nat.fib D := hU _ = Real.exp (-Real.log 2 * (Nat.fib D : ℝ)) := hpow _ ≤ _ := Real.exp_le_exp.mpr hexp