Proof of Theorem 1.2 — Eq. (2.3): , ,
ProvedAbelianCayleyHDX.eq_2_3_parameterscayley-complexeshigh-dimensional-expandersp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1spectral-graph-theory
Let with .
- If (Eq. (2.2)), then
- There is an absolute constant such that for every the least with and satisfies .
- If , then ; in particular .
These give the Cayley degree and the triangles per edge in Theorem 1.2.
Differences from the source:
- reading: choosing the least admissible gives → one constant , chosen before , bounds the least admissible by ; reason: the has no subscript, so its constant is absolute
- generalization: → whenever , ; reason: an explicit bound implying the statement; it is what (2.2) gives
Preamble
import Mathlib
Formal statement
namespace AbelianCayleyHDX
/-- **Proof of Theorem 1.2: Eq. (2.3) and the parameter bounds** (Mao, *Abelian Cayley High-Dimensional Expanders with Polylogarithmic Degree*, arXiv:2609.08937 (held version, sha256 6f5b0daa…75ba), proof of Theorem 1.2,
Section 2.5, p.10, Eq. (2.3)). With `q = 2^h`:
1. if `n ≥ 2h · 2^{t/3}` (Eq. (2.2)) then `M = (q² − 1) q^{2t} ≤ (q² − 1) (n/(2h))^{6h}`;
2. choosing the least admissible `q` (the least `h` with `q = 2^h ≥ 8` and `3/(q − 2) ≤ λ`)
gives `h = O(log(2 + 1/λ))`, with an absolute constant;
3. if `n ≥ 2h · 2^{t/3}` then `t ≤ 3 log₂ n`, so `t = O_λ(log n)`. -/
theorem eq_2_3_parameters :
(∀ h t n : ℕ, 1 ≤ h → 2 * (h : ℝ) * (2 : ℝ) ^ ((t : ℝ) / 3) ≤ n →
(((2 : ℝ) ^ h) ^ 2 - 1) * ((2 : ℝ) ^ h) ^ (2 * t) ≤
(((2 : ℝ) ^ h) ^ 2 - 1) * ((n : ℝ) / (2 * h)) ^ (6 * h)) ∧
(∃ C : ℝ, 0 < C ∧ ∀ lam : ℝ, 0 < lam → ∃ h : ℕ, 8 ≤ 2 ^ h ∧ 3 / ((2 : ℝ) ^ h - 2) ≤ lam ∧
(∀ h' < h, ¬ (8 ≤ 2 ^ h' ∧ 3 / ((2 : ℝ) ^ h' - 2) ≤ lam)) ∧
(h : ℝ) ≤ C * Real.log (2 + 1 / lam)) ∧
(∀ h t n : ℕ, 1 ≤ h → 2 * (h : ℝ) * (2 : ℝ) ^ ((t : ℝ) / 3) ≤ n →
(t : ℝ) ≤ 3 * Real.logb 2 n) := by sorry
end AbelianCayleyHDX
Source
Songtao Mao, Abelian Cayley High-Dimensional Expanders with Polylogarithmic Degree, arXiv:2609.08937 (held version, sha256 6f5b0daa…75ba), proof of Theorem 1.2, Section 2.5, p.10, Eq. (2.3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.