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

Analytic versus numerical regular-expander bounds — Remark 1.5

PDF p. 7: Remark 1.5; PDF p. 29: Section 5, paragraph following the numerical table

Statement

Assume countable choice: every countable family of nonempty sets has a choice function. Let $G = (V, E)$ be a finite undirected graph with $n = ∣ V ∣ > 0$ vertices, at most one edge between each pair, and self-loops allowed. Its binary symmetric adjacency matrix $A$ has $A_{x y} = 1$ when $x$ and $y$ are adjacent and $0$ otherwise; a diagonal entry records a self-loop. Assume $G$ is $d$ -regular with $d > 0$ : every row sum $\sum_{y \in V} A_{x y}$ equals $d$ , so a loop contributes once to its vertex degree. Write $J$ for the all-ones matrix. An $(n, d, α)$ -expander satisfies $∥ A - (d / n) J ∥ \leq α d$ , in the Euclidean operator norm. The graph is globally synchronizing if, for phase-volume almost every initial state of the homogeneous Kuramoto system, the rotating-frame trajectory converges to a state in which all phases agree.

If $G$ is an $(n, d, α)$ -expander with $α \leq 0.0068$ , then it is globally synchronizing. In the article's convention, a $d$ -regular Ramanujan graph is an $(n, d, 2 \sqrt{d - 1} / d)$ -expander; it is globally synchronizing when $d \geq 85730$ .

The article contrasts the $0.0068$ consequence of Theorem 1.10 with its stronger $0.0816$ regular-expander bound, whose proof uses numerical computations. The degree conclusion follows by applying Theorem 1.10 directly at a slightly larger parameter, not by asserting that $2 \sqrt{d - 1} / d \leq 0.0068$ at $d = 85730$ .

Statement references

The Axiom of Countable Choice (AC_ω)

Adjacency spectral expander — Definition 1.3

Ramanujan graph convention used in the article

Globally synchronizing graph — Definition 1.1

Facts & Assumptions

[F1]

A $d$ -regular $(n, d, a)$ -expander is an $(n, d, a, - a, a)$ -expander (Regular adjacency expansion supplies two-sided expansion). The adjacency predicate remains true if its nonnegative parameter is enlarged (Adjacency spectral expander — Definition 1.3).

[F2]

Under countable choice, Theorem 1.10 makes an $(n, d, a, c^{-}, c^{+})$ -expander globally synchronizing when $d > 0$ , $c^{-} > - 1$ , $0 < a \leq 1 / 5$ , and $\frac{32 a (1 + 4 c^{+} - 3 c^{-})}{(1 + c^{-})^{2}} \log ⁣ (\frac{1 + c^{+} + a}{2 a}) < 1$ (General two-sided spectral criterion — Theorem 1.10, The Axiom of Countable Choice (AC_ω)).

[F3]

For real $t$ , $\exp (t) = \sum_{k = 0}^{\infty} t^{k} / k!$ ; $\log$ is its inverse on positive reals, and $\exp$ is strictly increasing (The real exponential function and the number e by a power series, The natural logarithm as the inverse of the exponential function, The exponential function is strictly increasing).

Proof

Given: The graph and hypotheses in the Statement, with countable choice.

Goal: Establish the two consequences of Theorem 1.10 and distinguish the parameter calculations.

1.1F3algebra

Put $b = 85383 / 12500000$ and $t = 107669 / 25000$ . Exact rational arithmetic gives $0.0068 < b < 1 / 5$ , $\sum_{k = 0}^{20} t^{k} / k! > (1 + 2 b) / (2 b)$ , and $\frac{32 b (1 + 7 b)}{(1 - b)^{2}} t = \frac{481633281478542348}{481633485177153125} < 1$ . All terms after the twentieth in the exponential series are positive, so [F3] gives $\log ((1 + 2 b) / (2 b)) < t$ . Hence $\frac{32 b (1 + 7 b)}{(1 - b)^{2}} \log ((1 + 2 b) / (2 b)) < 1$ .

2.1givenF1F2step 1.1algebra

If the graph is an $(n, d, α)$ -expander with $α \leq 0.0068$ , its norm inequality and $d > 0$ force $α \geq 0$ ; enlargement makes it an $(n, d, b)$ -expander. By [F1] it is an $(n, d, b, - b, b)$ -expander. The hypotheses of [F2] hold: $d > 0$ , $- b > - 1$ , $0 < b < 1 / 5$ , and the numerical expression is the one bounded in step 1.1. Thus the graph is globally synchronizing.

3.1givenF1F2step 1.1algebra∎

Let $D = 85730$ and $d \geq D$ . Since $d$ and $D$ are positive integers and $D \geq 2$ , $(d - 1) / d^{2} \leq (D - 1) / D^{2}$ : after multiplying by the positive denominators, the difference is $(d - D) ((D - 1) d - D) \geq 0$ . Also $b^{2} D^{2} - 4 (D - 1) = 854109194681 / 1562500000000 > 0$ . Consequently $2 \sqrt{d - 1} / d < b$ . The Ramanujan definition therefore supplies an $(n, d, b)$ -expander, and the same application of [F1] and [F2] as in step 2.1 gives global synchrony. At $d = D$ , the separate inequality $25000000 (D - 1) > 289 D^{2}$ shows $2 \sqrt{D - 1} / D > 17 / 2500 = 0.0068$ , explaining why the degree conclusion uses the direct application.

Source notes

The comparison of the numerical and analytic bounds and the degree threshold are attributed to Expander graphs are globally synchronizing, Remark 1.5 and the opening of Section 5. The proof above is a local application of the stated suppliers; the article's $0.0816$ proof is mentioned for context and is not a premise of this deduction.

Depends on

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. 7, Remark 1.5; p. 29, paragraph following the numerical table