AFTD Auto-Formalizing Theoretical Domains

open_problem_1285_partial_no_crossings

theoremverified

For every finite diagram $D \subseteq \mathbb{N} \times \mathbb{N}$ having no crossings (∀ u ∈ D, ∀ v ∈ D, ¬ diagram_crossing u v), the leaf sliding tree DiagramSlidingTree.leaf D h satisfies agreement with descents (diagram_slide_expansion_agrees_with_descents D (DiagramSlidingTree.leaf D h)).

Statement

theorem open_problem_1285_partial_no_crossings (D : Finset (ℕ × ℕ)) (h : ∀ u ∈ D, ∀ v ∈ D, ¬ diagram_crossing u v) : diagram_slide_expansion_agrees_with_descents D (DiagramSlidingTree.leaf D h)
Source
arXiv:2611.07715, Theorem 3.22
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • diagram_crossingTwo cells $u, v \in \mathbb{N} \times \mathbb{N}$ form a crossing (diagram_crossing u v) if…
  • DiagramSlidingTreeA sliding tree DiagramSlidingTree D on a diagram $D$ is either a leaf diagram with no crossings (…
  • diagram_slide_expansion_agrees_with_descentsA sliding tree t on a finite diagram $D$ satisfies diagram_slide_expansion_agrees_with_descents D t if for every list $l$ representing…
  • terminal_boxesGiven a sliding tree t : DiagramSlidingTree D and a list $l$ of boxes representing a tableau on $D$, terminal_boxes t l transports $l$…
  • is_standard_young_tableau_listA list $l$ of cells in $\mathbb{N} \times \mathbb{N}$ represents a standard Young tableau on a finite diagram $D$…
  • list_descent_atA list of cells $l$ has a row descent at index $k$ (list_descent_at l k) if there exist cells $u$ and $v$ such that $l[k]? = some u$,…
Used by 1

Read back from the Lean

For every finite set $D$ of pairs of natural numbers ($D : \text{Finset}(\mathbb{N} \times \mathbb{N})$), and every hypothesis $h$ asserting that no two elements in $D$ cross (i.e., for all $u, v \in D$, neither $(u_1 < v_1 \land v_2 < u_2)$ nor $(v_1 < u_1 \land u_2 < v_2)$ holds), the tree DiagramSlidingTree.leaf D h satisfies diagram_slide_expansion_agrees_with_descents: for every list $l$ of pairs in $\mathbb{N} \times \mathbb{N}$, if $l$ is a standard Young tableau list for $D$, then for every $k \in \mathbb{N}$, $l$ has a descent at $k$ after applying terminal_boxes along the leaf tree if and only if $l$ has a descent at $k$.

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

The proof, explained

The theorem states that for any diagram D without crossings, the trivial sliding tree consisting of a single leaf satisfies the descent agreement property. Unfolding the definition, one must show that the descent positions of any standard Young tableau list on D are preserved by the sliding tree. For a leaf node, the sliding process is the identity by definition, returning the original list unchanged. Therefore, the descents before and after the operation are identical, and the equivalence holds by reflexivity.

  1. It suffices to fix an arbitrary list l and index k, and verify that the descent condition at k is preserved.

    The property `diagram_slide_expansion_agrees_with_descents` requires that for any list l that is a standard Young tableau on D and for any index k, the terminal list has a descent at k if and only if l does. We introduce l, discard the tableau hypothesis (written as `_`) because it is not needed, and introduce the position k.

    line 3

      intro l _ k
  2. The descent equivalence holds by definitional equality.

    By definition of `terminal_boxes`, evaluating a leaf node `DiagramSlidingTree.leaf D h` on l returns l without modification. The goal simplifies to `list_descent_at l k ↔ list_descent_at l k`, which is an equivalence between identical propositions and is closed immediately by reflexivity (`rfl`).

    line 4

      rfl

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

/-- For any diagram D with no crossings, the leaf sliding tree satisfies agreement with descents. -/theorem open_problem_1285_partial_no_crossings (D : Finset (ℕ × ℕ)) (h : ∀ u ∈ D, ∀ v ∈ D, ¬ diagram_crossing u v) : diagram_slide_expansion_agrees_with_descents D (DiagramSlidingTree.leaf D h) := by  intro l _ k  rfl
See it in the graphDiscuss this resultChallenge it