spectral_moore_degree_threshold_spec
Sanity lemma: if some degree threshold exists, the bound v(k, θ) ≤ 2k + 2⌊1 + θ²/4⌋ holds for every k ≥ K(θ).
Statement
theorem spectral_moore_degree_threshold_spec (θ : ℝ)
(h : ∃ K : ℕ, ∀ k : ℕ, K ≤ k →
spectral_moore_max_order k θ ≤ ((2 * k + 2 * ⌊1 + θ ^ 2 / 4⌋₊ : ℕ) : ℕ∞)) :
∀ k : ℕ, spectral_moore_degree_threshold θ ≤ k →
spectral_moore_max_order k θ ≤ ((2 * k + 2 * ⌊1 + θ ^ 2 / 4⌋₊ : ℕ) : ℕ∞)- 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 Moore order bound holds for all k ≥ K. The hypothesis h states that this set is nonempty. Since every nonempty set of natural numbers contains its infimum (`Nat.sInf_mem`), the threshold itself belongs to the set and therefore satisfies the bound for all k ≥ K(θ).
For every k ≥ spectral_moore_degree_threshold(θ), the order bound holds.
The threshold `spectral_moore_degree_threshold θ` is defined as the infimum of the set of natural numbers K such that the bound holds for all k ≥ K. The assumption h provides a witness, meaning this set of natural numbers is nonempty. By `Nat.sInf_mem`, every nonempty set of natural numbers contains its infimum; therefore, the infimum itself satisfies the condition, which means the bound holds for all k ≥ spectral_moore_degree_threshold(θ).
uses
Nat.sInf_memexact Nat.sInf_mem h
Nat.sInf_mem- Every nonempty set of natural numbers contains its infimum (its minimum element).
- The existential hypothesis `h` is definitionally identical to `s.Nonempty` for the set `s` used in the definition of `spectral_moore_degree_threshold θ`, so `Nat.sInf_mem` applies directly without an explicit rewrite.
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_spec (θ : ℝ) (h : ∃ K : ℕ, ∀ k : ℕ, K ≤ k → spectral_moore_max_order k θ ≤ ((2 * k + 2 * ⌊1 + θ ^ 2 / 4⌋₊ : ℕ) : ℕ∞)) : ∀ k : ℕ, spectral_moore_degree_threshold θ ≤ k → spectral_moore_max_order k θ ≤ ((2 * k + 2 * ⌊1 + θ ^ 2 / 4⌋₊ : ℕ) : ℕ∞) := by exact Nat.sInf_mem h