AFTD Auto-Formalizing Theoretical Domains

extremal_tree_vertex_bound

def

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

Statement

def extremal_tree_vertex_bound (C q : ℕ) : ℕ
Defined in
arXiv:2611.04184 Theorem 4.6 (Short permutation pattern waves: The complete length-five classification)
Verified
07 Nov 2026
Axioms
none listed
Used by 1

Read back from the Lean

The function extremal_tree_vertex_bound, taking two natural numbers C and q, is defined as: - 2 ^ q - 1 if q ≤ C; - (2 ^ C - 1) + 2 ^ C * (q - C) otherwise (i.e., 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.

Lean source view module on GitHub

/-- The extremal vertex bound F_C(q) for binary trees with child-subtree overlap at most C and at most q classes. -/
def extremal_tree_vertex_bound (C q : ℕ) : ℕ := if q ≤ C then 2 ^ q - 1 else (2 ^ C - 1) + 2 ^ C * (q - C)
See it in the graphDiscuss this resultChallenge it