tarski_query_complexity_one_le_log
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.
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).
/-- 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⟩
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.
uses
tarski_one_pt_valtheorem 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
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.
uses
Subsingleton.elim,Fin.ext,tarski_one_pt_valtheorem 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
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.
uses
tarski_one_pt_mono,tarski_one_eq_pttheorem 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]
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.
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⟩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.
uses
le_transby_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⟩
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.
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⟩
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].
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 => ?_⟩
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.
uses
Nat.lt_pow_succ_log_self,tarski_one_bs_spec,Nat.zero_le,le_rfl,Fin.isLthave 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).
- The 1-dimensional chain of size n = m + 1 is formalized as functions `Fin 1 → Fin (m + 1)`, representing points on a grid with dimension 1. Consequently, points have a single coordinate at index 0.
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 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)