one_layered_max_layers_one_le
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.
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`.
uses
one_layered_binomial_boundhave h := one_layered_binomial_bound m 1 (by omega) hm
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`.
uses
Nat.sub_self,Nat.choose_zero_right,mul_onesimp only [Nat.sub_self, Nat.choose_zero_right, mul_one] at h
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.
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
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.
/-- 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