AFTD Auto-Formalizing Theoretical Domains

open_problem_1285_exists_tree_of_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), there exists a sliding tree t : DiagramSlidingTree D such that diagram_slide_expansion_agrees_with_descents D t holds.

Statement

theorem open_problem_1285_exists_tree_of_no_crossings (D : Finset (ℕ × ℕ)) (h : ∀ u ∈ D, ∀ v ∈ D, ¬ diagram_crossing u v) : ∃ t : DiagramSlidingTree D, diagram_slide_expansion_agrees_with_descents D t
Source
arXiv:2611.07715, Theorem 3.22
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
  • open_problem_1285_partial_no_crossingsFor every finite diagram $D \subseteq \mathbb{N} \times \mathbb{N}$ having no crossings (∀ u ∈ D, ∀ v ∈ D, ¬ diagram_crossing u v), the…

Read back from the Lean

For every finite set $D \subseteq \mathbb{N} \times \mathbb{N}$, if no pair of elements $u, v \in D$ forms a crossing (meaning there do not exist $u, v \in D$ such that either $(u.1 < v.1 \land v.2 < u.2)$ or $(v.1 < u.1 \land u.2 < v.2)$), then there exists a sliding tree $t : \text{DiagramSlidingTree } D$ such that for every list $l$ of elements of $\mathbb{N} \times \mathbb{N}$ that is a standard Young tableau list of $D$ (meaning $l$ has no duplicates, the set of elements in $l$ is $D$, and whenever $u, v \in D$ satisfy $u.1 \le v.1$ and $u.2 \le v.2$, the index of $u$ in $l$ is $\le$ the index of $v$ in $l$) and for every $k : \mathbb{N}$, $\text{terminal\_boxes } t\ l$ has a descent at $k$ if and only if $l$ has a descent at $k$ (where a list $l'$ has a descent at $k$ if there exist $u, v$ such that $l'[k] = u$, $l'[k+1] = v$, and $u.1 < v.1$).

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

To show that a diagram with no crossings admits a sliding tree whose expansion agrees with descents, the proof provides an explicit witness. Because the diagram has no crossings, it directly forms the base case of a sliding tree as a single leaf. The fact that this trivial tree satisfies descent agreement is supplied directly by a previously established lemma.

  1. There exists a sliding tree for D whose slide expansion agrees with descents, namely the single-leaf tree.

    Since D contains no crossings (by assumption h), we instantiate the existential quantifier with the leaf sliding tree DiagramSlidingTree.leaf D h. The required agreement with descents is then given directly by open_problem_1285_partial_no_crossings applied to D and h.

    line 3

    uses DiagramSlidingTree.leaf, open_problem_1285_partial_no_crossings

      exact ⟨DiagramSlidingTree.leaf D h, open_problem_1285_partial_no_crossings D h⟩
DiagramSlidingTree.leaf
Given a diagram D and a proof that no pair of boxes forms a crossing, constructs a sliding tree on D consisting of a single leaf node.
open_problem_1285_partial_no_crossings
For any diagram D without crossings, the single-leaf sliding tree satisfies descent agreement with D.

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, there exists a sliding tree satisfying agreement with descents. -/theorem open_problem_1285_exists_tree_of_no_crossings (D : Finset (ℕ × ℕ)) (h : ∀ u ∈ D, ∀ v ∈ D, ¬ diagram_crossing u v) : ∃ t : DiagramSlidingTree D, diagram_slide_expansion_agrees_with_descents D t := by  exact ⟨DiagramSlidingTree.leaf D h, open_problem_1285_partial_no_crossings D h⟩
See it in the graphDiscuss this resultChallenge it