AFTD Auto-Formalizing Theoretical Domains

tarski_box_query_le_succ_halving

theoremverified

One dimension costs a factor log₂ n: from a box-search algorithm in dimension k with q queries one gets one in dimension k+1 with at most 3·(k+1)·(log₂ n + 2)·(q+1) + 2^(k+1) queries.

Statement

theorem tarski_box_query_le_succ_halving (n k q : ℕ) [NeZero n]
    (h : tarski_box_query_le n k q) :
    tarski_box_query_le n (k+1) (3 * (k+1) * (Nat.log 2 n + 2) * (q + 1) + 2 ^ (k+1))
Source
step towards tarski_query_complexity_five_le_log_sq
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 18
  • 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…
  • tarski_query_tree_bindSequential composition of query trees: run the tree, then feed its output point into the continuation g to obtain the tree that is…
  • tarski_query_tree_bind_specRun/cost law for sequential composition: the run of a bind is the run of the continuation g at the output of the first tree, and the cost…
  • tarski_query_tree_slice_liftSlice lifting of a query tree one dimension up: replace every query y in dimension k by the query (insertNth i c y) in dimension k+1, and…
  • tarski_query_tree_slice_lift_specRun/cost law for the slice lift: in dimension k+1, the lifted tree computes insertNth i c of the slice algorithm's output (run against the…
  • tarski_box_query_le_smallBrute force on small boxes: if every box in dimension k has at most M points, then every box query is answerable within M queries — and in…
  • tarski_slice_lower_boundMonotonicity preservation on coordinate slices: fixing coordinate i to any value m ≥ a_i preserves the lower subinterval invariant a_j ≤…
  • tarski_slice_upper_boundMonotonicity preservation on coordinate slices (upper bound): fixing coordinate i to any value m ≤ b_i preserves the upper subinterval…
  • tarski_subinterval_slice_shrinkSlicing contraction principle: if x is a fixed point of f on all coordinates j ≠ i within [a, b], then comparing f(x)_i with x_i either…
  • tarski_slice_subbox_monotone_and_fixedFor any monotone map f on [a, b] in dimension k+1 and any coordinate cut c with a_i <= c <= b_i, the sliced map g y j = f (insertNth i c…
  • tarski_subinterval_fixed_pointSubinterval fixed point theorem: if a monotone map f satisfies a ≤ f(a) and f(b) ≤ b, then f has a fixed point in the sub-box [a, b].
  • TarskiQueryTreeA deterministic adaptive query algorithm for an unknown map f : [n]^k → [n]^k, as a decision tree: a leaf outputs a point; an internal…
  • TarskiQueryTree.costThe number of queries a query tree makes when the black box is f (the length of the path f follows).
  • TarskiQueryTree.runThe point a query tree outputs when the black box is f.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • potentialThe potential (sum of unnormalized weights) at time $t$ is \[ W_t \;=\; \sum_{i=1}^{N} w_t(i). \] The potential telescopes to…
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Used by 2
  • tarski_box_query_le_polylogBox-form state of the art: for every dimension k there is a constant C such that every sub-box of [n]^k admits a box algorithm with at…
  • tarski_query_complexity_le_polylogMultidimensional Tarski search is polylogarithmic: for every fixed k there is a constant C with Tarski(n,k) ≤ C·(log₂ n + 2)^k for all n ≥…

The proof, explained

To find a fixed point of a monotone map on a (k+1)-dimensional grid, the algorithm bisects a coordinate with gap at least 2 at its midpoint, slices the function along this hyperplane, and applies the k-dimensional algorithm with q queries to find a point fixed in all other coordinates. Querying this point reveals whether the fixed point lies in the lower or upper sub-box, strictly decreasing the potential function (the sum of ceiling logarithms of the coordinate gaps) at a cost of q+1 queries. When all coordinate gaps are at most 1, the box contains at most 2^(k+1) points and is searched by brute force, yielding the overall query bound after bounding the initial potential by (k+1)·⌈log₂ n⌉.

  1. Shrinking a box coordinate-wise with a strict decrease in one coordinate strictly decreases its potential.

    The potential is defined as the sum of coordinate potentials. Since each coordinate gap shrinks or stays the same, the ceiling logarithm is non-increasing coordinate-wise by Nat.clog_mono. In coordinate i the gap strictly decreases, so by Finset.sum_lt_sum the total sum strictly decreases.

    lines 14–21

    uses tarski_box_query_le_succ_halving_pot, Finset.sum_lt_sum, Nat.clog_mono, le_refl, Finset.mem_univ

      unfold tarski_box_query_le_succ_halving_pot
      apply Finset.sum_lt_sum
      · intro j _
        refine Nat.clog_mono (b := 2) (c := 2) (by norm_num) (le_refl 2) ?_
        have h1 : (u j : ℕ) ≤ (u' j : ℕ) := huu' j
        have h2 : (v' j : ℕ) ≤ (v j : ℕ) := hvv' j
        omega
      · exact ⟨i, Finset.mem_univ i, hi⟩
  2. Halving a gap of size at least 2 strictly decreases its ceiling logarithm base 2.

    Let m = clog 2 d. Since d >= 2, m > 0. Then d <= 2^m = 2^(m-1) * 2, so d / 2 <= 2^(m-1). Thus clog 2 (d / 2) <= m - 1 < m.

    lines 26–37

    uses Nat.clog_pos, Nat.clog_le_iff_le_pow, le_refl, Nat.pow_succ

      have hb : 1 < 2 := by norm_num
      set m := Nat.clog 2 d with hm
      have hmpos : 0 < m := Nat.clog_pos hb (by omega)
      have hd2 : d ≤ 2 ^ m := (Nat.clog_le_iff_le_pow hb).mp (le_refl m)
      have hpow : 2 ^ m = 2 ^ (m - 1) * 2 := by
        conv_lhs => rw [show m = (m - 1) + 1 by omega]
        rw [Nat.pow_succ]
      have hle : d / 2 ≤ 2 ^ (m - 1) := by
        rw [hpow] at hd2
        omega
      have := (Nat.clog_le_iff_le_pow hb).mpr hle
      omega
  3. The upper half gap also strictly decreases clog 2 for gaps at least 2.

    Similar to halving, d - d/2 <= 2^(m-1) because d <= 2^(m-1)*2, so clog 2 (d - d/2) <= m - 1 < m.

    lines 42–53

    uses Nat.clog_pos, Nat.clog_le_iff_le_pow, le_refl, Nat.pow_succ

      have hb : 1 < 2 := by norm_num
      set m := Nat.clog 2 d with hm
      have hmpos : 0 < m := Nat.clog_pos hb (by omega)
      have hd2 : d ≤ 2 ^ m := (Nat.clog_le_iff_le_pow hb).mp (le_refl m)
      have hpow : 2 ^ m = 2 ^ (m - 1) * 2 := by
        conv_lhs => rw [show m = (m - 1) + 1 by omega]
        rw [Nat.pow_succ]
      have hle : d - d / 2 ≤ 2 ^ (m - 1) := by
        rw [hpow] at hd2
        omega
      have := (Nat.clog_le_iff_le_pow hb).mpr hle
      omega
  4. Inserting a cut value c between a_i and b_i keeps the point inside the box [a, b].

    Using the componentwise characterization of insertNth (Fin.le_insertNth_iff and Fin.insertNth_le_iff), the inequality holds at coordinate i because a_i <= c <= b_i, and at all other coordinates because y lies between the slices of a and b.

    lines 60–64

    uses Fin.le_insertNth_iff, Fin.insertNth_le_iff

      refine ⟨?_, ?_⟩
      · rw [Fin.le_insertNth_iff]
        exact ⟨hac, ha'y⟩
      · rw [Fin.insertNth_le_iff]
        exact ⟨hcb, hyb'⟩
  5. Bisection strictly decreases the potential in both resulting sub-boxes.

    The inserted point lies in [a, b]. In coordinate i, the lower sub-box has gap (b_i - a_i) / 2 and the upper sub-box has gap (b_i - a_i) - (b_i - a_i) / 2. By the previous halving lemmas, clog 2 strictly decreases at coordinate i in both sub-boxes, while all other coordinates are unchanged or shrink, so tarski_box_query_le_succ_halving_pot_lt shows both potentials strictly decrease.

    lines 77–94

    uses tarski_box_query_le_succ_halving_insertNth_mem, tarski_box_query_le_succ_halving_pot_lt, le_refl, tarski_box_query_le_succ_halving_clog_sub_half_lt, tarski_box_query_le_succ_halving_clog_half_lt

      obtain ⟨hax, hxb⟩ := tarski_box_query_le_succ_halving_insertNth_mem n k a b i c hac hcb y ha'y hyb'
      have hxi : (i.insertNth c y : Fin (k+1) → Fin n) i = c := by simp
      have hd : 2 ≤ (b i : ℕ) - (a i) := hstep
      constructor
      · refine tarski_box_query_le_succ_halving_pot_lt n (k+1) (u := a) (u' := i.insertNth c y)
          (v := b) (v' := b) hax (le_refl b) i ?_
        rw [hxi]
        have hb1 : (c : ℕ) ≤ (b i : ℕ) := hcb
        have hb2 : (a i : ℕ) ≤ (c : ℕ) := hac
        have : (b i : ℕ) - (c : ℕ) = ((b i : ℕ) - (a i)) - ((b i : ℕ) - (a i)) / 2 := by omega
        rw [this]
        exact tarski_box_query_le_succ_halving_clog_sub_half_lt hd
      · refine tarski_box_query_le_succ_halving_pot_lt n (k+1) (u := a) (u' := a) (v := b)
          (v' := i.insertNth c y) (le_refl a) hxb i ?_
        rw [hxi]
        have : (c : ℕ) - (a i : ℕ) = ((b i : ℕ) - (a i)) / 2 := hc
        rw [this]
        exact tarski_box_query_le_succ_halving_clog_half_lt hd
  6. The brute-force query tree finds a fixed point in a list within length queries.

    Induction on the list L. If the head is a fixed point, the tree queries it and outputs it in 1 query. Otherwise, the fixed point is in the tail, and the induction hypothesis applies with cost bounded by length.

    lines 112–130

    uses tarski_box_query_le_succ_halving_brute, TarskiQueryTree.run.eq_2, TarskiQueryTree.cost.eq_2, if_pos, TarskiQueryTree.run.eq_1, TarskiQueryTree.cost.eq_1, List.mem_cons_self, if_neg, List.mem_cons, List.mem_cons_of_mem, List.length_cons

      induction L with
      | nil => simp at hL
      | cons x xs ih =>
        obtain ⟨w, hw, hfw⟩ := hL
        rw [List.mem_cons] at hw
        simp only [tarski_box_query_le_succ_halving_brute, TarskiQueryTree.run.eq_2,
          TarskiQueryTree.cost.eq_2]
        by_cases hfx : f x = x
        · rw [if_pos hfx, TarskiQueryTree.run.eq_1, TarskiQueryTree.cost.eq_1]
          exact ⟨List.mem_cons_self, hfx, by simp⟩
        · rw [if_neg hfx]
          have hL' : ∃ y ∈ xs, f y = y := by
            rcases hw with rfl | hw
            · exact absurd hfw hfx
            · exact ⟨w, hw, hfw⟩
          obtain ⟨h1, h2, h3⟩ := ih hL'
          refine ⟨List.mem_cons_of_mem _ h1, h2, ?_⟩
          simp only [List.length_cons]
          omega
  7. A single bisection step yields a query tree satisfying the cost bound.

    We cut coordinate i at the midpoint c. We slice the function f at coordinate i = c and lift the k-dimensional query tree tq, which finds a point y fixed in all coordinates except i with cost at most q. Lifting to x = insertNth c y, we query f(x). If f(x)_i = x_i, x is a fixed point. If x_i < f(x)_i, then x <= f(x), so we recurse on [x, b]. If f(x)_i < x_i, then f(x) <= x, so we recurse on [a, x]. In both recursive cases, the potential strictly decreased, so by induction hypothesis the sub-tree solves the problem. The total query cost is at most q + 1 plus the recursive cost, which telescopes according to the potential decrease.

    lines 155–310

    uses tarski_box_query_le_succ_halving_insertNth_mem, tarski_query_tree_bind, tarski_query_tree_slice_lift, tarski_slice_subbox_monotone_and_fixed, tarski_query_tree_slice_lift_spec, tarski_box_query_le_succ_halving_pot_step, tarski_query_tree_bind_spec

      classical
      have hcval_lt : (a i : ℕ) + ((b i : ℕ) - (a i)) / 2 < n := by
        have hbn : (b i : ℕ) < n := Fin.is_lt (b i)
        have hdle : ((b i : ℕ) - (a i)) / 2 ≤ (b i : ℕ) - (a i) := Nat.div_le_self _ _
        omega
      set c : Fin n := ⟨(a i : ℕ) + ((b i : ℕ) - (a i)) / 2, hcval_lt⟩ with hcdef
      have hcval : (c : ℕ) = (a i : ℕ) + ((b i : ℕ) - (a i)) / 2 := by rw [hcdef]
      have hac : a i ≤ c := by rw [Fin.le_def, hcval]; omega
      have hcb : c ≤ b i := by rw [Fin.le_def, hcval]; omega
      obtain ⟨tq, htq⟩ := h (a ∘ i.succAbove) (b ∘ i.succAbove) (fun j => hab (i.succAbove j))
      let T : ∀ (u v : Fin (k+1) → Fin n), u ≤ v →
          tarski_box_query_le_succ_halving_pot n (k+1) u v < m → TarskiQueryTree n (k+1) :=
        fun u v huv hp => Classical.choose
          (ih (tarski_box_query_le_succ_halving_pot n (k+1) u v) hp u v huv (le_refl _))
      have hTspec : ∀ (u v : Fin (k+1) → Fin n) (huv : u ≤ v)
          (hp : tarski_box_query_le_succ_halving_pot n (k+1) u v < m),
          ∀ f : (Fin (k+1) → Fin n) → Fin (k+1) → Fin n, Monotone f → u ≤ f u → f v ≤ v →
            u ≤ TarskiQueryTree.run f (T u v huv hp) ∧
            TarskiQueryTree.run f (T u v huv hp) ≤ v ∧
            f (TarskiQueryTree.run f (T u v huv hp)) = TarskiQueryTree.run f (T u v huv hp) ∧
            TarskiQueryTree.cost f (T u v huv hp) ≤
              tarski_box_query_le_succ_halving_pot n (k+1) u v * (q + 1) + 2 ^ (k+1) := by
        intro u v huv hp f hf hu hv
        exact Classical.choose_spec
          (ih (tarski_box_query_le_succ_halving_pot n (k+1) u v) hp u v huv (le_refl _)) f hf hu hv
      let g : (Fin (k+1) → Fin n) → TarskiQueryTree n (k+1) := fun w =>
        if hw : a ≤ w ∧ w ≤ b ∧ tarski_box_query_le_succ_halving_pot n (k+1) w b < m ∧
            tarski_box_query_le_succ_halving_pot n (k+1) a w < m then
          TarskiQueryTree.query w (fun v =>
            if v i = w i then TarskiQueryTree.output w
            else if w i < v i then T w b hw.2.1 hw.2.2.1
            else T a w hw.1 hw.2.2.2)
        else TarskiQueryTree.output w
      refine ⟨tarski_query_tree_bind g (tarski_query_tree_slice_lift i c tq), ?_⟩
      intro f hf ha hb
      obtain ⟨hg_mono, hga, hgb, hglift⟩ :=
        tarski_slice_subbox_monotone_and_fixed n k f hf a b ha hb i c hac hcb
      obtain ⟨hya, hyb, hyfix, hycost⟩ :=
        htq (fun y j => f (i.insertNth c y) (i.succAbove j)) hg_mono hga hgb
      set y : Fin k → Fin n := TarskiQueryTree.run (fun y j => f (i.insertNth c y) (i.succAbove j)) tq
        with hydef
      set x : Fin (k+1) → Fin n := i.insertNth c y with hxdef
      obtain ⟨hax, hxb, hxsliced⟩ := hglift y hya hyb hyfix
      have hrun_lift : TarskiQueryTree.run f (tarski_query_tree_slice_lift i c tq) = x := by
        rw [(tarski_query_tree_slice_lift_spec i c f tq).1]
      have hcost_lift : TarskiQueryTree.cost f (tarski_query_tree_slice_lift i c tq) =
          TarskiQueryTree.cost (fun y j => f (i.insertNth c y) (i.succAbove j)) tq :=
        (tarski_query_tree_slice_lift_spec i c f tq).2
      have hlq : TarskiQueryTree.cost f (tarski_query_tree_slice_lift i c tq) ≤ q := by
        rw [hcost_lift]; exact hycost
      have hpstep := tarski_box_query_le_succ_halving_pot_step n k a b i c hac hcb hstep
        (by rw [hcval]; omega) y hya hyb
      have hpotx1 : tarski_box_query_le_succ_halving_pot n (k+1) x b < m :=
        lt_of_lt_of_le hpstep.1 hpot
      have hpotx2 : tarski_box_query_le_succ_halving_pot n (k+1) a x < m :=
        lt_of_lt_of_le hpstep.2 hpot
      have hguard : a ≤ x ∧ x ≤ b ∧ tarski_box_query_le_succ_halving_pot n (k+1) x b < m ∧
          tarski_box_query_le_succ_halving_pot n (k+1) a x < m := ⟨hax, hxb, hpotx1, hpotx2⟩
      have hgx : g x = TarskiQueryTree.query x (fun v =>
          if v i = x i then TarskiQueryTree.output x
          else if x i < v i then T x b hguard.2.1 hguard.2.2.1
          else T a x hguard.1 hguard.2.2.2) := by
        simp only [g]
        rw [dif_pos hguard]
      have hpotpos : 1 ≤ tarski_box_query_le_succ_halving_pot n (k+1) a b := by
        have hpos : 0 < Nat.clog 2 ((b i : ℕ) - (a i)) := Nat.clog_pos (by norm_num) (by omega)
        have := Finset.single_le_sum
          (f := fun j : Fin (k+1) => Nat.clog 2 ((b j : ℕ) - (a j)))
          (fun j _ => Nat.zero_le _) (Finset.mem_univ i)
        unfold tarski_box_query_le_succ_halving_pot
        omega
      have hbs := tarski_query_tree_bind_spec g f (tarski_query_tree_slice_lift i c tq)
      have key : a ≤ TarskiQueryTree.run f (g x) ∧ TarskiQueryTree.run f (g x) ≤ b ∧
          f (TarskiQueryTree.run f (g x)) = TarskiQueryTree.run f (g x) ∧
          TarskiQueryTree.cost f (tarski_query_tree_slice_lift i c tq) + TarskiQueryTree.cost f (g x)
            ≤ tarski_box_query_le_succ_halving_pot n (k+1) a b * (q + 1) + 2 ^ (k+1) := by
        by_cases h1 : f x i = x i
        · have hrun1 : TarskiQueryTree.run f (g x) = x := by
            rw [hgx, TarskiQueryTree.run.eq_2, if_pos h1, TarskiQueryTree.run.eq_1]
          have hcost1 : TarskiQueryTree.cost f (g x) = 1 := by
            rw [hgx, TarskiQueryTree.cost.eq_2, if_pos h1, TarskiQueryTree.cost.eq_1]
          have hfixx : f x = x := by
            funext j
            rcases Fin.eq_self_or_eq_succAbove i j with hji | ⟨t, ht⟩
            · rw [hji]; exact h1
            · rw [ht]
              exact hxsliced _ (Fin.succAbove_ne i t)
          refine ⟨by rw [hrun1]; exact hax, by rw [hrun1]; exact hxb, by rw [hrun1]; exact hfixx, ?_⟩
          rw [hcost1]
          have h1' : TarskiQueryTree.cost f (tarski_query_tree_slice_lift i c tq) + 1 ≤ q + 1 := by omega
          have h2' : q + 1 ≤ tarski_box_query_le_succ_halving_pot n (k+1) a b * (q + 1) := by
            calc q + 1 = 1 * (q + 1) := by ring
              _ ≤ tarski_box_query_le_succ_halving_pot n (k+1) a b * (q + 1) :=
                  Nat.mul_le_mul_right _ hpotpos
          exact le_trans h1' (le_trans h2' (Nat.le_add_right _ _))
        · by_cases h2 : x i < f x i
          · have hrun2 : TarskiQueryTree.run f (g x) =
                TarskiQueryTree.run f (T x b hguard.2.1 hguard.2.2.1) := by
              rw [hgx, TarskiQueryTree.run.eq_2, if_neg h1, if_pos h2]
            have hcost2 : TarskiQueryTree.cost f (g x) =
                TarskiQueryTree.cost f (T x b hguard.2.1 hguard.2.2.1) + 1 := by
              rw [hgx, TarskiQueryTree.cost.eq_2, if_neg h1, if_pos h2]
            have hxfx : x ≤ f x := by
              intro j
              rcases Fin.eq_self_or_eq_succAbove i j with hji | ⟨t, ht⟩
              · rw [hji]; exact le_of_lt h2
              · rw [ht]; rw [hxsliced _ (Fin.succAbove_ne i t)]
            obtain ⟨hT1, hT2, hT3, hT4⟩ := hTspec x b hxb hpotx1 f hf hxfx hb
            refine ⟨by rw [hrun2]; exact le_trans hax hT1, by rw [hrun2]; exact hT2,
              by rw [hrun2]; exact hT3, ?_⟩
            rw [hcost2]
            have hp3 : tarski_box_query_le_succ_halving_pot n (k+1) x b + 1 ≤
                tarski_box_query_le_succ_halving_pot n (k+1) a b := by
              rw [hxdef]; exact hpstep.1
            calc TarskiQueryTree.cost f (tarski_query_tree_slice_lift i c tq) +
                  (TarskiQueryTree.cost f (T x b hguard.2.1 hguard.2.2.1) + 1)
                ≤ q + ((tarski_box_query_le_succ_halving_pot n (k+1) x b * (q + 1) + 2 ^ (k+1))
                    + 1) := by omega
              _ = (tarski_box_query_le_succ_halving_pot n (k+1) x b + 1) * (q + 1) + 2 ^ (k+1) := by
                  ring
              _ ≤ tarski_box_query_le_succ_halving_pot n (k+1) a b * (q + 1) + 2 ^ (k+1) := by
                  apply Nat.add_le_add_right
                  exact Nat.mul_le_mul_right _ hp3
          · have h3 : f x i < x i := lt_of_le_of_ne (le_of_not_gt h2) h1
            have hrun3 : TarskiQueryTree.run f (g x) =
                TarskiQueryTree.run f (T a x hguard.1 hguard.2.2.2) := by
              rw [hgx, TarskiQueryTree.run.eq_2, if_neg h1, if_neg h2]
            have hcost3 : TarskiQueryTree.cost f (g x) =
                TarskiQueryTree.cost f (T a x hguard.1 hguard.2.2.2) + 1 := by
              rw [hgx, TarskiQueryTree.cost.eq_2, if_neg h1, if_neg h2]
            have hfxx : f x ≤ x := by
              intro j
              rcases Fin.eq_self_or_eq_succAbove i j with hji | ⟨t, ht⟩
              · rw [hji]; exact le_of_lt h3
              · rw [ht]; rw [hxsliced _ (Fin.succAbove_ne i t)]
            obtain ⟨hT1, hT2, hT3, hT4⟩ := hTspec a x hax hpotx2 f hf ha hfxx
            refine ⟨by rw [hrun3]; exact hT1, by rw [hrun3]; exact le_trans hT2 hxb,
              by rw [hrun3]; exact hT3, ?_⟩
            rw [hcost3]
            have hp3 : tarski_box_query_le_succ_halving_pot n (k+1) a x + 1 ≤
                tarski_box_query_le_succ_halving_pot n (k+1) a b := by
              rw [hxdef]; exact hpstep.2
            calc TarskiQueryTree.cost f (tarski_query_tree_slice_lift i c tq) +
                  (TarskiQueryTree.cost f (T a x hguard.1 hguard.2.2.2) + 1)
                ≤ q + ((tarski_box_query_le_succ_halving_pot n (k+1) a x * (q + 1) + 2 ^ (k+1))
                    + 1) := by omega
              _ = (tarski_box_query_le_succ_halving_pot n (k+1) a x + 1) * (q + 1) + 2 ^ (k+1) := by
                  ring
              _ ≤ tarski_box_query_le_succ_halving_pot n (k+1) a b * (q + 1) + 2 ^ (k+1) := by
                  apply Nat.add_le_add_right
                  exact Nat.mul_le_mul_right _ hp3
      obtain ⟨k1, k2, k3, k4⟩ := key
      exact ⟨by rw [hbs.1, hrun_lift]; exact k1,
             by rw [hbs.1, hrun_lift]; exact k2,
             by rw [hbs.1, hrun_lift]; exact k3,
             by rw [hbs.2, hrun_lift]; exact k4⟩
  8. Every box admits a query tree of cost at most pot * (q+1) + 2^(k+1), by strong induction on the potential bound m.

    If every coordinate gap is at most 1, the box has at most 2^(k+1) points, and we brute force search over the box using the brute tree. Otherwise, some coordinate has gap at least 2, and we apply the bisection step tarski_box_query_le_succ_halving_step.

    lines 324–352

    uses tarski_box_query_le_succ_halving_brute, tarski_subinterval_fixed_point, tarski_box_query_le_succ_halving_brute_spec, tarski_box_query_le_succ_halving_step

      intro m
      induction m using Nat.strong_induction_on with
      | h m ih =>
        intro a b hab hpot
        by_cases hsmall : ∀ i : Fin (k+1), (b i : ℕ) - (a i) ≤ 1
        · refine ⟨tarski_box_query_le_succ_halving_brute a (Finset.Icc a b).toList, ?_⟩
          intro f hf ha hb
          obtain ⟨x0, hx0a, hx0b, hx0f⟩ := tarski_subinterval_fixed_point n (k+1) f hf a b hab ha hb
          have hL : ∃ y ∈ (Finset.Icc a b).toList, f y = y :=
            ⟨x0, by rw [Finset.mem_toList, Finset.mem_Icc]; exact ⟨hx0a, hx0b⟩, hx0f⟩
          obtain ⟨h1, h2, h3⟩ := tarski_box_query_le_succ_halving_brute_spec a
            (Finset.Icc a b).toList f hL
          rw [Finset.mem_toList, Finset.mem_Icc] at h1
          refine ⟨h1.1, h1.2, h2, ?_⟩
          have hcard : (Finset.Icc a b).card ≤ 2 ^ (k+1) := by
            rw [Pi.card_Icc]
            calc ∏ i : Fin (k+1), (Finset.Icc (a i) (b i)).card ≤ ∏ _i : Fin (k+1), 2 := by
                  apply Finset.prod_le_prod
                  · intro i _; simp
                  · intro i _
                    rw [Fin.card_Icc]
                    have h2' := hab i
                    have h3' := hsmall i
                    omega
              _ = 2 ^ (k+1) := by simp
          rw [Finset.length_toList] at h3
          exact le_trans h3 (le_trans hcard (Nat.le_add_left _ _))
        · obtain ⟨i, hi⟩ := not_forall.mp hsmall
          exact tarski_box_query_le_succ_halving_step n k q m h ih a b hab hpot i (by omega)
  9. The halving recursion bound holds in dimension k+1.

    For any box [a, b], each coordinate gap is less than n, so the potential is at most (k+1) * clog 2 n. Since clog 2 n <= log 2 n + 1 <= 3 * (log 2 n + 2), the auxiliary induction bound pot * (q+1) + 2^(k+1) is at most 3*(k+1)*(log 2 n + 2)*(q+1) + 2^(k+1).

    lines 358–389

    uses tarski_box_query_le_succ_halving_aux, Nat.clog_mono, Nat.clog_le_iff_le_pow, Nat.lt_pow_succ_log_self

      intro a b hab
      obtain ⟨t, ht⟩ := tarski_box_query_le_succ_halving_aux n k q h
        (tarski_box_query_le_succ_halving_pot n (k+1) a b) a b hab (le_refl _)
      refine ⟨t, fun f hf ha hb => ?_⟩
      obtain ⟨h1, h2, h3, h4⟩ := ht f hf ha hb
      refine ⟨h1, h2, h3, le_trans h4 ?_⟩
      have hpot1 : tarski_box_query_le_succ_halving_pot n (k+1) a b ≤ (k+1) * Nat.clog 2 n := by
        unfold tarski_box_query_le_succ_halving_pot
        calc ∑ j : Fin (k+1), Nat.clog 2 ((b j : ℕ) - (a j)) ≤ ∑ _j : Fin (k+1), Nat.clog 2 n := by
              apply Finset.sum_le_sum
              intro j _
              refine Nat.clog_mono (b := 2) (c := 2) (by norm_num) (le_refl 2) ?_
              have h1' : (b j : ℕ) < n := Fin.is_lt (b j)
              omega
          _ = (k+1) * Nat.clog 2 n := by simp
      have hclog : Nat.clog 2 n ≤ Nat.log 2 n + 1 := by
        have hb : 1 < 2 := by norm_num
        rw [Nat.clog_le_iff_le_pow hb]
        exact Nat.le_of_lt (Nat.lt_pow_succ_log_self hb n)
      have hL : tarski_box_query_le_succ_halving_pot n (k+1) a b ≤
          3 * (k+1) * (Nat.log 2 n + 2) := by
        have hstep1 : tarski_box_query_le_succ_halving_pot n (k+1) a b ≤
            (k+1) * (Nat.log 2 n + 1) := le_trans hpot1 (Nat.mul_le_mul_left _ hclog)
        have hstep2 : (k+1) * (Nat.log 2 n + 1) ≤ 3 * (k+1) * (Nat.log 2 n + 2) := by
          have h1' : Nat.log 2 n + 1 ≤ 3 * (Nat.log 2 n + 2) := by omega
          calc (k+1) * (Nat.log 2 n + 1) ≤ (k+1) * (3 * (Nat.log 2 n + 2)) :=
                Nat.mul_le_mul_left _ h1'
            _ = 3 * (k+1) * (Nat.log 2 n + 2) := by ring
        exact le_trans hstep1 hstep2
      have hmul : tarski_box_query_le_succ_halving_pot n (k+1) a b * (q + 1) ≤
          3 * (k+1) * (Nat.log 2 n + 2) * (q + 1) := Nat.mul_le_mul_right _ hL
      exact Nat.add_le_add_right hmul _

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

open Finsetset_option maxHeartbeats 2000000/-- Potential of a box: the sum over coordinates of `clog 2` of the coordinate gap. -/def tarski_box_query_le_succ_halving_pot (n K : ℕ) (a b : Fin K → Fin n) : ℕ :=  ∑ j : Fin K, Nat.clog 2 ((b j : ℕ) - (a j))/-- A box that shrinks in every coordinate has no larger potential. -/theorem tarski_box_query_le_succ_halving_pot_lt (n K : ℕ) {u u' v v' : Fin K → Fin n}    (huu' : u ≤ u') (hvv' : v' ≤ v) (i : Fin K)    (hi : Nat.clog 2 ((v' i : ℕ) - (u' i)) < Nat.clog 2 ((v i : ℕ) - (u i))) :    tarski_box_query_le_succ_halving_pot n K u' v' <      tarski_box_query_le_succ_halving_pot n K u v := by  unfold tarski_box_query_le_succ_halving_pot  apply Finset.sum_lt_sum  · intro j _    refine Nat.clog_mono (b := 2) (c := 2) (by norm_num) (le_refl 2) ?_    have h1 : (u j : ℕ) ≤ (u' j : ℕ) := huu' j    have h2 : (v' j : ℕ) ≤ (v j : ℕ) := hvv' j    omega  · exact ⟨i, Finset.mem_univ i, hi⟩/-- Halving strictly decreases `clog 2` for gaps of size at least two. -/theorem tarski_box_query_le_succ_halving_clog_half_lt {d : ℕ} (hd : 2 ≤ d) :    Nat.clog 2 (d / 2) < Nat.clog 2 d := by  have hb : 1 < 2 := by norm_num  set m := Nat.clog 2 d with hm  have hmpos : 0 < m := Nat.clog_pos hb (by omega)  have hd2 : d ≤ 2 ^ m := (Nat.clog_le_iff_le_pow hb).mp (le_refl m)  have hpow : 2 ^ m = 2 ^ (m - 1) * 2 := by    conv_lhs => rw [show m = (m - 1) + 1 by omega]    rw [Nat.pow_succ]  have hle : d / 2 ≤ 2 ^ (m - 1) := by    rw [hpow] at hd2    omega  have := (Nat.clog_le_iff_le_pow hb).mpr hle  omega/-- The complementary half also strictly decreases `clog 2` for gaps of size at least two. -/theorem tarski_box_query_le_succ_halving_clog_sub_half_lt {d : ℕ} (hd : 2 ≤ d) :    Nat.clog 2 (d - d / 2) < Nat.clog 2 d := by  have hb : 1 < 2 := by norm_num  set m := Nat.clog 2 d with hm  have hmpos : 0 < m := Nat.clog_pos hb (by omega)  have hd2 : d ≤ 2 ^ m := (Nat.clog_le_iff_le_pow hb).mp (le_refl m)  have hpow : 2 ^ m = 2 ^ (m - 1) * 2 := by    conv_lhs => rw [show m = (m - 1) + 1 by omega]    rw [Nat.pow_succ]  have hle : d - d / 2 ≤ 2 ^ (m - 1) := by    rw [hpow] at hd2    omega  have := (Nat.clog_le_iff_le_pow hb).mpr hle  omega/-- An `insertNth` point stays inside the box when the slice and the cut do. -/theorem tarski_box_query_le_succ_halving_insertNth_mem (n k : ℕ) (a b : Fin (k+1) → Fin n)    (i : Fin (k+1)) (c : Fin n) (hac : a i ≤ c) (hcb : c ≤ b i)    (y : Fin k → Fin n) (ha'y : (a ∘ i.succAbove) ≤ y) (hyb' : y ≤ (b ∘ i.succAbove)) :    a ≤ i.insertNth c y ∧ i.insertNth c y ≤ b := by  refine ⟨?_, ?_⟩  · rw [Fin.le_insertNth_iff]    exact ⟨hac, ha'y⟩  · rw [Fin.insertNth_le_iff]    exact ⟨hcb, hyb'⟩/-- A bisection step strictly decreases the potential in both resulting sub-boxes. -/theorem tarski_box_query_le_succ_halving_pot_step (n k : ℕ) (a b : Fin (k+1) → Fin n)    (i : Fin (k+1)) (c : Fin n)    (hac : a i ≤ c) (hcb : c ≤ b i)    (hstep : 2 ≤ (b i : ℕ) - (a i))    (hc : (c : ℕ) - (a i : ℕ) = ((b i : ℕ) - (a i)) / 2)    (y : Fin k → Fin n) (ha'y : (a ∘ i.succAbove) ≤ y) (hyb' : y ≤ (b ∘ i.succAbove)) :    tarski_box_query_le_succ_halving_pot n (k+1) (i.insertNth c y) b <      tarski_box_query_le_succ_halving_pot n (k+1) a b ∧    tarski_box_query_le_succ_halving_pot n (k+1) a (i.insertNth c y) <      tarski_box_query_le_succ_halving_pot n (k+1) a b := by  obtain ⟨hax, hxb⟩ := tarski_box_query_le_succ_halving_insertNth_mem n k a b i c hac hcb y ha'y hyb'  have hxi : (i.insertNth c y : Fin (k+1) → Fin n) i = c := by simp  have hd : 2 ≤ (b i : ℕ) - (a i) := hstep  constructor  · refine tarski_box_query_le_succ_halving_pot_lt n (k+1) (u := a) (u' := i.insertNth c y)      (v := b) (v' := b) hax (le_refl b) i ?_    rw [hxi]    have hb1 : (c : ℕ) ≤ (b i : ℕ) := hcb    have hb2 : (a i : ℕ) ≤ (c : ℕ) := hac    have : (b i : ℕ) - (c : ℕ) = ((b i : ℕ) - (a i)) - ((b i : ℕ) - (a i)) / 2 := by omega    rw [this]    exact tarski_box_query_le_succ_halving_clog_sub_half_lt hd  · refine tarski_box_query_le_succ_halving_pot_lt n (k+1) (u := a) (u' := a) (v := b)      (v' := i.insertNth c y) (le_refl a) hxb i ?_    rw [hxi]    have : (c : ℕ) - (a i : ℕ) = ((b i : ℕ) - (a i)) / 2 := hc    rw [this]    exact tarski_box_query_le_succ_halving_clog_half_lt hd/-- Brute-force query tree: query the listed points in order, output the first fixed point. -/def tarski_box_query_le_succ_halving_brute {n K : ℕ} (dflt : Fin K → Fin n) :    List (Fin K → Fin n) → TarskiQueryTree n K  | [] => TarskiQueryTree.output dflt  | x :: xs =>    TarskiQueryTree.query x (fun v => if v = x then TarskiQueryTree.output x else      tarski_box_query_le_succ_halving_brute dflt xs)/-- The brute-force tree finds a fixed point contained in the list, within `length` queries. -/theorem tarski_box_query_le_succ_halving_brute_spec {n K : ℕ} (dflt : Fin K → Fin n)    (L : List (Fin K → Fin n))    (f : (Fin K → Fin n) → Fin K → Fin n) (hL : ∃ x ∈ L, f x = x) :    TarskiQueryTree.run f (tarski_box_query_le_succ_halving_brute dflt L) ∈ L ∧    f (TarskiQueryTree.run f (tarski_box_query_le_succ_halving_brute dflt L)) =      TarskiQueryTree.run f (tarski_box_query_le_succ_halving_brute dflt L) ∧    TarskiQueryTree.cost f (tarski_box_query_le_succ_halving_brute dflt L) ≤ L.length := by  induction L with  | nil => simp at hL  | cons x xs ih =>    obtain ⟨w, hw, hfw⟩ := hL    rw [List.mem_cons] at hw    simp only [tarski_box_query_le_succ_halving_brute, TarskiQueryTree.run.eq_2,      TarskiQueryTree.cost.eq_2]    by_cases hfx : f x = x    · rw [if_pos hfx, TarskiQueryTree.run.eq_1, TarskiQueryTree.cost.eq_1]      exact ⟨List.mem_cons_self, hfx, by simp⟩    · rw [if_neg hfx]      have hL' : ∃ y ∈ xs, f y = y := by        rcases hw with rfl | hw        · exact absurd hfw hfx        · exact ⟨w, hw, hfw⟩      obtain ⟨h1, h2, h3⟩ := ih hL'      refine ⟨List.mem_cons_of_mem _ h1, h2, ?_⟩      simp only [List.length_cons]      omega/-- One bisection step: slice, lift, query the lifted point, and dispatch to thesub-box promised by monotonicity, giving the potential-decrease cost bound. -/theorem tarski_box_query_le_succ_halving_step (n k q m : ℕ) [NeZero n]    (h : tarski_box_query_le n k q)    (ih : ∀ m' < m, ∀ (a b : Fin (k+1) → Fin n), a ≤ b →      tarski_box_query_le_succ_halving_pot n (k+1) a b ≤ m' →      ∃ t : TarskiQueryTree n (k+1),        ∀ f : (Fin (k+1) → Fin n) → Fin (k+1) → Fin n,          Monotone f → a ≤ f a → f b ≤ b →            a ≤ TarskiQueryTree.run f t ∧ TarskiQueryTree.run f t ≤ b ∧            f (TarskiQueryTree.run f t) = TarskiQueryTree.run f t ∧            TarskiQueryTree.cost f t ≤              tarski_box_query_le_succ_halving_pot n (k+1) a b * (q + 1) + 2 ^ (k+1))    (a b : Fin (k+1) → Fin n) (hab : a ≤ b)    (hpot : tarski_box_query_le_succ_halving_pot n (k+1) a b ≤ m)    (i : Fin (k+1)) (hstep : 2 ≤ (b i : ℕ) - (a i)) :    ∃ t : TarskiQueryTree n (k+1),      ∀ f : (Fin (k+1) → Fin n) → Fin (k+1) → Fin n,        Monotone f → a ≤ f a → f b ≤ b →          a ≤ TarskiQueryTree.run f t ∧ TarskiQueryTree.run f t ≤ b ∧          f (TarskiQueryTree.run f t) = TarskiQueryTree.run f t ∧          TarskiQueryTree.cost f t ≤            tarski_box_query_le_succ_halving_pot n (k+1) a b * (q + 1) + 2 ^ (k+1) := by  classical  have hcval_lt : (a i : ℕ) + ((b i : ℕ) - (a i)) / 2 < n := by    have hbn : (b i : ℕ) < n := Fin.is_lt (b i)    have hdle : ((b i : ℕ) - (a i)) / 2 ≤ (b i : ℕ) - (a i) := Nat.div_le_self _ _    omega  set c : Fin n := ⟨(a i : ℕ) + ((b i : ℕ) - (a i)) / 2, hcval_lt⟩ with hcdef  have hcval : (c : ℕ) = (a i : ℕ) + ((b i : ℕ) - (a i)) / 2 := by rw [hcdef]  have hac : a i ≤ c := by rw [Fin.le_def, hcval]; omega  have hcb : c ≤ b i := by rw [Fin.le_def, hcval]; omega  obtain ⟨tq, htq⟩ := h (a ∘ i.succAbove) (b ∘ i.succAbove) (fun j => hab (i.succAbove j))  let T : ∀ (u v : Fin (k+1) → Fin n), u ≤ v →      tarski_box_query_le_succ_halving_pot n (k+1) u v < m → TarskiQueryTree n (k+1) :=    fun u v huv hp => Classical.choose      (ih (tarski_box_query_le_succ_halving_pot n (k+1) u v) hp u v huv (le_refl _))  have hTspec : ∀ (u v : Fin (k+1) → Fin n) (huv : u ≤ v)      (hp : tarski_box_query_le_succ_halving_pot n (k+1) u v < m),      ∀ f : (Fin (k+1) → Fin n) → Fin (k+1) → Fin n, Monotone f → u ≤ f u → f v ≤ v →        u ≤ TarskiQueryTree.run f (T u v huv hp) ∧        TarskiQueryTree.run f (T u v huv hp) ≤ v ∧        f (TarskiQueryTree.run f (T u v huv hp)) = TarskiQueryTree.run f (T u v huv hp) ∧        TarskiQueryTree.cost f (T u v huv hp) ≤          tarski_box_query_le_succ_halving_pot n (k+1) u v * (q + 1) + 2 ^ (k+1) := by    intro u v huv hp f hf hu hv    exact Classical.choose_spec      (ih (tarski_box_query_le_succ_halving_pot n (k+1) u v) hp u v huv (le_refl _)) f hf hu hv  let g : (Fin (k+1) → Fin n) → TarskiQueryTree n (k+1) := fun w =>    if hw : a ≤ w ∧ w ≤ b ∧ tarski_box_query_le_succ_halving_pot n (k+1) w b < m ∧        tarski_box_query_le_succ_halving_pot n (k+1) a w < m then      TarskiQueryTree.query w (fun v =>        if v i = w i then TarskiQueryTree.output w        else if w i < v i then T w b hw.2.1 hw.2.2.1        else T a w hw.1 hw.2.2.2)    else TarskiQueryTree.output w  refine ⟨tarski_query_tree_bind g (tarski_query_tree_slice_lift i c tq), ?_⟩  intro f hf ha hb  obtain ⟨hg_mono, hga, hgb, hglift⟩ :=    tarski_slice_subbox_monotone_and_fixed n k f hf a b ha hb i c hac hcb  obtain ⟨hya, hyb, hyfix, hycost⟩ :=    htq (fun y j => f (i.insertNth c y) (i.succAbove j)) hg_mono hga hgb  set y : Fin k → Fin n := TarskiQueryTree.run (fun y j => f (i.insertNth c y) (i.succAbove j)) tq    with hydef  set x : Fin (k+1) → Fin n := i.insertNth c y with hxdef  obtain ⟨hax, hxb, hxsliced⟩ := hglift y hya hyb hyfix  have hrun_lift : TarskiQueryTree.run f (tarski_query_tree_slice_lift i c tq) = x := by    rw [(tarski_query_tree_slice_lift_spec i c f tq).1]  have hcost_lift : TarskiQueryTree.cost f (tarski_query_tree_slice_lift i c tq) =      TarskiQueryTree.cost (fun y j => f (i.insertNth c y) (i.succAbove j)) tq :=    (tarski_query_tree_slice_lift_spec i c f tq).2  have hlq : TarskiQueryTree.cost f (tarski_query_tree_slice_lift i c tq) ≤ q := by    rw [hcost_lift]; exact hycost  have hpstep := tarski_box_query_le_succ_halving_pot_step n k a b i c hac hcb hstep    (by rw [hcval]; omega) y hya hyb  have hpotx1 : tarski_box_query_le_succ_halving_pot n (k+1) x b < m :=    lt_of_lt_of_le hpstep.1 hpot  have hpotx2 : tarski_box_query_le_succ_halving_pot n (k+1) a x < m :=    lt_of_lt_of_le hpstep.2 hpot  have hguard : a ≤ x ∧ x ≤ b ∧ tarski_box_query_le_succ_halving_pot n (k+1) x b < m ∧      tarski_box_query_le_succ_halving_pot n (k+1) a x < m := ⟨hax, hxb, hpotx1, hpotx2⟩  have hgx : g x = TarskiQueryTree.query x (fun v =>      if v i = x i then TarskiQueryTree.output x      else if x i < v i then T x b hguard.2.1 hguard.2.2.1      else T a x hguard.1 hguard.2.2.2) := by    simp only [g]    rw [dif_pos hguard]  have hpotpos : 1 ≤ tarski_box_query_le_succ_halving_pot n (k+1) a b := by    have hpos : 0 < Nat.clog 2 ((b i : ℕ) - (a i)) := Nat.clog_pos (by norm_num) (by omega)    have := Finset.single_le_sum      (f := fun j : Fin (k+1) => Nat.clog 2 ((b j : ℕ) - (a j)))      (fun j _ => Nat.zero_le _) (Finset.mem_univ i)    unfold tarski_box_query_le_succ_halving_pot    omega  have hbs := tarski_query_tree_bind_spec g f (tarski_query_tree_slice_lift i c tq)  have key : a ≤ TarskiQueryTree.run f (g x) ∧ TarskiQueryTree.run f (g x) ≤ b ∧      f (TarskiQueryTree.run f (g x)) = TarskiQueryTree.run f (g x) ∧      TarskiQueryTree.cost f (tarski_query_tree_slice_lift i c tq) + TarskiQueryTree.cost f (g x)        ≤ tarski_box_query_le_succ_halving_pot n (k+1) a b * (q + 1) + 2 ^ (k+1) := by    by_cases h1 : f x i = x i    · have hrun1 : TarskiQueryTree.run f (g x) = x := by        rw [hgx, TarskiQueryTree.run.eq_2, if_pos h1, TarskiQueryTree.run.eq_1]      have hcost1 : TarskiQueryTree.cost f (g x) = 1 := by        rw [hgx, TarskiQueryTree.cost.eq_2, if_pos h1, TarskiQueryTree.cost.eq_1]      have hfixx : f x = x := by        funext j        rcases Fin.eq_self_or_eq_succAbove i j with hji | ⟨t, ht⟩        · rw [hji]; exact h1        · rw [ht]          exact hxsliced _ (Fin.succAbove_ne i t)      refine ⟨by rw [hrun1]; exact hax, by rw [hrun1]; exact hxb, by rw [hrun1]; exact hfixx, ?_⟩      rw [hcost1]      have h1' : TarskiQueryTree.cost f (tarski_query_tree_slice_lift i c tq) + 1 ≤ q + 1 := by omega      have h2' : q + 1 ≤ tarski_box_query_le_succ_halving_pot n (k+1) a b * (q + 1) := by        calc q + 1 = 1 * (q + 1) := by ring          _ ≤ tarski_box_query_le_succ_halving_pot n (k+1) a b * (q + 1) :=              Nat.mul_le_mul_right _ hpotpos      exact le_trans h1' (le_trans h2' (Nat.le_add_right _ _))    · by_cases h2 : x i < f x i      · have hrun2 : TarskiQueryTree.run f (g x) =            TarskiQueryTree.run f (T x b hguard.2.1 hguard.2.2.1) := by          rw [hgx, TarskiQueryTree.run.eq_2, if_neg h1, if_pos h2]        have hcost2 : TarskiQueryTree.cost f (g x) =            TarskiQueryTree.cost f (T x b hguard.2.1 hguard.2.2.1) + 1 := by          rw [hgx, TarskiQueryTree.cost.eq_2, if_neg h1, if_pos h2]        have hxfx : x ≤ f x := by          intro j          rcases Fin.eq_self_or_eq_succAbove i j with hji | ⟨t, ht⟩          · rw [hji]; exact le_of_lt h2          · rw [ht]; rw [hxsliced _ (Fin.succAbove_ne i t)]        obtain ⟨hT1, hT2, hT3, hT4⟩ := hTspec x b hxb hpotx1 f hf hxfx hb        refine ⟨by rw [hrun2]; exact le_trans hax hT1, by rw [hrun2]; exact hT2,          by rw [hrun2]; exact hT3, ?_⟩        rw [hcost2]        have hp3 : tarski_box_query_le_succ_halving_pot n (k+1) x b + 1 ≤            tarski_box_query_le_succ_halving_pot n (k+1) a b := by          rw [hxdef]; exact hpstep.1        calc TarskiQueryTree.cost f (tarski_query_tree_slice_lift i c tq) +              (TarskiQueryTree.cost f (T x b hguard.2.1 hguard.2.2.1) + 1)            ≤ q + ((tarski_box_query_le_succ_halving_pot n (k+1) x b * (q + 1) + 2 ^ (k+1))                + 1) := by omega          _ = (tarski_box_query_le_succ_halving_pot n (k+1) x b + 1) * (q + 1) + 2 ^ (k+1) := by              ring          _ ≤ tarski_box_query_le_succ_halving_pot n (k+1) a b * (q + 1) + 2 ^ (k+1) := by              apply Nat.add_le_add_right              exact Nat.mul_le_mul_right _ hp3      · have h3 : f x i < x i := lt_of_le_of_ne (le_of_not_gt h2) h1        have hrun3 : TarskiQueryTree.run f (g x) =            TarskiQueryTree.run f (T a x hguard.1 hguard.2.2.2) := by          rw [hgx, TarskiQueryTree.run.eq_2, if_neg h1, if_neg h2]        have hcost3 : TarskiQueryTree.cost f (g x) =            TarskiQueryTree.cost f (T a x hguard.1 hguard.2.2.2) + 1 := by          rw [hgx, TarskiQueryTree.cost.eq_2, if_neg h1, if_neg h2]        have hfxx : f x ≤ x := by          intro j          rcases Fin.eq_self_or_eq_succAbove i j with hji | ⟨t, ht⟩          · rw [hji]; exact le_of_lt h3          · rw [ht]; rw [hxsliced _ (Fin.succAbove_ne i t)]        obtain ⟨hT1, hT2, hT3, hT4⟩ := hTspec a x hax hpotx2 f hf ha hfxx        refine ⟨by rw [hrun3]; exact hT1, by rw [hrun3]; exact le_trans hT2 hxb,          by rw [hrun3]; exact hT3, ?_⟩        rw [hcost3]        have hp3 : tarski_box_query_le_succ_halving_pot n (k+1) a x + 1 ≤            tarski_box_query_le_succ_halving_pot n (k+1) a b := by          rw [hxdef]; exact hpstep.2        calc TarskiQueryTree.cost f (tarski_query_tree_slice_lift i c tq) +              (TarskiQueryTree.cost f (T a x hguard.1 hguard.2.2.2) + 1)            ≤ q + ((tarski_box_query_le_succ_halving_pot n (k+1) a x * (q + 1) + 2 ^ (k+1))                + 1) := by omega          _ = (tarski_box_query_le_succ_halving_pot n (k+1) a x + 1) * (q + 1) + 2 ^ (k+1) := by              ring          _ ≤ tarski_box_query_le_succ_halving_pot n (k+1) a b * (q + 1) + 2 ^ (k+1) := by              apply Nat.add_le_add_right              exact Nat.mul_le_mul_right _ hp3  obtain ⟨k1, k2, k3, k4⟩ := key  exact ⟨by rw [hbs.1, hrun_lift]; exact k1,         by rw [hbs.1, hrun_lift]; exact k2,         by rw [hbs.1, hrun_lift]; exact k3,         by rw [hbs.2, hrun_lift]; exact k4⟩/-- Main induction: every box admits a tree with cost at most `Φ · (q+1) + 2^(k+1)`. -/theorem tarski_box_query_le_succ_halving_aux (n k q : ℕ) [NeZero n]    (h : tarski_box_query_le n k q) :    ∀ (m : ℕ) (a b : Fin (k+1) → Fin n), a ≤ b →      tarski_box_query_le_succ_halving_pot n (k+1) a b ≤ m →      ∃ t : TarskiQueryTree n (k+1),        ∀ f : (Fin (k+1) → Fin n) → Fin (k+1) → Fin n,          Monotone f → a ≤ f a → f b ≤ b →            a ≤ TarskiQueryTree.run f t ∧ TarskiQueryTree.run f t ≤ b ∧            f (TarskiQueryTree.run f t) = TarskiQueryTree.run f t ∧            TarskiQueryTree.cost f t ≤              tarski_box_query_le_succ_halving_pot n (k+1) a b * (q + 1) + 2 ^ (k+1) := by  intro m  induction m using Nat.strong_induction_on with  | h m ih =>    intro a b hab hpot    by_cases hsmall : ∀ i : Fin (k+1), (b i : ℕ) - (a i) ≤ 1    · refine ⟨tarski_box_query_le_succ_halving_brute a (Finset.Icc a b).toList, ?_⟩      intro f hf ha hb      obtain ⟨x0, hx0a, hx0b, hx0f⟩ := tarski_subinterval_fixed_point n (k+1) f hf a b hab ha hb      have hL : ∃ y ∈ (Finset.Icc a b).toList, f y = y :=        ⟨x0, by rw [Finset.mem_toList, Finset.mem_Icc]; exact ⟨hx0a, hx0b⟩, hx0f⟩      obtain ⟨h1, h2, h3⟩ := tarski_box_query_le_succ_halving_brute_spec a        (Finset.Icc a b).toList f hL      rw [Finset.mem_toList, Finset.mem_Icc] at h1      refine ⟨h1.1, h1.2, h2, ?_⟩      have hcard : (Finset.Icc a b).card ≤ 2 ^ (k+1) := by        rw [Pi.card_Icc]        calc ∏ i : Fin (k+1), (Finset.Icc (a i) (b i)).card ≤ ∏ _i : Fin (k+1), 2 := by              apply Finset.prod_le_prod              · intro i _; simp              · intro i _                rw [Fin.card_Icc]                have h2' := hab i                have h3' := hsmall i                omega          _ = 2 ^ (k+1) := by simp      rw [Finset.length_toList] at h3      exact le_trans h3 (le_trans hcard (Nat.le_add_left _ _))    · obtain ⟨i, hi⟩ := not_forall.mp hsmall      exact tarski_box_query_le_succ_halving_step n k q m h ih a b hab hpot i (by omega)/-- Halving recursion: one extra dimension costs a multiplicative factor log₂ n. -/theorem tarski_box_query_le_succ_halving (n k q : ℕ) [NeZero n]    (h : tarski_box_query_le n k q) :    tarski_box_query_le n (k+1) (3 * (k+1) * (Nat.log 2 n + 2) * (q + 1) + 2 ^ (k+1)) := by  intro a b hab  obtain ⟨t, ht⟩ := tarski_box_query_le_succ_halving_aux n k q h    (tarski_box_query_le_succ_halving_pot n (k+1) a b) a b hab (le_refl _)  refine ⟨t, fun f hf ha hb => ?_⟩  obtain ⟨h1, h2, h3, h4⟩ := ht f hf ha hb  refine ⟨h1, h2, h3, le_trans h4 ?_⟩  have hpot1 : tarski_box_query_le_succ_halving_pot n (k+1) a b ≤ (k+1) * Nat.clog 2 n := by    unfold tarski_box_query_le_succ_halving_pot    calc ∑ j : Fin (k+1), Nat.clog 2 ((b j : ℕ) - (a j)) ≤ ∑ _j : Fin (k+1), Nat.clog 2 n := by          apply Finset.sum_le_sum          intro j _          refine Nat.clog_mono (b := 2) (c := 2) (by norm_num) (le_refl 2) ?_          have h1' : (b j : ℕ) < n := Fin.is_lt (b j)          omega      _ = (k+1) * Nat.clog 2 n := by simp  have hclog : Nat.clog 2 n ≤ Nat.log 2 n + 1 := by    have hb : 1 < 2 := by norm_num    rw [Nat.clog_le_iff_le_pow hb]    exact Nat.le_of_lt (Nat.lt_pow_succ_log_self hb n)  have hL : tarski_box_query_le_succ_halving_pot n (k+1) a b ≤      3 * (k+1) * (Nat.log 2 n + 2) := by    have hstep1 : tarski_box_query_le_succ_halving_pot n (k+1) a b ≤        (k+1) * (Nat.log 2 n + 1) := le_trans hpot1 (Nat.mul_le_mul_left _ hclog)    have hstep2 : (k+1) * (Nat.log 2 n + 1) ≤ 3 * (k+1) * (Nat.log 2 n + 2) := by      have h1' : Nat.log 2 n + 1 ≤ 3 * (Nat.log 2 n + 2) := by omega      calc (k+1) * (Nat.log 2 n + 1) ≤ (k+1) * (3 * (Nat.log 2 n + 2)) :=            Nat.mul_le_mul_left _ h1'        _ = 3 * (k+1) * (Nat.log 2 n + 2) := by ring    exact le_trans hstep1 hstep2  have hmul : tarski_box_query_le_succ_halving_pot n (k+1) a b * (q + 1) ≤      3 * (k+1) * (Nat.log 2 n + 2) * (q + 1) := Nat.mul_le_mul_right _ hL  exact Nat.add_le_add_right hmul _
See it in the graphDiscuss this resultChallenge it