AFTD Auto-Formalizing Theoretical Domains

tarski_subinterval_slice_shrink

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
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.

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

    lines 8–14

    uses le_total, eq_or_lt_of_le

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

    lines 15–21

    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⟩
  3. 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.

    lines 22–28

    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

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