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.

Uniform centered normalization across the full Bernoulli density range

Statement

Fix $g > 0$ . Let $n \geq 1$ be an integer and $0 < p \leq 1$ , $μ = n p \geq g \log n$ , and let $A$ be the zero-diagonal adjacency matrix of $G (n, p)$ . Put $H = (A - p (J - I)) / \sqrt{μ}$ and $q = \min {\sqrt{μ}, n^{1 / 10}}$ . For all sufficiently large $n$ , uniformly in this range of $p$ , $H$ is real symmetric with independent centered upper entries and zero diagonal, and $\max_{i} \sum_{j} E ∣ H_{i j} ∣^{2} \leq 1, \max_{i j} E ∣ H_{i j} ∣^{2} \leq 1 / n, \max_{i j} ∣ H_{i j} ∣ \leq 1 / \sqrt{μ} \leq 1 / q .$ Moreover $1 \leq q \leq n^{1 / 10}$ , $q \geq \sqrt{g \log n}$ eventually, and $A - p J = \sqrt{μ} H - p I$ .

For this $H$ , let $[n] = {1, \dots, n}$ and let $B$ be the complex endomorphism of $C^{[n]^{2}}$ whose rows and columns are indexed by all ordered pairs in $[n]^{2} = [n] \times [n]$ , including $(i, i)$ , with entries $B_{(i, j), (k, l)} = H_{k l} 1_{j = k} 1_{i \neq l}$ . Define $ρ (B) = \max {∣ z ∣ : z \in C is an eigenvalue of B}$ . This maximum exists for every $n \geq 1$ .

Facts & Assumptions

[F1]

The graph has independent Bernoulli edge coordinates and zero diagonal (Erdős–Rényi random graph and high probability); the reference centering is $A - p J$ (Centered graph matrices and reference degree).

[F2]

The Euclidean operator norm is The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖. For each $a > 0$ , $\log n / n^{a} \to 0$ (The logarithm grows more slowly than every positive real power).

[F3]

For $x > 0$ , the integral logarithm satisfies $L (x) = \log x$ (The integral logarithm L is the published natural logarithm) and is strictly increasing (The integral logarithm is continuous and strictly increasing on (0,∞)). For every real $M$ there is $b > 0$ with $L (b) > M$ (The integral logarithm is unbounded above and below). The natural numbers are cofinal in the reals (The Cauchy-sequence reals are Archimedean).

[F4]

A Cartesian product consists of all ordered pairs of elements from its two factors (The Cartesian product A × B := { z ∈ P(P(A ∪ B)) : ∃ a ∈ A ∃ b ∈ B z = (a,b) }). Over any field, the coordinate space $F^{m}$ , indexed from $0$ to $m - 1$ , has the standard basis and dimension $m$ (The standard list e : n → Fⁿ with eᵢ(i) = 1_F and eᵢ(j) = 0_F for j ≠ i is an ordered basis of Fⁿ; hence dim_F Fⁿ = n, and F⁰ is the zero space with basis ∅ and dimension 0). The spectrum consists of the scalars admitting a nonzero eigenvector (Eigenvalues, eigenvectors, eigenspaces E_λ(T)=ker(T-λ I), and the spectrum σ_F(T) of an endomorphism). The field $C$ is algebraically closed (The complex numbers are algebraically closed); every endomorphism of a nonzero finite-dimensional space over such a field has an eigenvalue (Every endomorphism of a nonzero finite-dimensional vector space over an algebraically closed field has an eigenvalue), and an endomorphism of dimension $m$ has at most $m$ distinct eigenvalues (An endomorphism of an n-dimensional space has at most n distinct eigenvalues).

[F5]

For $z = a + b i \in C$ , its modulus is the nonnegative real number $∣ z ∣ = \sqrt{a^{2} + b^{2}}$ (Real and imaginary parts, complex conjugation, and modulus). A nonempty finite set of real numbers has a maximum (Every nonempty finite set of reals has a maximum and a minimum).

