AFTD Auto-Formalizing Theoretical Domains

spectral_moore_degree_threshold_le

theoremverified

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.

  1. 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.

    line 5

    uses Nat.sInf_le

      exact 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

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
See it in the graphDiscuss this resultChallenge it