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.

Critical PSD kernel phases: quantitative tail growth

Statement

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$ . For normalized phases satisfying the preceding kernel inequality set $C_{t} = {x : ∣ θ_{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]

Use the graph, phase, algebraic and analytic interfaces of Regular critical PSD phases: kernel and half-circle, Two-sided spectral expander — Definition 1.9, Angular order and elementary inverse-trigonometric bounds. Every configuration assumed here is a critical point with positive-semidefinite Hessian; local minimality is never inferred from that condition.

[F2]

Sine is strictly increasing on $[- π / 2, π / 2]$ and has range $[- 1, 1]$ (Signs, monotonicity intervals, and ranges of sine and cosine).

[F3]

Sine is odd: $\sin (- t) = - \sin t$ for every real $t$ , and consequently $\sin 0 = 0$ (Parity and the Pythagorean identity for sine and cosine).

Proof

Given: The hypotheses of the Statement.

Goal: Establish its conclusions directly for critical PSD phases.

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.3F1F2F3algebra

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: for $x \in Y ∖ X$ the sine argument lies in $[- π / 2, 0]$ , and for $x \in Y^{c}$ it lies in $[- π / 2, - (β - γ)]$ ; monotonicity, oddness and the sine range give these bounds. 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 by oddness; 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

Certified regular amplification excludes a PSD half-circle tail

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.