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

Quantitative Erdős–Rényi synchrony and the false exact-expansion rate — Theorem 6.2

PDF p. 33: Theorem 6.2 and proof on p. 38; PDF p. 38: Theorem 6.2 and proof on p. 38

Statement

For $0 < ε < 1$ and $1 + ε < γ < 1 + ε^{- 2}$ , put $p = γ \log n / n$ , $d^{*} = p n$ , $α = 8 (γ \log n)^{- 1 / 2}$ , and let $- 1 < c^{-} < 0 < c^{+}$ be the unshifted roots of $γ ((1 + c) \log (1 + c) - c) = 1$ .

The article asserts that $G (n, p)$ is an $(n, d^{*}, α, c^{-}, c^{+})$ -expander with probability at least $1 - C (γ, ε) (\log n)^{4} n^{- ε}$ , and in particular is globally synchronizing with the same probability. The expansion probability assertion is false: at the admissible fixed pair $γ = 2$ , $ε = 1 / 2$ , its failure probability is at least $κ / \sqrt{\log n}$ for some fixed $κ > 0$ and all sufficiently large integers $n$ .

The synchronization conclusion nevertheless holds: assuming countable choice, for every displayed admissible pair there is $C = C (γ, ε) > 0$ such that $G (n, p)$ is globally synchronizing with probability at least $1 - C n^{- ε}$ for all sufficiently large $n$ , and therefore with the originally claimed $1 - C (\log n)^{4} n^{- ε}$ probability. Global synchrony is the almost-everywhere convergence of the identical Kuramoto flow to full phase agreement. A sound expander supplying this conclusion has slack parameters $c^{-} = a / 2 - 1$ , $c^{+} = b$ , where $I (x) = x \log x - x + 1$ for $x > 0$ , $0 < a < 1 < b$ and $γ I (a) = γ I (b) = (γ + 1 + ε) / 2$ . These slack parameters are distinct from the exact roots in the attributed assertion.

Facts & Assumptions

[F1]

The graph is the loop-free independent-edge law, the two-sided expander predicate includes $c^{-} d^{*} I ⪯ Δ_{L}$ , and the unshifted roots have their stated branches (Erdős–Rényi random graph and high probability, Two-sided spectral expander — Definition 1.9, Degree large-deviation rate function and roots).

[F2]

At any fixed $γ > 1$ , the expander event with the exact unshifted roots has failure probability at least $κ / \sqrt{\log n}$ , which cannot be $O ((\log n)^{4} n^{- ε})$ for any $ε > 0$ (The exact unshifted expansion event cannot have polynomial failure decay).

[F3]

Under countable choice, for every $0 < ε < 1$ and $γ > 1 + ε$ , with $μ = γ \log n$ , $α = 8 / \sqrt{μ}$ , $γ I (a) = γ I (b) = (γ + 1 + ε) / 2$ and $0 < a < 1 < b$ , the graph is an $(n, μ, α, a / 2 - 1, b)$ -expander and is globally synchronizing with probability at least $1 - C n^{- ε}$ eventually (Slack entropy thresholds preserve the quantitative synchronization bound, The Axiom of Countable Choice (AC_ω), Globally synchronizing graph — Definition 1.1).

[F4]

For $I (x) = x \log x - x + 1$ on $x > 0$ and every $0 < t < 1$ , the equation $I (x) = t$ has unique lower and upper branch solutions $0 < a < 1 < b$ (Entropy rates, inverse branches and shifted root contracts).

Proof

Given: The admissible parameters in the Statement; assume countable choice for the positive synchrony conclusion.

Goal: Separate the false exact-expansion rate from the sound full synchrony conclusion.

1.1F1F2givenalgebra

At $γ = 2$ , $ε = 1 / 2$ , all original parameter inequalities hold. The graph law, reference degree, adjacency tolerance and exact unshifted roots agree with [F1] and [F2]. Thus [F2] is a counterexample under the complete assumptions of the original expansion assertion, for every proposed constant $C > 0$ . It does not use the shifted-root Proposition 6.9 as a premise.

2.1F3F4step 1.1algebra∎

Every original admissible pair satisfies the parameter hypotheses of [F3]. Put $β = (γ + 1 + ε) / 2$ ; since $0 < β < γ$ , [F4] supplies exactly the displayed $a, b$ . With $μ = d^{*} = γ \log n$ , [F3] gives the expander with slack parameters $c^{-} = a / 2 - 1$ , $c^{+} = b$ and global synchrony on the same event. Hence global synchrony holds with failure probability at most $C n^{- ε}$ for large $n$ , which is at most $C (\log n)^{4} n^{- ε}$ once $\log n \geq 1$ . Its slack-root supplier verifies the positive-reference and numerical conditions of the deterministic theorem directly. This proves the original synchronization conclusion without claiming the false unshifted expansion rate.

Source notes

The original article, PDF p. 33, Theorem 6.2 and equation (6.3), supplies attribution for the full original assertion. Its proof on p. 38 invokes Proposition 6.9 and Remark 6.10. The present refutation concerns the original theorem's unshifted roots directly; it does not transfer the refutation of Proposition 6.9 to a different event. Original PDF images and extracted text on pp. 6, 8, 33 and 38 were inspected for the matrix convention, expander definition, exact statement and proof. No source beyond those locations was freshly read for this attribution. The positive synchronization proof uses completed independent nonbacktracking inputs through the restricted adjacency supplier and the local deterministic synchronization theorem. No article statement supplies its own proof.

Depends on

Used by · 1

Useful finite-size synchronization estimates near threshold

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 — Abdalla, Bandeira, Kassabov, Souza, Strogatz, Townsend (2026) · PDF p. 33, Theorem 6.2 and equation (6.3); p. 38, proof; p. 6, Section 1.2; p. 8, Definition 1.9