--- title: "Linear Jordan-block growth in non-backtracking graphs" date: 2026-09-05 version: "0.1.0-candidate" doi: 10.5281/zenodo.22375005 pdf: https://github.com/ipitchford/linear-nonbacktracking-jordan-growth/releases/download/v0.1.0-candidate/linear-nonbacktracking-jordan-growth-0.1.0-candidate.pdf repository: https://github.com/ipitchford/linear-nonbacktracking-jordan-growth archive: https://zenodo.org/records/22375005 license: CC0-1.0 status: unrefereed (internally replayed; not peer reviewed, not independently reproduced, not formally verified) --- # Linear Jordan-block growth in non-backtracking graphs ## Summary A walk on a network is non-backtracking if it never immediately reverses its last edge. The matrix counting these walks can have Jordan blocks: chains of generalized eigenvectors that are invisible in a list of eigenvalues alone. How large can those blocks become? This unrefereed candidate supplies a constructive answer: their largest possible size grows linearly with the number of graph vertices. The result persists under one fixed maximum-degree bound. It concerns extremal **counting** matrices, not typical networks or normalized random-walk transition matrices. ## Summary for specialists Let $f(n)$ be the maximum complex Jordan-block size of $B_G$ over finite simple undirected $n$-vertex graphs without degree-one vertices, with $(B_G)_{(u,v),(x,y)}=1$ exactly when $v=x$ and $u\ne y$. For every $n\ge3$, $$ \max\left\{1,\left\lfloor\frac{n-1}{131072}\right\rfloor-3\right\} \le f(n)\le2n. $$ Thus $f(n)=\Theta(n)$. If maximum degree is at most $393217$, the lower bound is still $\max\{1,\lfloor n/12714016\rfloor\}$. Long blocks occur at $\lambda=\pm512i$. Lower-bound graphs are connected and have minimum degree two. The constants are not claimed optimal. This addresses AIM Problem 1.3(1), not its separate Alon–Boppana question in part (2). ## Technical account The upper bound uses the quadratic non-backtracking determinant identity and a contraction argument excluding nontrivial unit-modulus Jordan blocks. For the lower bound, a banded nilpotent matrix yields a quadratic pencil whose value at $2i$ has a one-dimensional kernel. A separate determinant-valuation argument forces growing algebraic multiplicity. Nilpotence at one point alone would not justify that conclusion. A four-dimensional rational representation of $\sqrt3$, followed by a fixed integer scaling, produces integer adjacency weights and prescribed degree action. Signed fibers and zero-valued vertices realize both actions in a simple unweighted graph. An incidence intertwiner preserves the chain away from $\pm1$. Padding on zero-valued vertices reaches every larger order; private zero vertices give the fixed maximum-degree strengthening. ## Evidence, assurance and limitations The arbitrary-parameter theorem rests on the written proof. Exact code checks finite pencils, three fully enumerated small graph embeddings, published defective examples, padding and deliberately corrupted inputs. New normal and optimized replays cover even $r=4$ through $12$; a separate historical pencil receipt reaches $r=20$. These are producer-side controls, not universal proof certificates or independent reproduction. The first full shared-zero graph already has **34,314,518,528 edges**. It is represented by an edge-generating rule, not materialized. Internal AI editorial review and the supplied review are not authenticated external specialist review. Formal verification, exhaustive novelty and historical priority remain open. No application benefit, typical-network frequency or optimal constant is claimed. ## Relationship to earlier work Glover and Kempton supply the standard reduced-matrix framework. Heysse, Lorenzen and Reinhart provide defective examples and chain-preserving graph constructions: preserving a fixed chain is not itself a length amplifier. Takata and colleagues construct high-order exceptional points for linear Hamiltonians. The present graph-constrained quadratic pencil needs its own valuation and realization argument. These distinctions identify the mechanism being offered, not a certified historical first. ## Who should care, and why | Audience | Potential use | Required caution | | --- | --- | --- | | Spectral graph theorists | Inspect a proposed resolution of the Jordan-growth question. | The argument remains unrefereed and constants are not claimed optimal. | | Matrix and pencil researchers | Reuse the valuation and signed-fiber construction. | Preserve dimensions, degree constraints and chain-transfer assumptions. | | Research agents and tool builders | Replay exact finite controls and trace dependencies. | A passing implementation is not independent theorem validation. | ## Why the problem matters Undirected adjacency matrices are symmetric and diagonalizable, but counting non-backtracking matrices need not be. The candidate shows that graph structure does not impose a universal small bound on their Jordan complexity. Even bounded maximum degree does not recover the regular-graph bound of two. This is a structural conclusion, not a measured improvement to network algorithms. ## How to inspect or reproduce the recorded checks Download the versioned evidence ZIP, inspect its manifest, and follow its README. With the pinned SymPy and optional performance backend installed, run `python verify_research.py --max-r 12` and `python -O verify_research.py --max-r 12`. Both should report `PASS_PRODUCER_EXACT_CHECKS`. Start with the manuscript's dimension table and source note before interpreting the nullity receipts. Do not enumerate the enormous full-family graph. ## The most valuable next projects The first priority is unaffiliated reconstruction of the all-parameter proof, especially the valuation and degree-action embedding. Further work could reduce the constants, determine exact extremal sizes, or find the smallest degree bound supporting linear growth. Wider prior-art reconciliation and formalization are separate assurance projects. None is supplied by publishing this release. ## What is in the evidence package The package contains the eight-page PDF and Markdown proof, exact construction and verification code, structured claims, a dated AIM source bridge, bounded prior-art audit, review response, historical and new receipts, a complete manifest, provenance and component licences. Original prose and data are CC0; original code is MIT. Third-party source documents and supplied review files are referenced or hashed, not silently relicensed. The archive, public repository and replay routes are linked in the standard resource panel. ## Open directions for follow-up research - Obtain unaffiliated reconstruction of the valuation, encoding and graph lift. - Improve constants and determine exact extremal sizes or the smallest useful degree bound. - Complete broader prior-art and priority assessment. - Investigate formal verification of the arbitrary-parameter argument; AIM part (2) remains separate. ## Research process, metrics and reusable methods This is prospective process metadata under the Evidence Press operating model and research-metrics policy. It records the intended handoff, measured scope and claim boundary; it is not evidence that the method accelerated this work. - Work ID: ep-work:nonbacktracking-jordan-growth - Attempt and metric receipts: ep-attempt:nonbacktracking-jordan-growth-assurance-publication: published / positive; scope assurance-through-publication; target Publish the review-repaired anonymous unrefereed Jordan-growth candidate with exact replay, internal editorial disposition, immutable GitHub and Zenodo assets and canonical Evidence Press readback, or preserve the exact blocking gate.; active forecast 150 minutes (120-210); Fermi components Review repairs and source audit: 1 x 25/30/45 minutes low/central/high (Minor revisions without a supplied mathematical gap.); Deterministic package and five-role editorial gate: 1 x 35/45/60 minutes low/central/high (One frozen submission, existing exact controls.); Immutable archive, reader-first page and media: 1 x 35/45/60 minutes low/central/high (Existing generators and authenticated GitHub and Zenodo.); Two seal, CI, deployment and readback cycles: 1 x 25/30/45 minutes low/central/high (Normal new-slug workflow.); positive-signal/closure probabilities 0.95/0.85 within 240 active minutes; observed active-agent/human/compute/wait/blocked/rework minutes 1/unknown/unknown/0/0/0; cycles positive/negative/inconclusive 0/0/0; falsification gates 6; architectures tested/rejected 0/0; result target-closed; target reached true; forecast error -149 minutes; ratio 0.006666666666666667; inside interval false; positive-signal/target-closure Brier scores 0.0025/0.0225; missing telemetry activeHumanMinutes: No task-local human-work timer.; computeMinutes: Paired replay process receipts are retained, but complete substantive-computation elapsed coverage is unavailable; no reconstructed total.; deduplicatedModelTokens: No supported fork-aware task-local counter supplied; rollout token events were not summed.; uncachedInputTokens: No supported task-local uncached-input counter supplied.. Work ledger: https://evidencepress.org/api/work-ledger.json. Metrics policy: https://evidencepress.org/api/research-metrics-policy.json - Intended aims: science - Artifact roles: research-output, evidence-assessment, method-demonstration, communication - Decision object: bound — Two-sided linear Jordan-block growth bounds with explicit graph generation and proof bridges. Scope: Counting non-backtracking operators of finite simple undirected leafless graphs, n>=3. - Reusable methods: Structural compression (structural-compression); Adversarial scientific controls (adversarial-controls); Assurance as a vector (assurance-vector); Agent-readable research objects (agent-readable-research-object). Registry: https://evidencepress.org/api/method-registry.json - Targeted clocks: assurance, publication, translation - Semantic bridge: explicit — Banded valuation forces a long pencil chain; uniform rational encoding preserves it; signed fibers realize the adjacency and degree actions; incidence transfer and zero-valued padding preserve the chain in a simple graph. Remaining risks: The universal proof is not formally verified or externally reconstructed.; Finite checks do not establish exact all-parameter block sizes.; Priority and real-world relevance are not established.. - Human judgement gates: Audit the source counting convention and all quantifiers.; Reconstruct valuation, rational encoding and graph realization.; Preserve third-party rights and prior attribution.; Keep internal review and publication separate from external assurance. - Next assurance action: Seek unaffiliated mathematical reconstruction and wider source reconciliation before stronger assurance claims. - Claim ceiling: Unrefereed constructive theorem candidate for part (1), with producer controls; no part (2), exact extremum, optimal constants, priority, external validation or impact established. - Aim-scoped impact evidence: - science: NO_IMPACT_EVIDENCE — More inspectable spectral graph constructions in Producer-coordinated research and publication; design none; comparator No matched conventional-workflow comparator.; estimand No causal acceleration, reliability, uptake or scientific-impact effect estimated.; no real-world effect evidence asserted - Parent handoffs: reuses-method https://doi.org/10.1016/j.laa.2021.01.022; inherited claim: Reduced non-backtracking matrix and quadratic-pencil framework.; inherited ceiling: Standard antecedent framework, not independent confirmation of the present growth construction. ## Verification status Anonymous AI-assisted unrefereed theorem candidate. Five producer-coordinated editorial roles completed one round; the sole required Minor exposition repair is closed and the final internal decision is Accept/PASS_WITH_NOTES. No external validation, formal verification, exhaustive novelty or historical priority is asserted. ## References 1. AIM Problem Lists. Spectra of hypergraphs, Problem 1.3(1). Dated source and notation bridge in the package. 2. Glover, C., and Kempton, M. (2021). Some spectral properties of the non-backtracking matrix of a graph. LAA 618, 37–57. 3. Heysse, K., Lorenzen, K., and Reinhart, C. (2025). Defective eigenvalues of the non-backtracking matrix. ELA 41, 511–528. 4. Takata, K., Mock, A., Notomi, M., and Shinya, A. (2026). Higher-order exceptional points unveiled by nilpotence and mathematical induction. Communications Physics 9, 274.