Summary: A computational investigation using spectral analysis of residue-circulant matrices has discovered that primes congruent to 1 mod 4 exhibit a vanishing "Paley gap"—the discrepancy between computed and theoretical eigenvalues reaches machine precision (${10}^{-15}$)). This phenomenon connects quadratic residue theory, optimal graph expansion properties (Ramanujan graphs), and Fast Fourier Transform methods, offering new computational perspectives on prime number structure. While not constituting a primality test, the discovery demonstrates how modern algorithmic frameworks can illuminate classical mathematical structures.

Research outputs:

• Preprint: Spectral note: Paley gap via lambda_2 (residue circulants) on Zenodo
• Code repository: TNFR-Python-Engine on GitHub
• Accessible explanation: Medium article

The discovery

Recent work emerging from the TNFR computational framework has identified a remarkable spectral property of certain prime numbers. For primes $p\equiv 1\left(\mathrm{mod}4\right),$ the algebraic connectivity (second-smallest Laplacian eigenvalue (\(\lambda_2\\))) of the associated Paley graph matches its theoretical prediction with extraordinary precision—to within floating-point rounding error.

This "Paley gap" (\(g(p) = |\lambda_2 - (p - \sqrt{p})/2|\\)) effectively vanishes for tested primes up to 2601, consistently achieving values around \(10^{-13}\\) to ${10}^{-15}$. The phenomenon has been verified across dozens of primes and appears robust.

The complete numerical results, methodology and reproducible code are available in the Zenodo preprint and the TNFR-Python-Engine repository.

Mathematical background: from quadratic residues to graph spectra

A quadratic residue modulo prime $p$ is an integer $a$ such that \(x^2 \equiv a \pmod{p}\\) has a solution. For example, modulo 13, the quadratic residues are {1, 3, 4, 9, 10, 12}—exactly half of the non-zero elements. These residues encode deep arithmetic information about the prime's algebraic structure.

The Legendre symbol \(\left(\frac{a}{p}\right)\\) formalizes this: it equals $+1$ if \(a\\) is a quadratic residue modulo $p$, $-1$ if not and $0$ if $p|a$. A fundamental result states that for primes $p\equiv 1\left(\mathrm{mod}4\right)$, the element $-1$ is itself a quadratic residue. This congruence condition ensures crucial symmetry properties in what follows.

The Paley graph construction

The Paley graph $P\left(p\right)$ of prime order \(p \equiv 1 \pmod{4}\\) bridges number theory and graph theory. Its vertex set is $Z_p=\{0,1,\dots ,p-1\}$, and vertices $i$ and $j$ are adjacent if and only if $i-j$ is a quadratic residue modulo $p$.

This construction yields a strongly regular graph—every vertex has degree $(p-1)/2$, every pair of adjacent vertices shares $(p-5)/4$ common neighbors, and every non-adjacent pair shares $(p-1)/4$ common neighbors. The graph is self-complementary, meaning it is isomorphic to its complement.

Crucially, when $p$ is prime, the Paley graph is a circulant graph. The adjacency matrix $A$ is circulant: each row is a cyclic shift of the previous row. This circulant structure enables exact spectral computation via the Discrete Fourier Transform (DFT).

Spectral graph theory: the Laplacian and algebraic connectivity

The Laplacian matrix $L=D-A$ (where $D$ is the degree matrix and $A$ the adjacency matrix) encodes how signals or flows propagate through a graph's structure. Its eigenvalues $0={\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_n$ characterize fundamental network properties.

The algebraic connectivity \(\lambda_2\\)(also called the Fiedler value) measures how well-connected the graph is. Larger \(\lambda_2\\) indicates stronger connectivity, faster consensus dynamics in distributed systems and greater resilience to perturbations.

For circulant matrices with first row $[c_0,c_1,\dots ,c_{n-1}]$, eigenvalues are given by the DFT formula:

${\lambda }_j={\sum }_{k=0}^{n-1}{c}_k\cdot {\omega }^{-jk}$

where \(\omega = e^{2\pi i/n}\\) is a primitive $n$-th root of unity. This transforms eigenvalue computation from an $O\left(n^3\right)$ matrix problem to an $O\left(n\log n\right)$ FFT problem.

The DFT eigenvector basis for circulant matrices is universal—it depends only on the matrix size $n$, not the specific entries. This universality explains the numerical precision: eigenvectors are known exactly (as Fourier modes), and eigenvalues follow from discrete sums with minimal accumulation of floating-point error.

The theoretical prediction and the Paley gap

Spectral theory of Paley graphs

For a Paley graph of prime order $p\equiv 1\left(\mathrm{mod}4\right)$, spectral graph theory predicts that the Laplacian eigenvalues are:

 $\lambda =\frac{p-1}{2}-\frac{1}{2}(-1\pm \sqrt{p})$ 

