AFTD Auto-Formalizing Theoretical Domains

terminal_boxes

def

Given a sliding tree t : DiagramSlidingTree D and a list $l$ of boxes representing a tableau on $D$, terminal_boxes t l transports $l$ to the leaf: at each node with consecutive admissible pair $(b_1, b_2)$, if $b_2$ precedes $b_1$ in $l$ ($l.idxOf b_2 < l.idxOf b_1$, corresponding to the entry of $b_1$ being strictly greater than the entry of $b_2$), it slides vertically and continues in the left subtree; otherwise it slides horizontally and continues in the right subtree.

Statement

def terminal_boxes {D : Finset (ℕ × ℕ)} (t : DiagramSlidingTree D) (l : List (ℕ × ℕ)) : List (ℕ × ℕ)
Defined in
arXiv:2611.07715, Definition 4.12 and Proposition 3.21
Verified
06 Nov 2026
Axioms
none listed
Built on 7
  • DiagramSlidingTreeA sliding tree DiagramSlidingTree D on a diagram $D$ is either a leaf diagram with no crossings (…
  • diagram_vertical_slide_boxFor $D : \text{Finset } (\mathbb{N} \times \mathbb{N})$, $b_1, b_2, x \in \mathbb{N} \times \mathbb{N}$, and $c = (b_2.1, b_1.2)$,…
  • diagram_horizontal_slide_boxFor $D : \text{Finset } (\mathbb{N} \times \mathbb{N})$, $b_1, b_2, x \in \mathbb{N} \times \mathbb{N}$, and $c = (b_2.1, b_1.2)$,…
  • diagram_is_consecutive_admissible_pairAn admissible pair $(b_1, b_2)$ in a diagram $D$ is consecutive (diagram_is_consecutive_admissible_pair D b_1 b_2) if it is admissible…
  • diagram_vertical_slideThe vertical slide of a diagram $D$ with respect to cells $b_1, b_2$ is the diagram diagram_vertical_slide D b_1 b_2 obtained as the…
  • diagram_crossingTwo cells $u, v \in \mathbb{N} \times \mathbb{N}$ form a crossing (diagram_crossing u v) if…
  • diagram_horizontal_slideThe horizontal slide of a diagram $D$ with respect to cells $b_1, b_2$ is the diagram diagram_horizontal_slide D b_1 b_2 obtained as the…
Used by 2

Read back from the Lean

A recursive function terminal_boxes that takes a sliding tree t : DiagramSlidingTree D (associated with a finite set D ⊆ ℕ × ℕ) and a list l : List (ℕ × ℕ), returning a List (ℕ × ℕ). It is defined by recursion on t: 1. If t is a leaf node DiagramSlidingTree.leaf D _, it returns l. 2. If t is an internal node DiagramSlidingTree.node D b₁ b₂ _ left right: - If the first index of b₂ in l is strictly less than the first index of b₁ in l (l.idxOf b₂ < l.idxOf b₁), it recurses on left with the list l.map (diagram_vertical_slide_box D b₁ b₂). - Otherwise (i.e., if b₂ does not appear before b₁ in l, including the case where neither is in l or only b₁ is in l), it recurses on right with the list l.map (diagram_horizontal_slide_box D b₁ b₂).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Transports an ordered list of boxes along the root-to-leaf path determined by entry comparison at each node. -/
def terminal_boxes {D : Finset (ℕ × ℕ)} (t : DiagramSlidingTree D) (l : List (ℕ × ℕ)) : List (ℕ × ℕ) := match t with
  | DiagramSlidingTree.leaf _ _ => l
  | DiagramSlidingTree.node D b₁ b₂ _ left right =>
    if l.idxOf b₂ < l.idxOf b₁ then
      terminal_boxes left (l.map (diagram_vertical_slide_box D b₁ b₂))
    else
      terminal_boxes right (l.map (diagram_horizontal_slide_box D b₁ b₂))
See it in the graphDiscuss this resultChallenge it