AFTD Auto-Formalizing Theoretical Domains

spectral_moore_max_order_mono

theoremverified

Sanity lemma: v(k, θ) is monotone in θ.

Statement

theorem spectral_moore_max_order_mono (k : ℕ) {θ θ' : ℝ} (h : θ ≤ θ') :
    spectral_moore_max_order k θ ≤ spectral_moore_max_order k θ'
Source
Sanity lemma for spectral_moore_max_order (arXiv:2611.00591 (A spectral Moore problem and the Yang-Koolen conjecture), noted after Theorem 2.3: v(k, θ) ≤ v(k, ⌈θ⌉)).
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The maximal order spectral_moore_max_order(k, θ) is defined as the supremum of the orders of all connected k-regular graphs whose second eigenvalue is at most θ. When θ ≤ θ', any graph meeting this spectral condition for θ also meets it for θ' by transitivity of ≤. Thus every admissible graph in the left-hand supremum is also an admissible witness for the right-hand supremum, so the supremum is monotone non-decreasing in θ.

  1. To bound the supremum for θ by that for θ', it suffices to show that the order of any graph valid for θ is bounded by the supremum for θ'.

    Unfolding the definition of spectral_moore_max_order expresses both sides as suprema over graph orders n, graphs G on n vertices, and proofs that G is connected, k-regular, and has second eigenvalue at most the parameter. By iSup₂_le and iSup_le, bounding the left-hand supremum by the right-hand side reduces to showing that for any fixed n, graph G on Fin n, and assumption hG that G satisfies the three conditions for θ, the order n is at most the supremum for θ'.

    lines 3–5

    uses iSup₂_le, iSup_le

      classical
      unfold spectral_moore_max_order
      refine iSup₂_le fun n G => iSup_le fun hG => ?_
  2. The order n is at most the right-hand supremum, provided G satisfies the second eigenvalue condition for θ'.

    We bound n by instantiating the right-hand supremum at the exact same graph G on n vertices using le_iSup₂_of_le and le_iSup_of_le, observing that n ≤ n holds by reflexivity (le_rfl). The connectivity of G is provided directly by hG.1, and its k-regularity is supplied by hG.2.1, leaving only the verification of the eigenvalue condition for θ'.

    lines 6–7

    uses le_iSup₂_of_le, le_iSup_of_le, le_rfl

      refine le_iSup₂_of_le n G (le_iSup_of_le ⟨hG.1, ?_, ?_⟩ le_rfl)
      · convert hG.2.1
  3. The graph G satisfies the second eigenvalue bound for θ'.

    For any eigenvalue index i > 0, the hypothesis hG.2.2 guarantees that the i-th eigenvalue of G is at most θ. Since θ ≤ θ' by assumption h, the eigenvalue is at most θ' by transitivity of ≤.

    lines 8–9

      · intro i hi
        exact (hG.2.2 i hi).trans h
iSup₂_le
A double supremum ⨆ i, ⨆ j, f i j is bounded above by a if every term f i j is bounded above by a.
iSup_le
A supremum ⨆ i, f i is bounded above by a if every term f i is bounded above by a.
le_iSup₂_of_le
An element a is bounded above by a double supremum ⨆ i, ⨆ j, f i j if it is bounded above by any specific term f i j.
le_iSup_of_le
An element a is bounded above by a supremum ⨆ i, f i if it is bounded above by any specific term f i.
le_rfl
The inequality relation is reflexive: a ≤ a for every a.

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_max_order_mono (k : ℕ) {θ θ' : ℝ} (h : θ ≤ θ') :    spectral_moore_max_order k θ ≤ spectral_moore_max_order k θ' := by  classical  unfold spectral_moore_max_order  refine iSup₂_le fun n G => iSup_le fun hG => ?_  refine le_iSup₂_of_le n G (le_iSup_of_le ⟨hG.1, ?_, ?_⟩ le_rfl)  · convert hG.2.1  · intro i hi    exact (hG.2.2 i hi).trans h
See it in the graphDiscuss this resultChallenge it