tarski_slice_subbox_monotone_and_fixed
For 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 y) (i.succAbove j) is monotone on [a', b'] (where a' = a ∘ i.succAbove, b' = b ∘ i.succAbove) and satisfies the sub-box invariants a' <= g a' and g b' <= b'. Moreover, any fixed point y of g lifts to an ambient point x = insertNth i c y in [a, b] that agrees with f(x) on all coordinates j != i.
Statement
theorem tarski_slice_subbox_monotone_and_fixed (n k : ℕ) [NeZero n] (f : (Fin (k+1) → Fin n) → (Fin (k+1) → Fin n)) (hf : Monotone f) (a b : Fin (k+1) → Fin n) (ha : a ≤ f a) (hb : f b ≤ b) (i : Fin (k+1)) (c : Fin n) (hac : a i ≤ c) (hcb : c ≤ b i) : let g : (Fin k → Fin n) → (Fin k → Fin n) := fun y j => f (Fin.insertNth i c y) (i.succAbove j) let a' : Fin k → Fin n := a ∘ i.succAbove let b' : Fin k → Fin n := b ∘ i.succAbove Monotone g ∧ a' ≤ g a' ∧ g b' ≤ b' ∧ ∀ y : Fin k → Fin n, a' ≤ y → y ≤ b' → g y = y → let x := Fin.insertNth i c y a ≤ x ∧ x ≤ b ∧ (∀ j : Fin (k+1), j ≠ i → f x j = x j)
- Source
- step towards tarski_box_query_le_succ_halving
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- 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 theorem reduces to four claims about the coordinate slice map g obtained by fixing coordinate i to value c. Monotonicity of g follows from that of f because coordinate insertion preserves the product ordering. The sub-box invariants a' ≤ g a' and g b' ≤ b' follow by transitivity from the ambient box invariants on f combined with the cut bounds a i ≤ c ≤ b i. Finally, any fixed point y of g in [a', b'] lifts by coordinate insertion to an ambient point x in [a, b] which agrees with f(x) away from coordinate i because each index j ≠ i corresponds to a slice coordinate m where f(x)_j = g(y)_m = y_m = x_j.
The theorem reduces to four independent claims: monotonicity of g, the lower invariant a' ≤ g a', the upper invariant g b' ≤ b', and the fixed-point lifting property.
We simplify the definitions of the coordinate slice map g and the projected lower and upper bounds a' and b', and split the four-part conjunction into four separate goals.
dsimp only refine ⟨?_, ?_, ?_, ?_⟩
The coordinate slice map g is monotone.
Let y ≤ y' and let j be any coordinate in Fin k. To show g y j ≤ g y' j, by monotonicity of f it suffices to show that inserting c at index i into y yields a vector bounded by the corresponding insertion into y'. At index i, both vectors evaluate to c by Fin.insertNth_apply_same. At any other coordinate, indexed by l via succAbove, Fin.insertNth_apply_succAbove reduces the inequality to y l ≤ y' l, which holds by assumption. Fin.insertNth_le_iff.mpr combines these two coordinate checks to establish the vector inequality, completing the step.
uses
Fin.insertNth_le_iff.mpr,Fin.insertNth_apply_same,Fin.insertNth_apply_succAbove· intro y y' hyy' intro j refine hf (Fin.insertNth_le_iff.mpr ⟨?_, ?_⟩) (i.succAbove j) · rw [Fin.insertNth_apply_same] · intro l simp only [Fin.insertNth_apply_succAbove] exact hyy' l
The slice map satisfies the lower sub-box invariant a' ≤ g a'.
For any coordinate j, the ambient lower invariant a ≤ f a implies a' j = a (i.succAbove j) ≤ f a (i.succAbove j). Using Fin.le_insertNth_iff.mpr with the hypothesis a i ≤ c (hac) and reflexivity a' ≤ a' (le_refl), we have a ≤ Fin.insertNth i c a'. Since f is monotone, f a ≤ f (Fin.insertNth i c a') = g a'. By transitivity (le_trans), a' j ≤ g a' j.
uses
le_trans,Fin.le_insertNth_iff.mpr,le_refl· intro j apply le_trans (ha (i.succAbove j)) exact hf (Fin.le_insertNth_iff.mpr ⟨hac, le_refl _⟩) (i.succAbove j)
The slice map satisfies the upper sub-box invariant g b' ≤ b'.
For any coordinate j, the hypothesis c ≤ b i (hcb) and reflexivity b' ≤ b' (le_refl) imply Fin.insertNth i c b' ≤ b by Fin.insertNth_le_iff.mpr. Monotonicity of f then gives g b' j = f (Fin.insertNth i c b') (i.succAbove j) ≤ f b (i.succAbove j). Combining this with the ambient upper invariant f b (i.succAbove j) ≤ b' j via transitivity (le_trans) yields g b' j ≤ b' j.
uses
le_trans,Fin.insertNth_le_iff.mpr,le_refl· intro j apply le_trans (hf (Fin.insertNth_le_iff.mpr ⟨hcb, le_refl _⟩) (i.succAbove j)) exact hb (i.succAbove j)
Any fixed point y of g in [a', b'] lifts to a point x in [a, b] that agrees with f x on all coordinates j ≠ i.
Given y with a' ≤ y ≤ b' and g y = y, define x = Fin.insertNth i c y. The bound a ≤ x follows from a i ≤ c and a' ≤ y via Fin.le_insertNth_iff.mpr, and x ≤ b follows from c ≤ b i and y ≤ b' via Fin.insertNth_le_iff.mpr, so x lies in [a, b]. For any coordinate j ≠ i, Fin.exists_succAbove_eq gives an index m with j = i.succAbove m. By Fin.insertNth_apply_succAbove, x (i.succAbove m) = y m, and evaluating the fixed-point equation g y = y at m via congr_fun shows that f x j = g y m = y m = x j.
uses
Fin.le_insertNth_iff.mpr,Fin.insertNth_le_iff.mpr,Fin.exists_succAbove_eq,Fin.insertNth_apply_succAbove,congr_fun· intro y hay hyb hgy refine ⟨?_, ?_, ?_⟩ · exact Fin.le_insertNth_iff.mpr ⟨hac, hay⟩ · exact Fin.insertNth_le_iff.mpr ⟨hcb, hyb⟩ · intro j hj obtain ⟨m, hm⟩ := Fin.exists_succAbove_eq hj subst hm simp only [Fin.insertNth_apply_succAbove] exact congr_fun hgy m
Fin.insertNth_apply_same- Evaluating a vector with x inserted at index i at index i itself gives x.
Fin.insertNth_apply_succAbove- Evaluating a vector with x inserted at index i at any coordinate other than i (written as i.succAbove j) gives the j-th component of the original vector.
Fin.insertNth_le_iff.mpr- The vector obtained by inserting x at index i into p is coordinatewise bounded by q if x ≤ q i and p is coordinatewise bounded by q on all remaining coordinates.
Fin.le_insertNth_iff.mpr- A vector q is coordinatewise bounded by the result of inserting x at index i into p if q i ≤ x and q on all remaining coordinates is bounded by p.
le_trans- Transitivity of order: if a ≤ b and b ≤ c, then a ≤ c.
le_refl- Reflexivity of order: a ≤ a for every a.
Fin.exists_succAbove_eq- Every index j ≠ i in Fin (k + 1) can be uniquely written as i.succAbove m for some m in Fin k.
congr_fun- Equality of functions implies equality of their evaluations: if f = g, then f a = g a.
- The function `Fin.succAbove i : Fin k → Fin (k + 1)` embeds dimension k into dimension k + 1 by skipping index i. Its counterpart `Fin.insertNth i c y` inserts the coordinate c at index i and populates all other indices using y.
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.
/-- Monotonicity and sub-box bounds for the coordinate slice map, and lifting of a slice fixed point to an ambient point fixed off coordinate i. -/theorem tarski_slice_subbox_monotone_and_fixed (n k : ℕ) [NeZero n] (f : (Fin (k+1) → Fin n) → (Fin (k+1) → Fin n)) (hf : Monotone f) (a b : Fin (k+1) → Fin n) (ha : a ≤ f a) (hb : f b ≤ b) (i : Fin (k+1)) (c : Fin n) (hac : a i ≤ c) (hcb : c ≤ b i) : let g : (Fin k → Fin n) → (Fin k → Fin n) := fun y j => f (Fin.insertNth i c y) (i.succAbove j) let a' : Fin k → Fin n := a ∘ i.succAbove let b' : Fin k → Fin n := b ∘ i.succAbove Monotone g ∧ a' ≤ g a' ∧ g b' ≤ b' ∧ ∀ y : Fin k → Fin n, a' ≤ y → y ≤ b' → g y = y → let x := Fin.insertNth i c y a ≤ x ∧ x ≤ b ∧ (∀ j : Fin (k+1), j ≠ i → f x j = x j) := by dsimp only refine ⟨?_, ?_, ?_, ?_⟩ · intro y y' hyy' intro j refine hf (Fin.insertNth_le_iff.mpr ⟨?_, ?_⟩) (i.succAbove j) · rw [Fin.insertNth_apply_same] · intro l simp only [Fin.insertNth_apply_succAbove] exact hyy' l · intro j apply le_trans (ha (i.succAbove j)) exact hf (Fin.le_insertNth_iff.mpr ⟨hac, le_refl _⟩) (i.succAbove j) · intro j apply le_trans (hf (Fin.insertNth_le_iff.mpr ⟨hcb, le_refl _⟩) (i.succAbove j)) exact hb (i.succAbove j) · intro y hay hyb hgy refine ⟨?_, ?_, ?_⟩ · exact Fin.le_insertNth_iff.mpr ⟨hac, hay⟩ · exact Fin.insertNth_le_iff.mpr ⟨hcb, hyb⟩ · intro j hj obtain ⟨m, hm⟩ := Fin.exists_succAbove_eq hj subst hm simp only [Fin.insertNth_apply_succAbove] exact congr_fun hgy m