tarski_slice_lower_bound
Monotonicity preservation on coordinate slices: fixing coordinate i to any value m ≥ a_i preserves the lower subinterval invariant a_j ≤ f(a^{(i,m)})_j for all coordinates j.
Statement
theorem tarski_slice_lower_bound (n k : ℕ) (f : (Fin k → Fin n) → (Fin k → Fin n)) (hf : Monotone f) (a : Fin k → Fin n) (ha : a ≤ f a) (i : Fin k) (m : Fin n) (ham : a i ≤ m) (j : Fin k) : a j ≤ f (fun l => if l = i then m else a l) j
- Source
- step towards tarski_query_complexity_five_le_log_sq
- Verified
- 18 Oct 2026
- Axioms
propext- Built on 2
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
- 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 establishes that if a ≤ f(a) for a monotone function f on the lattice of coordinate vectors, increasing the i-th coordinate from a_i to m ≥ a_i preserves the lower bound a_j ≤ f(a^{(i,m)})_j at every coordinate j. The proof first shows that the slice update a^{(i,m)} dominates a pointwise because it only increases coordinate i. Monotonicity of f then yields f(a) ≤ f(a^{(i,m)}), and transitivity with the invariant a ≤ f(a) yields the desired inequality at coordinate j.
The vector a is bounded pointwise by the modified vector that replaces coordinate i with m, that is, a ≤ (fun l => if l = i then m else a l).
We check the inequality coordinatewise for an arbitrary index l. If l = i, the value at this coordinate is m, and the inequality a(i) ≤ m holds by hypothesis ham. If l ≠ i, the coordinate remains a(l), so the inequality a(l) ≤ a(l) holds by reflexivity.
have hle : a ≤ (fun l => if l = i then m else a l) := by intro l by_cases h : l = i · subst h simpa using ham · simp [h]
At coordinate j, a(j) ≤ f(fun l => if l = i then m else a l)(j).
Applying the monotonicity of f (hf) to the pointwise bound a ≤ a^{(i, m)} (hle) yields f(a) ≤ f(a^{(i, m)}). Evaluating this inequality at coordinate j and combining it with the assumption a(j) ≤ f(a)(j) (ha) via transitivity of inequality (le_trans) concludes the proof.
uses
le_transhave hmono := hf hle exact le_trans (ha j) (hmono j)
le_trans- In any preorder, if a ≤ b and b ≤ c, then a ≤ c.
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: increasing coordinate i from a_i to m preserves a ≤ f(a^{(i,m)}). -/theorem tarski_slice_lower_bound (n k : ℕ) (f : (Fin k → Fin n) → (Fin k → Fin n)) (hf : Monotone f) (a : Fin k → Fin n) (ha : a ≤ f a) (i : Fin k) (m : Fin n) (ham : a i ≤ m) (j : Fin k) : a j ≤ f (fun l => if l = i then m else a l) j := by have hle : a ≤ (fun l => if l = i then m else a l) := by intro l by_cases h : l = i · subst h simpa using ham · simp [h] have hmono := hf hle exact le_trans (ha j) (hmono j)