AFTD Auto-Formalizing Theoretical Domains

tarski_slice_subbox_monotone_and_fixed

theoremverified

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

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

    lines 13–14

      dsimp only
      refine ⟨?_, ?_, ?_, ?_⟩
  2. 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.

    lines 15–21

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

    lines 22–24

    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)
  4. 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.

    lines 25–27

    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)
  5. 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.

    lines 28–36

    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.

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