extremal_tree_vertex_bound_sharp
For any natural numbers C and q, there exists a binary tree t : BinaryTree ℕ such that (binary_tree_labels t).card ≤ q, binary_tree_no_ancestor_descendant_repeat t, binary_tree_bounded_child_overlap C t, and t.numNodes = extremal_tree_vertex_bound C q.
Statement
theorem extremal_tree_vertex_bound_sharp (C q : ℕ) :
∃ (t : BinaryTree ℕ),
(binary_tree_labels t).card ≤ q ∧
binary_tree_no_ancestor_descendant_repeat t ∧
binary_tree_bounded_child_overlap C t ∧
t.numNodes = extremal_tree_vertex_bound C q- Formalizes
- arXiv:2611.04184 Theorem 4.6 (Short permutation pattern waves: The complete length-five classification)
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- extremal_tree_vertex_boundFor integers C, q ≥ 0, the extremal vertex bound F_C(q) is defined by 2^q - 1 if q ≤ C, and (2^C - 1) + 2^C * (q - C) if q > C.
- binary_tree_labelsFor any type α with decidable equality, and any binary tree t : BinaryTree α, the finite set binary_tree_labels t : Finset α of labels…
- binary_tree_no_ancestor_descendant_repeatFor any type α with decidable equality, binary_tree_no_ancestor_descendant_repeat on BinaryTree α is defined recursively: it holds on nil,…
- binary_tree_bounded_child_overlapFor any type α with decidable equality and any natural number C, binary_tree_bounded_child_overlap C on BinaryTree α is defined…
Read back from the Lean
For all natural numbers $C$ and $q$, there exists a binary tree $t$ with labels in $\mathbb{N}$ such that:
1. The number of distinct labels appearing in $t$ is at most $q$ ((binary_tree_labels t).card ≤ q);
2. No node in $t$ shares a label with any of its proper descendants (binary_tree_no_ancestor_descendant_repeat t);
3. At every node in $t$, the number of labels common to both its left and right subtrees is at most $C$ (binary_tree_bounded_child_overlap C t); and
4. The total number of nodes in $t$ (t.numNodes) equals $2^q - 1$ if $q \le C$, and $(2^C - 1) + 2^C \cdot (q - C)$ if $q > C$.
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 extremal vertex bound equals 2^q - 1 when q ≤ C, and (2^C - 1) + 2^C * (q - C) when q > C. Sharpness is proven by constructing two families of binary trees: complete binary trees where nodes are labeled by their distance from the leaves, and extended trees consisting of a spine of length q - C with complete binary trees of depth C hanging off the left side. Depending on whether q ≤ C, one of these two constructions provides a valid binary tree with at most q labels, no ancestor-descendant repeats, child overlap at most C, and the exact maximal number of nodes.
The set of labels of the complete binary tree of depth k is {0, ..., k - 1}.
By induction on k. The base tree is empty and has no labels. In the inductive step, the root of the tree of depth k + 1 has label k, and both its children are complete trees of depth k, which by induction have label set {0, ..., k - 1}. Their union is {0, ..., k - 1}, and inserting the root label k gives {0, ..., k}.
uses
Finset.range_add_oneinduction k with | zero => rfl | succ k ih => simp [extremal_tree_vertex_bound_sharp_completeBinaryTree, binary_tree_labels, ih, Finset.range_add_one]
The complete binary tree of depth k has no ancestor-descendant label repeats.
By induction on k. The base case is vacuous. For depth k + 1, the root has label k while both child subtrees only contain labels from {0, ..., k - 1}. Since k does not belong to this set, the root label does not appear in either subtree, and both child subtrees satisfy the no-repeat condition by the induction hypothesis.
uses
extremal_tree_vertex_bound_sharp_complete_labelsinduction k with | zero => simp [extremal_tree_vertex_bound_sharp_completeBinaryTree, binary_tree_no_ancestor_descendant_repeat] | succ k ih => simp [extremal_tree_vertex_bound_sharp_completeBinaryTree, binary_tree_no_ancestor_descendant_repeat, extremal_tree_vertex_bound_sharp_complete_labels, ih]
Whenever k ≤ C, the complete binary tree of depth k has child subtree label overlap bounded by C at every node.
By induction on k. The empty tree satisfies the condition trivially. For depth k + 1 with k + 1 ≤ C, both children are complete trees of depth k; since k ≤ C, they satisfy bounded overlap by the induction hypothesis. At the root, both children have label set {0, ..., k - 1}, so their intersection has size k, which is at most C because k ≤ k + 1 ≤ C.
uses
Nat.le_of_succ_le,extremal_tree_vertex_bound_sharp_complete_labels,Nat.le_trans,Nat.le_succinduction k with | zero => simp [extremal_tree_vertex_bound_sharp_completeBinaryTree, binary_tree_bounded_child_overlap] | succ k ih => have hk : k ≤ C := Nat.le_of_succ_le h simp [extremal_tree_vertex_bound_sharp_completeBinaryTree, binary_tree_bounded_child_overlap, extremal_tree_vertex_bound_sharp_complete_labels, ih hk] exact Nat.le_trans (Nat.le_succ k) h
The complete binary tree of depth k has exactly 2^k - 1 nodes.
By induction on k. The empty tree has 0 nodes, matching 2^0 - 1. For depth k + 1, the node count is the sum of the root node and the two children, giving (2^k - 1) + (2^k - 1) + 1. Since 2^k ≥ 1, this simplifies to 2^(k + 1) - 1 by natural number arithmetic.
uses
Nat.one_le_two_powinduction k with | zero => simp [extremal_tree_vertex_bound_sharp_completeBinaryTree] | succ k ih => simp [extremal_tree_vertex_bound_sharp_completeBinaryTree, numNodes, ih] have : 1 ≤ 2 ^ k := Nat.one_le_two_pow omega
The extended tree with parameter C and spine length d has label set {0, ..., C + d - 1}.
By induction on d. When d = 0, the tree is the complete binary tree of depth C, with labels {0, ..., C - 1}. For spine length d + 1, the root has label C + d, the left child has labels {0, ..., C - 1}, and the right child has labels {0, ..., C + d - 1} by the induction hypothesis. Since {0, ..., C - 1} ⊆ {0, ..., C + d - 1}, the union of the children's labels is {0, ..., C + d - 1}, and inserting C + d yields {0, ..., C + d}.
uses
Finset.range_mono,Nat.le_add_right,Finset.range_add_one,extremal_tree_vertex_bound_sharp_complete_labels,Finset.union_eq_right.mprinduction d with | zero => simp [extremal_tree_vertex_bound_sharp_extTree, extremal_tree_vertex_bound_sharp_complete_labels] | succ d ih => have hsub : Finset.range C ⊆ Finset.range (C + d) := Finset.range_mono (Nat.le_add_right C d) have : C + (d + 1) = (C + d) + 1 := by omega rw [this, Finset.range_add_one] simp [extremal_tree_vertex_bound_sharp_extTree, binary_tree_labels, extremal_tree_vertex_bound_sharp_complete_labels, ih, Finset.union_eq_right.mpr hsub]
The extended tree with parameters C and d has no ancestor-descendant label repeats.
By induction on d. When d = 0, the claim reduces to the complete binary tree of depth C. For d + 1, the root label is C + d. The left child has labels strictly less than C, and the right child has labels strictly less than C + d; since C ≤ C + d and C + d ≤ C + d, the root label does not occur in either child subtree. The subtrees themselves satisfy the condition by the earlier complete tree lemma and the induction hypothesis.
uses
extremal_tree_vertex_bound_sharp_complete_no_repeat,extremal_tree_vertex_bound_sharp_complete_labels,extremal_tree_vertex_bound_sharp_ext_labels,Finset.mem_range,not_ltinduction d with | zero => simp [extremal_tree_vertex_bound_sharp_extTree, extremal_tree_vertex_bound_sharp_complete_no_repeat] | succ d ih => simp only [extremal_tree_vertex_bound_sharp_extTree, binary_tree_no_ancestor_descendant_repeat, extremal_tree_vertex_bound_sharp_complete_labels, extremal_tree_vertex_bound_sharp_ext_labels, Finset.mem_range, not_lt] refine ⟨by omega, by omega, extremal_tree_vertex_bound_sharp_complete_no_repeat C, ih⟩
The extended tree with parameters C and d satisfies the child overlap bound C at every node.
By induction on d. The base case d = 0 is the complete binary tree of depth C, which has overlap bounded by C since C ≤ C. In the inductive step, the left child has labels {0, ..., C - 1} and the right child has labels {0, ..., C + d - 1}. Because the left label set is a subset of the right, their intersection is {0, ..., C - 1}, which has cardinality C ≤ C. Both child subtrees satisfy the overlap condition by the complete tree lemma and the induction hypothesis.
uses
extremal_tree_vertex_bound_sharp_complete_bounded_overlap,le_rfl,Finset.range_mono,Nat.le_add_right,extremal_tree_vertex_bound_sharp_complete_labels,extremal_tree_vertex_bound_sharp_ext_labels,Finset.inter_eq_left.mpr,Finset.card_rangeinduction d with | zero => exact extremal_tree_vertex_bound_sharp_complete_bounded_overlap C le_rfl | succ d ih => have hsub : Finset.range C ⊆ Finset.range (C + d) := Finset.range_mono (Nat.le_add_right C d) simp only [extremal_tree_vertex_bound_sharp_extTree, binary_tree_bounded_child_overlap, extremal_tree_vertex_bound_sharp_complete_labels, extremal_tree_vertex_bound_sharp_ext_labels, Finset.inter_eq_left.mpr hsub, Finset.card_range] exact ⟨le_rfl, extremal_tree_vertex_bound_sharp_complete_bounded_overlap C le_rfl, ih⟩
The extended tree with parameters C and d contains exactly (2^C - 1) + 2^C * d nodes.
By induction on d. For d = 0, the node count is 2^C - 1, which equals (2^C - 1) + 2^C * 0. For d + 1, the tree consists of the root (1 node), the left complete tree of depth C (2^C - 1 nodes), and the right extended tree of spine length d ((2^C - 1) + 2^C * d nodes by induction). Using 2^C * (d + 1) = 2^C * d + 2^C and 2^C ≥ 1, this sums to (2^C - 1) + 2^C * (d + 1).
uses
extremal_tree_vertex_bound_sharp_complete_numNodes,Nat.one_le_two_pow,mul_add_oneinduction d with | zero => simp [extremal_tree_vertex_bound_sharp_extTree, extremal_tree_vertex_bound_sharp_complete_numNodes] | succ d ih => simp only [extremal_tree_vertex_bound_sharp_extTree, numNodes, extremal_tree_vertex_bound_sharp_complete_numNodes, ih] have : 1 ≤ 2 ^ C := Nat.one_le_two_pow have : 2 ^ C * (d + 1) = 2 ^ C * d + 2 ^ C := mul_add_one (2 ^ C) d omega
When q ≤ C, the complete binary tree of depth q witnesses the sharpness of the extremal vertex bound.
In the case q ≤ C, we choose t to be the complete binary tree of depth q. Its label set has size q ≤ q, it contains no ancestor-descendant repeats, and its child overlap is bounded by C because q ≤ C. Its node count 2^q - 1 matches the definition of the extremal vertex bound when q ≤ C.
uses
extremal_tree_vertex_bound_sharp_complete_no_repeat,extremal_tree_vertex_bound_sharp_complete_bounded_overlap,extremal_tree_vertex_bound_sharp_complete_labels,Finset.card_range,extremal_tree_vertex_bound_sharp_complete_numNodes,if_posby_cases hq : q ≤ C · use extremal_tree_vertex_bound_sharp_completeBinaryTree q refine ⟨?_, extremal_tree_vertex_bound_sharp_complete_no_repeat q, extremal_tree_vertex_bound_sharp_complete_bounded_overlap C hq, ?_⟩ · rw [extremal_tree_vertex_bound_sharp_complete_labels, Finset.card_range] · rw [extremal_tree_vertex_bound_sharp_complete_numNodes, extremal_tree_vertex_bound, if_pos hq]
When q > C, the extended tree with spine length q - C witnesses the sharpness of the extremal vertex bound.
In the case q > C, we set d = q - C, so that C + d = q, and take t to be the extended tree with parameters C and q - C. Its label set {0, ..., q - 1} has cardinality q ≤ q. It satisfies both the no-repeat and bounded child overlap conditions by the corresponding extended tree theorems. Finally, its node count (2^C - 1) + 2^C * (q - C) matches the definition of the extremal vertex bound when q > C.
uses
le_of_not_ge,Nat.add_sub_of_le,extremal_tree_vertex_bound_sharp_ext_no_repeat,extremal_tree_vertex_bound_sharp_ext_bounded_overlap,extremal_tree_vertex_bound_sharp_ext_labels,Finset.card_range,extremal_tree_vertex_bound_sharp_ext_numNodes,if_neg· use extremal_tree_vertex_bound_sharp_extTree C (q - C) have hCq : C ≤ q := le_of_not_ge hq have hCd : C + (q - C) = q := Nat.add_sub_of_le hCq refine ⟨?_, extremal_tree_vertex_bound_sharp_ext_no_repeat C (q - C), extremal_tree_vertex_bound_sharp_ext_bounded_overlap C (q - C), ?_⟩ · rw [extremal_tree_vertex_bound_sharp_ext_labels, hCd, Finset.card_range] · rw [extremal_tree_vertex_bound_sharp_ext_numNodes, extremal_tree_vertex_bound, if_neg hq]
Finset.range_add_one- The range {0, ..., n} is obtained by inserting n into {0, ..., n - 1}.
extremal_tree_vertex_bound_sharp_complete_labels- The set of labels of the complete binary tree of depth k is {0, ..., k - 1}.
Nat.le_of_succ_le- If n + 1 ≤ m, then n ≤ m.
Nat.le_trans- Less-than-or-equal on natural numbers is transitive.
Nat.le_succ- Every natural number n is at most n + 1.
Nat.one_le_two_pow- For any natural number n, 2^n ≥ 1.
Finset.range_mono- The range of consecutive natural numbers is monotone with respect to inclusion.
Nat.le_add_right- Every natural number n is at most n + k.
Finset.union_eq_right.mpr- If A ⊆ B, then A ∪ B = B.
extremal_tree_vertex_bound_sharp_complete_no_repeat- The complete binary tree of depth k has no repeated labels on any ancestor-descendant path.
extremal_tree_vertex_bound_sharp_ext_labels- The set of labels of the extended tree with parameter C and spine length d is {0, ..., C + d - 1}.
Finset.mem_range- A natural number m belongs to {0, ..., n - 1} if and only if m < n.
not_lt- In a linear order, a is not strictly less than b if and only if b ≤ a.
extremal_tree_vertex_bound_sharp_complete_bounded_overlap- If k ≤ C, the complete binary tree of depth k has child subtree label overlap at most C at every node.
le_rfl- The order relation ≤ is reflexive: any element is at most itself.
Finset.inter_eq_left.mpr- If A ⊆ B, then A ∩ B = A.
Finset.card_range- The cardinality of {0, ..., n - 1} is n.
extremal_tree_vertex_bound_sharp_complete_numNodes- The number of nodes in the complete binary tree of depth k is 2^k - 1.
mul_add_one- Multiplication distributes over successor: a * (b + 1) = a * b + a.
if_pos- If condition c is true, then 'if c then t else e' evaluates to t.
le_of_not_ge- In a linear order, if a is not at most b, then b ≤ a.
Nat.add_sub_of_le- If a ≤ b, then a + (b - a) = b.
extremal_tree_vertex_bound_sharp_ext_no_repeat- The extended tree with parameters C and d has no repeated labels on any ancestor-descendant path.
extremal_tree_vertex_bound_sharp_ext_bounded_overlap- The extended tree with parameters C and d has child subtree label overlap at most C at every node.
extremal_tree_vertex_bound_sharp_ext_numNodes- The number of nodes in the extended tree with parameters C and d is (2^C - 1) + 2^C * d.
if_neg- If condition c is false, then 'if c then t else e' evaluates to e.
- The proof is structured as eight inductive lemmas establishing the properties (label sets, absence of ancestor-descendant repeats, bounded child overlap, and node counts) of two tree families—complete binary trees and extended spine trees—before assembling them into the main case split.
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.
open BinaryTreedef extremal_tree_vertex_bound_sharp_completeBinaryTree : ℕ → BinaryTree ℕ | 0 => .nil | k + 1 => .node k (extremal_tree_vertex_bound_sharp_completeBinaryTree k) (extremal_tree_vertex_bound_sharp_completeBinaryTree k)def extremal_tree_vertex_bound_sharp_extTree (C : ℕ) : ℕ → BinaryTree ℕ | 0 => extremal_tree_vertex_bound_sharp_completeBinaryTree C | d + 1 => .node (C + d) (extremal_tree_vertex_bound_sharp_completeBinaryTree C) (extremal_tree_vertex_bound_sharp_extTree C d)theorem extremal_tree_vertex_bound_sharp_complete_labels (k : ℕ) : binary_tree_labels (extremal_tree_vertex_bound_sharp_completeBinaryTree k) = Finset.range k := by induction k with | zero => rfl | succ k ih => simp [extremal_tree_vertex_bound_sharp_completeBinaryTree, binary_tree_labels, ih, Finset.range_add_one]theorem extremal_tree_vertex_bound_sharp_complete_no_repeat (k : ℕ) : binary_tree_no_ancestor_descendant_repeat (extremal_tree_vertex_bound_sharp_completeBinaryTree k) := by induction k with | zero => simp [extremal_tree_vertex_bound_sharp_completeBinaryTree, binary_tree_no_ancestor_descendant_repeat] | succ k ih => simp [extremal_tree_vertex_bound_sharp_completeBinaryTree, binary_tree_no_ancestor_descendant_repeat, extremal_tree_vertex_bound_sharp_complete_labels, ih]theorem extremal_tree_vertex_bound_sharp_complete_bounded_overlap (C : ℕ) {k : ℕ} (h : k ≤ C) : binary_tree_bounded_child_overlap C (extremal_tree_vertex_bound_sharp_completeBinaryTree k) := by induction k with | zero => simp [extremal_tree_vertex_bound_sharp_completeBinaryTree, binary_tree_bounded_child_overlap] | succ k ih => have hk : k ≤ C := Nat.le_of_succ_le h simp [extremal_tree_vertex_bound_sharp_completeBinaryTree, binary_tree_bounded_child_overlap, extremal_tree_vertex_bound_sharp_complete_labels, ih hk] exact Nat.le_trans (Nat.le_succ k) htheorem extremal_tree_vertex_bound_sharp_complete_numNodes (k : ℕ) : (extremal_tree_vertex_bound_sharp_completeBinaryTree k).numNodes = 2 ^ k - 1 := by induction k with | zero => simp [extremal_tree_vertex_bound_sharp_completeBinaryTree] | succ k ih => simp [extremal_tree_vertex_bound_sharp_completeBinaryTree, numNodes, ih] have : 1 ≤ 2 ^ k := Nat.one_le_two_pow omegatheorem extremal_tree_vertex_bound_sharp_ext_labels (C d : ℕ) : binary_tree_labels (extremal_tree_vertex_bound_sharp_extTree C d) = Finset.range (C + d) := by induction d with | zero => simp [extremal_tree_vertex_bound_sharp_extTree, extremal_tree_vertex_bound_sharp_complete_labels] | succ d ih => have hsub : Finset.range C ⊆ Finset.range (C + d) := Finset.range_mono (Nat.le_add_right C d) have : C + (d + 1) = (C + d) + 1 := by omega rw [this, Finset.range_add_one] simp [extremal_tree_vertex_bound_sharp_extTree, binary_tree_labels, extremal_tree_vertex_bound_sharp_complete_labels, ih, Finset.union_eq_right.mpr hsub]theorem extremal_tree_vertex_bound_sharp_ext_no_repeat (C d : ℕ) : binary_tree_no_ancestor_descendant_repeat (extremal_tree_vertex_bound_sharp_extTree C d) := by induction d with | zero => simp [extremal_tree_vertex_bound_sharp_extTree, extremal_tree_vertex_bound_sharp_complete_no_repeat] | succ d ih => simp only [extremal_tree_vertex_bound_sharp_extTree, binary_tree_no_ancestor_descendant_repeat, extremal_tree_vertex_bound_sharp_complete_labels, extremal_tree_vertex_bound_sharp_ext_labels, Finset.mem_range, not_lt] refine ⟨by omega, by omega, extremal_tree_vertex_bound_sharp_complete_no_repeat C, ih⟩theorem extremal_tree_vertex_bound_sharp_ext_bounded_overlap (C d : ℕ) : binary_tree_bounded_child_overlap C (extremal_tree_vertex_bound_sharp_extTree C d) := by induction d with | zero => exact extremal_tree_vertex_bound_sharp_complete_bounded_overlap C le_rfl | succ d ih => have hsub : Finset.range C ⊆ Finset.range (C + d) := Finset.range_mono (Nat.le_add_right C d) simp only [extremal_tree_vertex_bound_sharp_extTree, binary_tree_bounded_child_overlap, extremal_tree_vertex_bound_sharp_complete_labels, extremal_tree_vertex_bound_sharp_ext_labels, Finset.inter_eq_left.mpr hsub, Finset.card_range] exact ⟨le_rfl, extremal_tree_vertex_bound_sharp_complete_bounded_overlap C le_rfl, ih⟩theorem extremal_tree_vertex_bound_sharp_ext_numNodes (C d : ℕ) : (extremal_tree_vertex_bound_sharp_extTree C d).numNodes = (2 ^ C - 1) + 2 ^ C * d := by induction d with | zero => simp [extremal_tree_vertex_bound_sharp_extTree, extremal_tree_vertex_bound_sharp_complete_numNodes] | succ d ih => simp only [extremal_tree_vertex_bound_sharp_extTree, numNodes, extremal_tree_vertex_bound_sharp_complete_numNodes, ih] have : 1 ≤ 2 ^ C := Nat.one_le_two_pow have : 2 ^ C * (d + 1) = 2 ^ C * d + 2 ^ C := mul_add_one (2 ^ C) d omega/-- Sharpness of the extremal vertex bound for binary trees with bounded child-subtree overlap (Theorem 4.6). -/theorem extremal_tree_vertex_bound_sharp (C q : ℕ) : ∃ (t : BinaryTree ℕ), (binary_tree_labels t).card ≤ q ∧ binary_tree_no_ancestor_descendant_repeat t ∧ binary_tree_bounded_child_overlap C t ∧ t.numNodes = extremal_tree_vertex_bound C q := by by_cases hq : q ≤ C · use extremal_tree_vertex_bound_sharp_completeBinaryTree q refine ⟨?_, extremal_tree_vertex_bound_sharp_complete_no_repeat q, extremal_tree_vertex_bound_sharp_complete_bounded_overlap C hq, ?_⟩ · rw [extremal_tree_vertex_bound_sharp_complete_labels, Finset.card_range] · rw [extremal_tree_vertex_bound_sharp_complete_numNodes, extremal_tree_vertex_bound, if_pos hq] · use extremal_tree_vertex_bound_sharp_extTree C (q - C) have hCq : C ≤ q := le_of_not_ge hq have hCd : C + (q - C) = q := Nat.add_sub_of_le hCq refine ⟨?_, extremal_tree_vertex_bound_sharp_ext_no_repeat C (q - C), extremal_tree_vertex_bound_sharp_ext_bounded_overlap C (q - C), ?_⟩ · rw [extremal_tree_vertex_bound_sharp_ext_labels, hCd, Finset.card_range] · rw [extremal_tree_vertex_bound_sharp_ext_numNodes, extremal_tree_vertex_bound, if_neg hq]