AFTD Auto-Formalizing Theoretical Domains

layered_capacity_geometric_inequality

theoremverifiedformalization

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.

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

    lines 4–7

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

    lines 8–10

    uses le_or_gt

      have key : ∀ ℓ : ℕ, g ^ (t - 3) * (ℓ + 3) ≤ t * g ^ ℓ := by
        intro ℓ
        rcases le_or_gt (t - 3) ℓ with hle | hlt
  3. 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`.

    lines 11–28

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

    lines 29–41

    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
  5. ℓ + 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`.

    lines 42–48

    uses pow_add, mul_pow, one_pow

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

    lines 49–56

    uses mul_le_mul_of_nonneg_left, mul_one_div, div_le_one, Nat.cast_nonneg

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

    lines 57–63

    uses pow_pos, mul_le_mul_of_nonneg_left, mul_one

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

    lines 64–67

    uses CharP.cast_eq_zero, zero_add, pow_zero, mul_one

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

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