spectralGap

formal source

  27noncomputable section
  28
  29/-- Spectral gap at k-core decomposition depth `k`. -/
  30def spectralGap (k : ℕ) : ℝ := phi ^ (-(k : ℤ))
  31
  32theorem spectralGap_pos (k : ℕ) : 0 < spectralGap k :=
  33  zpow_pos Constants.phi_pos _
  34
  35theorem spectralGap_strictly_decreasing (k : ℕ) :
  36    spectralGap (k + 1) < spectralGap k := by
  37  unfold spectralGap
  38  have hphi_ne : phi ≠ 0 := Constants.phi_ne_zero
  39  have h : phi ^ (-((k : ℤ) + 1)) = phi ^ (-(k : ℤ)) * phi⁻¹ := by
  40    rw [show (-((k : ℤ) + 1)) = -(k : ℤ) + (-1 : ℤ) by ring]
  41    rw [zpow_add₀ hphi_ne]; simp
  42  have hcast : ((k + 1 : ℕ) : ℤ) = (k : ℤ) + 1 := by push_cast; ring
  43  rw [hcast, h]
  44  have hk_pos : 0 < phi ^ (-(k : ℤ)) := zpow_pos Constants.phi_pos _
  45  have hphi_inv_lt_one : phi⁻¹ < 1 :=
  46    inv_lt_one_of_one_lt₀ (by have := Constants.phi_gt_onePointFive; linarith)
  47  have : phi ^ (-(k : ℤ)) * phi⁻¹ < phi ^ (-(k : ℤ)) * 1 :=
  48    mul_lt_mul_of_pos_left hphi_inv_lt_one hk_pos
  49  simpa using this
  50
  51/-- The AS-level spectral gap at k=2 (the observed CAIDA value ≈ 0.382 ≈ 1/φ²). -/
  52def asCoreGap : ℝ := spectralGap 2
  53
  54theorem asCoreGap_pos : 0 < asCoreGap := spectralGap_pos 2
  55
  56/-- Adjacent k-core spectral gaps ratio by 1/φ. -/
  57theorem spectralGap_ratio (k : ℕ) :
  58    spectralGap (k + 1) / spectralGap k = phi⁻¹ := by
  59  unfold spectralGap
  60  have hphi_ne : phi ≠ 0 := Constants.phi_ne_zero