AFTD Auto-Formalizing Theoretical Domains

one_layered_family_upper_bounds

theoremverifiedformalization

For all integers r ≥ 1 and m ≥ r, the maximum number of layers F(m, r) of a 1-layered family of r-subsets on at most m vertices satisfies F(m, r) ≤ 2^(r - 1) * (m - r) + 1 and F(m, r) ≤ (m - r + 1) * Nat.choose (Nat.log 2 (m - r + 1) + r - 1) (r - 1), and this binomial bound is at most (m - r + 1)^(1 + Real.log r / Real.log 2).

Statement

theorem one_layered_family_upper_bounds (m r : ℕ) (hr : 1 ≤ r) (hm : r ≤ m) :
    one_layered_max_layers m r ≤ 2 ^ (r - 1) * (m - r) + 1 ∧
    one_layered_max_layers m r ≤ (m - r + 1) * Nat.choose (Nat.log 2 (m - r + 1) + r - 1) (r - 1) ∧
    ((m - r + 1 : ℝ) * ((Nat.log 2 (m - r + 1) + r - 1).choose (r - 1) : ℝ)) ≤
      (m - r + 1 : ℝ) ^ (1 + Real.log (r : ℝ) / Real.log 2)
Formalizes
arXiv:2611.08071 Theorem 2.1
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • one_layered_max_layersFor natural numbers m and r, one_layered_max_layers m r is the supremum (maximum) over all n ≤ m and all 1-layered families of r-subsets…
  • one_layered_linear_boundFor all integers r ≥ 1 and m ≥ r, the maximum number of layers F(m, r) in a 1-layered family of r-subsets on at most m vertices satisfies…
  • one_layered_binomial_boundFor all integers r ≥ 1 and m ≥ r, the maximum number of layers F(m, r) in a 1-layered family of r-subsets on at most m vertices satisfies…
  • one_layered_binomial_bound_le_powerFor integers r ≥ 1 and m ≥ r, the binomial bound (m - r + 1) * choose(⌊log_2(m - r + 1)⌋ + r - 1, r - 1) is at most (m - r + 1)^(1 + log_2…

Read back from the Lean

For all natural numbers $m$ and $r$ satisfying $1 \le r$ and $r \le m$, the following three inequalities hold simultaneously: 1. $\text{one\_layered\_max\_layers}(m, r) \le 2^{r-1}(m - r) + 1$; 2. $\text{one\_layered\_max\_layers}(m, r) \le (m - r + 1) \dbinom{\lfloor \log_2(m - r + 1) \rfloor + r - 1}{r - 1}$; 3. When cast to the real numbers $\mathbb{R}$, $$(m - r + 1) \dbinom{\lfloor \log_2(m - r + 1) \rfloor + r - 1}{r - 1} \le (m - r + 1)^{1 + \frac{\ln r}{\ln 2}}.$$ Here, $\text{one\_layered\_max\_layers}(m, r)$ is the supremum (in $\mathbb{N}$) of the set of all integers $k$ such that there exists some $n \le m$ and a one-layered family $F$ of $r$-element subsets over the ground set $\text{Fin } n$ having $k$ layers. A one-layered family consists of: - an integer $k > 0$; - $k$ layers (indexed by $t \in \text{Fin } k$), each being a non-empty family of $r$-element subsets of $\text{Fin } n$; - pairwise disjoint layers (no $r$-set appears in multiple layers); - the interval property: for every non-empty subset $S \subseteq \text{Fin } n$, the set of layer indices $\{t \in \text{Fin } k \mid \exists F \in \text{layers } t, S \subseteq F\}$ is order-connected (an interval) in $\text{Fin } k$.

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 theorem collects three upper bounds on the maximum number of layers in a 1-layered family into a single conjunction: a linear bound, a binomial bound, and an exponentiated bound on the binomial quantity. The proof simply packages together three previously established lemmas, one for each conjunct.

  1. All three bounds—linear, binomial, and power upper bound—hold simultaneously.

    The goal is a conjunction of three inequalities. The proof constructs the conjunction directly by supplying the proofs from three previously established theorems: `one_layered_linear_bound`, `one_layered_binomial_bound`, and `one_layered_binomial_bound_le_power`, each applied to m, r, and the hypotheses 1 ≤ r and r ≤ m.

    lines 7–8

    uses one_layered_linear_bound, one_layered_binomial_bound, one_layered_binomial_bound_le_power

      exact ⟨one_layered_linear_bound m r hr hm, one_layered_binomial_bound m r hr hm,
        one_layered_binomial_bound_le_power m r hr hm⟩
one_layered_linear_bound
For integers r ≥ 1 and m ≥ r, the maximum number of layers of a 1-layered family on at most m vertices satisfies F(m, r) ≤ 2^(r - 1) * (m - r) + 1.
one_layered_binomial_bound
For integers r ≥ 1 and m ≥ r, the maximum number of layers satisfies F(m, r) ≤ (m - r + 1) * ((⌊log₂ (m - r + 1)⌋ + r - 1) choose (r - 1)).
one_layered_binomial_bound_le_power
For integers r ≥ 1 and m ≥ r, the binomial bound (m - r + 1) * ((⌊log₂ (m - r + 1)⌋ + r - 1) choose (r - 1)) is bounded above by (m - r + 1)^(1 + log r / log 2).

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

/-- Upper bounds on the number of layers in 1-layered families (Theorem 2.1 of arXiv:2611.08071). -/theorem one_layered_family_upper_bounds (m r : ℕ) (hr : 1 ≤ r) (hm : r ≤ m) :    one_layered_max_layers m r ≤ 2 ^ (r - 1) * (m - r) + 1 ∧    one_layered_max_layers m r ≤ (m - r + 1) * Nat.choose (Nat.log 2 (m - r + 1) + r - 1) (r - 1) ∧    ((m - r + 1 : ℝ) * ((Nat.log 2 (m - r + 1) + r - 1).choose (r - 1) : ℝ)) ≤      (m - r + 1 : ℝ) ^ (1 + Real.log (r : ℝ) / Real.log 2) := by  exact ⟨one_layered_linear_bound m r hr hm, one_layered_binomial_bound m r hr hm,    one_layered_binomial_bound_le_power m r hr hm⟩
See it in the graphDiscuss this resultChallenge it