AFTD Auto-Formalizing Theoretical Domains

comparison_tree_num_leaves_le_two_pow_depth

theoremverified

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.

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

    lines 4–7

    uses comparison_tree_num_leaves.eq_1, comparison_tree_depth.eq_1

      induction T with
      | leaf a =>
        rw [comparison_tree_num_leaves.eq_1, comparison_tree_depth.eq_1]
        omega
  2. 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.

    lines 8–9

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

    lines 10–13

    uses Nat.pow_le_pow_right, le_max_left, le_max_right

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

    lines 14–16

    uses pow_add, pow_one, mul_comm

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

    line 17

        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

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