tarski_box_query_le_log_sq_of_nat_budget
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.
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 ℝ.
rcases h with ⟨C, hC⟩ use 9 * (C : ℝ) + 1
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.
intro n hn refine ⟨C * (Nat.log 2 n + 2) ^ 2, hC n hn, ?_⟩
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`.
uses
Real.natLog_le_logb,Real.logb_self_eq_one,Real.logb_le_logb_of_le,Nat.cast_nonneghave 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 _
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.
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
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.
/-- 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