LemmaStatement: AI-generatedProof: 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.

Kernel phases on two-sided expanders: the two tail-growth estimates

Statement

Let $G$ have vertex set $V$ with $n = ∣ V ∣ > 0$ and symmetric binary adjacency matrix $A$ , allowing loops. Let $D$ be diagonal with $D_{x x} = \sum_{y} A_{x y}$ , put $L = D - A$ , and let $I$ and $J$ be the identity and all-ones matrices. Use the operator norm induced by the standard norm on $C^{V}$ and the Loewner order on Hermitian matrices. Let $d > 0$ , $a > 0$ , $- 1 < c_{-} \leq 0 \leq c_{+}$ , $w = c_{+} - c_{-} > 0$ , $s = 1 + c_{-}$ , $B = 1 + c_{+} + a$ . Suppose $∥ A - (d / n) J ∥ \leq a d$ and $c_{-} d I ⪯ L - d I + (d / n) J ⪯ c_{+} d I$ .

Choose phase representatives $θ_{x} \in (- π, π]$ normalized so that $ρ = n^{- 1} \sum_{x} e^{i θ_{x}}$ is real and nonnegative. For $u, v \in (- π, π]$ , define $K (u, v) = \sin (∣ u ∣ - \min (∣ v ∣, π / 2))$ . Assume $\sum_{x \in V} A_{x y} K (θ_{x}, θ_{y}) \geq 0$ for every $y \in V$ . Set $C_{t} = {x \in V : ∣ θ_{x} ∣ \geq t}$ and $m_{0} = ∣ C_{π / 2} ∣ > 0$ . For $0 < γ < β \leq π / 2$ , $0 < ϵ < s$ , and $u > 0$ :

(a) if $\sin (β - γ) \geq 2 (1 + u) a / (s - ϵ)$ , then $∣ C_{γ} ∣ \geq \min {(1 + ϵ / w) ∣ C_{β} ∣, u a n, n / 2}$ ;

(b) if $\sin (β - γ) \geq 2 B m_{0} / ((s - ϵ) ∣ C_{β} ∣)$ , then $∣ C_{γ} ∣ \geq \min {(1 + ϵ / w) ∣ C_{β} ∣, n / 2}$ .

Facts & Assumptions

[F1]

Graph and matrix conventions are supplied by Two-sided spectral expander — Definition 1.9, and phase normalization and kernel notation by Critical PSD phases: kernel inequality and half-circle rigidity. Elementary angular conventions are supplied by Angular order and elementary inverse-trigonometric bounds. The kernel inequality is assumed directly here; no critical-point, Hessian or local-minimum hypothesis is imposed. All additional notation used below is defined in the Statement or Proof.

[F2]

Sine is strictly increasing on $[- π / 2, π / 2]$ and has range $[- 1, 1]$ (Signs, monotonicity intervals, and ranges of sine and cosine). For every real $t$ , $\sin (- t) = - \sin t$ (Parity and the Pythagorean identity for sine and cosine).

Proof

Given: The data and hypotheses of the Statement.

Goal: Prove both tail-growth estimates for every configuration satisfying the stated spectral and kernel hypotheses.

1.1F1algebra

For sets define $e (U, W) = \sum_{x \in U, y \in W} A_{x y}$ and $p (U) = e (U, U^{c})$ . Testing the centered-adjacency bound on $1_{U}$ gives $e (U, U) \leq (d / n) ∣ U ∣^{2} + a d ∣ U ∣$ . Testing the centered-Laplacian inequalities on $1_{U} - (∣ U ∣ / n) 1$ gives $(1 + c_{-}) d ∣ U ∣ ∣ U^{c} ∣ / n \leq p (U) \leq (1 + c_{+}) d ∣ U ∣ ∣ U^{c} ∣ / n$ . Therefore $e (U, V) = e (U, U) + p (U) \leq B d ∣ U ∣$ , since $c_{+} \geq 0$ . These tests include loops under the stated degree convention.

1.2F1algebra

Suppose $\emptyset \neq X \subseteq Y$ , $∣ Y ∣ < n / 2$ , and $∣ Y ∣ < (1 + ϵ / w) ∣ X ∣$ . Put $x = ∣ X ∣$ , $y = ∣ Y ∣$ , $Z = Y ∖ X$ , $z = ∣ Z ∣ < ϵ x / w$ . The identity $2 e (X, Y^{c}) = p (X) + p (Y) - p (Z)$ and the two cut bounds give $e (X, Y^{c}) \geq (1 + c_{-}) d x (n - y) / n - w d z (n - z) / (2 n) > (s - ϵ) d x (n - y) / n$ . Indeed, $z (n - z) < (ϵ x / w) n < 2 (ϵ x / w) (n - y)$ . This inequality is strict also at $z = 0$ , because $ϵ x (n - y) > 0$ .

1.3F1F2algebra

Sum the kernel inequality over $y \in X = C_{β}$ , and split $x$ into $X$ , $Y ∖ X$ , $Y^{c}$ with $Y = C_{γ}$ . On these regions the kernel is at most $1$ , $0$ , and $- \sin (β - γ)$ respectively: the bounds follow by expanding its definition separately at $∣ θ_{y} ∣ \leq π / 2$ and $∣ θ_{y} ∣ \geq π / 2$ . Thus $e (X, X) \geq \sin (β - γ) e (X, Y^{c})$ . A second bound is obtained from $K (u, v) + K (v, u) \leq 1_{∣ u ∣ \geq π / 2} + 1_{∣ v ∣ \geq π / 2}$ . If both absolute phases are below $π / 2$ the sum is zero; if just one is above, the sum is at most $1$ because the other kernel term is nonpositive; if both are above each term is at most $1$ . Symmetrizing the internal sum gives $e (C_{π / 2}, X) \geq \sin (β - γ) e (X, Y^{c})$ .

2.1F1algebra∎

To prove (a), suppose the conclusion fails. Then $y < n / 2$ , $y < (1 + ϵ / w) x$ and $y < u a n$ , hence $x < u a n$ . Steps 1.1–1.2 yield $e (X, X) \leq (1 + u) a d x$ and $e (X, Y^{c}) > (s - ϵ) d x / 2$ . The sine hypothesis and step 1.3 now give $e (X, X) > (1 + u) a d x$ , a contradiction. To prove (b), failure gives the first two strict size inequalities. Steps 1.1–1.3 give $B d m_{0} \geq e (C_{π / 2}, X) \geq \sin (β - γ) e (X, Y^{c}) > B d m_{0}$ , also impossible. This proves both estimates.

Depends on

Used by · 1

Positive-reference expanders have only synchronized critical PSD phases

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.