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

Expected-norm estimate from the corrected moment comparison

PDF p. 34: Proof of Proposition 6.3, final displays

Statement

Assume the Axiom of Choice. Let $n \geq 1$ and $ℓ \geq 1$ be integers and $p \in [0, 1]$ . Let $A$ be the adjacency matrix of the loop-free Erdős–Rényi graph on $n$ vertices: distinct unordered edges occur independently with probability $p$ . Put $Δ_{A} = A - p J$ , where $J$ is the all-ones matrix, and use the Euclidean operator norm. Set $q = 2 p (1 - p)$ . Then

$E ∥ Δ_{A} ∥ \leq p + q^{1 / (2 ℓ)} (2 \sqrt{n} + 2 \sqrt{2 ℓ}) e^{\log n / (2 ℓ)} .$

For $α > 0$ and real $x \geq 3$ , define $f (α, x) = 2 \sqrt{2} e^{1 / (2 α)} (1 + \sqrt{2 α \log x / x})$ . This function is strictly decreasing in $x$ . If $ℓ = α \log n$ is a positive integer, the moment estimate becomes

$E ∥ Δ_{A} ∥ \leq p + q^{1 / (2 ℓ)} 2 \sqrt{n} e^{1 / (2 α)} (1 + \sqrt{2 α \log n / n}) .$

The article’s stronger displayed estimate is $E ∥ Δ_{A} ∥ \leq \sqrt{q} (2 \sqrt{n} + 2 \sqrt{2 ℓ}) e^{\log n / (2 ℓ)}$ ; it does not hold uniformly for $p \in (0, 1)$ . In particular, the substitution $ℓ = α \log n$ is available to the integer-moment argument only when that quantity is an integer.

Statement references

Centered graph matrices and reference degree

Loewner order, Hermitian inner product, and operator norm

Independent-copy symmetrization matrix

Gaussian comparison matrix in the moment argument

Facts & Assumptions

[F1]

For an independent copy $A^{'}$ , put $W = A - A^{'}$ . Corrected symmetrization gives $E ∥ Δ_{A} ∥ \leq p + E ∥ W ∥$ and $E ∥ W ∥ \leq (E Tr W^{2 ℓ})^{1 / (2 ℓ)}$ . Here $Tr$ is the sum of diagonal entries. Symmetrization and moments of the adjacency difference

[F2]

If $G$ is symmetric with independent standard normal entries on and above the diagonal, reflected below it, the corrected comparison is $E Tr W^{2 ℓ} \leq q E Tr G^{2 ℓ}$ . Trace-moment comparison with Gaussian matrices, Gaussian comparison matrix in the moment argument

[F3]

For that same Gaussian convention, $(E Tr G^{2 ℓ})^{1 / (2 ℓ)} \leq n^{1 / (2 ℓ)} (2 \sqrt{n} + 2 \sqrt{2 ℓ})$ . The Gaussian construction assumes Choice. Gaussian trace/norm estimate attributed to Slepian comparison, The Axiom of Choice

[F4]

The derivative of $\log x$ is $1 / x$ on $(0, \infty)$ , and the mean-value theorem gives strict decrease on an interval when the derivative is everywhere negative. The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t, Mean value theorem on a closed real interval

[F5]

If real functions $u, v$ are differentiable at $x$ and $v (x) \neq 0$ , then $(u / v)^{'} (x) = (u^{'} (x) v (x) - u (x) v^{'} (x)) / v (x)^{2}$ . Sums, scalar multiples, products and quotients: (f+g)'(c) = f'(c) + g'(c), (α f)'(c) = α f'(c), (fg)'(c) = f'(c)g(c) + f(c)g'(c), and (f/g)'(c) = (f'(c)g(c) - f(c)g'(c))/g(c)² when g(c) ≠ 0

[F6]

For $t \geq 0$ , $\log (1 + t) \geq 2 t / (2 + t)$ , with equality precisely at $t = 0$ (Angular order and elementary inverse-trigonometric bounds).

Proof

Given: The parameters, graph and Choice assumption in the Statement.

Goal: Prove the corrected estimate, the coefficient’s monotonicity, and the failure of the stronger displayed estimate.

1.1F1F2F3givenalgebra

Apply [F1] and [F2], then take nonnegative $2 ℓ$ -th roots and use [F3]. This yields $E ∥ Δ_{A} ∥ \leq p + q^{1 / (2 ℓ)} n^{1 / (2 ℓ)} (2 \sqrt{n} + 2 \sqrt{2 ℓ})$ . Since $n^{1 / (2 ℓ)} = e^{\log n / (2 ℓ)}$ , this is the first estimate, including $q = 0$ .

1.2F4F5F6givenalgebra

The identity function has derivative one by its difference quotient. Apply the quotient rule [F5] to $u (x) = \log x$ and $v (x) = x$ on $(0, \infty)$ : [F4] supplies $u^{'} (x) = 1 / x$ , and $v (x) > 0$ . The strict equality case in [F6], applied at $t = 2 > 0$ , gives $\log 3 > 1$ . The positive logarithm derivative in [F4] and its mean-value theorem give $\log x \geq \log 3 > 1$ for $x \geq 3$ . Thus the derivative of $\log x / x$ is $(1 - \log x) / x^{2} < 0$ there. By [F4], $\log x / x$ is strictly decreasing on $[3, \infty)$ . The square-root function is strictly increasing on positive arguments: if $0 < a < b$ and $\sqrt{a} \geq \sqrt{b}$ , squaring would contradict $a < b$ . The remaining factors in $f$ are positive and independent of $x$ , so $f (α, x)$ strictly decreases on $[3, \infty)$ .

2.1step 1.1givenalgebra

When $ℓ = α \log n$ , substitute this equality into step 1.1 and use $2 \sqrt{n} + 2 \sqrt{2 ℓ} = 2 \sqrt{n} (1 + \sqrt{2 ℓ / n})$ . This gives the stated specialized estimate with factor $2 \sqrt{n}$ . The moment comparison requires integer $ℓ$ , so the substitution has that stated restriction.

3.1givenalgebra∎

For fixed $n \geq 2$ and integer $ℓ \geq 1$ , every diagonal entry of $Δ_{A}$ is $- p$ ; applying it to a standard unit vector gives $∥ Δ_{A} ∥ \geq p$ . As $p ↑ 1$ , the article’s proposed right-hand side $\sqrt{2 p (1 - p)} (2 \sqrt{n} + 2 \sqrt{2 ℓ}) e^{\log n / (2 ℓ)}$ tends to zero, while $E ∥ Δ_{A} ∥ \geq p \to 1$ . Therefore the proposed inequality fails for all sufficiently large $p < 1$ , for every fixed $n$ and $ℓ$ in this range.

Source notes

The original article displays the stronger estimate and the coefficient $f$ at PDF p. 34. Its moment comparison uses $q^{ℓ}$ where the completed comparison supplies $q$ , and its symmetrization omits the $p$ term. The article citation is attribution only. The completed suppliers, rather than that display, provide the premises used above.

Depends on

Used by · 2

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 pp. 33–34, Proposition 6.3 and final displays of its proof