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.

The reported centered-adjacency estimate and its sparse-law limit

PDF p. 31: Section 6, equation (6.1)

Statement

The article attributes to Peche and Soshnikov the high-probability estimate $∥ Δ_{A} ∥ \leq 2 \sqrt{n p (1 - p)} + o (n^{- 1 / 44})$ as $n \to \infty$ and infers that $α = (2 + ε) (p n)^{- 1 / 2}$ can be used. Here $d^{*} = p n > 0$ and $Δ_{A} = A - p J$ for the simple graph $G (n, p)$ . The adjacency-expander parameter $α$ controls the inequality $∥ Δ_{A} ∥ \leq α d^{*}$ ; the reported choice therefore requires $∥ Δ_{A} ∥ \leq (2 + ε) \sqrt{n p}$ for fixed $ε > 0$ . This attribution is retained as the original claim. It does not hold throughout the near-connectivity regime $p = γ \log n / n$ , $γ > 1$ : the law $p = 3 \log n / (2 n)$ has a fixed leading-order spectral gap above $2 \sqrt{n p}$ , as in the counterexample below. In particular, this law excludes the reported choice of $α$ for every fixed $0 < ε < g / 2$ , where $g = 9 / (2 \sqrt{5}) - 2 > 0$ . The fixed-law Wigner input does not justify a changing sparse law or this loop-free diagonal convention.

Statement references

Erdős–Rényi random graph and high probability

Centered graph matrices and reference degree

Adjacency spectral expander — Definition 1.3

Asymptotic quantifiers and uniform parameter ranges

A fixed-law Wigner spectral-edge input

A near-threshold counterexample to the reported constant-two spectral bound

Facts & Assumptions

[F1]

The original equation and its attribution occur on original PDF p. 31, before the paragraph taking $p = γ \log n / n$ , $γ > 1$ .

[F2]

The independent Wigner supplier fixes a compactly supported entry law, its variance and moment envelope, and uses independent identically distributed entries including the diagonal. A fixed-law Wigner spectral-edge input

[F3]

The counterexample with $p = 3 \log n / (2 n)$ proves that $∥ A - p J ∥ \geq (2 + g / 2) \sqrt{n p}$ with high probability, where $g = 9 / (2 \sqrt{5}) - 2 > 0$ . A near-threshold counterexample to the reported constant-two spectral bound

[F4]

For a loop-free graph the centered-at-mean matrix has diagonal zero, but $Δ_{A} = A - p J$ has diagonal $- p$ . Centered graph matrices and reference degree Erdős–Rényi random graph and high probability

[F5]

The adjacency-expander predicate is $∥ Δ_{A} ∥ \leq α d^{*}$ , with $Δ_{A} = A - (d^{*} / n) J$ . At $d^{*} = p n > 0$ , the choice $α = (2 + ε) (p n)^{- 1 / 2}$ is therefore equivalent to $∥ A - p J ∥ \leq (2 + ε) \sqrt{n p}$ . Adjacency spectral expander — Definition 1.3 Centered graph matrices and reference degree

Proof

Given: The data and hypotheses in the Statement.

Goal: Establish the stated conclusions.

1.1F1F2algebra

Fact [F1] preserves the article attribution. The Wigner normalization in [F2] would turn its error $o (n^{- 6 / 11 + ε})$ into $o (n^{- 1 / 22 + ε})$ upon multiplying by $\sqrt{n}$ ; choosing $ε = 1 / 44$ explains the exponent in the reported formula. This computation still requires a fixed law and the stated diagonal assumptions, and supplies no theorem uniform in a vanishing $p$ .

2.1F3F4step 1.1algebra

By [F3], the claim fails for $γ = 3 / 2$ , with the same loop-free graph and reference-degree centering in [F4]. Since $2 \sqrt{n p (1 - p)} \leq 2 \sqrt{n p}$ , no $o (n^{- 1 / 44})$ error can close that positive leading-order gap. Thus the reported formula and its constant-two consequence cannot be used throughout the stated near-threshold regime. The original claim remains covered by its attribution and the explicit counterexample, rather than being silently weakened.

3.1F3F5step 2.1algebra∎

By [F5], the reported choice of $α$ requires $∥ A - p J ∥ \leq (2 + ε) \sqrt{n p}$ . For every fixed $0 < ε < g / 2$ , the event in [F3] instead gives $∥ A - p J ∥ \geq (2 + g / 2) \sqrt{n p} > (2 + ε) \sqrt{n p}$ . Thus the probability of the reported adjacency-expander predicate tends to zero for this law. This identifies the constant-two choices excluded by the counterexample without claiming that every positive $ε$ is excluded.

Source notes

This is a local authoring correction with explicit independent source support for its counterexample. The fixed-law source remains correctly bounded to its original hypotheses. No conclusion about the article synchronization theorems follows from this spectral counterexample: those statements and their other arguments remain separate obligations. The article-report concern remains a lead for the independent final original-PDF assessor.

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. 31, Section 6, equation (6.1) and the following p=gamma log n/n paragraph; p. 6 for centering