AFTD Auto-Formalizing Theoretical Domains

one_layered_max_layers_one_le

theoremverified

For any positive integer m, the maximum number of layers in a 1-layered family of 1-subsets on at most m vertices is at most m.

Statement

theorem one_layered_max_layers_one_le (m : ℕ) (hm : 1 ≤ m) :
    one_layered_max_layers m 1 ≤ m
Source
arXiv:2611.08071 Theorem 2.1
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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_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…

Read back from the Lean

For every natural number $m$ satisfying $1 \le m$, one_layered_max_layers m 1 is less than or equal to $m$.

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 establishes the base case r = 1 by specializing the general upper bound `one_layered_binomial_bound`. For r = 1, the binomial coefficient reduces to a choose-0 factor which equals 1, simplifying the upper bound directly to m - 1 + 1 = m.

  1. one_layered_max_layers m 1 ≤ (m - 1 + 1) * Nat.choose (Nat.log 2 (m - 1 + 1) + 1 - 1) (1 - 1)

    Instantiate the general binomial bound `one_layered_binomial_bound` with layer size r = 1. The condition 1 ≤ 1 is proved by linear integer arithmetic (`omega`), and 1 ≤ m is supplied by the assumption `hm`.

    line 4

    uses one_layered_binomial_bound

      have h := one_layered_binomial_bound m 1 (by omega) hm
  2. one_layered_max_layers m 1 ≤ m - 1 + 1

    Simplify the upper bound in `h`: the exponent and lower index 1 - 1 become 0 by `Nat.sub_self`, the binomial coefficient with bottom argument 0 evaluates to 1 by `Nat.choose_zero_right`, and multiplying by 1 leaves m - 1 + 1 by `mul_one`.

    line 5

    uses Nat.sub_self, Nat.choose_zero_right, mul_one

      simp only [Nat.sub_self, Nat.choose_zero_right, mul_one] at h
  3. one_layered_max_layers m 1 ≤ m

    From 1 ≤ m, natural number arithmetic gives m - 1 + 1 = m, so linear arithmetic (`omega`) closes the goal.

    line 6

      omega
one_layered_binomial_bound
For integers 1 ≤ r ≤ m, the maximum number of layers in a 1-layered family of r-subsets on at most m vertices is at most (m - r + 1) * ((log₂ (m - r + 1) + r - 1).choose (r - 1)).
Nat.sub_self
For any natural number n, n - n = 0.
Nat.choose_zero_right
For any natural number n, the binomial coefficient n.choose 0 equals 1.
mul_one
Multiplying any element by 1 on the right leaves it unchanged.

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

/-- Base case r = 1 for the maximum number of layers in a 1-layered family. -/theorem one_layered_max_layers_one_le (m : ℕ) (hm : 1 ≤ m) :    one_layered_max_layers m 1 ≤ m := by  have h := one_layered_binomial_bound m 1 (by omega) hm  simp only [Nat.sub_self, Nat.choose_zero_right, mul_one] at h  omega
See it in the graphDiscuss this resultChallenge it