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.

Numerical coefficients and thresholds — Remark 6.4

PDF p. 34: Remark 6.4

Statement

Assume the Axiom of Choice. For $α > 0$ and $x \geq 3$ , define $f (α, x) = 2 \sqrt{2} e^{1 / (2 α)} (1 + \sqrt{2 α \log x / x})$ , with natural logarithm and positive square roots. Then $f (2, 4) < 7.91$ , $f (3, 120) < 4.98$ , $f (5, 880) < 3.994$ , and $f (25, 450000) < 2.996$ . For each fixed $α$ , the function decreases in $x \geq 3$ .

The article proposes the thresholds $n_{0} (8) = 4$ , $n_{0} (5) = 120$ , $n_{0} (4) = 880$ , and $n_{0} (3) = 450000$ for Proposition 6.3. That proposition asserts that, for every $C > 2 \sqrt{2}$ , the estimate $E ∥ Δ_{A} ∥ \leq C \sqrt{n p (1 - p)}$ holds for all $n \geq n_{0} (C)$ and every $p \in (0, 1)$ . The uniform assertion fails for each of these constants at arbitrarily large $n$ . Here $G (n, p)$ is the loop-free random graph with independent edges of probability $p$ , $A$ is its adjacency matrix, $J$ is the all-ones matrix, $Δ_{A} = A - p J$ , and the norm is the Euclidean operator norm.

The article also states that the lost factor $\sqrt{2}$ is inevitable if symmetrization is used. For independent Bernoulli- $p$ variables $X, X^{'}$ , the difference $X - X^{'}$ has variance $2 p (1 - p)$ , twice the variance of $X - p$ . Thus a factor $\sqrt{2}$ occurs at the standard-deviation level in this independent-copy operation when $0 < p < 1$ . This calculation does not establish the broader inevitability claim for every symmetrization or norm estimate.

Statement references

Expected-norm estimate from the corrected moment comparison

Expected centered-adjacency norm — Proposition 6.3

Norm symmetrization at the actual matrix mean

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

Centered graph matrices and reference degree

Loewner order, Hermitian inner product, and operator norm

The Axiom of Choice

Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials

Pairwise and mutual independence of finite-valued random variables

Variance, standard deviation, and covariance on a finite probability space

Facts & Assumptions

[F1]

Under Choice, the corrected moment estimate defines the displayed $f$ and proves its strict decrease for $x \geq 3$ . Its moment argument requires an integer moment parameter (Expected-norm estimate from the corrected moment comparison, The Axiom of Choice).

[F2]

For the stated loop-free graph and centering, Proposition 6.3's original uniform-in- $p$ assertion fails for arbitrarily large $n$ . The graph has zero adjacency diagonal, and the operator norm is the supremum of $∥ Δ_{A} v ∥_{2}$ over Euclidean unit vectors $v$ (Expected centered-adjacency norm — Proposition 6.3, Erdős–Rényi random graph and high probability, Centered graph matrices and reference degree, Loewner order, Hermitian inner product, and operator norm).

[F3]

For $∣ u ∣ \leq 1 / 2$ , the exponential series through degree $12$ has absolute remainder at most $∣ u ∣^{13} / (13! (1 - ∣ u ∣ / 14))$ . For $1 \leq y \leq 2$ , the logarithm series through index $10$ , with $v = (y - 1) / (y + 1)$ , has absolute remainder at most $2 ∣ v ∣^{23} / (23 (1 - v^{2}))$ ; also $\log (2^{j} y) = j \log 2 + \log y$ . Rational interval operations preserve enclosure (Range-reduced exponential, logarithm and arctangent series have certified tails, Finite real interval operations enclose their exact values).

[F4]

Independent-copy norm symmetrization compares a matrix to an independent copy at its actual mean (Norm symmetrization at the actual matrix mean). Bernoulli- $p$ variables take values $1$ and $0$ with probabilities $p$ and $1 - p$ (Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials). Independence makes the joint probabilities of two finite-valued copies products of their marginal probabilities (Pairwise and mutual independence of finite-valued random variables). Variance is the expectation of the squared centered variable, and standard deviation is its nonnegative square root (Variance, standard deviation, and covariance on a finite probability space).

Proof

Given: The function and graph conventions in the Statement.

Goal: Certify the numerical comparisons, identify the status of the proposed thresholds, and calculate the independent-copy variance factor.

1.1F3givenalgebra

Apply [F3] with logarithm index $10$ , reducing each $n$ as $n = 2^{j} y$ with $j = 2, 6, 9, 18$ respectively and $1 \leq y < 2$ . Exact rational evaluation of upper endpoints gives $\log 4 < 1.386295$ , $\log 120 < 4.787492$ , $\log 880 < 6.779922$ , and $\log 450000 < 13.017003$ . Applying the exponential enclosure with $u = 1 / 4, 1 / 6, 1 / 10, 1 / 50$ gives respective upper bounds $1.284026, 1.181361, 1.105171, 1.020202$ . All displayed decimals in this step and the next are exact rationals.

1.2givenF1F2choosealgebra

For any of the four constants $C$ and any integer $n \geq 2$ , choose $p = 1 - 1 / (16 C^{2} n)$ . Then $p \in (0, 1)$ and $p > 1 / 2$ . By [F2], the diagonal of $Δ_{A}$ is $- p$ , so applying it to a coordinate unit vector gives $∥ Δ_{A} ∥ \geq p$ for every outcome. Consequently $E ∥ Δ_{A} ∥ > 1 / 2$ , whereas $C \sqrt{n p (1 - p)} = \sqrt{p} / 4 < 1 / 4$ . The proposed uniform bound therefore fails at arbitrarily large $n$ , independently of the proposed cutoff. The corrected moment estimate in [F1] does not supply the refuted uniform estimate.

2.1step 1.1F1F3algebra

Squaring positive rational endpoints and using step 1.1 gives respective upper bounds $1.177411, 0.489260, 0.277570, 0.038031$ for $\sqrt{2 α \log n / n}$ at the four indicated pairs. Also $\sqrt{2} < 1.414214$ . Substitution into $f$ , with outward rational arithmetic, gives upper bounds $7.907868, 4.976206, 3.993552, 2.995309$ , respectively; each is strictly below the corresponding bound in the Statement. Monotonicity follows from [F1].

3.1F4algebra∎

By independence in [F4], $P (X - X^{'} = 1) = P (X - X^{'} = - 1) = p (1 - p)$ , with the remaining probability at zero. Hence its mean is zero and its variance is $2 p (1 - p)$ . The centered Bernoulli variable $X - p$ has mean zero and variance $p (1 - p)$ by direct calculation. Taking square roots gives the stated standard-deviation ratio when $0 < p < 1$ ; at $p = 0, 1$ both variances vanish.

Source notes

Remark 6.4 gives the four numerical comparisons and proposed cutoffs. The next paragraph states that the lost factor $\sqrt{2}$ is inevitable if symmetrization is used. The article citation provides attribution only. The counterexample concerns the original uniform expected-norm assertion under its stated centering, and the variance calculation describes the particular independent-copy operation.

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. 34, Remark 6.4 and immediately following paragraph; PDF p. 33, Proposition 6.3