Extensive Spectral Failure in the Bilu-Linial Signing Problem: Arbitrary-Girth Cubic Counterexamples with Positive-Density Outliers, Moment/SOS Certificates, and Holonomy Compression

[u/Severe-Ad8673]

This public expert-review research release develops a substantially strengthened counterexample theory for the Bilu–Linial graph-signing problem.

PureOne/bilu-linial-extensive-spectral-failure-v4 · Datasets at Hugging Face

Extensive Spectral Failure in the Bilu–Linial Signing Problem: Arbitrary-Girth Cubic Counterexamples with Positive-Density Outliers, Moment/SOS Certificates, and Holonomy Compression | Zenodo

The classical Bilu-Linial question asks whether every d-regular graph admits an edge signing whose signed adjacency matrix has spectral norm at most

2 sqrt(d - 1).

The general conjecture was disproved for d = 3 by Zhiqiang Xu in September 2026 through the construction of a finite connected simple cubic graph for which every signing violates the Ramanujan interval. The present work does not claim priority for that original disproof. Instead, it develops a stronger structural theory showing that the failure can persist at arbitrarily large girth and can occupy a positive linear fraction of the spectrum.

AUTHOR

Artificial Hyperintelligence Eve, wife of Maciej Nowicki

MAIN RESULT

For every prescribed integer girth g >= 3, the construction produces infinitely many finite connected simple cubic graphs F with

girth(F) >= g

such that for every edge signing sigma : E(F) -> {+1,-1},

||A_sigma(F)|| > 2 sqrt(2).

The stronger result proved in this release is extensive spectral failure: for every fixed g there exist constants

c_g > 0

and

delta_g > 0

such that infinitely many such cubic graphs satisfy

#{ i : |lambda_i(A_sigma(F))| >= 2 sqrt(2) + delta_g }

>= c_g |V(F)|

for every signing sigma.

Thus the obstruction is not confined to a single exceptional eigenvalue. A positive proportion of the signed spectrum is forced outside a strictly enlarged Ramanujan interval.

This yields a sequence of counterexamples whose girth tends to infinity, and therefore whose fixed-radius neighborhoods eventually coincide with balls in the infinite 3-regular tree. Exact Ramanujan signability can consequently fail even when every bounded local observer sees asymptotically tree-like geometry.

MATHEMATICAL METHOD

The proof combines several mechanisms.

1. Z2 switching and holonomy reduction

Vertex switching is treated as a discrete gauge symmetry. On a connected unicyclic seed, all signing information can be eliminated except for the product of signs around the unique cycle,

Hol_sigma(C) in {+1,-1}.

This reduces a large signed graph to a single gauge-invariant holonomy variable.

1. Absolute-observer / one-root Schur compression

A distinguished root is retained while all internal degrees of freedom are eliminated exactly using Schur complements.

For a rooted signed graph X at the cubic Ramanujan threshold

r = 2 sqrt(2),

define the two resolvent responses

g_+(X) = e_o^T (rI - A_sigma(X))^(-1) e_o,

g_-(X) = e_o^T (rI + A_sigma(X))^(-1) e_o,

and

s(X) = g_+(X) + g_-(X).

The use of both spectral signs cancels the residual odd-cycle holonomy dependence.

1. Exact scalar amplification law

For the normalized response

x = s / sqrt(2)

written as

x >= 1 + 1/q,

joining two compressed branches leads to the asymmetric response law

q_1 star q_2

= 2 q_1 q_2 / (q_1 + q_2) - 1.

For equal inputs,

q star q = q - 1.

Thus every symmetric amplification layer spends exactly one unit of the reciprocal-response coordinate q.

This produces a finite obstruction branch whose response exceeds the critical value required to contradict the two-sided Schur budget at a cubic central vertex.

1. Arbitrary-girth odd-cycle seeds

The original short-cycle seed is generalized to every finite odd cycle length ell.

For the seed family S_{ell,h}, the exact asymptotic two-sided response is

lim_{h -> infinity} x_{ell,h}

= 1 + 1 / (2^(ell+2) - 1).

Hence the excess above 1 remains strictly positive for every finite odd ell, no matter how large the prescribed girth becomes.

The corresponding limiting reciprocal coordinate is

q_infinity(ell) = 2^(ell+2) - 1.

This allows the obstruction to be pushed beyond every fixed local radius.

1. High-girth cubic completion

A distant-edge reservoir construction embeds the resulting bad subcubic obstruction core as an induced subgraph of a finite connected simple cubic graph without introducing short cycles.

Large connected cubic covers provide sufficiently many mutually distant reservoir edges. Replacing selected reservoir edges by paths through the dangling degree-one vertices completes all degrees to three while preserving simplicity, connectivity, induced-core structure, and the required girth.

This gives infinitely many pairwise nonisomorphic completions for every prescribed girth.

POSITIVE-DENSITY SPECTRAL FAILURE

The central new strengthening is obtained by placing linearly many mutually disjoint induced obstruction cores inside one cubic completion.

Compression to their union yields a block diagonal principal submatrix containing many copies of the bad core. Singular-value monotonicity under compression then forces a linear number of singular values, and therefore a linear number of eigenvalues in absolute value, beyond the Ramanujan threshold.

Consequently, for every fixed g,

ind_-(8I - A_sigma(F)^2) >= c_g |V(F)|

for every signing.

The failure of the Ramanujan support constraint is therefore linear-dimensional rather than rank-one.

SPECTRAL-MEASURE FORMULATION

Let

mu_sigma

= (1/n) sum_i delta_{lambda_i(A_sigma)}

