tarski_subinterval_fixed_point
Subinterval 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].
Statement
theorem tarski_subinterval_fixed_point (n k : ℕ) [NeZero n]
(f : (Fin k → Fin n) → (Fin k → Fin n)) (hf : Monotone f)
(a b : Fin k → Fin n) (hab : a ≤ b) (ha : a ≤ f a) (hb : f b ≤ b) :
∃ x : Fin k → Fin n, a ≤ x ∧ x ≤ b ∧ f x = x- Source
- step towards tarski_query_complexity_five_le_log_sq
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- Used by 3
- 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_box_query_le_succ_halvingOne 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…
- 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…
The proof, explained
The proof applies the Knaster-Tarski fixed point theorem on the complete lattice of functions from Fin k to Fin n. By bundling the monotone map $f$ into an order homomorphism, we choose $x$ as the least fixed point of $f$ lying above $a$, which is constructed as the least fixed point of the operator $y \mapsto a \sqcup f(y)$. By definition, $x$ satisfies $a \le x$ and $f(x) = x$. Finally, the upper bound $x \le b$ holds by Knaster-Tarski because $b$ is a prefixpoint of $y \mapsto a \sqcup f(y)$, as $a \le b$ and $f(b) \le b$.
Define $x$ as the least fixed point of $f$ above $a$, which satisfies $f(x) = x$ and $a \le x$.
We bundle $f$ with its monotonicity hypothesis $hf$ into an order homomorphism $F$. Using the hypothesis $a \le f(a)$, we define $x$ as the next fixed point of $F$ starting from $a$ via `F.nextFixed`. By construction, $x$ is a fixed point of $f$ ($f(x) = x$) and satisfies $a \le x$ by `F.le_nextFixed`.
uses
F.le_nextFixedlet F : (Fin k → Fin n) →o (Fin k → Fin n) := ⟨f, hf⟩ have ha' : a ≤ F a := ha let x : Fin k → Fin n := (F.nextFixed a ha' : (Fin k → Fin n)) have hxfix : f x = x := (F.nextFixed a ha').2 have hax : a ≤ x := F.le_nextFixed ha'
$x \le b$
By definition of `nextFixed`, $x$ is the least fixed point of the operator $y \mapsto a \sqcup F(y)$. By `OrderHom.lfp_le`, to show this least fixed point is at most $b$, it suffices to check that $b$ is a prefixpoint, i.e., $a \sqcup f(b) \le b$. This follows from `sup_le` combined with the hypotheses $a \le b$ and $f(b) \le b$.
uses
OrderHom.lfp_le,sup_lehave hxb : x ≤ b := by change (OrderHom.const (Fin k → Fin n) a ⊔ F).lfp ≤ b apply OrderHom.lfp_le change a ⊔ f b ≤ b exact sup_le hab hb
There exists $x$ such that $a \le x$, $x \le b$, and $f(x) = x$.
We assemble the candidate point $x$ together with the established inequalities $a \le x$, $x \le b$, and the equality $f(x) = x$ to satisfy the existential conclusion.
exact ⟨x, hax, hxb, hxfix⟩
F.le_nextFixed- For an order homomorphism $F$ and a point $a$ satisfying $a \le F(a)$, $a$ is less than or equal to the next fixed point of $F$ above $a$.
OrderHom.lfp_le- For an order homomorphism $f$ on a complete lattice, if $f(b) \le b$, then the least fixed point of $f$ is at most $b$.
sup_le- In a join-semilattice, if $a \le c$ and $b \le c$, then the supremum $a \sqcup b \le c$.
- In Mathlib, the operator `OrderHom.nextFixed a ha'` is defined as the least fixed point of the map $y \mapsto a \sqcup F(y)$, which is why the proof of $x \le b$ unfolds $x$ to `(OrderHom.const ... a ⊔ F).lfp` and applies fixed-point reasoning.
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.
/-- Subinterval 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]. -/theorem tarski_subinterval_fixed_point (n k : ℕ) [NeZero n] (f : (Fin k → Fin n) → (Fin k → Fin n)) (hf : Monotone f) (a b : Fin k → Fin n) (hab : a ≤ b) (ha : a ≤ f a) (hb : f b ≤ b) : ∃ x : Fin k → Fin n, a ≤ x ∧ x ≤ b ∧ f x = x := by let F : (Fin k → Fin n) →o (Fin k → Fin n) := ⟨f, hf⟩ have ha' : a ≤ F a := ha let x : Fin k → Fin n := (F.nextFixed a ha' : (Fin k → Fin n)) have hxfix : f x = x := (F.nextFixed a ha').2 have hax : a ≤ x := F.le_nextFixed ha' have hxb : x ≤ b := by change (OrderHom.const (Fin k → Fin n) a ⊔ F).lfp ≤ b apply OrderHom.lfp_le change a ⊔ f b ≤ b exact sup_le hab hb exact ⟨x, hax, hxb, hxfix⟩