open_problem_1285_partial_no_crossings
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 Don a diagram $D$ is either a leaf diagram with no crossings (… - diagram_slide_expansion_agrees_with_descentsA sliding tree
ton a finite diagram $D$ satisfiesdiagram_slide_expansion_agrees_with_descents D tif for every list $l$ representing… - terminal_boxesGiven a sliding tree
t : DiagramSlidingTree Dand a list $l$ of boxes representing a tableau on $D$,terminal_boxes t ltransports $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$,…
- diagram_crossingTwo cells $u, v \in \mathbb{N} \times \mathbb{N}$ form a crossing (
- Used by 1
- open_problem_1285_exists_tree_of_no_crossingsFor every finite diagram $D \subseteq \mathbb{N} \times \mathbb{N}$ having no crossings (
∀ u ∈ D, ∀ v ∈ D, ¬ diagram_crossing u v),…
- open_problem_1285_exists_tree_of_no_crossingsFor every finite diagram $D \subseteq \mathbb{N} \times \mathbb{N}$ having no crossings (
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.
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.
intro l _ kThe 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`).
rfl
- The assumption that l is a standard Young tableau (`is_standard_young_tableau_list D l`) is discarded (introduced as `_` on line 3) because `terminal_boxes` returns l unconditionally for any list.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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