Keyboard shortcuts

Press ← or → to navigate between chapters

Press ? to show this help

Press Esc to hide this help

Tree endpoint moment certificates

Abstract

Actual rooted finite tree recurrence states and every-order positive Jacobi rigidity.

The coefficient field is arbitrary where stated. Algebraic pairing needs only a field; positivity and the tree norm statements use a linearly ordered field. All vertices and the selected port belong to the same actual finite graph. No spectral, positivity, cyclicity, contraction or oracle premise is added to that graph.

Definition 1.1 (The original spectral coordinate).

Formalization. D5/S3/Combinatorics/SpectralGraph/TreeEndpointMomentCertificates.affinePolynomial (✓ std3).

Source. Repository-derived.

Commentary.

Here X denotes the polynomial indeterminate and scalars denote constant polynomials. The formula is c inverse times (X minus a).

Definition 1.2 (The fixed chain polynomials).

Formalization. D5/S3/Combinatorics/SpectralGraph/TreeEndpointMomentCertificates.chainPolynomial (✓ std3).

Source. Repository-derived.

Commentary.

Mathlib Chebyshev.S has S minus one equal to zero, S zero equal to one, and S at j plus one equal to X times S at j minus S at j minus one. Thus this is precisely the original Q recurrence composed with (z-a)/c; no polynomial is fitted to the observed graph.

Definition 1.3 (Evaluation at the actual matrix).

Formalization. D5/S3/Combinatorics/SpectralGraph/TreeEndpointMomentCertificates.polynomialVector (✓ std3).

Source. Repository-derived.

Commentary.

Polynomial evaluation is in the matrix algebra; the resulting matrix acts on the selected unit coordinate.

Definition 1.4 (Chain states).

Formalization. D5/S3/Combinatorics/SpectralGraph/TreeEndpointMomentCertificates.chainVector (✓ std3).

Source. Repository-derived.

Commentary.

The index is a natural number, beginning with the actual selected unit vector.

Definition 1.5 (All positive symmetric Jacobi matrices).

Formalization. D5/S3/Combinatorics/SpectralGraph/TreeEndpointMomentCertificates.PositiveJacobi (✓ std3).

Source. Repository-derived.

Commentary.

Every natural order is allowed. The matrix is symmetric, entries farther than one from the diagonal vanish, and every existing adjacent link is strictly positive. The diagonals are unrestricted. The positive-order hypothesis is supplied only where an endpoint vector is needed.

Definition 1.6 (Absent coordinates mean zero).

Formalization. D5/S3/Combinatorics/SpectralGraph/TreeEndpointMomentCertificates.unitAt (✓ std3).

Source. Repository-derived.

Commentary.

The zero extension lets the rigidity proof treat short, exact and larger matrix orders in the same recurrence.

Definition 1.7 (Zero-extended diagonals).

Formalization. D5/S3/Combinatorics/SpectralGraph/TreeEndpointMomentCertificates.diagonalAt (✓ std3).

Source. Repository-derived.

Commentary.

The displayed entry uses its natural-number index only in the branch where that index is in range.

Definition 1.8 (Zero-extended links).

Formalization. D5/S3/Combinatorics/SpectralGraph/TreeEndpointMomentCertificates.nextLink (✓ std3).

Source. Repository-derived.

Commentary.

There is no fictitious terminal link: the value is zero when its second endpoint is absent.

Definition 1.9 (A locally saturated actual stem).

Formalization. D5/S3/Combinatorics/SpectralGraph/TreeEndpointMomentCertificates.IsStem (✓ std3).

Source. Repository-derived.

Commentary.

At every proper stem vertex, all actual neighbors are exactly the preceding vertex when present and the following vertex. This predicate alone does not assert existence; the tree theorem earns a simple path satisfying it.

Definition 1.10 (The actual terminal boundary).

Formalization. D5/S3/Combinatorics/SpectralGraph/TreeEndpointMomentCertificates.forward (✓ std3).

Source. Repository-derived.

Commentary.

Only the incoming edge is removed. A zero-length stem removes no edge, so its forward boundary is the actual root’s entire neighbor set.

