AFTD Auto-Formalizing Theoretical Domains

extremal_tree_vertex_bound_sharp

theoremverifiedformalization

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.

  1. 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}.

    lines 13–16

    uses Finset.range_add_one

      induction k with
      | zero => rfl
      | succ k ih =>
        simp [extremal_tree_vertex_bound_sharp_completeBinaryTree, binary_tree_labels, ih, Finset.range_add_one]
  2. 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.

    lines 20–24

    uses extremal_tree_vertex_bound_sharp_complete_labels

      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]
  3. 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.

    lines 28–34

    uses Nat.le_of_succ_le, extremal_tree_vertex_bound_sharp_complete_labels, Nat.le_trans, Nat.le_succ

      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) h
  4. 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.

    lines 38–43

    uses Nat.one_le_two_pow

      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
        omega
  5. 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}.

    lines 47–54

    uses Finset.range_mono, Nat.le_add_right, Finset.range_add_one, extremal_tree_vertex_bound_sharp_complete_labels, Finset.union_eq_right.mpr

      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]
  6. 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.

    lines 58–64

    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_lt

      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⟩
  7. 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.

    lines 68–75

    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_range

      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⟩
  8. 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).

    lines 79–85

    uses extremal_tree_vertex_bound_sharp_complete_numNodes, Nat.one_le_two_pow, mul_add_one

      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
  9. 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.

    lines 94–99

    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_pos

      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]
  10. 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.

    lines 100–106

    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.

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

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]
See it in the graphDiscuss this resultChallenge it