PropositionStatement: 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 bilinear centered-adjacency estimate without regularity

Statement

Let $V$ be a finite set of $n > 0$ vertices, and let $A = (A_{x y})_{x, y \in V}$ be a complex self-adjoint matrix, meaning $A_{x y} = \overline{A_{y x}}$ . Let $J$ be the matrix whose entries are all $1$ , let $d^{*} > 0$ and $α \geq 0$ , and put $B = A - (d^{*} / n) J$ . Use the vertex norm $∥ f ∥_{2} = (\sum_{x \in V} ∣ f (x) ∣^{2})^{1 / 2}$ and the induced operator norm $∥ B ∥$ . If $∥ B ∥ \leq α d^{*}$ , then for all $f, g \in C^{V}$ ,

$∣ f^{*} B g ∣ \leq α d^{*} ∥ f ∥_{2} ∥ g ∥_{2} .$

For subsets $X, Y \subseteq V$ , define the ordered matrix-entry sum $e (X, Y) = \sum_{x \in X} \sum_{y \in Y} A_{x y}$ . Then

$∣ e (X, Y) - (d^{*} / n) ∣ X ∣ ∣ Y ∣ ∣ \leq α d^{*} \sqrt{∣ X ∣ ∣ Y ∣} .$

For the graph interpretation, let $A$ be the symmetric binary adjacency matrix of a finite undirected graph on $V$ with possible self-loops: $A_{x y} = 1$ exactly when $x$ and $y$ are joined by an edge, including $x = y$ for a loop, and $A_{x y} = 0$ otherwise. Then $e (X, Y)$ counts ordered adjacency entries, including each diagonal entry once. The estimate permits $X$ and $Y$ to overlap and permits loop entries. It does not assert a multiplicative lower bound for every pair of small disjoint sets.

Statement references

Finite symmetric networks and loop removal

Finite vertex Hilbert space in the article convention

The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖

Facts & Assumptions

Given: The set $V$ , matrices $A, J, B$ , parameters $d^{*}, α$ , and vectors and subsets are as in the statement, and $∥ B ∥ \leq α d^{*}$ .

[F1]

The vertex pairing is $⟨ u, v ⟩ = \sum_{x \in V} \overline{u (x)} v (x)$ , and matrix action is $(B v) (x) = \sum_{y \in V} B_{x y} v (y)$ ; its norm is $∥ v ∥_{2}$ (Finite vertex Hilbert space in the article convention).

[F2]

For a linear map on this finite-dimensional inner-product space, the operator norm is the maximum of $∥ B v ∥_{2}$ over unit vectors (The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖).

[F3]

Cauchy–Schwarz gives $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥_{2} ∥ v ∥_{2}$ ; the vertex-space convention transfers the cited linear-first version by conjugation (Cauchy–Schwarz: |⟨ u,v⟩|≤‖ u‖‖ v‖, with equality exactly for linearly dependent vectors, Finite vertex Hilbert space in the article convention).

[F4]

A finite symmetric nonnegative matrix defines a network whose positive off-diagonal entries specify support edges and whose diagonal entries are loop weights (Finite symmetric networks and loop removal). In the binary graph case specified in the statement, an entry equal to $1$ records the corresponding edge or loop.

Proof

Given: The hypotheses and notation of the statement.

Goal: Prove the bilinear estimate and its ordered-entry specialization.

Proof technique: direct.

1.1F1F2

If $g = 0$ , then $B g = 0$ and $∥ B g ∥_{2} \leq ∥ B ∥ ∥ g ∥_{2}$ . Otherwise $g / ∥ g ∥_{2}$ is a unit vector, so the definition of operator norm and homogeneity give $∥ B g ∥_{2} = ∥ g ∥_{2} ∥ B (g / ∥ g ∥_{2}) ∥_{2} \leq ∥ B ∥ ∥ g ∥_{2}$ .

1.2givenF1F4algebra

Let $1_{X}$ and $1_{Y}$ be the indicator functions, equal to $1$ on their respective sets and $0$ elsewhere. Directly summing the entries gives $1_{X}^{*} A 1_{Y} = e (X, Y)$ and $1_{X}^{*} J 1_{Y} = ∣ X ∣ ∣ Y ∣$ ; also $∥ 1_{X} ∥_{2} = \sqrt{∣ X ∣}$ and $∥ 1_{Y} ∥_{2} = \sqrt{∣ Y ∣}$ . These identities include diagonal entries and do not require disjointness. In the binary graph case, each summand $A_{x y}$ is the indicator of the corresponding adjacency entry, and a loop contributes once when its vertex lies in $X \cap Y$ .

2.1givenF1F3step 1.1

The matrix pairing identity gives $f^{*} B g = ⟨ f, B g ⟩$ . Applying Cauchy–Schwarz and step 1.1, then the assumed norm bound, yields $∣ f^{*} B g ∣ \leq ∥ f ∥_{2} ∥ B g ∥_{2} \leq α d^{*} ∥ f ∥_{2} ∥ g ∥_{2}$ .

3.1givenstep 2.1step 1.2algebra∎

Substitute the indicators into step 2.1 and use $B = A - (d^{*} / n) J$ and step 1.2 to obtain the stated ordered-entry bound. No regularity hypothesis was used, and the additive estimate alone makes no asserted multiplicative lower bound for small disjoint sets.

Depends on

Used by · 1

Expansion and the distribution of phases in stable states

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.