comparison_tree_num_leaves_le_two_pow_depth
For any natural number n and any comparison decision tree T on n elements, the number of leaves of T is at most 2 raised to the depth of T.
Statement
theorem comparison_tree_num_leaves_le_two_pow_depth {n : ℕ} (T : ComparisonTree n) :
comparison_tree_num_leaves T ≤ 2 ^ (comparison_tree_depth T)- Source
- arXiv:2610.18740 Remark 9, Selecting the 7th Smallest of 16 Elements Takes Exactly 28 Comparisons
- Verified
- 08 Nov 2026
- Axioms
Quot.soundpropext- Built on 3
- comparison_tree_num_leavesThe number of leaves in a comparison decision tree is 1 for a leaf, and the sum of the leaf counts of its left and right subtrees for an…
- comparison_tree_depthThe depth of a comparison decision tree is the maximum number of comparisons along any branch from the root to a leaf.
- ComparisonTreeA binary comparison decision tree on n elements whose internal nodes perform pairwise comparisons and whose leaves return an element index.
Read back from the Lean
For every natural number $n$ and every comparison tree $T$ over $n$ elements (of type ComparisonTree n), the number of leaves of $T$ (comparison_tree_num_leaves T) is less than or equal to $2^{\text{depth}(T)}$ (comparison_tree_depth T).
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 proof proceeds by structural induction on the comparison tree T. For a leaf node, the tree has 1 leaf and depth 0, so the inequality 1 ≤ 2^0 holds trivially. For a branch node, the number of leaves is the sum of the leaves of its two subtrees, while its depth is 1 plus the maximum of their depths. Applying the induction hypothesis to each subtree and bounding both subtree depths by their maximum, the total number of leaves is at most 2^max + 2^max = 2 * 2^max = 2^(1 + max), which matches 2 raised to the depth of the branch.
The inequality holds for leaf nodes: leaves(leaf(a)) ≤ 2^(depth(leaf(a))).
We proceed by structural induction on T. For a leaf node T = leaf(a), the number of leaves is 1 and the depth is 0 by definition. Rewriting with these definitions simplifies the inequality to 1 ≤ 2^0 = 1, which holds immediately by arithmetic.
uses
comparison_tree_num_leaves.eq_1,comparison_tree_depth.eq_1induction T with | leaf a => rw [comparison_tree_num_leaves.eq_1, comparison_tree_depth.eq_1] omega
For a branch node with subtrees l and r, it suffices to show leaves(l) + leaves(r) ≤ 2^(1 + max(depth(l), depth(r))).
In the inductive step where T = branch(i, j, l, r), the number of leaves is the sum of the leaves of l and r, and the depth is 1 plus the maximum of their depths. Rewriting the goal using these definitions yields the simplified inequality.
uses
comparison_tree_num_leaves.eq_2,comparison_tree_depth.eq_2| branch i j l r ih_l ih_r => rw [comparison_tree_num_leaves.eq_2, comparison_tree_depth.eq_2]The powers of 2 for both subtree depths are bounded by 2 raised to the maximum depth: 2^(depth(l)) ≤ 2^(max(depth(l), depth(r))) and 2^(depth(r)) ≤ 2^(max(depth(l), depth(r))).
Since the depth of each subtree is at most the maximum of both depths (by le_max_left and le_max_right), and exponentiation with base 2 > 0 is monotonic, raising 2 to these exponents preserves the inequalities, yielding hypotheses h1 and h2.
uses
Nat.pow_le_pow_right,le_max_left,le_max_righthave h1 : 2 ^ comparison_tree_depth l ≤ 2 ^ max (comparison_tree_depth l) (comparison_tree_depth r) := Nat.pow_le_pow_right (by omega) (le_max_left _ _) have h2 : 2 ^ comparison_tree_depth r ≤ 2 ^ max (comparison_tree_depth l) (comparison_tree_depth r) := Nat.pow_le_pow_right (by omega) (le_max_right _ _)
2^(1 + max(depth(l), depth(r))) = 2 * 2^(max(depth(l), depth(r))).
By the laws of exponents, 2^(1 + m) = 2^1 * 2^m = 2 * 2^m, which is established by splitting the exponent sum, evaluating 2^1 = 2, and commuting multiplication.
uses
pow_add,pow_one,mul_commhave hpow : 2 ^ (1 + max (comparison_tree_depth l) (comparison_tree_depth r)) = 2 * 2 ^ max (comparison_tree_depth l) (comparison_tree_depth r) := by rw [pow_add, pow_one, mul_comm]
The inequality holds for the branch node, completing the inductive step.
By the induction hypotheses, leaves(l) ≤ 2^(depth(l)) and leaves(r) ≤ 2^(depth(r)). Combining these with the bounds h1 and h2 on the powers of 2 and the exponent identity hpow, linear arithmetic verifies that leaves(l) + leaves(r) ≤ 2^max + 2^max = 2 * 2^max = 2^(1 + max), completing the proof.
omega
comparison_tree_num_leaves.eq_1- A leaf node has exactly 1 leaf.
comparison_tree_depth.eq_1- A leaf node has depth 0.
comparison_tree_num_leaves.eq_2- The number of leaves of a branch node is the sum of the leaves of its left and right subtrees.
comparison_tree_depth.eq_2- The depth of a branch node is 1 plus the maximum of the depths of its left and right subtrees.
Nat.pow_le_pow_right- For any positive integer base n > 0, if i ≤ j then n^i ≤ n^j.
le_max_left- In any linear order, a ≤ max(a, b).
le_max_right- In any linear order, b ≤ max(a, b).
pow_add- In any monoid, a^(m + n) = a^m * a^n.
pow_one- In any monoid, a^1 = a.
mul_comm- Multiplication is commutative: a * b = b * a.
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.
/-- Every comparison decision tree has at most 2^depth leaves. -/theorem comparison_tree_num_leaves_le_two_pow_depth {n : ℕ} (T : ComparisonTree n) : comparison_tree_num_leaves T ≤ 2 ^ (comparison_tree_depth T) := by induction T with | leaf a => rw [comparison_tree_num_leaves.eq_1, comparison_tree_depth.eq_1] omega | branch i j l r ih_l ih_r => rw [comparison_tree_num_leaves.eq_2, comparison_tree_depth.eq_2] have h1 : 2 ^ comparison_tree_depth l ≤ 2 ^ max (comparison_tree_depth l) (comparison_tree_depth r) := Nat.pow_le_pow_right (by omega) (le_max_left _ _) have h2 : 2 ^ comparison_tree_depth r ≤ 2 ^ max (comparison_tree_depth l) (comparison_tree_depth r) := Nat.pow_le_pow_right (by omega) (le_max_right _ _) have hpow : 2 ^ (1 + max (comparison_tree_depth l) (comparison_tree_depth r)) = 2 * 2 ^ max (comparison_tree_depth l) (comparison_tree_depth r) := by rw [pow_add, pow_one, mul_comm] omega