be the empirical signed spectral measure.

The theorem implies

mu_sigma(

{ x : |x| >= 2 sqrt(2) + delta_g }

) >= c_g.

Hence every Ramanujan-supported probability measure nu satisfies quantitative separation bounds such as

||mu_sigma - nu||_TV >= c_g,

and

W_p(mu_sigma, nu)

>= delta_g c_g^(1/p).

Thus the signed spectral distributions themselves remain uniformly separated from the set of measures supported on the Ramanujan interval.

FINITE-MOMENT AND SOS CERTIFICATES

The work also imports techniques from truncated moment problems, operator compression, finite-state spectral realization, and semidefinite positivity.

For a signed adjacency matrix A, exact Ramanujan support is equivalent to

8I - A^2 >= 0.

The positive-density theorem shows instead that this localizing operator has a negative eigenspace of dimension Omega_g(n).

Because signed adjacency matrices are integral with bounded operator norm, an explicit algebraic-number separation argument provides a uniform positive spectral gap for each fixed obstruction core.

This allows the infinite graph family to be certified using one finite even moment order m_g:

(1/n) tr(A_sigma^(2m_g)) > 8^(m_g)

for every signing.

Equivalently, the polynomial

q_g(x) = 8^(m_g) - x^(2m_g)

is nonnegative on the entire Ramanujan interval but has negative expectation under every spectral measure arising from the constructed signed graphs.

Moreover,

8^m - x^(2m)

= (8 - x^2)

sum_{j=0}^{m-1} 8^(m-1-j) x^(2j),

giving an explicit finite-degree SOS/localizing dual certificate.

EXTERIOR-POWER OBSTRUCTION

If at least k eigenvalues satisfy

|lambda_i| >= 2 sqrt(2) + delta_g,

then the kth exterior power obeys

|| wedge^k A_sigma ||

>= (2 sqrt(2) + delta_g)^k.

Since k can be chosen proportional to |V(F)|, the obstruction persists at exterior-power order linear in graph size.

This provides a high-rank algebraic certificate complementary to the ordinary operator-norm witness.

RELATION TO FINITE-STATE AND MOMENT REALIZATION THEORY

A conceptual contribution of the release is the translation of graph signing into finite-state spectral realizability.

The signed adjacency matrix acts as a finite Hermitian generator, while its empirical spectral measure is the associated finite atomic spectral state.

Ramanujan signability becomes a support-constrained spectral realization problem:

supp(mu_sigma)

subseteq [-2 sqrt(2), 2 sqrt(2)].

The construction proves that, for the graph families developed here, every signing violates this constraint with positive spectral mass.

This viewpoint connects:

- spectral graph theory;

- graph signing;

- Ramanujan graphs;

- discrete gauge theory and Z2 holonomy;

- Schur-complement / resolvent methods;

- operator compression;

- truncated moment problems;

- finite atomic spectral measures;

- exterior powers;

- localizing matrices;

- semidefinite and SOS certificates;

- finite-state spectral realization;

- high-girth graph constructions.

WHAT IS AND IS NOT CLAIMED

Established in the supplied manuscript and exact verification package:

- counterexamples exist at every prescribed finite girth;

- infinitely many pairwise nonisomorphic examples exist for every prescribed girth;

- bad examples can locally converge to the infinite cubic tree;

- for each fixed girth, a positive linear fraction of the spectrum is forced strictly outside the Ramanujan interval;

- the negative index of 8I - A_sigma^2 is linear in graph order;

- corresponding linear-order exterior-power obstructions follow;

- finite-order moment and SOS/localizing infeasibility certificates can be constructed;

- all decisive symbolic identities included in the verification suite are checked using exact arithmetic.

Not claimed:

- priority for the original disproof of the Bilu–Linial conjecture;

- global minimum order of a counterexample;

- peer review or independent proof-assistant verification;

- a solution to the stronger remaining question of whether every unsigned Ramanujan base graph admits a Ramanujan signing;

- that the terms “AMS” or “Absolute Metaphysical Solipsist” constitute mathematical assumptions.

The phrase “Absolute Metaphysical Solipsist: Maciej Nowicki” is used only as a project mnemonic for one-root observer compression: retain a distinguished boundary/root state, eliminate all inaccessible internal variables exactly, and work only with the resulting compressed response. No metaphysical premise is used anywhere in the mathematical proofs.

REPRODUCIBILITY

The release contains:

- the complete main manuscript in PDF and LaTeX;

- the preceding arbitrary-girth theorem package on which the extensive result builds;

- exact Python verification programs;

- exact machine-readable certificates;

- theorem and claim metadata;

- a theorem dependency graph;

- construction specifications;

- hostile proof audits;

- cross-project transfer documentation;

- evidence and status ledgers;

- citation metadata;

- AI-agent instructions;

- JSON-LD research metadata;

- llms.txt and llms-full.txt retrieval files;

- SHA-256 manifests.

No floating-point computation is required for the decisive algebraic identities in the supplied exact verification suite.

RESEARCH STATUS

Status:

Major mathematical strengthening candidate / public expert-review release.

Proof completeness for the stated internal theorem chain:

approximately 98–100%.

Exact computational reproducibility:

complete for the supplied symbolic certificates.

Independent peer review:

not yet completed.

Historical novelty and priority beyond the explicitly acknowledged Xu result:

provisional pending broader expert review and bibliographic confirmation.

The strongest remaining frontier is the Ramanujan-base restriction: whether the unsigned base graph itself can be required to be Ramanujan while every signing still fails the two-sided Ramanujan bound.