AFTD Auto-Formalizing Theoretical Domains

tarski_box_query_le_log_sq_of_nat_budget

theoremverified

Assembly step: if some natural constant C gives, for every n ≥ 2, a five-dimensional box algorithm with at most C·(log₂ n + 2)² queries, then the real-constant O(log² n) box statement holds (with constant 9C + 1). Hence the target is equivalent in practice to the ℕ-valued budget form, and log-arithmetic can be kept out of the algorithmic argument entirely.

Statement

theorem tarski_box_query_le_log_sq_of_nat_budget
    (h : ∃ C : ℕ, ∀ n : ℕ, 2 ≤ n → tarski_box_query_le n 5 (C * (Nat.log 2 n + 2) ^ 2)) :
    ∃ C : ℝ, ∀ n : ℕ, 2 ≤ n → ∃ q : ℕ,
      tarski_box_query_le n 5 q ∧ (q : ℝ) ≤ C * Real.logb 2 n ^ 2
Source
step towards tarski_box_query_le_five_log_sq
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • tarski_box_query_leBox-local Tarski query invariant: for every sub-box [a,b] (a ≤ b) of [n]^k there is a single deterministic query tree — depending only on…

The proof, explained

Proof sketch: We unpack the natural constant C from the hypothesis and choose the real constant to be 9C + 1. For any n ≥ 2, we choose the witness query budget q = C(⌊log₂ n⌋ + 2)², which immediately satisfies the box query bound by assumption. Since n ≥ 2, we have 1 ≤ log₂ n and ⌊log₂ n⌋ ≤ log₂ n, which together imply ⌊log₂ n⌋ + 2 ≤ 3 log₂ n. Squaring both sides and multiplying by C ≥ 0 yields q ≤ 9C log₂² n ≤ (9C + 1) log₂² n.

  1. We obtain the integer constant C from the hypothesis and propose 9C + 1 as the real constant.

    We unpack the existential hypothesis into the natural number C and the assumption hC that the query budget C(⌊log₂ n⌋ + 2)² holds. We then provide 9C + 1 as the witness for the existential quantifier over ℝ.

    lines 6–7

      rcases h with ⟨C, hC⟩
      use 9 * (C : ℝ) + 1
  2. For any n ≥ 2, choosing q = C(⌊log₂ n⌋ + 2)² satisfies the algorithmic query bound, reducing the goal to a real inequality.

    Fix n and the hypothesis hn that 2 ≤ n. We choose q = C(⌊log₂ n⌋ + 2)² as the witness query bound. The algorithmic condition holds directly by applying hC to n and hn, leaving only the arithmetic inequality q ≤ (9C + 1) log₂² n over the real numbers.

    lines 8–9

      intro n hn
      refine ⟨C * (Nat.log 2 n + 2) ^ 2, hC n hn, ?_⟩
  3. The inequalities ⌊log₂ n⌋ ≤ log₂ n, 1 ≤ log₂ n, 0 ≤ ⌊log₂ n⌋, and 0 ≤ C hold in the real numbers.

    We bound ⌊log₂ n⌋ by log₂ n using `Real.natLog_le_logb`. To show 1 ≤ log₂ n, we rewrite 1 as log₂ 2 via `Real.logb_self_eq_one` and apply logarithmic monotonicity `Real.logb_le_logb_of_le` using 2 ≤ n. Non-negativity of ⌊log₂ n⌋ and C as real numbers is given by `Nat.cast_nonneg`.

    lines 10–15

    uses Real.natLog_le_logb, Real.logb_self_eq_one, Real.logb_le_logb_of_le, Nat.cast_nonneg

      have h1 : (Nat.log 2 n : ℝ) ≤ Real.logb 2 n := Real.natLog_le_logb n 2
      have h2 : 1 ≤ Real.logb 2 (n : ℝ) := by
        rw [← Real.logb_self_eq_one (by norm_num : (1 : ℝ) < 2)]
        exact Real.logb_le_logb_of_le (by norm_num) (by norm_num) (by exact_mod_cast hn)
      have h3 : (Nat.log 2 n : ℝ) ≥ 0 := Nat.cast_nonneg _
      have h4 : (C : ℝ) ≥ 0 := Nat.cast_nonneg _
  4. C(⌊log₂ n⌋ + 2)² ≤ (9C + 1) log₂² n in the real numbers.

    After pushing the integer-to-real cast through the arithmetic expressions, linear arithmetic combines ⌊log₂ n⌋ ≤ log₂ n and 1 ≤ log₂ n to deduce ⌊log₂ n⌋ + 2 ≤ 3 log₂ n as well as 0 ≤ ⌊log₂ n⌋ + 2. Squaring both sides yields (⌊log₂ n⌋ + 2)² ≤ 9 log₂² n, from which nonlinear arithmetic concludes C(⌊log₂ n⌋ + 2)² ≤ 9C log₂² n ≤ (9C + 1) log₂² n.

    lines 16–20

      push_cast
      have ha : (Nat.log 2 n : ℝ) + 2 ≤ 3 * Real.logb 2 n := by linarith
      have hb : 0 ≤ (Nat.log 2 n : ℝ) + 2 := by linarith
      have hc : ((Nat.log 2 n : ℝ) + 2) ^ 2 ≤ (3 * Real.logb 2 n) ^ 2 := by nlinarith
      nlinarith
Real.natLog_le_logb
For natural numbers a and b, the integer logarithm ⌊log_b a⌋ is at most the real logarithm log_b a.
Real.logb_self_eq_one
For any base b > 1, the logarithm log_b b equals 1.
Real.logb_le_logb_of_le
For base b > 1 and positive real numbers x ≤ y, the logarithm satisfies log_b x ≤ log_b y.
Nat.cast_nonneg
The coercion of any natural number into an ordered semiring is non-negative.

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

/-- The ℕ-budget normal form of the target implies the target: this is the last step of any proof that is carried out with natural-number budgets, and it fixes the exact residual open content. -/theorem tarski_box_query_le_log_sq_of_nat_budget    (h : ∃ C : ℕ, ∀ n : ℕ, 2 ≤ n → tarski_box_query_le n 5 (C * (Nat.log 2 n + 2) ^ 2)) :    ∃ C : ℝ, ∀ n : ℕ, 2 ≤ n → ∃ q : ℕ,      tarski_box_query_le n 5 q ∧ (q : ℝ) ≤ C * Real.logb 2 n ^ 2 := by  rcases h with ⟨C, hC⟩  use 9 * (C : ℝ) + 1  intro n hn  refine ⟨C * (Nat.log 2 n + 2) ^ 2, hC n hn, ?_⟩  have h1 : (Nat.log 2 n : ℝ) ≤ Real.logb 2 n := Real.natLog_le_logb n 2  have h2 : 1 ≤ Real.logb 2 (n : ℝ) := by    rw [← Real.logb_self_eq_one (by norm_num : (1 : ℝ) < 2)]    exact Real.logb_le_logb_of_le (by norm_num) (by norm_num) (by exact_mod_cast hn)  have h3 : (Nat.log 2 n : ℝ) ≥ 0 := Nat.cast_nonneg _  have h4 : (C : ℝ) ≥ 0 := Nat.cast_nonneg _  push_cast  have ha : (Nat.log 2 n : ℝ) + 2 ≤ 3 * Real.logb 2 n := by linarith  have hb : 0 ≤ (Nat.log 2 n : ℝ) + 2 := by linarith  have hc : ((Nat.log 2 n : ℝ) + 2) ^ 2 ≤ (3 * Real.logb 2 n) ^ 2 := by nlinarith  nlinarith
See it in the graphDiscuss this resultChallenge it