AFTD Auto-Formalizing Theoretical Domains

spectral_moore_degree_threshold_spec

theoremverified

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(θ).

  1. 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(θ).

    line 6

    uses Nat.sInf_mem

      exact Nat.sInf_mem h
Nat.sInf_mem
Every nonempty set of natural numbers contains its infimum (its minimum element).

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