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

A nonbacktracking tail smaller than the required polynomial

Statement

Fix $γ > 1$ . With $H$ and $B$ as in the normalization and ordered-pair definitions, for every sufficiently large $n$ , $P (ρ (B) \geq 2) \leq n^{- γ} .$ The size cutoff may depend on $γ$ and on the universal constants in the external theorem.

Facts & Assumptions

[F1]

The normalized matrix $H$ is real symmetric, hence Hermitian, with independent mean-zero upper-triangular entries. It has row variance at most 1, entry variance at most $1 / n$ , entry bound $1 / q$ , and eventually $1 \leq q = \sqrt{γ \log n} \leq n^{1 / 10}$ (Normalize the logarithmic random graph for nonbacktracking estimates).

[F2]

Under independent mean-zero Hermitian upper entries with row variance sum at most 1, entry variance at most $κ / n$ , and entry bound $1 / q$ , Theorem 2.5 gives universal $C, c > 0$ with $P (ρ (B) \geq 1 + t) \leq C n^{3 - c q \log (1 + t)}$ for $1 \lor q \leq n^{1 / 10} κ^{- 1 / 9}$ and $t \geq 0$ ..

[F3]

The natural logarithm is strictly increasing on $(0, \infty)$ , is onto $R$ , and satisfies $\log 1 = 0$ (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).

[F4]

The logarithm is inverse to the exponential (The natural logarithm as the inverse of the exponential function).

External input

For a matrix $H$ , its nonbacktracking matrix $B$ is indexed by ordered vertex pairs and has $B_{(i, j), (k, l)} = H_{k l} 1_{j = k} 1_{i \neq l}$ . Write $ρ (B) = \max {∣ z ∣ : z is an eigenvalue of B}$ . Under independent mean-zero Hermitian upper entries with row variance sum at most 1, entry variance at most $κ / n$ , and entry bound $1 / q$ , Theorem 2.5 gives universal $C, c > 0$ with $P (ρ (B) \geq 1 + t) \leq C n^{3 - c q \log (1 + t)}$ for $1 \lor q \leq n^{1 / 10} κ^{- 1 / 9}$ and $t \geq 0$ .

Proof

Given: The objects and hypotheses in the Statement.

Goal: Prove its conclusions.

1.1F1F2given

Apply [F2] to [F1] with $κ = 1$ and $t = 1$ . This gives $P (ρ (B) \geq 2) \leq C n^{3 - c \sqrt{γ \log n} \log 2}$ . All normalization and independence hypotheses are precisely those in [F1].

2.1F3step 1.1algebra∎

By [F3], $\log 2 > \log 1 = 0$ . For each real $M$ , surjectivity gives $x > 0$ with $\log x > M$ , and monotonicity gives $\log n \geq \log x > M$ for every integer $n \geq x$ . Hence $\log n \to \infty$ . Since $c > 0$ and $γ > 1$ are fixed, eventually $c \sqrt{γ \log n} \log 2 \geq γ + 4$ and $n \geq \max {2, C}$ . Then the right side in step 1.1 is at most $C n^{- γ - 1} \leq n^{- γ}$ .

Depends on

Used by · 1

The restricted spectral estimate needed above the connectivity 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.

External dependencies

Benaych-Georges, Bordenave and Knowles, Spectral radii of sparse random matrices (19 September 2019) · PDF p. 3, Definition 2.1; p. 4, Assumption 2.4 and Theorem 2.5

Under independent mean-zero Hermitian upper entries with row variance sum at most 1, entry variance at most $\kappa/n$, and entry bound $1/q$, Theorem 2.5 gives universal $C,c>0$ with $\mathbb P(\rho(B)\ge1+t)\le Cn^{3-cq\log(1+t)}$ for $1\vee q\le n^{1/10}\kappa^{-1/9}$ and $t\ge0$.

Hypotheses: Hermitian H with independent mean-zero upper entries; q>0, kappa>=1 and all three bounds in Assumption 2.4; 1 vee q<=n^(1/10) kappa^(-1/9).

Reading limits: Checked the extracted PDF text on pp. 3–4, including Definition 2.1, Theorem 2.2, Assumption 2.4 and Theorem 2.5. The theorem is imported, not locally reconstructed; its proof and the remaining paper were not reviewed for this application.

Sources

Benaych-Georges, Bordenave and Knowles, Spectral radii of sparse random matrices (19 September 2019) · PDF p. 3, Definition 2.1; p. 4, Assumption 2.4 and Theorem 2.5