AFTD Auto-Formalizing Theoretical Domains

tarski_query_complexity_one_le_log

theoremverifiedformalization

One-dimensional Tarski by binary search: for n ≥ 1, a fixed point of any monotone map on the chain {0, …, n−1} can be found with at most ⌊log₂ n⌋ + 1 queries.

Statement

theorem tarski_query_complexity_one_le_log (n : ℕ) (hn : 1 ≤ n) :
    tarski_query_complexity_le n 1 (Nat.log 2 n + 1)
Formalizes
arXiv:2610.07055 (Tarski fixed points in quasi-FPT queries), Sec. 1 (the binary search baseline, which the recursive algorithm giving O(log^k n) builds on); the case k = 1
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • tarski_query_complexity_leTarski(n, k) ≤ q: some deterministic query algorithm finds a fixed point of every monotone map f : [n]^k → [n]^k (componentwise order)…
  • 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.runThe point a query tree outputs when the black box is f.
  • TarskiQueryTree.costThe number of queries a query tree makes when the black box is f (the length of the path f follows).

The proof, explained

The one-dimensional Tarski fixed point theorem on {0, …, n−1} is proved by binary search. Given a monotone function f and an interval [lo, hi] with f(lo) ≥ lo and f(hi) ≤ hi, querying the midpoint either finds a fixed point immediately or preserves the boundary invariants on a subinterval of half the size. Initializing on [0, n−1] with fuel depth ⌊log₂ n⌋ ensures the search terminates at a fixed point within ⌊log₂ n⌋ + 1 queries.

  1. The function tarski_one_pt embeds an index i into the chain Fin 1 → Fin (m + 1) as min(i, m).

    The point assigns to the single coordinate in Fin 1 the value min(i, m). Linear arithmetic verifies that min(i, m) < m + 1 so that it is a valid element of Fin (m + 1).

    lines 1–2

    /-- The point `min i m` of the chain `{0, …, m}`, as a point of `[m+1]^1`. -/
    def tarski_one_pt (m i : ℕ) : Fin 1 → Fin (m + 1) := fun _ => ⟨min i m, by omega⟩
  2. The embedding tarski_one_pt is monotone in the index.

    Given i ≤ j, we compare tarski_one_pt m i and tarski_one_pt m j pointwise at their single coordinate. Rewriting with tarski_one_pt_val reduces this to min(i, m) ≤ min(j, m), which holds by linear arithmetic.

    lines 16–20

    uses tarski_one_pt_val

    theorem tarski_one_pt_mono (m : ℕ) {i j : ℕ} (h : i ≤ j) : tarski_one_pt m i ≤ tarski_one_pt m j := by
      intro x
      show ((tarski_one_pt m i x : Fin (m + 1)) : ℕ) ≤ tarski_one_pt m j x
      simp only [tarski_one_pt_val]
      omega
  3. Any point x in Fin 1 → Fin (m + 1) whose single coordinate is i ≤ m equals tarski_one_pt m i.

    By function extensionality, it suffices to check the single coordinate j : Fin 1. Since Fin 1 is a subsingleton, Subsingleton.elim gives j = 0. By Fin.ext, the equality reduces to x(0) = min(i, m), which holds by tarski_one_pt_val and the assumption i ≤ m.

    lines 22–29

    uses Subsingleton.elim, Fin.ext, tarski_one_pt_val

    theorem tarski_one_eq_pt (m i : ℕ) (hi : i ≤ m) (x : Fin 1 → Fin (m + 1)) (h : (x 0 : ℕ) = i) :
        x = tarski_one_pt m i := by
      funext j
      have : j = 0 := Subsingleton.elim _ _
      subst this
      apply Fin.ext
      rw [h, tarski_one_pt_val]
      omega
  4. Monotone maps preserve chain order, and the binary search specification tarski_one_bs_spec holds in the base case d = 0.

    Composing f with the monotone embedding tarski_one_pt_mono shows that f is monotone in the index. We proceed by induction on depth d. When d = 0, the length condition (hi - lo + 1) < 2 forces hi = lo. The boundary conditions lo ≤ f(lo)₀ and f(hi)₀ ≤ hi then sandwich f(lo)₀ = lo. By tarski_one_eq_pt, this point is a fixed point of f, and the query tree outputs it with cost 0 ≤ 0 + 1.

    lines 31–49

    uses tarski_one_pt_mono, tarski_one_eq_pt

    theorem tarski_one_bs_spec (m : ℕ) (f : (Fin 1 → Fin (m + 1)) → (Fin 1 → Fin (m + 1)))
        (hf : Monotone f) :
        ∀ d lo hi, lo ≤ hi → hi ≤ m → hi - lo + 1 < 2 ^ (d + 1) →
          lo ≤ (f (tarski_one_pt m lo) 0 : ℕ) → (f (tarski_one_pt m hi) 0 : ℕ) ≤ hi →
          f ((tarski_one_bs m d lo hi).run f) = (tarski_one_bs m d lo hi).run f ∧
            (tarski_one_bs m d lo hi).cost f ≤ d + 1 := by
      have hmono : ∀ {i j : ℕ}, i ≤ j →
          (f (tarski_one_pt m i) 0 : ℕ) ≤ f (tarski_one_pt m j) 0 :=
        fun h => hf (tarski_one_pt_mono m h) 0
      intro d
      induction d with
      | zero =>
        intro lo hi hlh hhm hsz hlo hhi
        have : hi = lo := by simp at hsz; omega
        subst this
        refine ⟨?_, ?_⟩
        · simp only [tarski_one_bs, TarskiQueryTree.run]
          exact tarski_one_eq_pt m hi hhm _ (by omega)
        · simp [tarski_one_bs, TarskiQueryTree.cost]
  5. In the inductive step, if the midpoint is already a fixed point, the search tree outputs it immediately.

    We query the midpoint mid = (lo + hi) / 2. If f(mid)₀ = mid, then tarski_one_eq_pt identifies mid as a fixed point of f. The tree outputs it using 1 query, which is at most (d + 1) + 1.

    lines 50–55

    uses tarski_one_eq_pt

      | succ d ih =>
        intro lo hi hlh hhm hsz hlo hhi
        have hP : 2 ^ (d + 1 + 1) = 2 * 2 ^ (d + 1) := by ring
        by_cases h1 : (f (tarski_one_pt m ((lo + hi) / 2)) 0 : ℕ) = (lo + hi) / 2
        · simp only [tarski_one_bs, TarskiQueryTree.run, TarskiQueryTree.cost, h1, if_true]
          exact ⟨tarski_one_eq_pt m _ (by omega) _ h1, by omega⟩
  6. If f(mid)₀ < mid, the search recurses on the lower subinterval [lo, mid - 1].

    When f(mid)₀ < mid, the boundary conditions lo ≤ f(lo)₀ and f(mid - 1)₀ ≤ mid - 1 are preserved by transitivity (le_trans) and monotonicity of f. The new subinterval has length strictly less than 2^(d + 1). Applying the induction hypothesis gives a fixed point with query cost at most d + 1, so the total cost including the midpoint query is at most d + 2.

    lines 56–63

    uses le_trans

        by_cases h2 : (f (tarski_one_pt m ((lo + hi) / 2)) 0 : ℕ) < (lo + hi) / 2
        · have hl : lo ≤ (f (tarski_one_pt m ((lo + hi) / 2)) 0 : ℕ) :=
            le_trans hlo (hmono (by omega))
          have := ih lo ((lo + hi) / 2 - 1) (by omega) (by omega) (by omega) hlo
            (by have := hmono (show (lo + hi) / 2 - 1 ≤ (lo + hi) / 2 by omega); omega)
          simp only [tarski_one_bs, TarskiQueryTree.run, TarskiQueryTree.cost, h1, h2, if_false,
            if_true]
          exact ⟨this.1, by omega⟩
  7. If f(mid)₀ > mid, the search recurses on the upper subinterval [mid + 1, hi].

    When f(mid)₀ > mid, the boundary conditions mid + 1 ≤ f(mid + 1)₀ and f(hi)₀ ≤ hi are preserved by transitivity (le_trans) and monotonicity. The new subinterval length is strictly less than 2^(d + 1). Applying the induction hypothesis yields a fixed point with total query cost at most d + 2.

    lines 64–68

    uses le_trans

        · have hh : (f (tarski_one_pt m ((lo + hi) / 2)) 0 : ℕ) ≤ hi := le_trans (hmono (by omega)) hhi
          have := ih ((lo + hi) / 2 + 1) hi (by omega) hhm (by omega)
            (by have := hmono (show (lo + hi) / 2 ≤ (lo + hi) / 2 + 1 by omega); omega) hhi
          simp only [tarski_one_bs, TarskiQueryTree.run, TarskiQueryTree.cost, h1, h2, if_false]
          exact ⟨this.1, by omega⟩
  8. For the main theorem, rewrite n as m + 1 and instantiate the binary search tree on [0, m].

    Since n ≥ 1, we write n = m + 1 for m = n - 1. We choose the binary search tree tarski_one_bs with fuel depth ⌊log₂ (m + 1)⌋ on the initial interval [0, m].

    lines 70–73

    theorem tarski_query_complexity_one_le_log (n : ℕ) (hn : 1 ≤ n) :
        tarski_query_complexity_le n 1 (Nat.log 2 n + 1) := by
      obtain ⟨m, rfl⟩ : ∃ m, n = m + 1 := ⟨n - 1, by omega⟩
      refine ⟨tarski_one_bs m (Nat.log 2 (m + 1)) 0 m, fun f hf => ?_⟩
  9. The binary search tree finds a fixed point of f within ⌊log₂ n⌋ + 1 queries.

    We apply tarski_one_bs_spec on [0, m]. The interval size m + 1 is strictly less than 2^(⌊log₂ (m + 1)⌋ + 1) by Nat.lt_pow_succ_log_self. The lower boundary condition 0 ≤ f(0)₀ holds by Nat.zero_le, and the upper boundary condition f(m)₀ ≤ m holds because the codomain is Fin (m + 1) by Fin.isLt. Reflexivity le_rfl handles m ≤ m.

    lines 74–76

    uses Nat.lt_pow_succ_log_self, tarski_one_bs_spec, Nat.zero_le, le_rfl, Fin.isLt

      have hlt := Nat.lt_pow_succ_log_self (b := 2) (by norm_num) (m + 1)
      exact tarski_one_bs_spec m f hf _ 0 m (Nat.zero_le _) le_rfl (by omega) (Nat.zero_le _)
        (by have := (f (tarski_one_pt m m) 0).isLt; omega)