Simplifying the second-smallest eigenvalue:

${\lambda }_2=\frac{p-\sqrt{p}}{2}$

This formula emerges from the analysis of Gauss sums—exponential sums over quadratic residues that appear throughout analytic number theory.

Defining the Paley gap

The Paley gap measures the discrepancy between numerical computation and theory:

 $g\left(p\right)=|{\lambda }_2^{\text{computed}}-\frac{p-\sqrt{p}}{2}|$ 

The computational verification from the TNFR framework shows ($g\left(p\right)\approx {10}^{-13}$ to ${10}^{-15}$ for all tested primes ($p\equiv 1\left(\mathrm{mod}4\right)$ up to 2601. This precision is at the limit of IEEE 754 double-precision arithmetic, suggesting the theoretical formula captures the true spectral structure with perfect fidelity.

Why the gap vanishes: circulant structure and FFT

The vanishing Paley gap is not accidental—it reflects the deep mathematical structure of circulant matrices. Because the Paley graph's Laplacian is circulant (for prime order), its eigenvalues can be computed exactly using the FFT.

Unlike general matrix eigenvalue algorithms that accumulate iterative errors, the FFT-based approach uses an exact eigenvector basis (the Fourier modes), computes eigenvalues as discrete sums (not iterative approximations) and incurs only rounding error from individual arithmetic operations

The number of arithmetic operations in the FFT is $O\left(n\log n\right)$, and each introduces at most ${ϵ}_{\text{machine}}$ relative error. For double precision, ${ϵ}_{\text{machine}}\approx 2.2\times {10}^{-16}$, explaining the observed gap magnitudes.

Connection to Ramanujan graphs and optimal expansion

What are Ramanujan graphs?

Paley graphs of prime order $p\equiv 1\left(\mathrm{mod}4\right)$ are Ramanujan graphs—optimal spectral expanders. A $d$-regular graph $G$ is Ramanujan if all non-trivial eigenvalues \(\lambda\\) satisfy:

 $|\lambda |\le 2\sqrt{d-1}$ 

The Alon-Boppana bound establishes that for infinite families of $d$-regular graphs, the second-largest eigenvalue magnitude must satisfy

$\lambda \ge 2\sqrt{d-1}-o\left(1\right)$ 

Ramanujan graphs achieve this bound—they are optimal expanders in a precise spectral sense.

For Paley graphs with $d=(p-1)/2$, the non-trivial eigenvalues are

 $\frac{1}{2}(-1\pm \sqrt{p})$ 

Computing:

 $\left|\frac{-1+\sqrt{p}}{2}\right|=\frac{\sqrt{p}-1}{2}\approx \sqrt{\frac{p-1}{2}}=\sqrt{d}$ 

This matches (up to lower-order terms) the Ramanujan bound $2\sqrt{d-1}\approx 2\sqrt{d}$ for large $d$, confirming Paley graphs' optimal expansion properties.

Applications of optimal expanders

Ramanujan graphs have profound applications across mathematics and computer science:

• Network design: Sparse but highly resilient communication topologies for supercomputing interconnects
• Error-correcting codes: Construction of codes with optimal distance properties
• Randomness extraction: Derandomization of probabilistic algorithms
• Neural network architectures: Sparse connectivity patterns that maintain information flow
• Distributed consensus: Fast convergence in multi-agent systems due to large spectral gap

The fact that simple number-theoretic constructions (quadratic residues) yield these optimal structures reveals a deep connection between algebraic number theory and extremal graph theory.

Computational and theoretical implications

Is this a primality test?

The TNFR paper explicitly states this is "not a primality test". However, the consistent vanishing of the Paley gap for primes $p\equiv 1\left(\mathrm{mod}4\right)$ raises intriguing questions about spectral signatures of primality.

Challenges for a primality test:

• Computational cost: FFT-based eigenvalue computation scales as $O\left(n\log n\right)$, but for an $n$-digit number this is still slower than Miller-Rabin or AKS primality tests
• Composite behavior unclear: the gap's behavior for composite $n\equiv 1\left(\mathrm{mod}4\right)$ hasn't been systematically characterized
• Theoretical gap: no proof yet connects gap vanishing to primality with certainty

Potential advantages:

• Global structural signature: the gap captures the entire quadratic residue distribution, potentially detecting composites that pass local congruence tests
• Parallelizability: FFT algorithms are highly parallelizable, potentially offsetting computational cost on modern hardware
• Robustness: spectral methods are less sensitive to adversarial input construction than some deterministic tests

TNFR framework: pattern coherence through resonance

The discovery emerged from the TNFR computational framework, which emphasizes structural coherence maintained through network resonance. From this perspective, the vanishing Paley gap indicates perfect resonance between local connectivity rules (quadratic residue patterns) and global spectral properties (eigenvalue distribution).

TNFR views systems not as collections of static objects but as dynamically maintained patterns that persist through continuous reorganization. The circulant structure acts as a coherence mechanism, ensuring local patterns propagate consistently across the network without distortion.

This paradigm shift—from viewing mathematical structures as fixed objects to understanding them as self-sustaining patterns—offers a fresh lens for computational mathematics. The TNFR approach prioritizes:

• FFT-based spectral computation: leveraging circulant structure for efficient, precise eigenvalue calculation
• Residue circulant Laplacians: defining specialized matrices that make number-theoretic structure computationally accessible
• Empirical verification across families: systematically testing conjectures across extensive parameter ranges to identify structural invariants

Open questions and future directions

Extending beyond primes

• Prime powers: does a Paley gap formula exist for $q=p^r$ where $q\equiv 1\left(\mathrm{mod}4\right)$ but $q$ is not prime?
• Composite moduli: what spectral signatures distinguish prime-order Paley graphs from composite-order generalizations?
• Higher-order residues: can analogous gap phenomena be identified for cubic residues, quartic residues, or higher powers?

Theoretical development

• Rigorous gap bounds: prove that $g\left(p\right)=O({ϵ}_{\text{machine}}\cdot p\log p)$ or tighter
• Characterize composite behavior: derive expected gap magnitudes for composite $n$, potentially enabling spectral primality heuristics
• Connection to L-functions: relate gap behavior to special values of Dirichlet L-functions associated with quadratic characters

Computational explorations

• Dynamical systems on Paley graphs: analyze random walks, diffusion processes, and consensus dynamics—do they exhibit special convergence properties?
• Quantum applications: could Paley graphs' optimal expansion properties be leveraged in quantum error correction or quantum network design?
• Machine learning on graphs: use Paley graphs as benchmark networks for testing graph neural network architectures

Connections to broader mathematical landscape

Number theory and graph theory synthesis

The Paley gap discovery exemplifies how computational frameworks can reveal hidden symmetries in classical structures. Quadratic residues have been studied for millennia—Gauss devoted significant portions of Disquisitiones Arithmeticae to their properties. Yet the spectral perspective, enabled by modern FFT algorithms and numerical precision, illuminates structure that purely algebraic methods might overlook.

This synergy between number theory (quadratic residues), graph theory (circulant graphs) and spectral analysis (Laplacian eigenvalues) demonstrates the power of interdisciplinary mathematical thinking.

Computational mathematics: algorithms as microscopes

Just as physical microscopes revealed previously invisible biological structures, computational algorithms act as mathematical microscopes, making abstract patterns concrete and measurable. The FFT, in particular, has transformed multiple fields by making spectral information efficiently accessible.

The TNFR framework's contribution lies in systematically applying these tools to uncover patterns—not through massive brute-force computation but through algorithmically informed exploration of mathematical structures.

The role of empirical mathematics

The Paley gap work represents empirical mathematics—discovering patterns through computation, then seeking theoretical understanding. This approach has a rich history:

• Birch and Swinnerton-Dyer formulated their conjecture after extensive numerical calculations on elliptic curves
• Prime number theorem conjectures predated rigorous proofs by decades, guided by numerical evidence
• Ramanujan himself discovered many identities empirically before proofs were found

Modern computational power amplifies this methodology. The LessWrong and rationalist communities value empiricism balanced with rigorous reasoning—testing ideas against reality while demanding theoretical coherence. The Paley gap discovery fits this ethos: observe a pattern, verify it extensively, propose mechanisms, but acknowledge what remains unproven.

Why this matters

For mathematicians

• New computational tools: FFT-based spectral analysis of residue circulants offers efficient methods for exploring number-theoretic structures
• Unexplored connections: The perfect alignment between algebraic number theory and optimal graph expansion deserves deeper investigation
• Empirical methodology: Demonstrates the value of systematic computational exploration in pure mathematics

For computer scientists

• Network design principles: Understanding why number-theoretic constructions yield optimal expanders can inform practical network architecture
• Algorithm design: Spectral methods for primality testing or factorization might emerge from deeper study of these phenomena
• Benchmark structures: Paley graphs with known spectral properties serve as rigorous test cases for graph algorithms

For the rationalist community

• Interdisciplinary synthesis: The discovery showcases how insights emerge at the intersection of multiple fields—number theory, linear algebra, graph theory, computational methods
• Computational epistemology: Demonstrates how algorithmic tools extend our mathematical intuition, making abstract patterns concrete
• Pattern recognition over object manipulation: TNFR's emphasis on coherent patterns rather than static objects aligns with rationalist themes of understanding systems dynamically

Conclusion: symmetry hidden in plain sight

For over a century mathematicians have studied quadratic residues, Paley graphs and Ramanujan expanders. Yet the vanishing Paley gap—the remarkable numerical precision with which a simple formula predicts the spectral properties of prime-order residue circulants—was only recently made explicit through systematic computational investigation.

This discovery reminds us that even in well-trodden mathematical territory, new perspectives can reveal hidden structure. The combination of:

• Classical number theory (quadratic residues modulo primes)
• Modern computational methods (FFT algorithms)
• Interdisciplinary thinking (connecting graph spectra to arithmetic)

yields insights that none alone would provide.

The phenomenon itself—that certain primes possess a perfect spectral symmetry detectable at machine precision—is beautiful in its simplicity. The underlying mathematics—connecting optimal network expansion, algebraic number theory, and discrete Fourier analysis—is rich and deep.

Whether this leads to practical primality tests, better network designs or simply deeper appreciation of mathematical structure remains to be seen. But the discovery exemplifies how computational frameworks, when guided by theoretical understanding, can illuminate patterns that were always there waiting to be recognized.

Technical appendix: implementation notes

For readers interested in reproducing or extending this work:

Key algorithms:

• Construct Paley graph adjacency matrix via quadratic residue detection (Legendre symbol computation)
• Form Laplacian $L=D-A$ where $D_{ii}=(p-1)/2$ for all $i$
• Compute eigenvalues via FFT (leveraging circulant structure) or standard eigenvalue solver as verification
• Compare ${\lambda }_2^{\text{computed}}$ with $(p-\sqrt{p})/2$

Numerical considerations:

• Use double precision (IEEE 754 binary64) throughout
• For primes $p>{10}^6$, be aware of potential precision loss in $\sqrt{p}$ computation
• Verify circulant structure before applying FFT methods

Extensions to explore:

• Non-prime orders $q=p^r$ with $q\equiv 1\left(\mathrm{mod}4\right)$
• Generalized Paley graphs using cubic or higher-order residues
• Spectral properties of other strongly regular graphs from algebraic constructions

Recommended reading and bibliography

Foundational texts on spectral graph theory

• Fan Chung, "Spectral Graph Theory" (1997): The definitive introduction to Laplacian eigenvalues and their applications to graph properties. Essential for understanding algebraic connectivity and expansion.
• Andrei Broder & Anna Karlin, "Introduction to Expander Graphs": Accessible overview of expansion properties and the connection to random walks and connectivity.

Ramanujan graphs and optimal expanders

• Lubotzky, Phillips & Sarnak, "Ramanujan graphs" (1988): The original construction of explicit Ramanujan graphs using number theory, a landmark paper connecting modular forms to extremal combinatorics.
• Hoory, Linial & Wigderson, "Expander graphs and their applications" (2006): Comprehensive survey of expander graphs across mathematics and computer science, including Ramanujan graphs and the Alon-Boppana bound.

Paley graphs and number-theoretic constructions

• R.E.A.C. Paley, "On orthogonal matrices" (1933): The original construction of Paley graphs from quadratic residues.
• Bollobás & Thomason, "Graphs which contain all small graphs" (1981): Analysis of Paley graphs' extremal properties and their role in Ramsey theory.
• Recent research on Paley graph spectra: The arxiv paper "On the Paley graph of a quadratic character" (2022) provides modern perspectives on spectral properties.

Circulant matrices and FFT methods

• Philip J. Davis, "Circulant Matrices" (1979): Classic monograph on the algebraic structure of circulant matrices and their spectral properties via DFT.
• Van Loan, "Computational Frameworks for the Fast Fourier Transform" (1992): Detailed treatment of FFT algorithms and their numerical properties, essential for understanding computational precision.

Applications to network science and computer science

• Mark Newman, "Networks: An Introduction" (2010): Modern treatment of network science including spectral methods and their applications to real-world systems.
• Spielman & Teng on spectral graph algorithms: Their work on nearly-linear time algorithms for Laplacian systems demonstrates practical applications of spectral graph theory.

Empirical and computational mathematics

• Jonathan Borwein & David Bailey, "Mathematics by Experiment" (2008): Philosophical and practical treatment of computational discovery in mathematics, aligning with the TNFR approach.
• The OEIS (Online Encyclopedia of Integer Sequences): Neil Sloane's database exemplifies how computational pattern recognition advances number theory.

This bibliography provides entry points for readers at multiple levels—from undergraduate introductions to spectral graph theory, through foundational papers on Ramanujan graphs and Paley constructions, to modern computational perspectives. The interdisciplinary nature of the Paley gap phenomenon rewards exploration across these diverse mathematical domains.