[F6]

On the finite graph probability space, $E [X] = \sum_{ω \in Ω} X (ω) w (ω)$ for a real random variable $X$ (Expectation of a real random variable on a finite probability space); its mean is $E [X]$ , and centered means this is zero. Also $Var (X) = E [(X - E [X])^{2}]$ (Variance, standard deviation, and covariance on a finite probability space).

Proof

Given: The objects and hypotheses in the Statement.

Goal: Prove all stated conclusions.

1.1F1F6givenalgebra

By [F1], the graph outcomes form a finite probability space, and for $i \neq j$ the entry $H_{i j}$ takes values $(1 - p) / \sqrt{μ}$ and $- p / \sqrt{μ}$ with probabilities $p$ and $1 - p$ . Grouping the finite sum in [F6] by the two edge outcomes gives $E [H_{i j}] = (p (1 - p) - (1 - p) p) / \sqrt{μ} = 0$ and $E ∣ H_{i j} ∣^{2} = (p (1 - p)^{2} + (1 - p) p^{2}) / μ = p (1 - p) / μ = (1 - p) / n \leq 1 / n$ . By [F6] this second moment is also the variance. Each value has absolute value at most $1 / \sqrt{μ}$ , and the row second-moment sum is $(n - 1) (1 - p) / n \leq 1$ . Symmetry and independence follow from [F1], since each upper entry is a function of its own independent edge coordinate. The zero diagonal entries are deterministic centered variables and are independent of the others. The centering identity follows entry by entry, including the diagonal.

1.2F3givenchoosealgebra

Fix any $M \in R$ . By [F3], choose $b > 0$ with $L (b) > M$ and an integer $N > b$ . For every integer $n \geq N$ , monotonicity and agreement give $\log n = L (n) \geq L (N) > L (b) > M$ . Therefore $\log n \to + \infty$ , so $g \log n \geq 1$ eventually.

1.3F4givenalgebra

The pairs in $[n]^{2}$ are put in bijection with ${0, \dots, n^{2} - 1}$ by $(i, j) \mapsto (i - 1) n + (j - 1)$ , listing successive blocks of $n$ coordinates. Thus [F4] identifies $C^{[n]^{2}}$ with a coordinate space of dimension $n^{2} > 0$ . The displayed entries define the action $(B v)_{i j} = \sum_{k = 1}^{n} \sum_{l = 1}^{n} H_{k l} 1_{j = k} 1_{i \neq l} v_{k l}$ . These are finite sums of complex scalar multiples of coordinates; distributivity gives $B (α v + β w) = α B v + β B w$ . Hence $B$ is an endomorphism of that nonzero finite-dimensional complex space.

2.1F2step 1.1step 1.2givenalgebra

By [F2] with $a = 1 / 5$ , $g \log n \leq n^{1 / 5}$ eventually. Together with $μ \geq g \log n$ and step 1.2, this shows that both terms in the minimum defining $q$ are eventually at least $\sqrt{g \log n} \geq 1$ . Thus $1 \leq q \leq n^{1 / 10}$ and $q \geq \sqrt{g \log n}$ , while $q \leq \sqrt{μ}$ implies $1 / \sqrt{μ} \leq 1 / q$ . All cutoffs depend only on $g$ , so the estimates in step 1.1 hold uniformly in $p$ , including $p = 1$ , where $H = 0$ .

3.1F4F5step 1.1step 2.1step 1.3algebra∎

By [F4] and step 1.3, $B$ has at least one and at most $n^{2}$ distinct complex eigenvalues. Their moduli therefore form a nonempty finite subset of $R$ , which has a maximum by [F5]. This proves that $ρ (B)$ is well defined for each realization and every $n \geq 1$ , including $H = 0$ , when $B = 0$ and its only eigenvalue is $0$ . Combining this with steps 1.1 and 2.1 proves every conclusion.

Depends on

Used by · 3

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.