AFTD Auto-Formalizing Theoretical Domains

nae_p_rule_strong_rate_separation

theoremverified

For every real C there is a natural d such that C(3/√2)^d is strictly less than (1/2)(12/5)^d.

Statement

theorem nae_p_rule_strong_rate_separation (C : ℝ) :
    ∃ d : ℕ, C * (3 / Real.sqrt 2) ^ d < (1 / 2 : ℝ) * (12 / 5 : ℝ) ^ d
Source
Consequence of nae_p_schedule_lower_bound_strong; related rules: arXiv:1211.0721, Section 3.3.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The theorem compares the exponential growth of (3/√2)^d and (12/5)^d. Because 3/√2 < 12/5, the ratio r = (12/5) / (3/√2) is strictly greater than 1. Since powers of r grow without bound, there is an exponent d such that r^d > 2C, which upon clearing the denominator and dividing by 2 yields the desired inequality.

  1. The ratio between the bases 12/5 and a = 3/√2 is strictly greater than 1.

    Let a = 3/√2. Since a > 0 and a < 12/5 by nae_p_rule_strong_base_exceeds_adversary_base, dividing by a via one_lt_div shows that 1 < (12/5) / a.

    lines 3–6

    uses nae_p_rule_strong_base_exceeds_adversary_base, one_lt_div

      let a : ℝ := 3 / Real.sqrt 2
      have ha : 0 < a := by dsimp [a]; positivity
      have hab : a < (12 / 5 : ℝ) := nae_p_rule_strong_base_exceeds_adversary_base
      have hr : 1 < (12 / 5 : ℝ) / a := (one_lt_div ha).2 hab
  2. There is an exponent d such that 2C < (12/5)^d / a^d.

    Because the ratio (12/5) / a is strictly greater than 1, its powers eventually exceed any given real number by pow_unbounded_of_one_lt, yielding a natural number d such that 2C < ((12/5) / a)^d. Distributing the exponent over division via div_pow gives 2C < (12/5)^d / a^d.

    lines 7–9

    uses pow_unbounded_of_one_lt, div_pow

      obtain ⟨d, hd⟩ := pow_unbounded_of_one_lt (2 * C) hr
      have hd' : 2 * C < (12 / 5 : ℝ) ^ d / a ^ d := by
        simpa [div_pow] using hd
  3. Clearing the denominator gives 2C * a^d < (12/5)^d.

    Since a > 0, its power a^d is also positive by pow_pos. Multiplying both sides by a^d using lt_div_iff₀ transforms the inequality into 2C * a^d < (12/5)^d.

    lines 10–11

    uses pow_pos, lt_div_iff₀

      have ha' : 0 < a ^ d := pow_pos ha d
      have hmul := (lt_div_iff₀ ha').mp hd'
  4. The natural number d satisfies C * (3/√2)^d < (1/2) * (12/5)^d.

    We provide d as the required witness. Expanding a back to 3/√2 in 2C * a^d < (12/5)^d and dividing through by 2 completes the proof via arithmetic.

    lines 12–14

      refine ⟨d, ?_⟩
      dsimp [a] at hmul
      nlinarith
nae_p_rule_strong_base_exceeds_adversary_base
The constant 3 / √2 is strictly less than 12/5.
one_lt_div
For b > 0, 1 < a / b if and only if b < a.
pow_unbounded_of_one_lt
In an Archimedean ordered semiring, if y > 1, then for any x there is a natural exponent n such that x < y^n.
div_pow
(a / b)^n = a^n / b^n for all elements in a division group and natural exponents n.
pow_pos
If a > 0, then a^n > 0 for every natural number n.
lt_div_iff₀
For c > 0, a < b / c if and only if a * c < b.

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 nae_p_rule_strong_rate_separation (C : ℝ) :    ∃ d : ℕ, C * (3 / Real.sqrt 2) ^ d < (1 / 2 : ℝ) * (12 / 5 : ℝ) ^ d := by  let a : ℝ := 3 / Real.sqrt 2  have ha : 0 < a := by dsimp [a]; positivity  have hab : a < (12 / 5 : ℝ) := nae_p_rule_strong_base_exceeds_adversary_base  have hr : 1 < (12 / 5 : ℝ) / a := (one_lt_div ha).2 hab  obtain ⟨d, hd⟩ := pow_unbounded_of_one_lt (2 * C) hr  have hd' : 2 * C < (12 / 5 : ℝ) ^ d / a ^ d := by    simpa [div_pow] using hd  have ha' : 0 < a ^ d := pow_pos ha d  have hmul := (lt_div_iff₀ ha').mp hd'  refine ⟨d, ?_⟩  dsimp [a] at hmul  nlinarith
See it in the graphDiscuss this resultChallenge it