LemmaStatement: AI-adaptedProof: AI-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Spectral estimates for phase Fourier sums

PDF p. 12: Proof of Lemma 2.1; PDF p. 13: Proof of Lemma 2.1

Statement

Let $G = (V, E)$ be a finite undirected $(n, d^{*}, α)$ -expander with $n = ∣ V ∣ > 0$ , symmetric binary adjacency matrix $A$ , and possible self-loops. Thus $Δ_{A} = A - (d^{*} / n) J$ and $∥ Δ_{A} ∥ \leq α d^{*}$ , where $J$ is the all-ones matrix. Let $θ_{x}$ be phases modulo $2 π$ , and put $ρ_{k} = n^{- 1} \sum_{x \in V} e^{i k θ_{x}}$ for $k = 1, 2$ . With $f (x) = e^{i θ_{x}}$ , $g (x) = e^{2 i θ_{x}}$ and $h (x) = 1$ , and with $⟨ u, v ⟩ = \sum_{x} \overline{u (x)} v (x)$ , one has

$∣ ⟨ f, A f ⟩ - d^{*} n ∣ ρ_{1} ∣^{2} ∣ \leq α d^{*} n, ∣ ⟨ g, A g ⟩ - d^{*} n ∣ ρ_{2} ∣^{2} ∣ \leq α d^{*} n, ∣ ⟨ h, A h ⟩ - d^{*} n ∣ \leq α d^{*} n .$

Consequently,

$\sum_{x, y \in V} A_{x y} \cos^{2} (θ_{x} - θ_{y}) \geq \frac{d^{*} n}{2} (1 + ∣ ρ_{2} ∣^{2}) - α d^{*} n .$

If $\sum_{x, y} A_{x y} = d^{*} n$ , the constant-vector estimate is an equality with zero error, and the last lower bound improves to $d^{*} n (1 + ∣ ρ_{2} ∣^{2}) / 2 - α d^{*} n / 2$ . This equality holds for a $d^{*}$ -regular graph. If $ℓ$ is the number of self-loops, then $\sum_{x, y} A_{x y} = 2 ∣ E ∣ - ℓ$ ; in particular $∣ E ∣ = d^{*} n / 2$ implies the required equality when $ℓ = 0$ .

Facts & Assumptions

[F1]

The expander definition gives $Δ_{A} = A - (d^{*} / n) J$ and $∥ Δ_{A} ∥ \leq α d^{*}$ ; graph notation makes $A$ real symmetric and counts a loop once in a row sum (Adjacency spectral expander — Definition 1.3, Centered graph matrices and reference degree, Adjacency, degrees, graph Laplacian, and spectral notation).

[F2]

The vertex inner product and matrix action are as stated, and $u^{*} J u = ∣ \sum_{x} u (x) ∣^{2}$ for every vertex vector $u$ (Loewner order, Hermitian inner product, and operator norm, The constant projection and centering decomposition).

[F3]

The Daido parameters are the stated averages, independent of phase lifts. Unit phasors have modulus one, obey the exponential addition law, and have real part equal to cosine (Daido order parameters, Phasors, trigonometric identities and periodic derivatives).

[F4]

Cauchy–Schwarz and the induced operator norm imply $∣ ⟨ u, Δ_{A} u ⟩ ∣ \leq ∥ Δ_{A} ∥ ∥ u ∥^{2}$ for every vertex vector $u$ (Cauchy–Schwarz: |⟨ u,v⟩|≤‖ u‖‖ v‖, with equality exactly for linearly dependent vectors, The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖, Loewner order, Hermitian inner product, and operator norm).

Proof

Given: The graph, expander bound and phase configuration in the statement.

Goal: Establish the three estimates, the cosine-square bound and the corrected equality cases.

Proof technique: direct.

1.1givenF1F2F3F4algebra

By [F1], $A = (d^{*} / n) J + Δ_{A}$ . By [F2] and [F3], for $u = f, g$ respectively, $u^{*} J u = n^{2} ∣ ρ_{k} ∣^{2}$ with $k = 1, 2$ , and $∥ u ∥^{2} = n$ ; for $u = h$ , $h^{*} J h = n^{2}$ and $∥ h ∥^{2} = n$ . Applying [F4] and the bound in [F1] to these three vectors gives all three displayed quadratic-form estimates.

2.1F1F2F3step 1.1algebra

Matrix expansion and the phasor identities give $Re ⟨ g, A g ⟩ = \sum_{x, y} A_{x y} \cos (2 θ_{x} - 2 θ_{y})$ . Since $A$ is real symmetric, $⟨ g, A g ⟩$ is real. The identities in [F3] also give $2 \cos^{2} t = 1 + \cos (2 t)$ : write $z = e^{i t}$ , use $z + \overline{z} = 2 \cos t$ , $z \overline{z} = 1$ , and $Re z^{2} = \cos (2 t)$ . Thus twice the cosine-square sum equals $⟨ h, A h ⟩ + ⟨ g, A g ⟩$ . Taking the two lower estimates from step 1.1 proves the stated bound.

3.1givenF1F2step 2.1algebra∎

If the ordered entry sum is $d^{*} n$ , then $⟨ h, A h ⟩ = d^{*} n$ by [F2], so using that equality in step 2.1 gives the improved bound. For a $d^{*}$ -regular graph every row sum is $d^{*}$ , giving the ordered sum $d^{*} n$ . Each non-loop edge contributes two ordered entries and each loop one, so the ordered sum is $2 ∣ E ∣ - ℓ$ ; the stated loop-free edge-count case follows. These calculations also complete the equality assertions.

Source notes

The estimates and the edge-count comparison are attributed to the proof of Lemma 2.1 in Expander graphs are globally synchronizing, PDF pages 12–13. The loop correction follows from the graph convention stated above; the article is not a proof premise.

Depends on

Used by · 1

First and second order parameter inequality — Lemma 2.1

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.

Sources

Expander graphs are globally synchronizing · PDF pp. 12–13, proof of Lemma 2.1; p. 18, Section 3