Definition 1.11 (Rooted endpoint paths).

Formalization. D5/S3/Combinatorics/SpectralGraph/TreeEndpointMomentCertificates.EndpointPath (✓ std3).

Source. Repository-derived.

Commentary.

A genuine graph isomorphism to a nonempty finite path sends the actual selected port to zero. This includes a singleton and excludes an interior port on a nontrivial path.

Definition 1.12 (The same actual graph law).

Formalization. D5/S3/Combinatorics/SpectralGraph/TreeEndpointMomentCertificates.uniformMatrix (✓ std3).

Source. Repository-derived.

Commentary.

The adjacency matrix has unit edges and zero diagonal. The shift a is arbitrary, including zero and negative values.

Definition 1.13 (Squared recurrence norms).

Formalization. D5/S3/Combinatorics/SpectralGraph/TreeEndpointMomentCertificates.chainNorm (✓ std3).

Source. Repository-derived.

Commentary.

Over the rationals this dot product is the exact sum of squares defining the squared Euclidean length; no square-root normalization is used.

Definition 1.14 (Actual boundary indicators).

Formalization. D5/S3/Combinatorics/SpectralGraph/TreeEndpointMomentCertificates.indicatorVector (✓ std3).

Source. Repository-derived.

Commentary.

The value is one exactly on the given finite set of actual vertices.

Theorem 1.15 (Moments determine the needed Gram entries).

Proof. Machine-checked in Lean as D5/S3/Combinatorics/SpectralGraph/TreeEndpointMomentCertificates.prefix_chain_pairing (✓ std3). ∎

Source. Repository-derived.

Commentary.

Expand matrix polynomial evaluation and use symmetry to identify the pairing of powers i and j with moment i+j. The degrees of the fixed chain polynomials are at most their indices. Equal moments through d therefore transfer every pairing with i+j at most d. This helper is consumed by the endpoint classification’s prefix-rigidity step.

Theorem 1.16 (Moments determine the needed diagonal pairings).

Proof. Machine-checked in Lean as D5/S3/Combinatorics/SpectralGraph/TreeEndpointMomentCertificates.prefix_chain_diagonal (✓ std3). ∎

Source. Repository-derived.

Commentary.

Apply the same polynomial pairing to p_j and X p_j. The total degree is at most 2j+1. This helper is consumed by the same prefix-rigidity step.

Theorem 1.17 (Rigidity without an order bound).

Proof. Machine-checked in Lean as D5/S3/Combinatorics/SpectralGraph/TreeEndpointMomentCertificates.positive_jacobi_prefix_rigidity (✓ std3). ∎

Source. Repository-derived.

Commentary.

Inductively the required unit state forces the next coordinate to exist. Its positive coefficient divided by positive c has square one, hence equals one. The diagonal pairing fixes the next diagonal. Applying the recurrence once more gives the displayed last-link norm, with zero for an exact terminating order. This proves the order bound, all earlier coefficients, and the short, exact and larger-order alternatives over the reals as well as the rationals. No normalized representation or supplied stem is assumed. The classification consumes this result to exclude all rational competitor orders and to force the positive matrix.

Theorem 1.18 (Earn the first departure on the actual tree).

Proof. Machine-checked in Lean as D5/S3/Combinatorics/SpectralGraph/TreeEndpointMomentCertificates.tree_first_departure (✓ std3). ∎

Source. Repository-derived.

Commentary.

Choose a maximal simple locally saturated rooted stem among the finitely bounded possible lengths. Acyclicity keeps every forward neighbor off that stem. A single forward neighbor would extend it, so maximality excludes boundary size one. The degree bound leaves only zero, two or three; a positive-length stem has at most two forward neighbors. The actual recurrence states are exactly its distinct coordinate vectors, followed by its actual boundary indicator. Thus all earlier norms are one and the next norm is zero, two or three. If the boundary is empty, connectivity exhausts every actual vertex; the path-to-subgraph isomorphism becomes a genuine rooted isomorphism of the whole graph. The theorem supplies, rather than assumes, every stem, Gram and diagonal premise used by the classification.

References