layered_capacity_geometric_inequality
Let t ≥ 4 be an integer, g = 1 + 1/t and q = g^(t−3). Then t·g^ℓ ≥ q·(ℓ + 3) for every integer ℓ ≥ 0; in particular q ≤ t/3.
Statement
theorem layered_capacity_geometric_inequality (t : ℕ) (ht : 4 ≤ t) :
(∀ ℓ : ℕ, (1 + 1 / (t : ℝ)) ^ (t - 3) * (ℓ + 3) ≤ t * (1 + 1 / (t : ℝ)) ^ ℓ) ∧
(1 + 1 / (t : ℝ)) ^ (t - 3) ≤ t / 3- Formalizes
- arXiv:2610.15520 (Improving the bounds on approximating weighted maximin shares of chores), Lemma 5.3; the proof here uses Bernoulli's inequality instead of the ratio argument.
- Verified
- 14 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof establishes the inequality g^(t - 3) * (ℓ + 3) ≤ t * g^ℓ by comparing ℓ with t - 3. If ℓ ≥ t - 3, writing ℓ = (t - 3) + j reduces the claim to t + j ≤ t * g^j, which follows directly from Bernoulli's inequality g^j ≥ 1 + j/t. If ℓ < t - 3, setting t - 3 = ℓ + (i + 1) and using the reciprocal base 1 - 1/(t + 1) = g^(-1) reduces the claim to t - (i + 1) ≤ t * (1 - 1/(t + 1))^(i + 1), which again follows from Bernoulli's inequality since t/(t + 1) ≤ 1. Finally, evaluating the main inequality at ℓ = 0 immediately gives 3 * g^(t - 3) ≤ t, hence g^(t - 3) ≤ t / 3.
t ≥ 4 > 0 over the reals, and g = 1 + 1/t > 0.
Cast the hypothesis t ≥ 4 from ℕ to ℝ, which immediately gives t > 0. Define g = 1 + 1/t, which is strictly positive because t > 0.
have htR : (4 : ℝ) ≤ t := by exact_mod_cast ht have htpos : (0 : ℝ) < t := by linarith set g : ℝ := 1 + 1 / (t : ℝ) with hg have hg0 : 0 < g := by positivity
It suffices to establish g^(t - 3) * (ℓ + 3) ≤ t * g^ℓ for all ℓ ∈ ℕ, split into cases t - 3 ≤ ℓ and ℓ < t - 3.
Introduce ℓ to prove the universal inequality `key`. By totality of order (`le_or_gt`), either t - 3 ≤ ℓ or ℓ < t - 3.
uses
le_or_gthave key : ∀ ℓ : ℕ, g ^ (t - 3) * (ℓ + 3) ≤ t * g ^ ℓ := by intro ℓ rcases le_or_gt (t - 3) ℓ with hle | hlt
When ℓ ≥ t - 3, the inequality g^(t - 3) * (ℓ + 3) ≤ t * g^ℓ holds.
Write ℓ = (t - 3) + j for some j ∈ ℕ using `Nat.exists_eq_add_of_le`. Bernoulli's inequality `one_add_mul_le_pow` gives g^j = (1 + 1/t)^j ≥ 1 + j/t. Multiplying this by t > 0 and canceling t * (1/t) = 1 yields t + j ≤ t * g^j. Multiplying both sides by the positive factor g^(t - 3) and noting that (t - 3 + j) + 3 = t + j establishes g^(t - 3) * (ℓ + 3) ≤ t * g^(t - 3) * g^j = t * g^ℓ by `pow_add`.
uses
Nat.exists_eq_add_of_le,one_add_mul_le_pow,Nat.cast_sub,pow_add,pow_pos,mul_le_mul_of_nonneg_left,mul_add,mul_one,mul_assoc,mul_comm,mul_one_div_cancel· -- ℓ = (t - 3) + j : Bernoulli for g ^ j obtain ⟨j, rfl⟩ := Nat.exists_eq_add_of_le hle have hB : 1 + (j : ℝ) * (1 / t) ≤ g ^ j := one_add_mul_le_pow (by have : (0 : ℝ) ≤ 1 / t := by positivity linarith) j have hcast : ((t - 3 + j : ℕ) : ℝ) + 3 = t + j := by push_cast [Nat.cast_sub (show 3 ≤ t by omega)] ring rw [hcast, pow_add] have hpow : 0 < g ^ (t - 3) := pow_pos hg0 _ have : (t : ℝ) + j ≤ t * g ^ j := by have := mul_le_mul_of_nonneg_left hB htpos.le rw [mul_add, mul_one, ← mul_assoc, mul_comm (t : ℝ) j, mul_assoc, mul_one_div_cancel htpos.ne', mul_one] at this linarith calc g ^ (t - 3) * ((t : ℝ) + j) ≤ g ^ (t - 3) * (t * g ^ j) := mul_le_mul_of_nonneg_left this hpow.le _ = t * (g ^ (t - 3) * g ^ j) := by ring
When ℓ < t - 3, writing t - 3 = ℓ + (i + 1) and setting h = 1/(t + 1), we have g * (1 - h) = 1 and (1 - h)^(i + 1) ≥ 1 - (i + 1)h.
From ℓ < t - 3, obtain i ∈ ℕ such that t - 3 = ℓ + (i + 1) via `Nat.exists_eq_add_of_lt`. Setting h = 1/(t + 1), direct calculation shows g * (1 - h) = ((t + 1)/t) * (t/(t + 1)) = 1. Since t ≥ 4 implies h ≤ 1, we have -h ≥ -1 ≥ -2, so Bernoulli's inequality `one_add_mul_le_pow` applies with -h and exponent i + 1, giving (1 - h)^(i + 1) ≥ 1 - (i + 1)h.
uses
Nat.exists_eq_add_of_lt,one_add_mul_le_pow,div_le_one,sub_eq_add_neg· -- t - 3 = ℓ + i : Bernoulli for (1 - 1/(t+1)) ^ i, whose product with g ^ i is 1 obtain ⟨i, hi⟩ := Nat.exists_eq_add_of_lt hlt set h : ℝ := 1 / ((t : ℝ) + 1) with hh have hh0 : 0 ≤ h := by positivity have hgh : g * (1 - h) = 1 := by rw [hg, hh] field_simp ring have hB : 1 + ((i + 1 : ℕ) : ℝ) * (-h) ≤ (1 - h) ^ (i + 1) := by have := one_add_mul_le_pow (show (-2 : ℝ) ≤ -h by have : h ≤ 1 := by rw [hh, div_le_one (by linarith)]; linarith linarith) (i + 1) simpa [sub_eq_add_neg] using this
ℓ + 3 = t - (i + 1), g^(t - 3) = g^ℓ * g^(i + 1), and g^(i + 1) * (1 - h)^(i + 1) = 1.
Rearranging t - 3 = ℓ + (i + 1) gives t = ℓ + (i + 1) + 3, so ℓ + 3 = t - (i + 1). Splitting the exponent gives g^(t - 3) = g^ℓ * g^(i + 1) by `pow_add`. Distributing powers over products gives g^(i + 1) * (1 - h)^(i + 1) = (g * (1 - h))^(i + 1) = 1^(i + 1) = 1 via `mul_pow` and `one_pow`.
uses
pow_add,mul_pow,one_powhave hcast : (ℓ : ℝ) + 3 = t - ((i + 1 : ℕ) : ℝ) := by have : t = ℓ + (i + 1) + 3 := by omega rw [this] push_cast ring rw [hi, show ℓ + i + 1 = ℓ + (i + 1) by ring, pow_add, hcast] have hgi : g ^ (i + 1) * (1 - h) ^ (i + 1) = 1 := by rw [← mul_pow, hgh, one_pow]
t - (i + 1) ≤ t * (1 - h)^(i + 1).
Multiplying the Bernoulli bound 1 - (i + 1)h ≤ (1 - h)^(i + 1) by t > 0 gives t - t(i + 1)h ≤ t(1 - h)^(i + 1). Since t * h = t/(t + 1) ≤ 1 by `div_le_one` and i + 1 ≥ 0, we have t(i + 1)h ≤ i + 1, hence t - (i + 1) ≤ t - t(i + 1)h ≤ t(1 - h)^(i + 1).
uses
mul_le_mul_of_nonneg_left,mul_one_div,div_le_one,Nat.cast_nonneghave hti : (t : ℝ) - ((i + 1 : ℕ) : ℝ) ≤ t * (1 - h) ^ (i + 1) := by have h1 : (t : ℝ) * (1 + ((i + 1 : ℕ) : ℝ) * (-h)) ≤ t * (1 - h) ^ (i + 1) := mul_le_mul_of_nonneg_left hB htpos.le have h2 : (t : ℝ) * h ≤ 1 := by rw [hh, mul_one_div, div_le_one (by linarith)] linarith have h3 : (0 : ℝ) ≤ ((i + 1 : ℕ) : ℝ) := Nat.cast_nonneg _ nlinarith
When ℓ < t - 3, the inequality g^(t - 3) * (ℓ + 3) ≤ t * g^ℓ holds.
Multiplying t - (i + 1) ≤ t * (1 - h)^(i + 1) by the positive factor g^ℓ * g^(i + 1) preserves the inequality. Regrouping the right-hand side produces t * g^ℓ * (g^(i + 1) * (1 - h)^(i + 1)) = t * g^ℓ * 1 = t * g^ℓ, which matches the required bound since the left-hand side is g^(t - 3) * (ℓ + 3).
uses
pow_pos,mul_le_mul_of_nonneg_left,mul_onehave hpos : 0 < g ^ ℓ := pow_pos hg0 _ have hpos' : 0 < g ^ (i + 1) := pow_pos hg0 _ calc g ^ ℓ * g ^ (i + 1) * ((t : ℝ) - ((i + 1 : ℕ) : ℝ)) ≤ g ^ ℓ * g ^ (i + 1) * (t * (1 - h) ^ (i + 1)) := mul_le_mul_of_nonneg_left hti (by positivity) _ = t * g ^ ℓ * (g ^ (i + 1) * (1 - h) ^ (i + 1)) := by ring _ = t * g ^ ℓ := by rw [hgi, mul_one]
Both conjuncts hold: g^(t - 3) * (ℓ + 3) ≤ t * g^ℓ for all ℓ, and g^(t - 3) ≤ t / 3.
The key inequality handles the first conjunct. Evaluating it at ℓ = 0 gives g^(t - 3) * (0 + 3) ≤ t * g^0, which simplifies via `zero_add`, `pow_zero`, and `mul_one` to 3 * g^(t - 3) ≤ t. Dividing by 3 yields g^(t - 3) ≤ t / 3.
uses
CharP.cast_eq_zero,zero_add,pow_zero,mul_onerefine ⟨key, ?_⟩ have := key 0 simp only [CharP.cast_eq_zero, zero_add, pow_zero, mul_one] at this linarith
le_or_gt- In a linear order, for any two elements either a ≤ b or b < a.
Nat.exists_eq_add_of_le- If m ≤ n for natural numbers, then n = m + k for some natural number k.
one_add_mul_le_pow- Bernoulli's inequality: (1 + a)^n ≥ 1 + na for any real a ≥ -2 and natural number n.
Nat.cast_sub- The cast of the natural difference n - m equals the difference of the casts, provided m ≤ n.
pow_add- Exponents add under multiplication: a^(m + n) = a^m * a^n.
pow_pos- Any natural power of a strictly positive element is strictly positive.
mul_le_mul_of_nonneg_left- Multiplying an inequality b ≤ c on the left by a nonnegative element a ≥ 0 yields a * b ≤ a * c.
mul_add- Left distributivity of multiplication over addition: a * (b + c) = a * b + a * c.
mul_one- Multiplying on the right by 1 leaves an element unchanged: a * 1 = a.
mul_assoc- Multiplication is associative: (a * b) * c = a * (b * c).
mul_comm- Multiplication is commutative: a * b = b * a.
mul_one_div_cancel- Multiplying a nonzero element by its reciprocal gives 1: a * (1 / a) = 1.
Nat.exists_eq_add_of_lt- If m < n for natural numbers, then n = m + k + 1 for some natural number k.
div_le_one- For b > 0, a / b ≤ 1 if and only if a ≤ b.
sub_eq_add_neg- Subtraction equals addition of the additive inverse: a - b = a + (-b).
mul_pow- In a commutative monoid, powers distribute over multiplication: (a * b)^n = a^n * b^n.
one_pow- Any power of 1 is 1: 1^n = 1.
mul_one_div- Multiplying by 1 / y equals division by y: x * (1 / y) = x / y.
Nat.cast_nonneg- The cast of any natural number into an ordered semiring is nonnegative.
CharP.cast_eq_zero- In characteristic p, the cast of p is 0; in particular, casting 0 from ℕ gives 0.
zero_add- Adding zero on the left is the identity: 0 + a = a.
pow_zero- Any element raised to the zeroth power equals 1: a^0 = 1.
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 layered_capacity_geometric_inequality (t : ℕ) (ht : 4 ≤ t) : (∀ ℓ : ℕ, (1 + 1 / (t : ℝ)) ^ (t - 3) * (ℓ + 3) ≤ t * (1 + 1 / (t : ℝ)) ^ ℓ) ∧ (1 + 1 / (t : ℝ)) ^ (t - 3) ≤ t / 3 := by have htR : (4 : ℝ) ≤ t := by exact_mod_cast ht have htpos : (0 : ℝ) < t := by linarith set g : ℝ := 1 + 1 / (t : ℝ) with hg have hg0 : 0 < g := by positivity have key : ∀ ℓ : ℕ, g ^ (t - 3) * (ℓ + 3) ≤ t * g ^ ℓ := by intro ℓ rcases le_or_gt (t - 3) ℓ with hle | hlt · -- ℓ = (t - 3) + j : Bernoulli for g ^ j obtain ⟨j, rfl⟩ := Nat.exists_eq_add_of_le hle have hB : 1 + (j : ℝ) * (1 / t) ≤ g ^ j := one_add_mul_le_pow (by have : (0 : ℝ) ≤ 1 / t := by positivity linarith) j have hcast : ((t - 3 + j : ℕ) : ℝ) + 3 = t + j := by push_cast [Nat.cast_sub (show 3 ≤ t by omega)] ring rw [hcast, pow_add] have hpow : 0 < g ^ (t - 3) := pow_pos hg0 _ have : (t : ℝ) + j ≤ t * g ^ j := by have := mul_le_mul_of_nonneg_left hB htpos.le rw [mul_add, mul_one, ← mul_assoc, mul_comm (t : ℝ) j, mul_assoc, mul_one_div_cancel htpos.ne', mul_one] at this linarith calc g ^ (t - 3) * ((t : ℝ) + j) ≤ g ^ (t - 3) * (t * g ^ j) := mul_le_mul_of_nonneg_left this hpow.le _ = t * (g ^ (t - 3) * g ^ j) := by ring · -- t - 3 = ℓ + i : Bernoulli for (1 - 1/(t+1)) ^ i, whose product with g ^ i is 1 obtain ⟨i, hi⟩ := Nat.exists_eq_add_of_lt hlt set h : ℝ := 1 / ((t : ℝ) + 1) with hh have hh0 : 0 ≤ h := by positivity have hgh : g * (1 - h) = 1 := by rw [hg, hh] field_simp ring have hB : 1 + ((i + 1 : ℕ) : ℝ) * (-h) ≤ (1 - h) ^ (i + 1) := by have := one_add_mul_le_pow (show (-2 : ℝ) ≤ -h by have : h ≤ 1 := by rw [hh, div_le_one (by linarith)]; linarith linarith) (i + 1) simpa [sub_eq_add_neg] using this have hcast : (ℓ : ℝ) + 3 = t - ((i + 1 : ℕ) : ℝ) := by have : t = ℓ + (i + 1) + 3 := by omega rw [this] push_cast ring rw [hi, show ℓ + i + 1 = ℓ + (i + 1) by ring, pow_add, hcast] have hgi : g ^ (i + 1) * (1 - h) ^ (i + 1) = 1 := by rw [← mul_pow, hgh, one_pow] have hti : (t : ℝ) - ((i + 1 : ℕ) : ℝ) ≤ t * (1 - h) ^ (i + 1) := by have h1 : (t : ℝ) * (1 + ((i + 1 : ℕ) : ℝ) * (-h)) ≤ t * (1 - h) ^ (i + 1) := mul_le_mul_of_nonneg_left hB htpos.le have h2 : (t : ℝ) * h ≤ 1 := by rw [hh, mul_one_div, div_le_one (by linarith)] linarith have h3 : (0 : ℝ) ≤ ((i + 1 : ℕ) : ℝ) := Nat.cast_nonneg _ nlinarith have hpos : 0 < g ^ ℓ := pow_pos hg0 _ have hpos' : 0 < g ^ (i + 1) := pow_pos hg0 _ calc g ^ ℓ * g ^ (i + 1) * ((t : ℝ) - ((i + 1 : ℕ) : ℝ)) ≤ g ^ ℓ * g ^ (i + 1) * (t * (1 - h) ^ (i + 1)) := mul_le_mul_of_nonneg_left hti (by positivity) _ = t * g ^ ℓ * (g ^ (i + 1) * (1 - h) ^ (i + 1)) := by ring _ = t * g ^ ℓ := by rw [hgi, mul_one] refine ⟨key, ?_⟩ have := key 0 simp only [CharP.cast_eq_zero, zero_add, pow_zero, mul_one] at this linarith