tarski_subinterval_slice_shrink
Slicing 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 shows x is a fixed point, or x ≤ f(x) and f has a fixed point in [x, b], or f(x) ≤ x and f has a fixed point in [a, x].
Statement
theorem tarski_subinterval_slice_shrink (n k : ℕ) [NeZero n]
(f : (Fin k → Fin n) → (Fin k → Fin n)) (hf : Monotone f)
(a b : Fin k → Fin n) (ha : a ≤ f a) (hb : f b ≤ b)
(x : Fin k → Fin n) (hax : a ≤ x) (hxb : x ≤ b) (i : Fin k)
(hslice : ∀ j : Fin k, j ≠ i → f x j = x j) :
(f x = x) ∨ (x ≤ f x ∧ ∃ z, x ≤ z ∧ z ≤ b ∧ f z = z) ∨ (f x ≤ x ∧ ∃ z, a ≤ z ∧ z ≤ x ∧ f z = z)- Source
- step towards tarski_query_complexity_five_le_log_sq
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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].
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- 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…
The proof, explained
The proof proceeds by trichotomy on coordinate i, comparing x i with f(x) i. If x i = f(x) i, then f(x) = x across all coordinates because all other coordinates are already fixed by the slice hypothesis. If x i < f(x) i, then x ≤ f(x) componentwise, and Tarski's subinterval fixed point theorem on [x, b] guarantees a fixed point in that upper subinterval. Otherwise f(x) i ≤ x i, which implies f(x) ≤ x componentwise, and the theorem on [a, x] guarantees a fixed point in that lower subinterval.
If x i = f x i, then x is a fixed point of f (f x = x).
By the totality of the linear order on Fin n (`le_total`), either x i ≤ f x i or f x i ≤ x i. In the former branch, `eq_or_lt_of_le` further splits into x i = f x i or x i < f x i. When x i = f x i, we show f x = x by function extensionality over coordinates j: if j = i, then f x i = x i by assumption; if j ≠ i, then f x j = x j by the slice fixed-point hypothesis `hslice`. This establishes the first disjunct.
uses
le_total,eq_or_lt_of_lercases le_total (x i) (f x i) with h | h · rcases eq_or_lt_of_le h with he | hlt · left funext j by_cases hj : j = i · subst hj; exact he.symm · exact hslice j hj
If x i < f x i, then x ≤ f x and f has a fixed point in [x, b].
Selecting the second disjunct, we first show x ≤ f x coordinatewise: at coordinate i, x i ≤ f x i follows from x i < f x i; at any other coordinate j ≠ i, x j = f x j by `hslice`, so x j ≤ f x j. Then, because x ≤ b, x ≤ f x, and f b ≤ b, `tarski_subinterval_fixed_point` applied to the subinterval [x, b] yields a fixed point z such that x ≤ z ≤ b and f z = z.
uses
tarski_subinterval_fixed_point· right; left have hxf : x ≤ f x := by intro j by_cases hj : j = i · subst hj; exact hlt.le · rw [hslice j hj] exact ⟨hxf, tarski_subinterval_fixed_point n k f hf x b hxb hxf hb⟩
If f x i ≤ x i, then f x ≤ x and f has a fixed point in [a, x].
Selecting the third disjunct, we first show f x ≤ x coordinatewise: at coordinate i, f x i ≤ x i is our case hypothesis; at coordinates j ≠ i, f x j = x j by `hslice`, so f x j ≤ x j. Then, because a ≤ x, a ≤ f a, and f x ≤ x, `tarski_subinterval_fixed_point` applied to the subinterval [a, x] yields a fixed point z such that a ≤ z ≤ x and f z = z.
uses
tarski_subinterval_fixed_point· right; right have hfx : f x ≤ x := by intro j by_cases hj : j = i · subst hj; exact h · rw [hslice j hj] exact ⟨hfx, tarski_subinterval_fixed_point n k f hf a x hax ha hfx⟩
le_total- In a linear order, any two elements are comparable: either a ≤ b or b ≤ a.
eq_or_lt_of_le- In a partial order, if a ≤ b, then either a = b or a < b.
tarski_subinterval_fixed_point- A monotone map on a finite grid Fin k → Fin n has a fixed point in any subinterval [a, b] satisfying a ≤ b, a ≤ f(a), and f(b) ≤ b.
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.
/-- Slicing contraction principle: a slice fixed point with all other coordinates fixed contracts the search sub-box along coordinate i while preserving the subinterval lattice invariant. -/theorem tarski_subinterval_slice_shrink (n k : ℕ) [NeZero n] (f : (Fin k → Fin n) → (Fin k → Fin n)) (hf : Monotone f) (a b : Fin k → Fin n) (ha : a ≤ f a) (hb : f b ≤ b) (x : Fin k → Fin n) (hax : a ≤ x) (hxb : x ≤ b) (i : Fin k) (hslice : ∀ j : Fin k, j ≠ i → f x j = x j) : (f x = x) ∨ (x ≤ f x ∧ ∃ z, x ≤ z ∧ z ≤ b ∧ f z = z) ∨ (f x ≤ x ∧ ∃ z, a ≤ z ∧ z ≤ x ∧ f z = z) := by rcases le_total (x i) (f x i) with h | h · rcases eq_or_lt_of_le h with he | hlt · left funext j by_cases hj : j = i · subst hj; exact he.symm · exact hslice j hj · right; left have hxf : x ≤ f x := by intro j by_cases hj : j = i · subst hj; exact hlt.le · rw [hslice j hj] exact ⟨hxf, tarski_subinterval_fixed_point n k f hf x b hxb hxf hb⟩ · right; right have hfx : f x ≤ x := by intro j by_cases hj : j = i · subst hj; exact h · rw [hslice j hj] exact ⟨hfx, tarski_subinterval_fixed_point n k f hf a x hax ha hfx⟩