Fin.ext
Two elements of `Fin n` are equal if and only if their underlying natural values are equal.
Fin.isLt
The underlying natural value of any element of `Fin n` is strictly less than n.
le_rfl
Reflexivity of less-than-or-equal: every element in a preorder is ≤ itself.
le_trans
Transitivity of less-than-or-equal: if a ≤ b and b ≤ c, then a ≤ c.
Nat.lt_pow_succ_log_self
For any base b > 1 and natural number x, x is strictly less than b^(⌊log_b x⌋ + 1).
Nat.zero_le
Zero is less than or equal to any natural number.
Subsingleton.elim
Any two elements of a subsingleton type are equal. In particular, any index j : Fin 1 is equal to 0.
tarski_one_bs_spec
Given a monotone map f on the chain {0, …, m} and an interval [lo, hi] satisfying the boundary conditions lo ≤ f(lo)₀ and f(hi)₀ ≤ hi with length strictly less than 2^(d + 1), binary search of depth d returns a fixed point of f using at most d + 1 queries.
tarski_one_eq_pt
For i ≤ m, any point x in Fin 1 → Fin (m + 1) with x(0) = i is equal to tarski_one_pt m i.
tarski_one_pt_mono
Embedding indices into the 1-dimensional chain is monotone: if i ≤ j, then tarski_one_pt m i ≤ tarski_one_pt m j.
tarski_one_pt_val
The value of the single coordinate of tarski_one_pt m i is min(i, m).

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 point `min i m` of the chain `{0, …, m}`, as a point of `[m+1]^1`. -/def tarski_one_pt (m i : ℕ) : Fin 1 → Fin (m + 1) := fun _ => ⟨min i m, by omega⟩/-- Binary search on `[lo, hi]` with `d` levels of fuel. -/def tarski_one_bs (m : ℕ) : ℕ → ℕ → ℕ → TarskiQueryTree (m + 1) 1  | 0, lo, _ => .output (tarski_one_pt m lo)  | d + 1, lo, hi =>    .query (tarski_one_pt m ((lo + hi) / 2)) (fun y =>      if (y 0 : ℕ) = (lo + hi) / 2 then .output (tarski_one_pt m ((lo + hi) / 2))      else if (y 0 : ℕ) < (lo + hi) / 2 then tarski_one_bs m d lo ((lo + hi) / 2 - 1)      else tarski_one_bs m d ((lo + hi) / 2 + 1) hi)theorem tarski_one_pt_val (m i : ℕ) (j : Fin 1) : ((tarski_one_pt m i j : Fin (m + 1)) : ℕ) = min i m :=  rfltheorem tarski_one_pt_mono (m : ℕ) {i j : ℕ} (h : i ≤ j) : tarski_one_pt m i ≤ tarski_one_pt m j := by  intro x  show ((tarski_one_pt m i x : Fin (m + 1)) : ℕ) ≤ tarski_one_pt m j x  simp only [tarski_one_pt_val]  omegatheorem tarski_one_eq_pt (m i : ℕ) (hi : i ≤ m) (x : Fin 1 → Fin (m + 1)) (h : (x 0 : ℕ) = i) :    x = tarski_one_pt m i := by  funext j  have : j = 0 := Subsingleton.elim _ _  subst this  apply Fin.ext  rw [h, tarski_one_pt_val]  omegatheorem tarski_one_bs_spec (m : ℕ) (f : (Fin 1 → Fin (m + 1)) → (Fin 1 → Fin (m + 1)))    (hf : Monotone f) :    ∀ d lo hi, lo ≤ hi → hi ≤ m → hi - lo + 1 < 2 ^ (d + 1) →      lo ≤ (f (tarski_one_pt m lo) 0 : ℕ) → (f (tarski_one_pt m hi) 0 : ℕ) ≤ hi →      f ((tarski_one_bs m d lo hi).run f) = (tarski_one_bs m d lo hi).run f ∧        (tarski_one_bs m d lo hi).cost f ≤ d + 1 := by  have hmono : ∀ {i j : ℕ}, i ≤ j →      (f (tarski_one_pt m i) 0 : ℕ) ≤ f (tarski_one_pt m j) 0 :=    fun h => hf (tarski_one_pt_mono m h) 0  intro d  induction d with  | zero =>    intro lo hi hlh hhm hsz hlo hhi    have : hi = lo := by simp at hsz; omega    subst this    refine ⟨?_, ?_⟩    · simp only [tarski_one_bs, TarskiQueryTree.run]      exact tarski_one_eq_pt m hi hhm _ (by omega)    · simp [tarski_one_bs, TarskiQueryTree.cost]  | succ d ih =>    intro lo hi hlh hhm hsz hlo hhi    have hP : 2 ^ (d + 1 + 1) = 2 * 2 ^ (d + 1) := by ring    by_cases h1 : (f (tarski_one_pt m ((lo + hi) / 2)) 0 : ℕ) = (lo + hi) / 2    · simp only [tarski_one_bs, TarskiQueryTree.run, TarskiQueryTree.cost, h1, if_true]      exact ⟨tarski_one_eq_pt m _ (by omega) _ h1, by omega⟩    by_cases h2 : (f (tarski_one_pt m ((lo + hi) / 2)) 0 : ℕ) < (lo + hi) / 2    · have hl : lo ≤ (f (tarski_one_pt m ((lo + hi) / 2)) 0 : ℕ) :=        le_trans hlo (hmono (by omega))      have := ih lo ((lo + hi) / 2 - 1) (by omega) (by omega) (by omega) hlo        (by have := hmono (show (lo + hi) / 2 - 1 ≤ (lo + hi) / 2 by omega); omega)      simp only [tarski_one_bs, TarskiQueryTree.run, TarskiQueryTree.cost, h1, h2, if_false,        if_true]      exact ⟨this.1, by omega⟩    · have hh : (f (tarski_one_pt m ((lo + hi) / 2)) 0 : ℕ) ≤ hi := le_trans (hmono (by omega)) hhi      have := ih ((lo + hi) / 2 + 1) hi (by omega) hhm (by omega)        (by have := hmono (show (lo + hi) / 2 ≤ (lo + hi) / 2 + 1 by omega); omega) hhi      simp only [tarski_one_bs, TarskiQueryTree.run, TarskiQueryTree.cost, h1, h2, if_false]      exact ⟨this.1, by omega⟩theorem tarski_query_complexity_one_le_log (n : ℕ) (hn : 1 ≤ n) :    tarski_query_complexity_le n 1 (Nat.log 2 n + 1) := by  obtain ⟨m, rfl⟩ : ∃ m, n = m + 1 := ⟨n - 1, by omega⟩  refine ⟨tarski_one_bs m (Nat.log 2 (m + 1)) 0 m, fun f hf => ?_⟩  have hlt := Nat.lt_pow_succ_log_self (b := 2) (by norm_num) (m + 1)  exact tarski_one_bs_spec m f hf _ 0 m (Nat.zero_le _) le_rfl (by omega) (Nat.zero_le _)    (by have := (f (tarski_one_pt m m) 0).isLt; omega)
See it in the graphDiscuss this resultChallenge it