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.

Extracting a nonconstant eigenvalue from closed-walk moments

Statement

Fix an integer $d \geq 2$ . Let $A_{n}$ be finite $d$ -regular adjacency-slot matrices of orders $n \to \infty$ : each $A_{n}$ is a symmetric nonnegative integer matrix with row sum $d$ , and diagonal entries count loop slots. Set $Λ_{n} = ∥ A_{n} - (d / n) J ∥_{o p}$ , where $J$ has all entries one and the norm is Euclidean. For every fixed integer $k \geq 1$ and all $n \geq 2$ ,

$Λ_{n}^{2 k} \geq \frac{n C_{k} (d - 1)^{k} - d^{2 k}}{n - 1} .$

Here $C_{k}$ is the number of Dyck words of length $2 k$ , namely words with $k$ symbols $+ 1$ and $k$ symbols $- 1$ whose every initial partial sum is nonnegative. In particular, for every $ε > 0$ , eventually $Λ_{n} \geq C_{k}^{1 / (2 k)} \sqrt{d - 1} - ε$ , with $d, k$ held fixed as the order grows.

Statement references

Regular multigraph and normalized adjacency

Dyck words and elementary Catalan growth

Regular adjacency spectra and normalized expansion

Asymptotic quantifiers and uniform parameter ranges

Facts & Assumptions

Given: The objects and hypotheses in the statement.

Goal: Establish every assertion in the statement.

[F1]

The trace of $A_{n}^{2 k}$ counts closed labelled slot walks (Matrix powers count closed labelled slot walks).

[F2]

At each starting vertex their number is at least $C_{k} (d - 1)^{k}$ , including loops and parallel slots (Stack construction of closed walks with loops and repeated edges).

[F3]

A regular symmetric matrix has an orthonormal eigenbasis with first eigenvalue $d$ at the constant vector, and the remaining eigenvalues $λ_{2}, \dots, λ_{n}$ satisfy $\max_{i \geq 2} ∣ λ_{i} ∣ = Λ_{n}$ (Regular adjacency spectra and normalized expansion).

[F4]

A conclusion holds eventually if it holds beyond a single order cutoff along the sequence under consideration (Asymptotic quantifiers and uniform parameter ranges).

[F5]

In the adjacency-slot convention, $A_{n}$ is symmetric with nonnegative integer entries and row sum $d$ ; diagonal entries count loop slots (Regular multigraph and normalized adjacency).

[F6]

Such a matrix admits directed slot labels with an endpoint-reversing involution, possibly fixing loop labels, and exactly $(A_{n})_{x y}$ labels from $x$ to $y$ . Labelled walks are composable lists of these labels and are closed when their endpoints agree (Reversible labels for adjacency slots).

[F7]

The Dyck-word count satisfies $C_{k} = (\binom{2 k}{k}) / (k + 1) \geq 4^{k} / ((2 k + 1) (k + 1)) > 0$ for $k \geq 1$ (Dyck words and elementary Catalan growth).

Proof

1.1F1F2F3F5F6choosealgebra

By [F5] and [F6], choose reversible slot labels for $A_{n}$ ; these satisfy the hypotheses of [F1] and [F2]. Hence $tr (A_{n}^{2 k}) \geq n C_{k} (d - 1)^{k}$ . By [F3], write $A_{n} = Q diag (d, λ_{2}, \dots, λ_{n}) Q^{⊤}$ with $Q$ orthogonal. Expanding diagonal entries and using $\sum_{x} Q_{x i}^{2} = 1$ gives $tr (A_{n}^{2 k}) = d^{2 k} + \sum_{i = 2}^{n} λ_{i}^{2 k} \leq d^{2 k} + (n - 1) Λ_{n}^{2 k}$ . Rearranging proves the finite-order inequality, even if its right side is negative.

2.1F3F4F7step 1.1algebra∎

By [F7] and $d \geq 2$ , put $a = C_{k}^{1 / (2 k)} \sqrt{d - 1} > 0$ and hold $d, k$ fixed. The right side of the inequality is $a^{2 k} + (a^{2 k} - d^{2 k}) / (n - 1)$ and tends to $a^{2 k}$ . If $0 < ε < a$ , then $a^{2 k} - (a - ε)^{2 k} > 0$ , so beyond a cutoff that right side exceeds $(a - ε)^{2 k}$ . Since $Λ_{n} \geq 0$ , step 1.1 gives $Λ_{n} > a - ε$ . If $ε \geq a$ , the same desired weak inequality follows from nonnegativity. This proves the eventual assertion.

Depends on

Used by · 1

The fixed-degree Alon–Boppana lower bound

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.