tarski_slice_upper_bound
Monotonicity preservation on coordinate slices (upper bound): fixing coordinate i to any value m ≤ b_i preserves the upper subinterval invariant f(b^{(i,m)})_j ≤ b_j for all coordinates j.
Statement
theorem tarski_slice_upper_bound (n k : ℕ) (f : (Fin k → Fin n) → (Fin k → Fin n)) (hf : Monotone f) (b : Fin k → Fin n) (hb : f b ≤ b) (i : Fin k) (m : Fin n) (hbm : m ≤ b i) (j : Fin k) : f (fun l => if l = i then m else b l) j ≤ b j
- Source
- step towards tarski_query_complexity_five_le_log_sq
- Verified
- 18 Oct 2026
- Axioms
propext- 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 2
- tarski_slice_subbox_monotone_and_fixedFor 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…
- 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 states that decreasing coordinate i of an upper invariant point b (satisfying f(b) ≤ b) to any m ≤ b_i preserves the upper invariant f(b')_j ≤ b_j at every coordinate j. The proof first shows that the modified vector b' is pointwise bounded above by b by checking coordinate i and the remaining coordinates separately. It then applies the monotonicity of f to obtain f(b') ≤ f(b), which yields f(b')_j ≤ b_j after chaining with f(b)_j ≤ b_j by transitivity.
The modified vector b^{(i, m)}, obtained by setting the i-th coordinate of b to m, is pointwise less than or equal to b.
To show that the updated vector is bounded by b, we inspect each coordinate l. If l = i, its value is m, which is bounded by b_i by the hypothesis hbm. If l ≠ i, its value remains b_l, which is bounded by b_l by reflexivity (le_rfl).
uses
le_rflhave h_le : (fun l => if l = i then m else b l) ≤ b := by intro l dsimp split_ifs with h · subst h exact hbm · exact le_rfl
f(b^{(i, m)})_j ≤ b_j for any coordinate j.
Because f is monotone (hf), the pointwise inequality b^{(i, m)} ≤ b implies f(b^{(i, m)}) ≤ f(b), and evaluating at coordinate j gives f(b^{(i, m)})_j ≤ f(b)_j. Chaining this with the assumption f(b)_j ≤ b_j (hb j) by transitivity completes the proof.
exact (hf h_le j).trans (hb j)
le_rfl- In any preorder, every element is less than or equal to itself: a ≤ a.
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 preservation on coordinate slices: decreasing coordinate i from b_i to m preserves f(b^{(i,m)}) ≤ b. -/theorem tarski_slice_upper_bound (n k : ℕ) (f : (Fin k → Fin n) → (Fin k → Fin n)) (hf : Monotone f) (b : Fin k → Fin n) (hb : f b ≤ b) (i : Fin k) (m : Fin n) (hbm : m ≤ b i) (j : Fin k) : f (fun l => if l = i then m else b l) j ≤ b j := by have h_le : (fun l => if l = i then m else b l) ≤ b := by intro l dsimp split_ifs with h · subst h exact hbm · exact le_rfl exact (hf h_le j).trans (hb j)