AFTD Auto-Formalizing Theoretical Domains

tarski_slice_lower_bound

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
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.

  1. 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.

    lines 5–10

      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]
  2. 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.

    lines 11–12

    uses le_trans

      have 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

/-- 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)
See it in the graphDiscuss this resultChallenge it