An arithmetic floor plan

Six Doors From Every Room

Six arithmetic moves wire 2,184 vertices into a network whose nontrivial spectrum stays inside the optimal asymptotic barrier. Build the graph, test its eigenvalues, release a lazy random walk, then inspect the signing trick that reaches every degree.

The object is the card below. Each little matrix is a door. Multiply any room by one of them, reducing modulo 13 and forgetting nonzero scalar multiples, and you arrive at another room.

Layer 1: the graph in the card

Build X5,13

No file of edges is hidden here. The browser solves the norm equation, regenerates the six matrices, enumerates PGL2(F13), and performs every multiplication.

a02 + a12 + a22 + a32 = 5

Use a0 positive and odd, the other coordinates even, and the least i with i2 = −1 mod 13. The browser finds i = 5.

verticeswaiting
degree rangewaiting
componentswaiting
bipartitewaiting
partswaiting
edgeswaiting
neighbourhood shellspress Build
lazy-walk mass by shellP = (I + A/6) / 2
adjacency spectrumtrivial values stay visible

identity will be found live

Only nonempty balls containing at most half the vertices are admitted.

L2 from uniform
waiting
theorem envelope
waiting
chosen |S|
waiting
boundary / |S|
waiting
Ritz |lambda|
waiting
A squared residual
waiting

h(G) waits for the graph.

The selected cut is an exact upper bound on the unknown minimum h(G). The theorem gives the displayed lower bound. The Ritz substitution is a numerical diagnostic only.

What the band says

A d-regular graph is called Ramanujan when every nontrivial adjacency eigenvalue has absolute value at most 2sqrt(d − 1). Here d = 6, so the line is 2sqrt(5), about 4.472136. The values +6 and −6 are trivial for this connected bipartite graph. Only one copy of each is discarded.

The point is not that this graph reaches equality. It does not need to. The line is the asymptotic obstruction: for fixed d, any growing family of d-regular graphs has liminf lambda2 at least 2sqrt(d − 1). A finite graph can sit elsewhere.

The ordinary walk would bounce forever between the two determinant classes. The lazy walk stays put with probability one half, so periodicity cannot masquerade as failed mixing.

Layer 2: every degree

Lift the six-room seed

K3,3 has six vertices and degree 3. Give each of its nine edges a sign. A plus edge stays on its sheet in the doubled graph; a minus edge crosses sheets. The old eigenvalues come from A. The new ones come from the signed matrix As.

Nine edge signs

Each button cycles unknown, plus, minus. Unknown signs are exhaustively completed.

fixed signs
0 / 9
completions
512
cutoff passes
480
connected lifts
480
the explicit 12-vertex liftunknown edges show both routes

Conditional mean polynomial

x^6 - 9x^4 + 18x^2 - 6

Mean over all 512 exact characteristic polynomials.

old spectrum of K3,3

+3, 0, 0, 0, 0, −3

new spectrum of As

choose all nine signs

roots of the conditional meanlargest 2.507976 < 2sqrt(2)

The further result

The small lift is not the theorem. It is the mechanism laid open. Along the displayed edge order, the two child mean polynomials average back to the parent, and their roots interlace. One child therefore keeps the largest new root from moving past its parent. Press Complete the branch and watch that choice continue until no question marks remain.

Marcus, Spielman and Srivastava used this method to prove that infinite bipartite Ramanujan families exist for every degree greater than 2. The proof is existential, not unfindable: finite exhaustive search can locate a signing, but the 2015 paper does not give a polynomial-time construction.

The check

Recomputed exactly

  • 5 and 13 are prime and both equal 1 mod 4.
  • The Legendre symbol (5/13) is −1.
  • Six norm-5 quaternions give the six displayed matrices.
  • PGL2(F13) has 2,184 enumerated vertices.
  • The graph is simple, symmetric, connected, bipartite, and 6-regular.
  • The determinant parts contain 1,092 vertices each.
  • All 512 K3,3 signings and their lift polynomials are enumerated.
  • 480 lifts are connected and the same 480 pass the new-root cutoff.

Theorem, diagnostic, uncertainty

The LPS theorem proves the full nontrivial bound after the exact construction checks pass. The gold Ritz point is a floating-point power diagnostic. Its A squared residual is printed, and it is not presented as the proof or as an exhaustive eigenvalue computation.

The conditional polynomial coefficients are exact averages. Its plotted roots use floating-point bisection. The verifier checks the coefficient identities exactly and the root inequalities with stated numerical tolerance.

Every free choice

We chose p = 5 and q = 13 from the LPS family, the least root i = 5 rather than i = 8, first-nonzero-entry projective normalisation, lexicographic vertex enumeration, a point source, a walk time, and a ball radius. The source, time, and radius are yours to change.

In the lift, you choose signs and their order. The drawing layout, colour, and the tie choice between equal child roots do not affect the graph or polynomial.

Settings that say nothing

A uniform initial walk has zero deviation forever by definition, so it is not offered. Empty sets, the whole graph, and sets above half the vertices are excluded from the cut readout.

The all-positive signing makes two disconnected copies of K3,3. Its extra +3 is not erased as "trivial"; press the preset and the failure remains visible.

node research/ramanujan-graphs/verify-ramanujan-graphs.mjs

What the names do and do not claim

Ramanujan did not construct these graphs. The name records the number-theoretic estimate used in the spectral proof. LPS and Margulis independently supplied the first constant-degree infinite Ramanujan families, so the historical credit is not assigned to LPS alone here.

The 2015 Annals paper is Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees. Its arXiv record has two versions, from 2013 and 2014. Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes is a separate one-version 2015 preprint published by SIAM in 2018.