CorollaryStatement: 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.

Lower bound for the second order parameter — Corollary 2.4

PDF p. 15: Corollary 2.4, equation (2.10)

Statement

Assume countable choice. Let $G = (V, E)$ be a connected finite undirected graph with $n = ∣ V ∣ > 0$ , symmetric binary adjacency matrix $A$ and possible self-loops. Connected means that every two vertices can be joined by a finite edge path. Let $d^{*}, α \in R$ , and suppose $G$ is an $(n, d^{*}, α)$ -expander: $∥ A - (d^{*} / n) J ∥ \leq α d^{*}$ , where $J$ is the all-ones matrix and the norm is the Euclidean operator norm. Let $θ$ be a stable state, meaning a local minimum on the phase torus of $E_{G} (θ) = \frac{1}{2} \sum_{x, y \in V} A_{x y} (1 - \cos (θ_{x} - θ_{y}))$ . For $k \geq 1$ , define its Daido order parameter by $ρ_{k} (θ) = n^{- 1} \sum_{x \in V} e^{i k θ_{x}}$ , using real representatives of the phases. If $ρ_{1} (θ)$ is real and positive, then $∣ ρ_{2} (θ) ∣ \geq 1 - 2 α^{2} / ρ_{1} (θ)^{2}$ .

Statement references

Adjacency, degrees, graph Laplacian, and spectral notation

Adjacency spectral expander — Definition 1.3

Equilibria, stable states, synchronized states, and spurious minima

Daido order parameters

Phasors, trigonometric identities and periodic derivatives

The Axiom of Countable Choice (AC_ω)

Real and imaginary parts, complex conjugation, and modulus

Facts & Assumptions

[F1]

Under the statement's hypotheses, after choosing representatives $θ_{x} \in (- π, π]$ , Lemma 2.3 gives $n α^{2} \geq ρ_{1} (θ)^{2} \sum_{x} H (θ_{x})$ . It assumes countable choice and applies to connected graphs, including zero reference degree (Order parameter control of total H mass — Lemma 2.3, The Axiom of Countable Choice (AC_ω)).

[F2]

On $(- π, π]$ , $H (t) = \sin^{2} (∣ t ∣)$ for $∣ t ∣ \leq π / 2$ and $H (t) = 1$ for $π / 2 \leq ∣ t ∣ \leq π$ ; in particular $H (t) \geq \sin^{2} t$ (Truncated sine-square function, Elementary properties of the function H).

[F3]

The Daido parameter is the stated average, independent of the representatives. For real $t$ , $e^{i t} = \cos t + i \sin t$ , $∣ e^{i t} ∣ = 1$ , and $e^{i (u + v)} = e^{i u} e^{i v}$ ; the real part of a finite sum is the sum of its real parts (Daido order parameters, Phasors, trigonometric identities and periodic derivatives).

[F4]

For $z = a + i b$ with $a, b \in R$ , $Re z = a$ and $∣ z ∣ = \sqrt{a^{2} + b^{2}}$ , where the square root is nonnegative (Real and imaginary parts, complex conjugation, and modulus).

Proof

Given: The connected expander and stable state in the statement, with $ρ_{1} (θ) > 0$ real, under countable choice.

Goal: Prove $∣ ρ_{2} (θ) ∣ \geq 1 - 2 α^{2} / ρ_{1} (θ)^{2}$ .

1.1F2F3F4givenalgebra

Choose each phase representative in $(- π, π]$ . By [F3] and [F4], $\cos^{2} t + \sin^{2} t = ∣ e^{i t} ∣^{2} = 1$ ; squaring $e^{i t} = \cos t + i \sin t$ and using the addition law gives $\cos (2 t) = \cos^{2} t - \sin^{2} t = 1 - 2 \sin^{2} t$ . For any $z = a + i b$ , put $m = ∣ z ∣$ . By [F4], $m \geq 0$ and $m^{2} = a^{2} + b^{2}$ . If $m < a$ , then $a > 0$ and $0 < (a - m) (a + m) = - b^{2} \leq 0$ , a contradiction. Thus $∣ z ∣ \geq Re z$ . Hence $∣ ρ_{2} ∣ \geq Re ρ_{2} = 1 - (2 / n) \sum_{x} \sin^{2} θ_{x} \geq 1 - (2 / n) \sum_{x} H (θ_{x})$ .

2.1F1step 1.1givenalgebra∎

Because $n > 0$ and $ρ_{1} > 0$ , [F1] gives $(1 / n) \sum_{x} H (θ_{x}) \leq α^{2} / ρ_{1}^{2}$ . Substitution into step 1.1 proves the claimed bound.

Source notes

The corollary and its standing connectedness assumption are attributed to Expander graphs are globally synchronizing, PDF pp. 11 and 15. The proof above derives the conclusion from the stated suppliers.

Depends on

Used by · 3

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 p. 11, last paragraph of Section 2.1; p. 15, Corollary 2.4 and its proof