spectral_moore_degree_threshold_le
Sanity lemma: K(θ) is at most every degree from which the bound holds.
Statement
theorem spectral_moore_degree_threshold_le (θ : ℝ) (K : ℕ)
(h : ∀ k : ℕ, K ≤ k →
spectral_moore_max_order k θ ≤ ((2 * k + 2 * ⌊1 + θ ^ 2 / 4⌋₊ : ℕ) : ℕ∞)) :
spectral_moore_degree_threshold θ ≤ K- Source
- Sanity lemma for spectral_moore_degree_threshold (arXiv:2611.00591 (A spectral Moore problem and the Yang-Koolen conjecture), Question 8.1).
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- spectral_moore_degree_thresholdK(θ): the least natural number K such that v(k, θ) ≤ 2k + 2⌊1 + θ²/4⌋ for every degree k ≥ K (defaulting to 0 if there is no such K).
- spectral_moore_max_orderv(k, θ): the maximum number of vertices of a connected k-regular finite simple graph whose second largest adjacency eigenvalue is at most…
The proof, explained
The degree threshold `spectral_moore_degree_threshold θ` is defined as the infimum of the set of natural numbers K' for which the spectral Moore bound holds for all degrees k ≥ K'. By hypothesis, the given K satisfies this condition and therefore belongs to the set. The claim follows immediately since the infimum of a set of natural numbers is at most any element in that set.
spectral_moore_degree_threshold θ ≤ K
By definition, `spectral_moore_degree_threshold θ` is the infimum of the set of all integers K' such that the spectral Moore order bound holds for all degrees k ≥ K'. The hypothesis h states that K belongs to this set. Thus, the infimum of the set is at most K by Nat.sInf_le.
uses
Nat.sInf_leexact Nat.sInf_le h
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to any element of the set.
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.
theorem spectral_moore_degree_threshold_le (θ : ℝ) (K : ℕ) (h : ∀ k : ℕ, K ≤ k → spectral_moore_max_order k θ ≤ ((2 * k + 2 * ⌊1 + θ ^ 2 / 4⌋₊ : ℕ) : ℕ∞)) : spectral_moore_degree_threshold θ ≤ K := by exact Nat.sInf_le h